7

与えられた 2 つのポリゴンがあります。あるポリゴンが他のポリゴンの内側、外側、または交差しているかどうかをどのように判断できますか? ポリゴンは凹面または凸面にすることができます。

4

4 に答える 4

3

凸多角形に分離軸定理を使いたい。基本的に、各ポリゴンの各面について、各ポリゴンをその面の法線に投影し、それらの投影が交差するかどうかを確認します。

さまざまなトリックを実行して、実行する必要があるこれらの計算の数を減らすことができます。たとえば、オブジェクトの周りに四角形を描画し、2 つのオブジェクトの四角形が交差しない場合、それら自体も交差しないと想定できます。(これらのボックスの交点をチェックする方が計算コストがかからず、一般的に非常に直感的であるため、これは簡単です。)

凹面ポリゴンはより困難です。多角形を一連の凸多角形に分解し、交差の各組み合わせをチェックしようとすることはできると思いますが、この分野で試してみるのに十分なスキルがあるとは思いません。

于 2012-06-27T17:50:43.277 に答える
2

一般に、このような問題はスイープ ライン アルゴリズムによって簡単に解決されます。ただし、スイープ ライン アプローチを使用する主な目的と利点は、入力が 2 つの比較的大きなポリゴン セットで構成される場合に問題を効率的に解決できることです。スイープ ライン ソリューションが実装されると、必要に応じてポリゴンのペアに効率的に適用することもできます。将来、大規模な問題を解決する必要がある場合に備えて、その方向に進むことを検討する必要があるかもしれません。

ただし、2 つだけのポリゴンのソリューションが必要であることが確実な場合は、ポイント対ポリゴンおよびセグメント対ポリゴンの順次テストによって解決できます。

于 2012-06-28T00:08:02.523 に答える
0

ポイントがポリゴン内にあるかどうかを確認する簡単な方法があります。このウィキペディアの記事によると、それはレイキャスティングアルゴリズムと呼ばれています。

アルゴリズムの基本的な考え方は、テストしている点から任意の方向に光線を放ち、それが交差するポリゴンのエッジの数を数えることです。この数が偶数の場合、ポイントはポリゴンの外側にあり、奇数の場合、ポイントはポリゴンの内側にあります。

このアルゴリズムには、掘り下げない多くの問題がありますが (以前にリンクしたウィキペディアの記事で説明されています)、このアルゴリズムを簡単だと私が呼ぶ理由はそこにあります。しかし、アイデアを得るには、光線が頂点と交差する、光線が平行に走り、エッジと交差する、および点がエッジの近くにある場合の数値安定性の問題を含むコーナーケースを処理する必要があります。

次に、トーマスが回答で説明した方法でこのメソッドを使用して、2 つのポリゴンが交差するかどうかをテストできます。これによりO(NM)、2 つのポリゴンがそれぞれNとM頂点を持つアルゴリズムが得られます。

于 2012-06-28T00:05:03.240 に答える
0

以下は、特定のポイントが特定のポリゴンの内側にあるか外側にあるかを知る簡単なアルゴリズムです。

bool isInside(point a, polygon B)
{
    double angle = 0;
    for(int i = 0; i < B.nbVertices(); i++)
    {
        angle += angle(B[i],a,B[i+1]);
    }
    return (abs(angle) > pi);
}
  • A の線分が B の線分と交差する場合、2 つのポリゴンは互いに交差します。
  • それ以外の場合、ポリゴン A のすべてのポイントがポリゴン B の内側にある場合、A は B の内側にあります。
  • それ以外の場合、ポリゴン B のすべてのポイントがポリゴン A の内側にある場合、B は A の内側にあります。
  • それ以外の場合、ポリゴン A のすべてのポイントがポリゴン B の外側にある場合、A は B の外側にあります。
  • それ以外の場合、2 つのポリゴンは互いに交差します。
于 2012-06-27T14:10:34.403 に答える