アルゴリズムハブのページをめくって、ポリゴン内のポイントのローカライズの問題を解決することに専念するトピックに出会いました：ポリゴンが与えられます（自己交差のない閉じたポリライン）。与えられたポイントAがこのポリゴン内にあるかどうかを判断する必要があります。 このトピックに関する最新のコメントの1つで 、そのような純粋に数学的な問題がアルゴリズムの理論にどのように関係するかについて戸惑いが表明されました。 Has-has、および最も即時。 ローカリゼーションの問題は、計算幾何学の古典的なタスクです（コンピューターグラフィックスと混同しないでください）。 ウォームアップとして、右側の写真を見て、ペアノ曲線（ソース[ 1 ]）のような多角形を示し、質問に答えてみるポリゴンが三角形または四角形の場合、単語の意味でのアルゴリズムはまったく発生しませんが、プログラムする必要のある3つまたは4つの式が発生することは明らかです。 ただし、ポリゴンの頂点の数が多い場合は、まったく異なるストーリーが始まります。 たとえば、100万または1億のピーク。 そのようなタスクは、すでにそれ自体が非常にアルゴリズム的なように見えます。 ナイーブアルゴリズム（特定のポイントからレイを開始し、ポリゴンの辺との交点の数をカウントする）は、ポリゴンnの頂点の数で線形です。 光線とポリゴンのすべての辺の交差を確認する必要があります。 したがって、問題が発生します、これをより速く行うことは可能ですか？ このステートメントのローカリゼーション問題を解決するための準線形アルゴリズムはありますか？ この質問に対する正しい答えはイエスです。問題は時間O（log 2 n）で解決できます。 一般的な場合の解決策の詳細は、多角形が凸である必要がない場合、すばらしい本[ 2 ]で見つけることができます。 以下では、バイナリサーチアルゴリズムを凸多角形の点の位置を特定する問題に適用する方法を検討します。
小さな教育プログラム
A、B、Cの3つのポイントを指定すると、ポイントAからポイントBを見ると、ポイントCは、視線の方向に対して右または左になります。 この質問は、ベクトルa = ABとb = BCのベクトル積、より正確には、単純な式z = a x b y -a y b xで計算されるこのような積のz座標の助けを借りて答えることができます。 z> 0の場合、必要な回転は左、z <0の場合、右です。
回転方向を計算するPythonコードは基本です（ポイントは長さ2のリストで表されます）。
def rotate(A,B,C): return (B[0]-A[0])*(C[1]-B[1])-(B[1]-A[1])*(C[0]-B[0])
このような便利な機能を使用すると、多くの善行を行うことができます。 たとえば、2つの指定されたセグメントABとCDが交差するかどうかを判断できますか？ ちなみに、これは計算ジオメトリのもう1つの基本的な操作であり、すぐに（一度だけ）必要になります。 考え方は単純です。2つのセグメントが交差するのは、一方のセグメントの端が他方のセグメントの反対側にあり、その逆の場合のみです。
点CとDがセグメント（ベクトル）ABに対して反対側にあるかどうかを確認するには、回転（A、B、C）および回転（A、B、D）の回転方向を調べる必要があります。 これらの式の符号が異なる場合、線ABはセグメントCDと交差します（内部ポイントで）。 2つの数値の符号は、積が負の場合にのみ異なります。 したがって、セグメントABとCDの交差の基準は、2つの式の回転（A、B、C）*回転（A、B、D）と回転（C、D、A）*回転（C、D、B）の否定です。 厳密な否定性を非肯定性に置き換えると、セグメントの終点で交差点をキャッチできます。 中間オプションが必要になります。つまり、1つの製品がゼロと比較して厳密に比較されず、2番目の製品が厳密に比較されます。
def intersect(A,B,C,D): return rotate(A,B,C)*rotate(A,B,D)<=0 and rotate(C,D,A)*rotate(C,D,B)<0
不等号のこのような奇妙な選択の理由は、この関数の将来の使用の特異性です（特に、ポイントA、B、Cは凸多角形の異なる頂点になり、ポイントD-ローカライズしようとしている点になります）。
バイナリ検索
次に、ローカライズに移ります。 n個の頂点と点Aで構成される凸多角形Pを考えます。Pの頂点には反時計回りの番号が付けられていると仮定されます（Pの周囲に沿ったトラバースの方向は正であると言います）。
アルゴリズムの考え方：ポリゴンP 0の最初の頂点を取得し、どのセグメント（角度）P i P 0 P i + 1ポイントAであるかを判断します。まず、AがセグメントP n-1 P 0 P 1に該当することを確認します。そうではないため、Aはポリゴンの外側にあることが保証されます。
コード：
def pointloc(P,A): n = len(P) if rotate(P[0],P[1],A)<0 or rotate(P[0],P[n-1],A)>0: return False
その後、すべてが古典的なバイナリ検索のようになります-p = 1、r = n-1（現在のセグメントの境界）を設定し、平均頂点q =（p + r）/ 2を計算します。AがベクトルP 0 P qに対する相対位置を参照してください左、rをqで置き換え、右の場合、pをqで置き換えます。
rp = 1になるまでこのプロセスを続けます。
p, r = 1, n-1 while rp>1: q = (p+r)/2 if rotate(P[0],P[q],A)<0: r = q else: p = q
ここで、セグメントP 0 AとP p P rが交差するかどうかを確認しますか？
それらが交差する場合、ポイントAは外側にあり、交差しない場合は内側にあります。
コード：
return not intersect(P[0],A,P[p],P[r])
それだけです...
まとめ
アルゴリズムの複雑さが従来のバイナリ検索アルゴリズムの複雑さ-O（log 2 n）と同じであることを確認するのは簡単です。 そして、このアルゴリズムが凸多角形に対してシャープ化されていなければ、すべてが素晴らしいでしょう。 公平に、私たちが調べたアルゴリズムはいくつかの非凸多角形でも動作しますが、非常に特殊なタイプです-そのような多角形では、ゼロ頂点から続くすべての対角線は多角形の内側になければなりません：
普遍的なローカリゼーションアルゴリズムは、バイナリ検索の原理でも機能します。バイナリ検索の内部でのみ、すべてが配置され、少し複雑になります。
ご清聴ありがとうございました！
PS：トピックの上部にある画像を使用したタスクは、任意のグラフィックエディターで簡単に解決できます。塗りつぶしツールを選択し、背景とは異なる色を選択し、画像の端（ポリゴンの外側）をクリックします。