1. ホーム
  2. math

[解決済み】ポリゴンの点のリストが時計回りに並んでいるかどうかを判断する方法は?

2022-03-30 22:10:15

質問

点のリストがあるとき、それらが時計回りに並んでいるかどうかを調べるにはどうしたらよいでしょうか。

例えば

point[0] = (5,0)
point[1] = (6,4)
point[2] = (4,5)
point[3] = (1,5)
point[4] = (1,0)

は、反時計回り(人によっては反時計回り)と言うことになります。

解き方は?

提案されている方法の中には、三日月のような非凸の多角形の場合、失敗するものがあります。ここでは、凸でない多角形で動作する簡単な方法を紹介する(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