algorithm - ジオフェンスを定義し、ポイントがその内側/外側にあるかどうかを確認するアルゴリズム

Question

ジオフェンスを作成し、デバイスがフェンスに出入りしているかどうかを確認できるアルゴリズムを探しています。多角形アルゴリズム (レイ キャスティングと巻き数) の点を見てきましたが、円や不規則な形状にも適用できるアルゴリズムはありますか? 重要な制約は時間効率です。

ありがとうございました。

Answer 1

Here is the c code algorithm that is simple to understand:

http://alienryderflex.com/polygon/

Answer 2

円はかなり簡単です (少なくとも局所的に平らな表面を想定している場合) - 点からの絶対距離だけです。

速度が必要な場合の通常の方法は、最初に円をチェックするカスケード、またはポイントの周りの正方形、次に凸多角形、必要に応じてより詳細な多角形をチェックするカスケードです。

多角形でない場合、不規則な形状をどのように定義していますか?

ps参照点が2D整数座標の凸多角形の内側にあるかどうかをテストする方法は?

Answer 3

quadtrees、空間インデックス、quadkeys、および r-trees を見てください。