圖形簡化算法建議需要

Question

我有一個需要採取一個二維圖形的n個點，並減少它的r點（其中r是一個小於n的具體數字）。例如，我可能有兩個數據集，總點數略有不同，例如1021和1001，我想強制這兩個數據集有1000個點。我知道一些簡化算法：Lang Simplification和Douglas-Peucker。我在以前的項目中使用過Lang，但需求略有不同。

我找了該算法的具體性能爲：

1）必須保留線的形狀

2）必須讓我減少數據集點的具體數量

3）相對較快

這篇文章討論了不同算法的優點。我將發佈第二條消息，提供有關Java或Groovy實現方面的建議（爲什麼重新發明輪子）。

我很關心上面的要求2。我在這些算法中不夠專業，無法知道我是否可以決定輸出點的確切數量。我使用過的Lang的實現將lookAhead，tolerance和Points數組作爲輸入，所以我不知道如何規定輸出中的點數。這是我目前需求的關鍵要求。也許這是由於我們使用了Lang的具體實現，但是我沒有在網絡上看到關於Lang的大量信息。或者，我們可以使用Douglas-Peucker，但我不確定輸出中的點數是否可以指定。

我應該加我不是這些類型的算法或任何類型的數學知識的專家，所以我正在尋找凡人類型的建議:)我如何滿足上述要求1和2？我會犧牲正確的解決方案的性能。

Answer 1

你可以在Douglas-Peucker簡化版here和here上找到我的C++實現和文章。我還提供了Douglas-Peucker簡化的修改版本，允許您指定生成的簡化線的點數。它使用'彼得泰勒'提到的優先隊列。雖然它的速度要慢很多，所以我不知道它是否會滿足'是比較快的'的要求。

我正在計劃爲Lang簡化（和其他幾個）提供實現。目前我沒有看到任何簡單的方法如何調整朗減少到固定點數。如果您的 可以滿足一個不太嚴格的要求：'必須允許我將數據集縮小到大約點數'，那麼您可以使用迭代方法。猜測前瞻的初始值：點數/期望點數。然後緩慢增加向前的距離，直到您大致達到所需的點數。

我希望這會有所幫助。

p.s .:我只記得一些事情，你也可以試試Visvalingam-Whyatt算法。總之： -compute與它直接鄰居每個點的三角形區域 -sort這些領域 -remove面積最小 點-update其鄰國的區域 -resort - 繼續直到N個點，仍

Answer 2

我認爲你可以非常直接地適應Douglas-Pücker。調整遞歸算法，以便不會生成列表，而是生成一個鏡像遞歸調用結構的樹。樹的根將是單線逼近P0-Pn;下一級將表示兩行近似值P0-Pm-Pn，其中Pm是P0和Pn之間距離P0-Pn最遠的點;下一級（如果已滿）將表示四行近似值等。然後，您可以根據深度或根據插入點與父行的距離來修剪樹。

編輯：事實上，如果你採取後一種方法，你不需要建立一棵樹。而是填充優先級隊列，其中的優先級由插入點與父行的距離給出。然後，當您完成隊列時，會告訴您要刪除哪些點（或根據優先級的順序保留）。