geometry - 一連の点からの頂点を持つポリゴン

Question

指定されたポイント セットからポリゴンを作成するにはどうすればよいですか。

可能な多角形 :

無効なポリゴン:

ポリゴンは自己交差してはなりません。

1点を基準に点を並べ替えようと考えていたのですが、うまくいかない場合もあるようです。ありがとう。

Answer 1

たぶん、そう：

1. 与えられた点の凸包 H を見つける
2. ハル内にない各ポイント P について、ハルの最も近いエッジ HiHi+1 を見つけ、それをエッジ HiP および PHi+1 に置き換えます。
3. 2 つのポイントが同じ最も近いエッジを持つ場合、それらを結びます