我想製作一張地圖，用戶可以勾畫出他們想要的任何形狀。但我遇到了一個問題，用戶可以選擇使多邊形的線交叉並排除我想包含的區域的點。如何對Google地圖多邊形中的點進行排序，以便線條不會交叉？
要看看我說的去this page並採取以下步驟：
你SH烏爾德看到這樣的事情：
alt text http://polygon.abemiester.com/1.bmp
有沒有一種簡單的方法來解決這個問題，還是我基本上這裏處理一個「貨郎擔」類的情況？所有的邏輯都是在JavaScript中完成的，所以如果你想看看我是如何做到這一點的話，請隨時「查看源代碼」。
凸包可能包含用戶希望排除的區域。這是另一種解決這個問題的方法，可能會帶來更令人滿意的結果檢查每一行以查看哪些行越過（有很多方法可以做到這一點）。然後顛倒這兩行之間出現的點的子序列。例如，假設給出A-B-C-D-E-F-A點，其中B-C和E-F交叉。您可以通過逆轉導致A-B-E-D-C-F-A的子序列C..E使其不交叉。
無論如何都要嘗試。
我在過去解決了類似的問題，遇到了Jeffrey提到的關於不知道用戶期望的形狀的問題。我最終通過要求用戶選擇他們希望新點之間的兩點來解決該問題。它需要更多的點擊（3對1），但用戶完全控制他們想要的形狀。如果您有興趣，我可能仍然會在某個地方使用代碼（這是Google地圖的代碼）。
它不是凸包。
想象一下，如果您在靠近這兩條線的「林菲爾德橡樹」處停留，一個凸包可以跳過這個並在「國際」和「82」之間畫出一條直線
你要做的是確定每個新點是否在由現有點形成的多邊形內 - 如果它是你需要打破最近的多邊形邊，並在該邊上插入新的點。 查看http://softsurfer.com/Archive/algorithm_0103/algorithm_0103.htm多邊形測試中的點。
