線分のソートアルゴリズムについて

環境/言語:[windows XP VS2003]
分類:[.NET]

本掲示版では毎回お世話になっております。

VB.NETで線分を構成するアルゴリズムについて考えているのですが、
どのように構築するか悩んでいます。
（言語の質問というよりはアルゴリズムの質問になってしまいますが・・・）

例えば１線分A-B（Aが始点,Bが終点）のような形式で
線分が配列(ArrayList内の始点と終点を持った構造体を格納)に複数格納されているとします。

0 A-B　　　※数値は配列のインデックス
1 B-C
2 C-D
3 D-E
4 E-F
5 F-G
6 G-A

上記の配列に格納されていたデータを結合すると
A-B-C-D-E-F-G-A
といった線分として認識するとします。
（配列の０番目から順番に終点と次の線分の始点を比較していく）

編集により要素２番目を削除し詰めると

0 A-B
1 B-C
2 D-E
3 E-F
4 F-G
5 G-A

となり、上記の配列に格納されているデータを結合すると
A-B-C
D-E-F-G-A
と２つの線分と認識してしまいます。

なので上記の配列を
0 D-E
1 E-F
2 F-G
3 G-A
4 A-B
5 B-C
にソートし、結合時にD-E-F-G-A-B-Cとして
１線分として認識できるようにしたいのですが、どのような
アルゴリズムを考えればいいのでしょうか？

仕様としては可能な限り結合時の線分が少なくなるようにソート
を実施することです。

※結合のロジックは都合上修正することができません。

申し訳ございませんがよろしくお願い致します。

■No23885に返信(zonoさんの記事)
理解できていない上に”線分”の用法に日本語で悩みますが，とりあえず．

> 編集により要素２番目を削除し詰めると
>
> 0 A-B
> 1 B-C
> 2 D-E
> 3 E-F
> 4 F-G
> 5 G-A
>
> となり、上記の配列に格納されているデータを結合すると
> A-B-C
> D-E-F-G-A
> と２つの線分と認識してしまいます。
>
> なので上記の配列を
> 0 D-E
> 1 E-F
> 2 F-G
> 3 G-A
> 4 A-B
> 5 B-C
> にソートし、結合時にD-E-F-G-A-B-Cとして
> １線分として認識できるようにしたいのですが、どのような
> アルゴリズムを考えればいいのでしょうか？
むしろそのアルゴリズムが分からないと何もいえないような…
私の考えでは，{AB, BC, CD, EF, FG, GA} から BC を削除する時に，BCの直前の要素を差し替えて
{AC, CD, EF, FG, GA} にした方がよさそうな気がしますが．
# 元のデータだと最初の要素 AB の頭("A")と最後の要素 GA のしっぽ("A")が同じでなければならないような気がするけど
# 大丈夫なんだろうか．わからない

> 仕様としては可能な限り結合時の線分が少なくなるようにソート
> を実施することです。
「結合時の線分は常に１つか，結合する線分が何もなくなり０になる．」だと思うのですが，
”結合時の線分が少なくなるように”とはどういう状況でしょうか？
ついでにソートの必要性もわかりません．
# そしてソートという単語を使っていいものかもわかりません．

> ※結合のロジックは都合上修正することができません。
つまりデータ構造は変えられないということですね．
データ構造まで変えられるのなら連結リストという単語で検索してみてください．
本当にそのままな気がします．

でさぁ、ちょっと質問です。
その配列を利用して
正立方体を線で表現して、それを3D化して
縦と横等に自在に回転させるプログラムを書いてみてよ。
test><

> 結合時にD-E-F-G-A-B-Cとして
> １線分として認識できるようにしたいのですが、どのような
> アルゴリズムを考えればいいのでしょうか？

.NETはよく判りませんがロジックの考え方として一言。

「再ソート」として考えるからややこしくなってるんじゃありませんか？
あらかじめソートしてある配列（例：A-B-C-D-E）を
分断するわけですから（例：A-B、D-E）
それの接続は（A-B-D-E）か（D-E-A-B）の二択しかないんじゃないでしょうか？
どちらの接続も成り立たなければ2つの線分であると判断できると思います。

※途中で枝分かれするような並びだったらどうするんだろう…？

zonoさん

琴さんも書かれていますが、枝分かれがあればどうするか、
いくつもに分断される場合は？等、疑問も残りますが。
ソートというより、
> 0 A-B　　　※数値は配列のインデックス
> 1 B-C
> 2 C-D
> 3 D-E
> 4 E-F
> 5 F-G
> 6 G-A

