22

平面、おそらく地図上に多数の凸多角形があるとします。これらのポリゴンは互いに衝突してエッジを共有できますが、重なり合うことはできません。

代替テキスト

2 つのポリゴンPとQがオーバーラップしているかどうかをテストするには、まずPの各エッジをテストして、 Qのいずれかのエッジと交差するかどうかを確認します。交差が見つかれば、 PとQが交差すると宣言します。交差しない場合は、PがQに完全に含まれているか、またはその逆かをテストする必要があります。次に、 P == Qの場合です。最後に、いくつかのエッジを共有しているが、すべてではないケースがあります。(これらの最後の 2 つのケースは、おそらく同じ一般的なケースと考えることができますが、それは重要ではないかもしれません。)

2 つの線分が交差する場所を検出するアルゴリズムがあります。2 つのセグメントが同一線上にある場合、私の目的では交差しているとは見なされません。

ケースを適切に列挙しましたか？これらのケースをテストするための提案はありますか?

交差点である新しい凸多角形を探しているわけではないことに注意してください。交差点が存在するかどうかを知りたいだけです。交点を見つけるための十分に文書化されたアルゴリズムが多数ありますが、すべての作業を行う必要はありません。

4

7 に答える 7

4

  • 多角形が常に凸状である場合は、最初に多角形の中心から中心に引いた線の角度を計算します。これにより、他のポリゴンから 180 度離れたポリゴンの半分でエッジ セグメントをテストする必要がなくなります。

  • エッジを削除するには、左側のポリゴンから始めます。前の箇条書きの線分に垂直な多角形の中心から線分を取り、多角形の両側に接します。頂点 p1 と p2 を持つこの線分を p と呼びます。次に、すべての頂点について、x 座標が p1.x および p2.x より小さい場合、その頂点は「安全なバケット」に入れることができます。

  • そうでない場合は、ラインの「安全な」側にあることを確認する必要があります（y座標も確認してください）

-多角形の線分のすべての頂点が「安全なバケット」にある場合は、それを無視できます。

-極性を逆にして、2 番目のポリゴンの「右向き」にします。

于 2009-04-15T18:57:53.567 に答える
3

GJK 衝突 検出が機能 するはず です。

于 2009-04-15T19:16:52.633 に答える
1

ここにアイデアがあります：

  • 各ポリゴンの中心点を見つけます

  • 他の中心点に最も近い各ポリゴンの2つの点を見つけます。それらは凸多角形の隣接する点になります。これらは各ポリゴンの最も近いエッジを定義します。ポイントを{A、B}および{Y、Z}と呼びましょう。

  • 線ABとYZの交点を見つけます。線分が交差する場合（ABの交点がAとBの間にある場合）、ポリゴンは交差します。ABとXYが並列である場合、この条件を無視すると、次のステップで問題がトラップされます。

  • 確認する必要があるもう1つのケースがあります。これは、ポリゴンが十分に交差しているため、ABとXYが完全に交差していて、実際には交差していない場合です。このケースをトラップするには、各ポリゴンの中心点に対するABとXYの垂直距離を計算します。いずれかの中心点が反対側のポリゴンの線分に近い場合、ポリゴンは大きく重なります。

于 2009-04-15T19:15:24.120 に答える
1

ポリゴンがまったく交差しないケース (完全に外側または完全に内側) と、何らかの形の部分的な交差があるケース (オーバーラップがある場合は常にエッジが交差する) をチェックしているため、テスト ケースは機能するはずです。 .

テストのために、考えられるすべての組み合わせをテストするようにします。上に表示されていないのは、共有されている単一のエッジですが、1 つのポリゴンが別のエッジに含まれています。また、予防措置として、tri -> many side など、より複雑なポリゴン形状のテストも追加します。

また、ポリゴンを完全に囲んでいるが重なっていない U 字型のポリゴンがある場合は、ケースで処理されると思いますが、それもチェックとして追加します。

于 2009-04-15T18:57:03.617 に答える
1

altCognito はすでに解決策を提供しているので、興味を引く可能性のある計算幾何学に関する優れた本のみを紹介します。

于 2009-04-15T19:05:27.823 に答える