ポイントがポリゴン内にあるかどうかを検出するには、ポイントから無限に線を投影し、それが交差するポリゴンの頂点の数を確認します...簡単です。私の問題は、レイがポイントの1つでポリゴンと交差する場合、それは2つのセグメントと交差するものとしてカウントされ、ポリゴンの外側と見なされることです。光線がポリゴンのポイントと交差するときにセグメントの 1 つだけをカウントするように関数を変更しましたが、線が外側にあるときにポイントと交差する場合もあります。この画像を例に取ります。
左上のポイントが「無限」であると仮定し、他のポイントのいずれかにレイをキャストすると、両方がポリゴンのポイントで交差し、1 つが内側にある場合でも、同じ数の頂点と交差していると見なされます。そして1つは外にあります。
それを補う方法はありますか、それとも、それらのフリンジケースがポップアップしないと想定する必要がありますか?
光線が頂点で正確に側面を横切る場合、他の頂点が光線の上にある場合にのみ、その側面をカウントします。それはあなたのコーナーケースを修正します。
例えば、あなたが投稿した写真では、下の光線が左上の頂点で正方形の 2 つの辺を横切っていますが、一方の辺が光線の上にあり、もう一方の辺が光線の下にあるため、1 が寄与し、ターゲット ポイントが内側にあることがわかります。上の光線は右上の頂点で 2 つの側面を横切り、両側は光線の下にあるため、カウントに 0 が寄与し、ターゲット ポイントは外側にあることがわかります。
更新：
一般的に特異なケースを処理するためのテクニックを説明する記事を読んだことを思い出しました。興味があれば私の他の回答を読んでください。
別の方向に光線を送ります。
n+1さまざまな方向を試すと (nポリゴン ポイントの数)、そのうちの 1 つが確実にどの頂点も通過しません。
これにより、コーナーケースを考慮するよりもコードが簡素化されます。
最悪の場合O(n)*CheckComplexity(n)どちらになりそうかO(n^2)。それが受け入れられない場合は、ポイントからそれらへの方向ですべての頂点を並べ替えて、ある間隔の中央を選択することができます。これにより が得られO(n*log n)ます。
私の最初の答えはこの単純な問題のトリックを行うはずですが、この種の特殊なケースを処理するための一般的な手法が存在することを言及せずにはいられません。
この記事では、この種の問題に一般的に対処するための手法について説明します。そして、彼らが提供する最初の例の 1 つは、たまたまあなたが尋ねたアルゴリズムです!
アイデアは、記号摂動を計算するために、自動微分別名二重数を適用することです。
ちなみに、同じテクニックを使用して、プログラムで 0/0 を特別なケースとして処理することを回避することもできます!
これは、私が最初にこれを学んだブログ投稿です。これは、この手法の素晴らしい背景を示しており、著者は自動微分 (AD) について多くのブログを書いています。
見た目にも関わらず、AD は特に演算子のオーバーロードを適切にサポートする言語 (例: C++、Haskell、Python ...) では非常に実用的な手法であり、私はそれを「実生活」(C++ の産業用アプリケーション) で使用しました。