1. 概要

このチュートリアルでは、ポイントがポリゴンの内側にあるか外側にあるかを判断する方法を学習します。

2. ポイントとポリゴン

2.1. ジオフェンスの問題

ポイントが特定のポリゴンの内側にあるか外側にあるかを識別する問題は、地理空間分析のジオフェンスの典型的な問題です。 自動侵入者検出やフリート管理などの多くの実際のアプリケーションでは、目的のサービスを提供するためにソリューションが必要になるため、この問題は一般的です。

ジオフェンスでは、ポリゴンとポイントを事前に識別する必要があります。 次に、ポイントがポリゴンの外側にあるかどうかを判断します。

または、逆に、それがその中にあるかどうか：

2.2. 単純なポリゴンのジオフェンス

非常に単純なポリゴンの場合、ポリゴンの分析的な定義に基づいて、いくつかの決定ルールを特定できる可能性があります。

たとえば、上の画像で表されているポリゴンの場合、ポイントの座標がである場合、ポイントはその周囲の内側にあります。

ルールベースのソリューションを見つけることができれば、アルゴリズムは必要ありません。 ポリゴンがもっと複雑な場合、問題はそれほど簡単には解決できません：

その場合、特定のポイントが形状の内側にあるか外側にあるかを判別できる手順が必要です。 この手順は、次に、周囲の分析式の知識を必要とせずに機能するはずですが、頂点の座標のみが機能します。

3. ジオフェンスのアルゴリズム

このアルゴリズムの適用を正当化するために、最初に、ポイントがポリゴンが存在する一般的な領域にあるかどうかを事前にテストします。 ポイントの座標を、ポリゴンを含む最小の長方形の座標と比較することで、これを効率的に行うことができます：

このテストでは、長方形の境界を。として決定するだけです。 次に、ポイントがその内側にあるかどうかを確認します。 そうでない場合は、ポイントをポリゴンの外部と見なします。 それ以外の場合は、さらに進みます。

3.1. キャスティングレイ

偶数奇数ルールアルゴリズムは、レイキャスティングアルゴリズムとも呼ばれ、ポリゴンとポイントの相対的な位置を決定するのに適しています。 このアルゴリズムは、ポイントがポリゴンの内側にある場合、そのポイントから出発する光線が周囲に奇数回出会うという考慮に基づいています。

代わりに、ポイントがポリゴンの外側にある場合、すべての光線が偶数回周囲に到達します：

この考慮事項は、ポイントとポリゴンの相対位置に関係なく有効です。 ただし、ポリゴンの複雑さやキャストされる光線の方向に関係なく有効です。

3.2. 手順の簡素化

ただし、実際には、アルゴリズムは実際のランダムな光線を投影しません。 これは、上記の定式化では、自由度が多すぎるため、そのアルゴリズムの文字通りの実装が計算上非効率になるためです。

その後、問題の自由度を減らすために、点から水平光線を投影することを選択します。 上記の手順はすべての可能な光線に対して有効であるため、これを行うことができます。 次に、軸に平行な水平光線とポリゴンの各セグメントとの間の交差の数を計算します。

このコンテキストでは、ポリゴンは、頂点の座標を表す2タプルの順序付けられた循環シーケンスに対応するパスです。 アルゴリズムは、頂点のすべての連続するペアを反復処理し、それらがすべて考慮されると終了します。

次に、頂点の各ペアについて、それらの座標が同時にポイントの座標の上にあるか下にあるかを検討します。 そうである場合、セグメントがポイントからキャストされた水平光線と交差していないことを意味します。

次に、ポイントの座標を、現在のセグメントに属するポイントの座標と比較します。その座標はに対応します。 次に、かどうか、あるいは、代わりに、しかし一貫して、をチェックします。

この式を使用して、2つの頂点と：に関連して計算できます。

最後に、最後の2つのポイントの条件が両方とも同時に満たされる場合、ブール変数の値を内部で反転するか、カウンターnumberOfIntersectionsをインクリメントします。

inside？の値は、終了条件に達すると返されます。 代わりにカウンターを使用する場合、見つかった交差の数がである場合、それはそのポイントをポリゴンの内側として宣言します。 それ以外の場合、ポイントはポリゴンの外側にあります。

3.3. フローチャート

これは、アルゴリズムのフローチャート表現です。

falseに初期化するBoolean変数inside？。、は、この特定の実装におけるアルゴリズムの出力です。

アルゴリズムのメインループは、座標を含むタプルとして定義された、ポリゴン内のすべての連続する頂点のペアを繰り返し処理します。

次に、2つの条件に従って、現在の頂点のペアを結合するセグメントが、ポイントからキャストされた水平光線と交差するかどうかを決定します。 両方が同時に満たされる場合、交差点が存在します。その場合、の値を内側に反転しますか？。 どちらかが満たされない場合は、シーケンス内の次の頂点のペアにスキップします。

最初の条件はそれです。 つまり、2つの頂点は、ポイントの光線から発生する同じ半平面上に配置されていません。

これが当てはまる場合は、2番目の条件もテストします。 2番目の条件は、ポイントの水平位置がポイントの位置の右側にあることです。 この特定の実装では、ポイントの左側に光線をキャストすることを選択しました。 代わりにの右側にキャストする場合は、との予想される相対位置を逆にして、がの左側にあるかどうかをテストします。

この2番目の条件も最初の条件と一緒に満たされる場合は、の値をinside？に反転します。 終了条件は、頂点のシーケンシャルペアを含む循環パスの枯渇です。 到達すると、 inside？は、ポイントがポリゴンの内側にある場合は値 True を保持し、それ以外の場合はFalseを保持します。

4. 実用的なアプリケーション

ポリゴンとポイントの相対位置を決定する問題は、地理空間分析に実際に適用できることを説明しました。 先に引用した2つのコンテキストは、自動手段による侵入者の識別と、海事コンテキストでの艦隊または貨物の管理です。 これが事実である理由をここで見てみましょう。

4.1. 物理的な脅威からの保護

最初のケースに関しては、法律は伝統的に不法侵入を、私有財産または安全地帯のいずれかである、立ち入りを制限している境界領域への不正アクセスの犯罪として定義しています。 歴史的に、この問題は主に国内の家庭に対する強盗の防止に関係しています。

ただし、現代では、主要なセキュリティの脅威は、重要なインフラストラクチャに対する無人テロ攻撃のリスクに関連しています。 特に、国際航空交通用のターミナルへの無人航空機の不正アクセスに関連しています：

このリスクを軽減する方法は、UAVがインフラストラクチャの境界内にあるかどうかを識別するドローンを早期に検出するためのシステムを開発および運用することです。 このシステムは、ここで説明したものと同様のアルゴリズムを使用します。

4.2. 自律型船舶の管理

別のアプリケーションは、自律型船舶の活動のガイダンスと監視に関するものです。 実際、国際海事法は、船舶が管轄の海事当局による許可を受けない限り、州の海岸線近くに位置する地域へのアクセスは禁止されていると決定しています。

したがって、船を運転するシステム を開発したい場合は、不注意で制限区域に入るのを防ぐ必要があります。 残念ながら、世界の一部の地域の海岸線は非常に複雑です。

結果として、船舶が海の制限された部分の中にあるかどうかを判断するのはそれほど簡単ではありません。

この問題の解決策は、制限区域の周囲を区切ることができる信号ブイを水上に配備することです。 それらに関連して、次にアルゴリズムを適用し、船と制限された周囲長の相対位置を決定できます。

5. 結論

この記事では、ポイントがポリゴンの内側にあるかどうかを判断する方法を学習しました。