最小化多邊形頂點

Question

什麼是減少多邊形頂點數而不改變其顯示方式的好算法？

輸入：多邊形，表示爲點列表，方式太多verticies：例如鼠標的原始輸入。

輸出：一個多邊形，它的頂點很少，看上去很像原始樣式：例如可用於碰撞檢測的東西（不一定是凸面）。

編輯：對此的解決方案將類似於在圖上找到最適合的多段線。在我的算法書中稱爲分段最小二乘。

編輯2：道格拉斯皮克算法是我真正想要的。

Answer 1

編輯：哦，看，Simplifying Polygons

你提到碰撞檢測。你可以非常簡單地計算一個包圍它的邊界凸包。

如果您關心凹面區域，可以通過取多邊形的質心並選擇一個點來計算凹面。從起始點圍繞質心旋轉，找到要保留的每個頂點，並將其指定爲邊界殼體中的下一個頂點。算法的複雜性在於如何確定要保留哪些頂點，但我相信你已經想到了。您可以根據它們相對於質心的位置將所有頂點放入桶中。當一個桶獲得的頂點數超過任意數時，可以將其分割。然後將該桶中的頂點的平均值作爲邊界殼體中使用的頂點。或者，忘記水桶，並且當你在質心附近移動時，如果距離最後一個點超過給定距離，則只選擇一個點。

實際上，您可能只需使用多邊形中的所有頂點作爲「雲點」，然後計算其周圍的凹形外殼。我會尋找一個算法鏈接。最糟糕的情況將是一個完全凸多邊形。

另一種選擇是以邊界矩形開始。對於矩形上的每個頂點，找出從該點到多邊形的距離。對於最遠的頂點，將它分成兩個頂點並將它們移動一些。重複，直到滿足某個比例的頂點或區域。我不得不再仔細想想這個細節。

如果您關心實際上看起來相似的多邊形，即使在自相交多邊形的情況下，也需要使用另一種方法，但是因爲您詢問了碰撞檢測，所以聽起來不像那樣。

這個post有關於凸包部分的一些細節。

Answer 2

這裏有很多材料。只是谷歌的東西，如「目減少」，「網格簡化」，「網格優化」等