2つのポリゴンを1つの三角形のファンで描画できるかどうかを調べる

Question

最初は、この問題はポリゴンが凸であるかどうかを判断するのと同じだと思っていましたが、ファン。 Consider this shape、非凸多角形。三角形のファンでこのポリゴンを描画できる中心点の一部の領域を簡単に想像することができます（他の中心点はありませんが）。固定された中心点が与えられていれば、ポリゴンを定義する2d点のセットが単一の三角形のファンで描画できるかどうかを判断できるようにしたい。

キーは、中心点から任意の頂点、つまり頂点の他の稜線に描かれた線の「途中に」入ることを何も確認していないようです。しかし、これをできるだけ計算機的に安価にすることが重要です。これを行うための簡単な数学のショートカットがあるかどうかはわかりません。

最終的に、私はポリゴンの頂点を動かすつもりです。そして、残りが固定されているならば、頂点が移動することを許された "境界"を決定する必要がありますダイレクト2近傍の動きも）、ポリゴンを単一の三角形のファンで描画できるようにします。しかし、これは未来です。完全多角形のテストは、既に凸状のポリゴンを仮定して、単一の頂点の動きの境界をテストするための計算のサブセットに分割することができます。

Answer 1

アンカーから各頂点までの角度が同じ方向に移動すると、ポリゴンは三角形のファンとして描画できます。これをテストする最も簡単な方法は、連続する頂点の外積の内積をチェックすることです。

それは次のようなものになります。すべての潜在的な中心点は、あなたのポリゴンのすべてのエッジの内側にする必要がありますように見えます

vector lastCross = cross_product(vector(vertex[0] - center), vector(vertex[numVerts - 1] - center)); 

canBeFan = true; 
for (n = 1; canBeFan && n < numVerts; ++n) { 
    vector testCross = cross_product(vector(vertex[n] - center), vector(vertex[n - 1] - center)); 
    if (0.0 >= dot_product(testCross, lastCross)) { 
     canBeFan = false; 
    } 
} 

Answer 2

あなたが探しているプロパティは "star-shaped"です。星型ポリゴンは、ポリゴン全体が見える点を持つことによって定義されます。

ポリゴンが星型であることをテストするには、ポリゴン全体が表示される領域を作成できます。その領域は凸型の集合であるため、O(log(n))のハーフプレーンと交差することができます。

つまり、エッジによって形成されたハーフプレーンを交差させ、結果の可視領域がO(n log n)で空でないことを確認できます。

Answer 3

を。したがって、すべてのエッジを半空間として扱い、交差が空であるかどうかを判断します。

@jpalecekによると、これはという星形です。ポリゴンが星型である場合、ポイントがオリジナルのすべての端を見ることができる凸状のポリゴン（オリジナルの内部）があります。逆に、そのようなサブポリゴンが存在しない場合、オリジナルはスター型ではありません三角形のファンで描くことはできません。

このサブポリゴンを特定することは、基本的にはdualという問題のconvex hullアプリケーションの適用です。 O(n log n)で計算できます。