如何减少点集？

Question

我有一个路线上的点的有序列表（lat，long）。我有一个有序的车站清单（纬度，长距离）。假设我有1000分和20站。我想把1000点减少到100点左右，这取决于哪些点与路线更相关。例如诱导转弯的点。在

我想我能做到这一点的一个方法是聚集在站点周围，随机选择点。但对我来说，这似乎还是不太有效。我已经在用道格拉斯-派克算法了。除了这些还有什么想法吗？在

Answer 1

您可以使用Ramer–Douglas–Peucker算法来简化折线。在

在给定初始复折线的情况下，该算法得到一条新的折线，该折线具有指定的误差容限e。定义新多段线的点是原始多段线的子集。在

该算法是增量的，从多段线的端点开始，在每次迭代中添加距离当前近似值最远的点。当所有剩余点在当前近似值的垂直距离e内时，算法收敛。在

该算法基于“分而治之”类型的方法，因此预期复杂度为O(n*log(n))（尽管最坏的情况是O(n^2)）。在

由于它的“最差优先”行为，生成的多段线包含定义锐角的“重要”点，同时排除公差范围内沿平坦截面的伪冗余点e。在