と循環するものを分断された場合に、
D-E-F-G-A-B-Cとして認識したいと言うことでしたら、
１． Dの様に自分へ連結がない物を先頭とする。
　　（無ければあるルールで）
２．Dから追って、新たな配列に入れなおす。

と言う手順ではどうでしょう。

■No23890に返信(きいよさんの記事)
> zonoさん
>
> 琴さんも書かれていますが、枝分かれがあればどうするか、
> いくつもに分断される場合は？等、疑問も残りますが。
> ソートというより、
>>0 A-B　　　※数値は配列のインデックス
>>1 B-C
>>2 C-D
>>3 D-E
>>4 E-F
>>5 F-G
>>6 G-A
>
> と循環するものを分断された場合に、
> D-E-F-G-A-B-Cとして認識したいと言うことでしたら、
> １． Dの様に自分へ連結がない物を先頭とする。
> 　　（無ければあるルールで）
> ２．Dから追って、新たな配列に入れなおす。
>
> と言う手順ではどうでしょう。
>
>

色々と説明に不備があり申し訳ございません。
指摘していただいたように枝分かれの考慮が抜けていたので
別途仕様を確認してから整理し再度ご質問させていただきたいと
思います。

色々と回答していただいてありがとうございます。

■No23892に返信(zonoさんの記事)
> ■No23890に返信(きいよさんの記事)
>>zonoさん
>>
>>琴さんも書かれていますが、枝分かれがあればどうするか、
>>いくつもに分断される場合は？等、疑問も残りますが。
>>ソートというより、
> >>0 A-B　　　※数値は配列のインデックス
> >>1 B-C
> >>2 C-D
> >>3 D-E
> >>4 E-F
> >>5 F-G
> >>6 G-A
>>
>>と循環するものを分断された場合に、
>>D-E-F-G-A-B-Cとして認識したいと言うことでしたら、
>>１． Dの様に自分へ連結がない物を先頭とする。
>>　　（無ければあるルールで）
>>２．Dから追って、新たな配列に入れなおす。
>>
>>と言う手順ではどうでしょう。
>>
>>
>
> 色々と説明に不備があり申し訳ございません。
> 指摘していただいたように枝分かれの考慮が抜けていたので
> 別途仕様を確認してから整理し再度ご質問させていただきたいと
> 思います。
>
> 色々と回答していただいてありがとうございます。
>
初心者本を推奨します。
まず購入しましょうね（＾＾）

■No23893に返信(reoさんの記事)
> ■No23892に返信(zonoさんの記事)
>>■No23890に返信(きいよさんの記事)
> >>zonoさん
> >>
> >>琴さんも書かれていますが、枝分かれがあればどうするか、
> >>いくつもに分断される場合は？等、疑問も残りますが。
> >>ソートというより、
>>>>0 A-B　　　※数値は配列のインデックス
>>>>1 B-C
>>>>2 C-D
>>>>3 D-E
>>>>4 E-F
>>>>5 F-G
>>>>6 G-A
> >>
> >>と循環するものを分断された場合に、
> >>D-E-F-G-A-B-Cとして認識したいと言うことでしたら、
> >>１． Dの様に自分へ連結がない物を先頭とする。
> >>　　（無ければあるルールで）
> >>２．Dから追って、新たな配列に入れなおす。
> >>
> >>と言う手順ではどうでしょう。
> >>
> >>
>>
>>色々と説明に不備があり申し訳ございません。
>>指摘していただいたように枝分かれの考慮が抜けていたので
>>別途仕様を確認してから整理し再度ご質問させていただきたいと
>>思います。
>>
>>色々と回答していただいてありがとうございます。
>>
> 初心者本を推奨します。
> まず購入しましょうね（＾＾）
結構、真面目な質問をしたつもりですけど。ホント＾＾
線の位置を配列に入れて使用するんでしょ？
使い道は2Dか3Dだと思うが、まぁ線で普通のノートの線ですかｗｗｗ
アルゴリズムっかさ、フロチャートの勉強のが有効だと思うが。
いやぁ、真面目ですよ（笑）

