简化路径的算法

Question

给定一个路径,我想优化它,以便可以删除直线上的所有顶点.

例如:路径:

*******
*      *
*        *
***********

可以优化为:

*-----*
|      \
|        \
*---------*

但是我希望控制斜率的偏差,这样它就不必完全在斜率上.

什么样的算法可以做到这一点？

谢谢

Answer 1

我相信你可以通过简单的迭代步行穿过路径上的点来做到这一点.在每个点跟踪您遇到的最后三个点.如果它们中的所有三个都是共线的,则从路径中移除中间点,因为从第一个节点到第三个节点的直线路径将通过中间节点.你可以控制有多少偏差,因为有一个术语可以控制点的共线距离.

如果您将点存储在数据结构(如双向链表)中,则可以在O(n)时间内通过简单的数据传递来实现.

希望这可以帮助!