本文算法来自
https://skemman.is/bitstream/1946/15343/3/SS_MSthesis.pdf
作者对比了几个算法,主要突出的是 Largest-Triangle-Three-Buckets算法,我个人翻译为最大三点【三角】面积特征。同样作者给出了代码,我也找到了C#代码,适当改了下。主要是说说算法
主要说说几点:
1:算法的主要源于Visvalingam-Whyatt,也就是基于点与前后点形成的面积是否大于阈值,小于阈值则删除点。
简单说一下Visvalingam-Whyatt,
①当节点从首位开始,连接前两个(因为是首位,没有后面),紧接着是第二点,2点连接首点,连接三点,依次向下,末位点参考首点
②当形成全部的三角后删除面积最小的结点,并由移至附近两点,重新形成三角形【或者从头重新连接~~】
③重复①,确定所有三角形的面积都小于阈值
2:LTTB是可以控制返回点的数量(亮点!!)
基本操作:点集排除首尾点后的 数量与输出点的数量(同样减去首尾点,也就是-2)的比值,然后每比值的一个点集,默认第一个点是独立的一个点集,最后一个点也是独立的一个点集
理论上第二步是选择点与下两个点集中的点所形成的最大的三角形的面积的点,实际上,算法中是 点1确定,点集3通过计算按照第几个点集,然后计算这个点集中所有的点的平均值(X,Y两个值的平均值)所创造的点,不一定存在。
这样子就可以确定点1,点集2,然后不断筛选点集2的点,经行计算面积来比较大小。最后 依次重复上述步骤到下一个点,直至结束。
同样,不用平均值,也可以枚举点集3与点集2的点与点1 所形成的每个三角形的面积。论文中 作者指出 差不多的效果~~(水啊