「通過頂點射線」特殊情況下檢測多邊形中的點

Question

要檢測一個點是否在多邊形中，可以投射一條從點到無窮的直線，並查看它與多邊形相交的頂點數量...簡單足夠。我的問題是，如果射線與其中一個點上的多邊形相交，那麼它會被計算爲相交兩個線段，並在多邊形之外進行考慮。當射線與多邊形的某一點相交時，我改變了函數使其只能計算其中一個分段，但有些情況下線條可能與點相交，同時仍然位於外部。就拿這個圖像爲例：

如果假設在左上角的一點是「無窮大」，投出光線要麼其他點，既相交於多邊形的一個點，並且即使一個在裏面，一個在外面，也會算作相同數量的頂點。

有沒有辦法彌補這一點，還是我只是假設那些邊緣案例不會彈出？

Answer 1

如果光線正好穿過頂點的一側，則只有在另一側頂點在光線上方的情況下計算該側。這將解決你的角落案件。

例如，在您張貼的圖片中，較低的光線穿過廣場左上角頂點的兩側，但一側位於光線之上，另一側位於光線之上，另一側位於光線之上，因此它貢獻1並找到目標點在裏面。上面的光線在右上角交叉兩邊，兩邊都在光線下面，所以它們對計數貢獻0，並且目標點被發現在外面。

更新：

我記得讀它描述了一種技術，用於處理與一般的奇異情況的文章。如果感興趣，請閱讀我的其他答案。

Answer 2

雖然我的第一個答案應該爲這個簡單的問題做訣竅，但我不禁要提到存在處理這些特殊情況的一般技巧。

This article描述了用於總體處理這些問題的技術。他們提供的第一個例子恰好是你問的算法！

這個想法是應用Automatic differentiation又名Dual numbers計算符號擾動。

順便說一句，同樣的技術也可以用來避免處理0/0作爲程序中的特殊情況！

Here是我最初從中學到的博客文章，它給了這個技術一些很好的背景，作者博客了很多關於自動分化（AD）的內容。儘管外觀AD是一種非常實用的技術，特別是在對運算符重載（例如：C++，Haskell，Python ...）有良好支持的語言中，並且我在「現實生活」（C++中的工業應用程序）中使用了它。

Answer 3

向另一個方向發射光線。

如果您嘗試n+1不同的方向（n是多邊形點的數量），其中一個肯定不會穿過任何頂點。

與考慮角落案例相比，這將簡化代碼。

最壞情況變成O(n)*CheckComplexity(n)這很可能是O(n^2)。如果不可接受，您可以按照從點到它們的方向對所有頂點進行排序，並選擇某個間隔的中間值。這會給O(n*log n)。