如何减少点数？

Question

我在路线上有一个有序的点列表（lat，long）。我有一个有序的停止列表（lat，long）。假设我有1000分和20站。我想将1000点减少到100点，这取决于哪些点与路线更相关。就像例如引发转弯的点一样。

我认为我可以做到这一点的一种方法是围绕停靠点集群，并可能随机选择点。但它对我来说似乎仍然不起作用。我已经在使用Douglas Peucker算法。除了这些任何想法？

Answer 1

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

给定一个初始复折线，该算法获得一个新的折线，该折线逼近具有指定误差容差e的原始折线。定义新折线的点是原始的子集。

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

该算法基于“除法&征服”类型的方法，因此具有预期的复杂性O(n*log(n))（尽管最坏的情况是O(n^2)）。

由于它是“最坏的优先”行为，生成的多段线包括定义尖角的“重要”点，但排除了容差为e内平坦部分的伪冗余点。