2D でポリゴンを表すポイントのリストが与えられた場合、そのポイントがポリゴンの内側にあるかどうかを判断するにはどうすればよいですか。
多角形は凹面または凸面のいずれかであることに注意してください。また、点の順序について何らかの仮定を立てることもできます。
質問する
495 次
4 に答える
7
これを行う最善の方法は、ポイントから任意の方向に線を引き、オブジェクトの境界を横切る回数を数えることです。境界に偶数回当たった場合はオブジェクトの外側になり、奇数回の場合は内側になります。通常、この決定を行うには、軸の 1 つに沿って進むのが最も簡単です。
基本的に、ポイントを通過したかどうかを判断する方法を見つける必要があります。直線の勾配 ( m=(y1-y2)/(x1-x2), y=m*x(x-x1)+y1, を使用し、点が有効である境界内を横切るかどうかを確認します。点間の直線についてこの方程式が与えられると、直線がこの直線と交差する場所を決定し、それが範囲内にあるかどうかを判断します。ラインの範囲。
ちなみに、同じ方法は任意の次元で機能しますが、顔に当たったかどうかを判断するだけで難しくなります.
いくつかの例を示すために、私は単純なイラストを描いて、内部と外部の両方で何が起こっているかを示しています。
ちなみに、コーナーを打った場合は、インサイドからアウトサイドへのトランジションの回数としてカウントされます。
于 2012-12-17T18:23:38.567 に答える
2
多角形の外側の点を選択します。あなたのポイントと外側のポイントの間に線を引きます。ラインがポリゴンと奇数回交差する場合は内側、それ以外の場合は外側です。ゼロ交差点も外です。ただし、これは重なり合っていないポリゴンに対してのみ機能します
于 2012-12-17T18:29:40.083 に答える
1
これは、多くのソリューションで既知の問題です。Google で検索してください。そしてこれを読んでください： http://en.wikipedia.org/wiki/Point_in_polygon
于 2012-12-17T19:08:57.793 に答える
0
ポイントから任意の線を、確実にポリゴンの外側 (境界の外側) にある任意のポイントに引きます。その線が多角形のエッジの 1 つと何回交差するかを確認します。値が奇数の場合、ポイントは内側にあります。
チェックするときは、頂点を通過する線に注意してください。テストで 2 つのエッジの交差が示される場合があります。
于 2012-12-17T18:23:23.917 に答える