python - 如何减少点集？

Question

我有一个路线上的点（纬度，经度）的有序列表。我有一个有序的站点列表（纬度，经度）。假设我有 1000 个点和 20 个停止点。我想根据哪些点与路线更相关，将 1000 个点减少到 100 个左右。例如引起转弯的点。

我认为我可以做到这一点的一种方法是围绕停靠点聚集并可能随机选择点。但这对我来说似乎仍然无效。我已经在使用 Douglas Peucker 算法了。除了这些还有什么想法吗？

Answer 1

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

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

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

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

由于它的“最坏优先”行为，生成的折线包括定义尖角的“重要”点，同时排除公差内平坦部分的伪冗余点e。