如何找到一個點是否在使用球拍的多邊形內

Question

我正在開發一個項目，在特定的緯度和經度座標下輸出該點所在的鄰域。我有經緯度座標在一個城市內的幾個街區的邊界。我必須從文件中讀取鄰域數據，並從文件中讀取測試點。我正在使用Racket編程語言。

到目前爲止，我已經能夠讀取文件併爲每個鄰域創建一個點列表，現在我被卡住了。我想爲每個鄰域創建一個多邊形，然後有一個方法來檢查點是否位於該多邊形內。但是，我無法弄清楚如何使用Racket來做到這一點。

任何人都可以幫助我找出如何解決，如果一個點是在多邊形內，或者更好的方法來解決問題？

Answer 1

我現在不會發布任何代碼，因爲我不想解決作業/任務。不過，我會發布一些提示。

看看下面的圖片：

我們怎樣才能知道C是邊緣OA和OB和D是外部之間？它很簡單：我們比較一些角度：如果OC和OA之間的角度小於OB和OA之間的角度，那麼C明顯更接近於OA，而不是OB。

現在，我們如何才能知道只有一些向量的角度？我們可以使用單調的餘弦：它隨着參數的增加而減小。因此，OC和OA之間的角度的餘弦大於OB和OA之間的角度的餘弦，這又大於OD和OA之間的角度的餘弦。

下一步是弄清楚如何計算餘弦。矢量點產品有助於：它的值是角度乘積的餘弦值，大於操作數長度的乘積。那就是：

cos(OC; OA) = dotproduct(OC; OA)/(length(OA) * length(OC)) 

在2D的dotproduct很簡單：

dotproduct(OC; OA) = (C.x - O.x) * (A.x - O.x) + (C.x - O.x) * (A.x - O.x) 

結合上述所有你應該有一個簡單的測試，以檢查你的觀點是否在同樣的情況C或D ：比上一個邊更靠近一個邊。

現在，您必須對多邊形的每個邊重複此操作，然後完成。如果測試是謂詞，則可以使用fold執行此操作。

注意：這隻適用於多邊形是凸的。對於凹多邊形，您需要添加更多測試。

秒注意：在圖中，會發生什麼，如果D或C或者兩者都是OA線以下？想想這個，並檢查它是否意味着對上述fold方法進行了一些更改。

後記：在幾周內，我會發佈一個完整的代碼，假設任務結束。另外，那時我會在上面的註釋中回答這個問題。