Loading article…
計算幾何学において、点と多角形の境界内（PIP）問題は、平面上の与えられた点が多角形の内側、外側、または境界上にあるかどうかを問う問題です。これは点位置特定問題の特殊なケースであり、コンピュータグラフィックス、コンピュータビジョン、地理情報システム（GIS）、モーションプランニング、コンピュータ支援設計（CAD）など、幾何学的データの処理を扱う分野で応用されています。
コンピュータグラフィックスにおけるこの問題の初期の記述では、1974年にはすでに2つの一般的なアプローチ（レイキャスティングと角度加算）が使用されていたことが示されている。[ 1 ]
コンピュータグラフィックスのベテランたちがこの問題の歴史をたどり、その解決策をいくつか試みた記事が、Ray Tracing Newsの号に掲載されている。[ 2 ]
点が単純な多角形の内側にあるか外側にあるかを判断する簡単な方法の一つは、その点から任意の固定方向へ伸びる光線が多角形の辺と交差する回数を調べることです。点が多角形の外側にある場合、光線は辺と偶数回交差します。点が多角形の内側にある場合は、辺と奇数回交差します。点が多角形の辺上にあるかどうかは、光線交差アルゴリズムの詳細によって異なります。
このアルゴリズムは、交差数アルゴリズムまたは偶奇ルールアルゴリズムとも呼ばれ、1962年には既に知られていました。[ 3 ]このアルゴリズムは、点が無限遠からプローブ点までの光線に沿って移動し、多角形の境界を複数回横断する場合、外側から内側へ、次に内側から外側へ、といったように交互に移動するという単純な観察に基づいています。結果として、2回の「境界横断」ごとに移動点は外側に出ます。この観察は、ジョルダン曲線定理を使用して数学的に証明できます。
有限精度演算を行うコンピュータで実装した場合、丸め誤差のために、点が境界に非常に近い位置にあると結果が不正確になる可能性があります。ビデオゲームやその他のエンターテイメント製品など、一部のアプリケーションでは、精度よりも速度が優先されることが多いため、これは大きな問題にはなりません。しかし、厳密に正しいコンピュータプログラムでは、数値許容誤差εを導入し、点Pが線Lからεの範囲内にあるかどうかをライン上でテストする必要があります。εの範囲内にある場合は、アルゴリズムを停止し、「Pは境界に非常に近い位置にあります」と報告する必要があります。
レイキャスティングアルゴリズムのほとんどの実装では、レイと多角形のすべての辺との交点を順番にチェックします。この場合、次の問題に対処する必要があります。レイが多角形の頂点を正確に通過する場合、2 つのセグメントの端点で交差します。例の最上部の頂点、または 4 と 5 の交点の間の頂点の場合は問題ありませんが、例の最右端の頂点の場合は、アルゴリズムが正しく動作するために 1 つの交点をカウントする必要があります。レイ上に位置する水平セグメントでも同様の問題が発生します。この問題は次のように解決されます。交点がテスト対象の多角形の辺の頂点である場合、その辺のもう一方の頂点がレイの下にある場合にのみ交点がカウントされます。これは実質的に、レイ上の頂点がレイのわずかに上にあると考えることと同じです。
繰り返しになりますが、光線が頂点を通過する場合、有限精度演算では数値的な問題が発生する可能性があります。同じ頂点に隣接する2つの辺について、光線との交点を単純に計算しても、両方の頂点が一致するとは限りません。多角形が頂点によって指定されている場合は、交点を実際に計算する前に、光線のy座標とテスト対象の多角形辺の端点をチェックすることで、この問題は解消されます。多角形の辺が他の種類のデータから計算される場合は、アルゴリズムの数値的な堅牢性を確保するために、別の工夫が必要となります。
点が多角形の内側にあるかどうかを判定する別の手法として、多角形に対する点の巻き数を計算する方法があります。巻き数がゼロでない場合、その点は多角形の内側にあります。このアルゴリズムは、非ゼロルールアルゴリズムとも呼ばれます。
巻き数を計算する1つの方法は、多角形の各辺がなす角度を合計することです。 [ 4 ]しかし、これにはコストのかかる逆三角関数が必要となるため、一般的にこのアルゴリズムはレイキャスティングアルゴリズムと比較してパフォーマンス効率が悪くなります（遅くなります）。幸いなことに、これらの逆三角関数を計算する必要はありません。結果であるすべての角度の合計は、0または（または倍数））だけであれば、テストポイントの周りを回転する際に多角形がどの象限を通過するかを追跡するだけで十分であり、[ 5 ]これにより、巻き数アルゴリズムは境界交差を数えるのと同等の速度になります。
2001 年に Dan Sunday によって、巻き数を計算する改良されたアルゴリズムが開発されました。[ 6 ]このアルゴリズムは、計算に角度や三角法を使用せず、上記のレイキャスティング アルゴリズムとまったく同じように機能します。Sunday のアルゴリズムは、チェック対象の点から無限に水平に発射されたレイを考慮することで機能します。そのレイが多角形の辺を横切るたびに、Juan Pineda の辺交差アルゴリズム (1988) [ 7 ]を使用して、交差が巻き数にどのように影響するかを決定します。Sunday の説明によると、辺が「上向き」のレイを横切る場合は巻き数が増加し、辺が「下向き」のレイを横切る場合は、巻き数が減少します。Sunday のアルゴリズムは非単純多角形に対して正しい答えを与えますが、境界交差アルゴリズムはこの場合失敗します。[ 6 ]
2019年に発表された修正多角形法は、凸型と凹型の両方に対応しており、形状の空間的寸法に応じて多角形のサイズ（線/面積/体積）を基本的に定義することに基づいています。その結果、既存の手法と比較して非常に高速かつ正確な方法となっています。[ 8 ]
同様の方法は、 SVGでさまざまな形状 (パス、ポリライン、ポリゴン、テキストなど) を色で塗りつぶす方法を定義するために使用されます。[ 9 ]塗りつぶしのアルゴリズムは、'fill-rule' 属性によって影響を受けます。値は または のいずれかになりますnonzero。evenoddたとえば、ペンタグラムでは、 の場合は中央に「穴」(背景が見える) がありevenodd、 の場合は穴がありませんnonzero。[ 10 ]
単純な多角形の場合、アルゴリズムは同じ結果を返します。しかし、複雑な多角形の場合、多角形が自身と交差する領域、つまり多角形の内側と外側が明確に定義されていない領域の点については、アルゴリズムが異なる結果を返す可能性があります。偶奇ルールを使用した解決策の 1 つは、交差チェックの前に (複雑な) 多角形を偶奇等価なより単純な多角形に変換することです。[ 11 ]ただし、これは計算コストが高くなります。多角形が自身と重なる場合でも正しい結果を返す高速な非ゼロ巻き数アルゴリズムを使用する方がコストが低くなります。
多角形内の点の問題は、一般的な反復幾何学クエリの設定で考えることができます。つまり、単一の多角形と一連のクエリ点が与えられた場合、各クエリ点に対する答えを迅速に見つける必要があります。明らかに、平面上の点位置特定のための一般的なアプローチのいずれも使用できます。一部の特殊な多角形については、より簡単な解法が利用可能です。
単調多角形、星形多角形、凸多角形、三角形については、より単純なアルゴリズムが可能である。
三角形の場合は、重心座標系、媒介変数方程式、または内積を使用して簡単に解くことができます。[ 12 ]内積法は、任意の凸多角形に自然に拡張されます。
