2 つの凸多角形が交差しているかどうかを判断するにはどうすればよいですか?
https://stackoverflow.com/questions/753140
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian質問
平面 (おそらく地図) 上に多数の凸多角形があると仮定します。これらのポリゴンは互いにぶつかってエッジを共有できますが、重なることはできません。
2 つのポリゴンかどうかをテストするには P そして Q オーバーラップ、最初に各エッジをテストできます P のいずれかのエッジと交差するかどうかを確認します Q. 。交差点が見つかったら、次のように宣言します。 P そして Q 交差する。交差するものがない場合は、次の場合をテストする必要があります。 P によって完全に封じ込められている Q, 、 およびその逆。次に、こんなケースがあります P==Q. 。最後に、いくつかのエッジを共有する場合がありますが、すべてではありません。(これら最後の 2 つのケースはおそらく同じ一般的なケースと考えることができますが、それは重要ではない可能性があります。)
2 つの線分が交差する場所を検出するアルゴリズムがあります。2 つのセグメントが同一直線上にある場合、この目的ではそれらは交差するとみなされません。
ケースを適切に列挙しましたか?このような場合のテストに関する提案はありますか?
交差点である新しい凸多角形を見つけようとしているのではなく、交差点が存在するかどうかを知りたいだけであることに注意してください。交差点を見つけるアルゴリズムは詳しく文書化されていますが、すべての労力を費やす必要はありません。
解決
使用できます この衝突アルゴリズム:
2 つの凸多角形が交差している (互いに接触している) かどうかを判断するには、分離軸定理を使用できます。基本的に:
- 2 つの凸多角形が交差していない場合、それらの間を通る線が存在します。
- このような線は、多角形の 1 つの辺の 1 つがそのような線を形成している場合にのみ存在します。
最初のステートメントは簡単です。多角形は両方とも凸であるため、交差しない限り、一方の多角形を一方の側に、もう一方の多角形を反対側に持つ線を描くことができます。2 番目の方法は直感的ではありません。図 1 を見てください。多角形の最も近い辺が互いに平行でない限り、多角形が互いに最も近づく点は、一方の多角形の角がもう一方の多角形の辺に最も近づく点となります。この辺は多角形間の分離軸を形成します。辺が平行である場合、それらは両方とも分離軸です。
では、これは具体的に、ポリゴン A と B が交差するかどうかを判断するのにどのように役立つのでしょうか?各ポリゴンの各辺を調べて、それが分離軸を形成しているかどうかを確認するだけです。これを行うには、基本的なベクトル計算を使用して、両方の多角形のすべての点を、潜在的な分離線に垂直な線上に押し込みます (図 2 を参照)。これで、問題全体が都合よく 1 次元になりました。各多角形の点が存在する領域を決定できます。これらの領域が重ならない場合、この線が分離軸になります。
両方の多角形の各線をチェックした後、分離軸が見つからなかった場合は、多角形が交差していることが証明されており、それに対して何らかの措置を講じる必要があります。
他のヒント
多角形が常に凸状である場合は、まず多角形の中心から中心まで引いた線の角度を計算します。これにより、他のポリゴンから 180 度離れたポリゴンの半分のエッジ セグメントをテストする必要がなくなります。
エッジを削除するには、左側の多角形から始めます。前の箇条書きの線分に垂直で、多角形の両側に接する多角形の中心から線分を取得します。頂点 p1 と p2 を持つこの線分を p と呼びます。次に、すべての頂点について、x 座標が p1.x および p2.x より小さい場合、その頂点は「安全なバケット」に入れることができます。
そうでない場合は、それがラインの「安全な」側にあることを確認する必要があります（y 座標もチェックしてください）。
- ポリゴン内の線分のすべての頂点が「安全なバケット」内にある場合は、それを無視できます。
-極性を反転して、2 番目の多角形が「右向き」になるようにします。
ポリゴンがまったく交差していない (完全に外側または完全に内側) 場合と、何らかの形で部分的に交差している (オーバーラップがある場合はエッジが常に交差する) 場合をチェックしているため、テスト ケースは機能するはずです。 。
テストの場合は、考えられるすべての組み合わせを必ずテストします。私が見たものから上に欠けているものは、単一のエッジが共有されていますが、一方のポリゴンがもう一方のポリゴンに含まれています。予防措置として、三角形から多面体まで、より複雑なポリゴン シェイプのテストも追加します。
また、ポリゴンを完全に囲んでいるが重なり合っていない U 字型のポリゴンがある場合、あなたのケースではそれが処理されると思いますが、それもチェックとして追加します。
altCognito がすでに解決策を提供しているため、指摘するだけです 計算幾何学に関する優れた本 興味があるかもしれません。
ここにアイデアがあります:
各多角形の中心点を見つける
各多角形の中心点に最も近い 2 つの点を見つけます。凸多角形の隣接する点になります。これらは各多角形の最も近いエッジを定義します。点を {A, B} と {Y, Z} と呼びます。
線ABとYZの交点を見つけます。線分が交差する場合 (AB 上の交点が A と B の間にある場合)、ポリゴンは交差します。AB と XY が並列の場合、この条件を無視すると、次のステップで問題が発生します。
確認する必要があるケースがもう 1 つあります。それは、ポリゴンが激しく交差し、AB と XY が完全に互いにすれ違っていて、実際には交差していない場合です。このケースをトラップするには、各ポリゴンの中心点までの AB と XY の垂直距離を計算します。いずれかの中心点が反対側の多角形の線分に近い場合、多角形は重なり合います。
凸多角形間の交差や包含を検出するには、いくつかの方法があります。それはすべて、アルゴリズムをどの程度効率的にしたいかによって決まります。それぞれ頂点 r と b を持つ 2 つの凸多角形 R と B を考えてみましょう。
