1

多角形の座標が与えられると、点が多角形内にあるかどうかを検出する多くのアルゴリズムが見つかりました。たとえば、[1]と[2]です。しかし、これらのアルゴリズムはいずれも、点がこの多角形の頂点にあるかどうかを検出できません。たとえば、私は多角形を持っています:

|---------------------|
|                     |
|                     |
|---------------------|

私のポイントは右上隅にあります。ポイントがポリゴンの内側にあるかどうかを教えてくれるアルゴリズムが必要です。これどうやってするの？

4

2 に答える 2

1

正確に一致しないが十分に近い浮動小数点に関連する問題を処理する問題を除いて 、同じアルゴリズムが両方で機能するはずです。
ポリゴンの内側のポイントを選択し、テスト ポイントから内側のポイントまでのテスト ライン セグメントを作成します。次に、ポリゴンの各セグメントについて、テスト ライン セグメントがそのポリゴン セグメントと交差するかどうかを判断します。交差としてカウントするには、交差をカウントします。ポリゴン セグメントの一方の端が開いていて、もう一方の端が閉じています。つまり、交差点がポリゴンの始点とまったく同じ場合はカウントしますが、終点とまったく同じ場合はカウントしません。これを行う必要があるのは、テスト セグメントがポリゴンの頂点と交差するときに、頂点の両側にある 2 つのセグメントの 1 つとの交差としてのみカウントする必要があるためです。

次に、テストポイントがポリゴンの内側にある場合、交差点の数は偶数になり、外側にある場合は奇数になります。

于 2013-07-08T13:45:53.810 に答える