凸型の多角形の座標

凸型の多角形が作れるような座標があります。
それぞれの座標を

P(0),P(1)・・・P(n)

とします。今それぞれの座標はバラバラで

P(0)→P(1)→P(2)→・・・→P(n)→P(0)

と結んでも凸型の多角形になりません。
これを凸型の多角形が作れるように時計回りか反時計回りに並び替えるプログラムは
どのように書いたらいいでしょうか？

No.3 ベストアンサー 回答者： Tacosan 回答日時： 2014/09/04 10:14

凸多角形になることが保証されているなら, 例えば

1. y座標が最小の点を見つける
2. その点から他の各点を結んだ直線の, x軸からの偏角を求める
3. 偏角の小さい順にソートする
でできるはず.

一般的には Jarvis march (ジャービスの行進) とかで調べてくれ.

No.4 回答者： Tacosan 回答日時： 2014/09/04 13:04

#3 をちと変更.

本質は何も変わらないけどコードとしては 1 を「x座標が最小の点を見つける」とした方がおそらく簡単.

No.2 回答者： hashioogi 回答日時： 2014/09/04 09:42

とりあえず

P(0)→P(1)→P(2)→・・・→P(n)→P(0)
と結ぶ。この状態では複数の線分が交差している可能性がある。

[外側のループ]
P(0)→P(1)、P(1)→P(2)、P(3)→P(4)、…、P(n-1)→P(n)のそれぞれの線分に対して、順番に[内側のループ]の処理を行う。

[内側のループ]
今外側のループでP(r)→P(r+1)が選択されていると仮定する。
P(r+2)→P(r+3)、P(r+3)→P(r+4)、…、P(n)→P(0)のそれぞれがP(r)→P(r+1)と交差するかどうか調べる。
もしP(s)→P(s+1)が交差していたら、P(r+1)～P(s)の範囲の座標を全て逆転させる（これで交差が1つ解消される。でもまだP(r)→P(r+1)に対して交差が残っているかもしれない）。
例えば今、P(5)→P(6)とP(9)→P(10)が交差していたら、入れ替えた後では、
…、P(4)、P(5)、P(9)、P(8)、P(7)、P(6)、P(10)、P(11)、…
となる。でもこれは改めて以後
…、P(4)、P(5)、P(6)、P(7)、P(8)、P(9)、P(10)、P(11)、…
と呼ばれることになる。
交差が無くなったら外側のループに戻って外側の線分を次の線分にする。

つまり今回の場合は全ての線分が互いに交差しなくなれば凸多角形になっているはず。

No.1 回答者： hitomura 回答日時： 2014/09/04 05:05

P(0),P(1)・・・P(n) が凸多角形を形成できることが保障されているならば、

(1) 求める多角形の初期値として Poly := [P(0), P(1), P(2)] とする。
(2) k := (Poly の要素数) とし、P(k) に対して、(Poly[0], Poly[1]), (Poly[1], Poly[2]),..., (Poly[k - 2], Poly[k - 1]), (Poly[k - 1], Poly[0]) のうち最も距離が近い線分（直線ではなく）を求める。
　(2-1) (2) で求めた線分が (Poly[k - 1], Poly[0]) の時： Poly の末尾に P(k) を追加する。
　(2-2) 上記を満たさない、すなわち、(2) で求めた線分が (Poly[m], Poly[m + 1]) の時： Poly の m 番目の要素の後に P(k) を追加する。
(3) Poly の要素数が n になるまで (2) へ。

でできる、と思うんだけどどうかなぁ。