確定點是否在多邊形內

Question

目前我正在使用光線投射算法，但它有一些侷限性，例如光線通過頂點時無法確定其是否在內部。

我可以使用哪種算法，它總能用於任何種類的多邊形？

Answer 1

您可以根據多邊形本身選擇光線方向，使其不會穿過任何頂點。

對於整數座標它就足以沿着(1,0.5/deltaX)，其中deltaX是多邊形頂點的x座標之間的最大差值投下射線。射線上的整數座標的第一個點將成爲它的開始。下一個將有多邊形之外的x座標startX+2*deltaX，並且不能是其頂點。通過精確的算術，您可以穩健地確定點內外的點。

對於浮點數精確算術是一個問題，所以您希望射線儘可能遠離多邊形頂點。爲此，您可以計算每個多邊形頂點的方向，並按頂點排序。然後選擇此排序序列中相鄰頂點之間的最大差異，並在它們之間投射光線。