■No23897に返信(レオ♪さんの記事)
> ■No23893に返信(reoさんの記事)
>>■No23892に返信(zonoさんの記事)
> >>■No23890に返信(きいよさんの記事)
>>>>zonoさん
>>>>
>>>>琴さんも書かれていますが、枝分かれがあればどうするか、
>>>>いくつもに分断される場合は？等、疑問も残りますが。
>>>>ソートというより、
> >>>>0 A-B　　　※数値は配列のインデックス
> >>>>1 B-C
> >>>>2 C-D
> >>>>3 D-E
> >>>>4 E-F
> >>>>5 F-G
> >>>>6 G-A
>>>>
>>>>と循環するものを分断された場合に、
>>>>D-E-F-G-A-B-Cとして認識したいと言うことでしたら、
>>>>１． Dの様に自分へ連結がない物を先頭とする。
>>>>　　（無ければあるルールで）
>>>>２．Dから追って、新たな配列に入れなおす。
>>>>
>>>>と言う手順ではどうでしょう。
>>>>
>>>>
> >>
> >>色々と説明に不備があり申し訳ございません。
> >>指摘していただいたように枝分かれの考慮が抜けていたので
> >>別途仕様を確認してから整理し再度ご質問させていただきたいと
> >>思います。
> >>
> >>色々と回答していただいてありがとうございます。
> >>
>>初心者本を推奨します。
>>まず購入しましょうね（＾＾）
> 結構、真面目な質問をしたつもりですけど。ホント＾＾
> 線の位置を配列に入れて使用するんでしょ？
> 使い道は2Dか3Dだと思うが、まぁ線で普通のノートの線ですかｗｗｗ
> アルゴリズムっかさ、フロチャートの勉強のが有効だと思うが。
> いやぁ、真面目ですよ（笑）
別に荒らしじゃないですよｗｗｗ
今さぁ、偶然にC++の米貴チャンの3Dドラゴンのとこを勉強してるんです。
始点-終点-始点
3Dの基本、アフィン変換と透視変換。
米ちゃんのｃ++コードをBasicに移植できないか、やってるんですよ
なかなか難しいなぁ〜
魔界ちゃんなら、目をつぶっていても作れそうだね。
しかし、僕チンは初心者だからアレだが。

■No23911に返信(レオ♪さんの記事)
> ■No23897に返信(レオ♪さんの記事)
>>■No23893に返信(reoさんの記事)
> >>■No23892に返信(zonoさんの記事)
>>>>■No23890に返信(きいよさんの記事)
> >>>>zonoさん
> >>>>
> >>>>琴さんも書かれていますが、枝分かれがあればどうするか、
> >>>>いくつもに分断される場合は？等、疑問も残りますが。
> >>>>ソートというより、
>>>>>>0 A-B　　　※数値は配列のインデックス
>>>>>>1 B-C
>>>>>>2 C-D
>>>>>>3 D-E
>>>>>>4 E-F
>>>>>>5 F-G
>>>>>>6 G-A
> >>>>
> >>>>と循環するものを分断された場合に、
> >>>>D-E-F-G-A-B-Cとして認識したいと言うことでしたら、
> >>>>１． Dの様に自分へ連結がない物を先頭とする。
> >>>>　　（無ければあるルールで）
> >>>>２．Dから追って、新たな配列に入れなおす。
> >>>>
> >>>>と言う手順ではどうでしょう。
> >>>>
> >>>>
>>>>
>>>>色々と説明に不備があり申し訳ございません。
>>>>指摘していただいたように枝分かれの考慮が抜けていたので
>>>>別途仕様を確認してから整理し再度ご質問させていただきたいと
>>>>思います。
>>>>
>>>>色々と回答していただいてありがとうございます。
>>>>
> >>初心者本を推奨します。
> >>まず購入しましょうね（＾＾）
>>結構、真面目な質問をしたつもりですけど。ホント＾＾
>>線の位置を配列に入れて使用するんでしょ？
>>使い道は2Dか3Dだと思うが、まぁ線で普通のノートの線ですかｗｗｗ
>>アルゴリズムっかさ、フロチャートの勉強のが有効だと思うが。
>>いやぁ、真面目ですよ（笑）
> 別に荒らしじゃないですよｗｗｗ
> 今さぁ、偶然にC++の米貴チャンの3Dドラゴンのとこを勉強してるんです。
> 始点-終点-始点
> 3Dの基本、アフィン変換と透視変換。
> 米ちゃんのｃ++コードをBasicに移植できないか、やってるんですよ
> なかなか難しいなぁ〜
> 魔界ちゃんなら、目をつぶっていても作れそうだね。
> しかし、僕チンは初心者だからアレだが。
>
> 掲示板の内容が復元してるよですね。
まぁ、アレだ。

レオ♪さん、あるいはreoさん、あるいはレオさんへのお願いです。

「書き込みのルールについて」をお読みいただいていればお分かりいただけていると思いますが、この掲示板ではタメ口が禁止されています。また、他の投稿者を揶揄するような表現がありますが、このような書き込みは絶対にしないでください（きっとお知り合いなのだと思いますが、他の方に誤解を与えますので、ご遠慮ください）。よろしくお願いいたします。

