python - 如何减少集点？

Question

我有一个路线上点(纬度、经度)的有序列表。我有一个有序的站点列表(lat，long)。假设我有 1000 点和 20 个停靠点。我想将 1000 点减少到 100 点，具体取决于哪些点与路线更相关。例如引起转弯的点。

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

Answer 1

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

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

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

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

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