c++ - 多角形の凸 C++?

Question

C ++で座標を持つポリゴンのポイントを知るだけで、ポリゴンが凸面であるかどうかをテストするにはどうすればよいですか?

Answer 1

多角形の各辺について、線の方程式 ( ) を計算し、すべての点がその 1 つの辺からのものであることをAx+By+C=0確認します (方程式にxとを入れて符号を取得します)。y

編集:凸多角形を移動する場合、すべてのポイントで常に一方向(左または右)に回転します。外積を使用すると、次のターンに回転する側 (負または正) を簡単に推測できます。連続する 3 つの点のすべての外積が等号の場合、多角形は凸面になります。

Answer 2

一般的なアルゴリズムのいずれかを使用して凸包を見つけます。すべての頂点が凸包に属している場合にのみ、多角形は凸です。

これは O(n log n) ですが、ポイントがポリゴンのエッジの周りで適切な順序で与えられているという仮定に依存していません。仮定が真の場合、ヘイトエンジンからの答えは最適です (つまり、線形時間)。

Answer 3

ギフト ラッピング アルゴリズムは、特定のポイント セットの凸包を計算するためのアルゴリズムです。

wikiからの疑似コード:

jarvis(S)
   pointOnHull = leftmost point in S
   i = 0
   repeat
      P[i] = pointOnHull
      endpoint = S[0]  // initial endpoint for a candidate edge on the hull
      for j from 1 to |S|-1
         if (endpoint == pointOnHull) or
            (S[j] is on left of line from P[i] to endpoint)
            endpoint = S[j]   // found greater left turn, update endpoint
      i = i+1
      pointOnHull = endpoint
   until endpoint == P[0] // wrapped around to first hull point

ポイントが上記のアルゴリズムで検出されたポイントと一致する場合、ポリゴンは凸面です。