書き込みのルールについて
http://dobon.net/vb/bbs/index.html

■No23921に返信(管理人さんの記事)
> レオ♪さん、あるいはreoさん、あるいはレオさんへのお願いです。
>
> 「書き込みのルールについて」をお読みいただいていればお分かりいただけていると思いますが、この掲示板ではタメ口が禁止されています。また、他の投稿者を揶揄するような表現がありますが、このような書き込みは絶対にしないでください（きっとお知り合いなのだと思いますが、他の方に誤解を与えますので、ご遠慮ください）。よろしくお願いいたします。
>
> 書き込みのルールについて
> http://dobon.net/vb/bbs/index.html
zonoさんの書き込みは多数の掲示板で重複されて書き込みされてます。

■No23924に返信(小川一樹さんの記事)
> ■No23921に返信(管理人さんの記事)
>>レオ♪さん、あるいはreoさん、あるいはレオさんへのお願いです。
>>
>>「書き込みのルールについて」をお読みいただいていればお分かりいただけていると思いますが、この掲示板ではタメ口が禁止されています。また、他の投稿者を揶揄するような表現がありますが、このような書き込みは絶対にしないでください（きっとお知り合いなのだと思いますが、他の方に誤解を与えますので、ご遠慮ください）。よろしくお願いいたします。
>>
>>書き込みのルールについて
>>http://dobon.net/vb/bbs/index.html
> zonoさんの書き込みは多数の掲示板で重複されて書き込みされてます。
＞＞Yes

■No23924に返信(小川一樹さんの記事)
> zonoさんの書き込みは多数の掲示板で重複されて書き込みされてます。

マルチポストを発見したのなら、マルチポスト先のURLを併記して下さい。
でなければ只の言いがかりになってしまいますよ。

No23924 のご投稿者の小川一樹さんと No23926 のご投稿者の戸田明宏さんへのお願いです。

すでに指摘されていますが、もしこのスレッドの質問がマルチポストであるということであれば、そのURLを明記してください。そうでないと、本当にマルチポストであるか判断できません。これでは、太郎冠者さんがおっしゃっているように、マルチポストの報告ではなく、ただの言いがかりになってしまいますので、必ずURLのご報告をお願いいたします。（マルチポストされたURLの記述がない場合は、マルチポストの報告とは判断しません。）

また、小川一樹さんと戸田明宏さんは同一人物でしょうか?もしそうであれば、なぜ2回目にあたかも別人が自分の投稿に同調するようなていで投稿されたのでしょうか?この2つが同じ人の投稿であり、閲覧者にいかにも自分の主張が正しいように思わせるための小細工であったならば、悪質であると判断せざるを得ません。（もし小川一樹さんと戸田明宏さんが別の方であったならば、申し訳ありません。）

もし小川一樹さんと戸田明宏さんが同一人物で、さらにその方がすでに私が注意したことのある方でいらっしゃった場合、これを最後にしていただけますように、心からお願いいたします。もし次に同じ様なことがあった場合は、予告なしで厳しい処置がとられてしまうかもしれないことをお許しください。

■No23933に返信(管理人さんの記事)
> No23924 のご投稿者の小川一樹さんと No23926 のご投稿者の戸田明宏さんへのお願いです。
>
> すでに指摘されていますが、もしこのスレッドの質問がマルチポストであるということであれば、そのURLを明記してください。そうでないと、本当にマルチポストであるか判断できません。これでは、太郎冠者さんがおっしゃっているように、マルチポストの報告ではなく、ただの言いがかりになってしまいますので、必ずURLのご報告をお願いいたします。（マルチポストされたURLの記述がない場合は、マルチポストの報告とは判断しません。）
>
> また、小川一樹さんと戸田明宏さんは同一人物でしょうか?もしそうであれば、なぜ2回目にあたかも別人が自分の投稿に同調するようなていで投稿されたのでしょうか?この2つが同じ人の投稿であり、閲覧者にいかにも自分の主張が正しいように思わせるための小細工であったならば、悪質であると判断せざるを得ません。（もし小川一樹さんと戸田明宏さんが別の方であったならば、申し訳ありません。）
>
> もし小川一樹さんと戸田明宏さんが同一人物で、さらにその方がすでに私が注意したことのある方でいらっしゃった場合、これを最後にしていただけますように、心からお願いいたします。もし次に同じ様なことがあった場合は、予告なしで厳しい処置がとられてしまうかもしれないことをお許しください。
消していただいて結構です。
URLを掲載できる掲示板は、すべて信用していませんので。