algorithm - 如何简化样条曲线？

Question

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

我想将这条锯齿形曲线平滑化，以线性化底层街道。

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

1. 使用大约六个点的滚动平均值计算质心，并使用它们。
2. Spline regression .

有没有更好或最好的方法来解决这个问题？ (我使用的是 Python 3.5)

Answer 1

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

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

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

这个家族中的其他算法是:

• Opheim
• Lang
• Zhao

了解他们，了解他们试图缩小什么并选择最适合您的。