凹型 (非凸型) 多角形の対角線 (対角線は、隣接しない頂点を接続するセグメントです) は、完全に多角形の内側または外側にある場合があります (または、多角形のエッジと交差する場合があります)。完全にポリゴン内にあるかどうかを判断する方法は? (ポイント イン ポリゴン テストを使用しない方法)。
5984 次
6 に答える
6
対角線がエッジとの交差を少なくとも 1 つ持つ場合、それは部分的に多角形の中にあり、部分的に多角形の外にあります。ただし、対角線がそれらと交差しない場合は、2 つの状態しかありません: 完全に多角形の中にあるか、完全に多角形の外にある.
ポリゴンの内側か外側かを判断するには:
ポリゴンの頂点が反時計回りにソートされているとします。P[i] という名前の頂点にある対角線の端点の 1 つを考えてみましょう (もう一方の端点は p[j] です)。次に、最初の点が p[i] である 3 つのベクトルを作成します。
V1 : p[i+1] - p[i]
V2 : p[i-1] - p[i]
V3 : p[j] - p[i]
V1 から V2 に反時計回りに移動したときに、V3 が V1 と V2 の間にある場合にのみ、対角線は完全に多角形内にあります。
V1 から V2 に反時計回りに移動するときに、V3 が V1 と V2 の間にあるかどうかを判断するにはどうすればよいですか? ここに行きます。
この方法を使用してプログラムを作成しましたが、効果的に動作します。
于 2009-03-30T02:33:33.163 に答える
4
完全にポリゴン内にあるかどうかを判断する方法は?
対角線がポリゴンの境界を決して離れないかどうかを判断したい場合は、隣接する 2 つの頂点間の線と交差するかどうかを判断するだけです。
含まれている場合は、部分的にポリゴン内にあり、部分的にポリゴンの外にあります。
そうでない場合は、ポリゴンに完全に入っているか、完全に出ています。そこから、最も簡単な方法は、対角線上の任意の点でポイント イン ポリゴンを使用することですが、それを行いたくない場合は、ワインディング アルゴリズムを使用します。
于 2009-03-29T00:27:01.273 に答える
3
ジョンの答えは、重要なケースを見逃していると思います。対角線が最初から完全にポリゴンの外側にある場合です。対角線の「橋」を、彼の「u」字型の多角形の 2 つの塔にすることを想像してみてください。
数年前にこれを解決しなければならなかったので、私の記憶が少しむらがある場合はご容赦ください。
これを解決した方法は、ポリゴンのすべてのエッジに対して対角線の交差テストを実行することでした。次に、2 つのケースが考えられます。少なくとも 1 つの交差点がある場合と、交差点がない場合です。交点がある場合、対角線はポリゴンの内側にありません。
交点が得られない場合は、対角線が完全にポリゴンの内側にあるか完全に外側にあるかを判断する必要があります。対角線が p[i] を p[j] に結合していて、i < j であり、時計回りに曲がった多角形があるとします。p[i] を p[i+1] に結合するエッジを調べることで、対角線が多角形の外側にあるかどうかを判断できます。このエッジの 2D 角度を計算します (たとえば、x 軸をベースラインとして使用します)。p[i]-p[i+1] エッジがベースラインになるように対角線を回転させ、その 2D 角度を計算します。
これを行うと、対角線がポリゴンの外側にある場合は対角線の 2D 角度が正になり、ポリゴンの内側にある場合は負になります。
于 2009-03-29T00:37:46.867 に答える
1
線分間の交点のチェック (最初に行う必要がある可能性が高い) に関しては、SoftSurferの説明が役立つことがわかりました。対角線とポリゴンのいずれかのエッジとの交差を確認する必要があります。MATLAB を使用している場合は、行列演算とベクトル演算を使用してすべてのエッジの交点を同時にチェックする効率的な方法を見つけることができるはずです (光線と三角形の交点について、この方法で交点を計算しました)。
于 2009-03-30T03:09:29.113 に答える
0
ジョンの答えは次のとおりです。
対角線がポリゴンの境界を決して離れないかどうかを判断したい場合は、隣接する 2 つの頂点間の線と交差するかどうかを判断するだけです。もしそうなら、それはポリゴンのままです。
このチェックを行う効率的な方法は、データに対して Bentley-Ottman スイープライン アルゴリズムを実行することです。実装は簡単ですが、数値を安定させるのは難しいです。ポリゴン内のエッジが ... たとえば ... 20 未満の場合、ブルート フォース検索のほうが高速になる可能性が高くなります。
于 2009-03-29T00:32:07.317 に答える