道格拉斯-普克折线压缩/抽稀算法 实现

道格拉斯-普克算法,根据wiki,全名“Ramer–Douglas–Peucker algorithm”   是一种采用迭代式方法对折线进行压缩的方法,选取一些特征点代表原折线,并且保证原折线的点距离压缩后的折线不超过一定的范围阈值\(d\)。

即已知折线\(l_{old}= (X_1,X_2,…,X_n)\),求索引序列\(\{1,?,…,?,n\}\),使得原点集到压缩后的新折线\(l_{new}=(X_1,X_?,…,X_?,X_n)\)的距离小于\(d\)。算法思路是:

1)初始连接\(X_1X_n\),计算\(X_2,…,X_{n-1}\)到\(X_1X_n\)的距离,并将最大距离值\(d_i\)与\(d\)比较,并且记录最大距离对应的节点\(X_i\)。如果\(d_i<d\);算法终止。

2)如果\(d_i>=d\),则将\(X_1X_n\)分为\(X_1X_i\)与\(X_iX_n\)两部分,对于每一部分,分别执行步骤1,注意此时步骤一对应的起终点应该分别为\( [1,i] ,[i,n] \)。

3)所有分支全部终止之后,记录到的\(\{(X_i)\} \)序列就是所求的节点序列。

插一副wiki上面的图片,直观的记录了算法处理流程。

我实现的C++版本的道格拉斯-普克算法如下

其中,向量的 重载运算符,模长,单位向量化算法略去实现。

发表评论

电子邮件地址不会被公开。