增量式线条简化

Question

互联网上有很多关于普通线路简化的信息，

https://www.jasondavies.com/simplify/

https://bost.ocks.org/mike/simplify/

http://geomalgorithms.com/a16-_decimate-1.html

http://mourner.github.io/simplify-js/

即当简化点是预先已知的时。Visvalingam算法，Douglas-Peucker算法，但是如果公差参数是固定的，并且点是未知的，该怎么办？我有很多点，我不想运行N* Log(N)算法M千次，相反，我希望它增量地处理我的集合，交集并不重要，重点只是减少数据集的大小，视觉影响最小。有没有什么聪明的方法来处理这个问题？

Answer 1

如果交集无关紧要，你所需要的是视觉相似性(假设在光栅化之后，ε接近像素大小)，那么简单地丢弃足够接近简化链的点就可以了。

在伪代码中：

Let C be the original chain
Let R be the reduced chain (initially empty)

Add the first point of C to R
For every subsequent point p of C:
    If distance(p, the last point of R) >= ε:
        Add p to R

这种方法所保证的：

减少链中每一段的长度将最少为ε

• The，链之间的距离将至多为ε

它不能保证的是：

缺少self-intersections

• Any类型的最优性(可能存在一个不同的链，它既在豪斯道夫距离上更接近，在点数上也更少)