11

最初は、この問題は多角形が凸面であるかどうかを判断することと同じだと思いましたが、非凸多角形は1つの三角形のファンで描画できるようです。 この形状、非凸多角形を考えてみましょう。このポリゴンを三角形のファンで描画できるようにする中心点の領域を簡単に想像できます（ただし、そうでない他の中心点もあります）。固定された中心点が与えられた場合、ポリゴンを定義する2Dポイントのセットによって、単一の三角形のファンでポリゴンを描画できるかどうかを判断できるようにしたいと思います。

重要なのは、中心点から頂点のいずれかに引かれた線、つまり頂点の他のエッジ線を「邪魔」しないようにすることのようです。ただし、これを可能な限り計算コストを下げることが重要であり、これを行うための優れた数学のショートカットがあるかどうかはわかりません。

最終的には、ポリゴンの頂点を移動させます。残りが固定されている場合、頂点が移動できる「境界」を決定する必要があります（おそらく、後で直接のリアクティブな移動を同時に許可することもできます）。 2つのネイバーも）、単一の三角形のファンでポリゴンを描画できるようにします。しかし、それは将来のことです。うまくいけば、ポリゴン全体に対するテストを計算のサブセットに分割して、すでに凸多角形を想定した単一の頂点の動きの境界をテストできます。

4

3 に答える 3

13

お探しの物件は「星型」です。星型ポリゴンは、ポリゴン全体が見えるポイントを持つことで定義されます。

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

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

于 2012-04-25T17:25:30.067 に答える
2

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

次のようになります。

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;
    }
}
于 2012-04-25T17:35:15.067 に答える
1

すべての潜在的な中心点は、ポリゴンのすべてのエッジの内側にある必要があるようです。したがって、すべてのエッジをハーフスペースとして扱い、それらの交点が空かどうかを判断します。

@jpalecek が言うように、これを表す用語は星形です。多角形が星形の場合、凸多角形 (元の内部) があり、その点から元のすべてのエッジを表示できます。逆に、そのようなサブ多角形が存在しない場合、元の多角形は星形ではありません。となり、三角扇では描けません。

このサブポリゴンを決定することは、基本的に凸包問題の二重の適用です。で計算できます。O(n log n)

于 2012-04-25T17:37:47.490 に答える