ポイントのリストがある場合、それらが時計回りの順序になっているかどうかをどのように確認すればよいでしょうか?
例えば:
point[0] = (5,0)
point[1] = (6,4)
point[2] = (4,5)
point[3] = (1,5)
point[4] = (1,0)
反時計回り(人によっては反時計回り)だと言うでしょう。
ベストアンサー1
提案された方法のいくつかは、三日月形などの非凸多角形の場合に失敗します。ここでは、非凸多角形に使用できる簡単な方法を紹介します (8 の字のような自己交差多角形にも使用でき、主に時計回りかどうかがわかります)。
エッジの合計は (x 2 − x 1 )(y 2 + y 1 ) です。結果が正の場合、曲線は時計回りになり、負の場合、曲線は反時計回りになります。(結果は、+/- 規則に従って、囲まれた領域の 2 倍になります。)
point[0] = (5,0) edge[0]: (6-5)(4+0) = 4
point[1] = (6,4) edge[1]: (4-6)(5+4) = -18
point[2] = (4,5) edge[2]: (1-4)(5+5) = -30
point[3] = (1,5) edge[3]: (1-1)(0+5) = 0
point[4] = (1,0) edge[4]: (5-1)(0+0) = 0
---
-44 counter-clockwise