algorithm - 如何简化样条曲线？

Question

在我正在进行的项目中，我遇到了一个有趣的算法挑战。我有一个坐标点的排序列表，指向街道两侧的建筑物，充分放大后，看起来像这样：

我想采用这种锯齿形并将其平滑以线性化底层街道。

我可以想到几个解决方案：

1. 使用六个左右点的滚动平均值计算质心，并使用它们。
2. 样条回归。

有没有更好或最好的方法来解决这个问题？（我正在使用 Python 3.5）

Answer 1

根据您的描述和评论，您正在寻找线条简化算法。

Ramer-Doublas算法（在评论中建议）很可能是这个家族中最知名的算法，但还有更多。

例如， Visvalingam 的算法通过删除变化最小的点来工作，该点由三角形的最小平方计算。这使得编码非常容易并且直观易懂。如果很难阅读研究论文，您可以阅读这篇简单的文章。

该系列中的其他算法有：

• 奥普海姆
• 郎
• 赵

阅读它们，了解它们试图缩小的内容并选择最适合您的内容。

Answer 2

Dali 的帖子正确地推测线简化算法对这项任务很有用。在发布这个问题之前，我实际上检查了一些这样的算法，但对它们不太满意，因为即使它们产生了我喜欢的简化几何，它们并没有直接解决我遇到的点在两边的问题功能，从不在中间。

因此，我使用了两步过程：

1. 我通过使用五个周围点的坐标的滚动平均值来计算折线的质心。这对平滑函数没有多大帮助，但它确实成功地将它们重新映射到街道中间。
2. 我将 Visvalingam 的算法应用于新的折线，并n=20指定了点（使用这个奇妙的实现）。

结果不是很完美，但已经足够好了：

感谢大家的帮助！