c - C - 凸多角形 - ソート ポイント (時計回り)

Question

点で表現された凸多角形があります。点はx 座標の配列と y座標の配列で表されます。

例えば：

X = {6, 1, 5, 0, 3}
Y = {4, 0, 0, 4, 6}

このポイントを時計回りに並べ替えるにはどうすればよいですか? ポイントの数は常に同じではありませんが、ポリゴンは依然として凸状です。

---

atan2 またはmath.hの他の関数を使用しない解決策はありますか?

Answer 1

極角でソートすることをお勧めしますが、そのためには凸多角形の内側を原点とする方がよいでしょう。そのようなポイントを取得するには、ポリゴンの対角線の中間点を使用できます。たとえば、 ( (x[0] + x[2])/2, (y[0]+y[2])/2 ）。

Answer 2

それらを極座標に変換することで回避できると思います。Cにはatan2次のようなものがあります:

atan2(y[0], x[0]);

それぞれの角度を取得したら、それらを使用してポイントを並べ替えることができます。