3

网上有很多关于普通线路简化的资料，

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 千次，而是希望它逐步处理我的集合，交点无关紧要，重点只是减少具有最小视觉影响的数据集的大小是否有一些聪明的方法来处理这个问题？

4

1 回答 1

0

如果交点无关紧要并且您所需要的只是视觉相似性（大概在光栅化之后并且ε接近像素大小），那么只需丢弃足够接近缩减链的点就可以完成这项工作。

在伪代码中：

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

这种方法保证了什么：

  • 缩减链中每个段的长度至少为ε
  • 链之间的豪斯多夫距离最多为ε

它不能保证：

  • 没有自相交
  • 任何一种最优性（可能有一条不同的链，它的 Hausdorff 距离更近，点数更小）
于 2017-08-09T21:17:51.373 回答