綱要繪製算法

Question

我一直在考慮我的妻子這個任務，所以它的當務之急:-)

我點的集合（實際上北進&東進，但它其實並不重要）。我想採取這些觀點並創建一組代表輪廓的矢量，以便我可以在Google地球上進行繪圖。

所以，像這樣：

#      # 
      #    #  # 
#    # # 
     # # 

      # 

還會送：

#-----------------------#-- 
/       \ --# 
#     #------------/ 
\-----#  /
     \ /
      # 

我想出了一個可能的解決辦法，是計算向量每個點之間，並丟棄每個由重疊的矢量另一個矢量。我還沒有實現（不知道如何），但我想知道是否有其他方法。

該算法只需要運行幾次，因此如果每次運行需要一個小時以及RAM的演出，這不是問題。

Answer 1

候選人多邊形的配方

好像你要尋找的多邊形，使得

• 所有的頂點是在你點設置
• 它包含了你的觀點的每一個點設置爲

這定義了一組關於您的點集合的候選多邊形。

凸殼？

一個目標函數可能是「在這些多邊形中，選擇頂點數最少的那個。」這將是你的點集的凸包。其他答案解決了這種方法，所以我不會再多說這些。

更多...

但這不是您可以選擇的唯一目標函數。例如，您可以在之間進行折衷，使其具有較少的頂點，總面積較小，並且在頂點處具有較不尖銳的角度。我不知道任何現有的命名算法，但它絕對是一個有趣的。

一種方法可以是先找到凸包，然後將邊緣「拉入」邊緣到附加頂點的成本超過總面積較少的位置的內部頂點。

例如，這樣的：

將成爲這一點，通過沿頂部的邊緣拉：

這第二個多邊形可能是一個更 「自然」適合點集，即使它是而不是點集的凸包。

Answer 2

你可能正在尋找凸點的凸點;有一個variety of algorithms發現。

Answer 3

Here是從code.google.com

Here找出凸包庫是同樣的事情GitHub的庫，但使用賈維斯比賽凸殼算法。

希望他們幫忙！