- A+
本文算法来自
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 所形成的每个三角形的面积。论文中 作者指出 差不多的效果~~（水啊?）
最后 视觉效果上真的不错！ 不过论文中说，当波峰值较大时，也有可能表现不好~
代码实现的步骤：
零 初始点1为首点
① 计算比值（除去首尾，每个点集的数量）
② 计算点集3中点的平均点
③ 枚举点集2与点集3的平均和点1形成最大的三角形面积，并加入输出点集
④ 点1设置位点集2的最大面积点，并进入下一次循环步骤②
截图
代码 来自https://github.com/cgddrd/CSharp-LargestTriangleThreeBuckets（略微改造）
public static List<Point> Get(List<Point> data, int threshold) { int dataLength = data.Count; if (threshold >= dataLength || threshold == 0) return data; // Nothing to do List<Point> sampled = new List<Point> (threshold); // 点集大小，排除首尾点，阈值减2， double every = (double)(dataLength - 2) / (threshold - 2); int a = 0; Point maxAreaPoint = new Point(); int nextA = 0; sampled.Add(data[a]); //默认添加首点 for (int i = 0; i < threshold - 2; i++) { // 假设第三个点是此前区间的平均值，大概率不存在，凭空捏造一个? double avgX = 0; double avgY = 0; int avgRangeStart = (int)(((i + 1) * every) + 1); int avgRangeEnd = (int)(((i + 2) * every) + 1); avgRangeEnd = avgRangeEnd < dataLength ? avgRangeEnd : dataLength; int avgRangeLength = avgRangeEnd - avgRangeStart; for (; avgRangeStart < avgRangeEnd; avgRangeStart++) { avgX += data[avgRangeStart].X; // * 1 enforces Number (value may be Date) avgY += data[avgRangeStart].Y; } avgX /= avgRangeLength; avgY /= avgRangeLength; // +1是为了排除当前点 int rangeOffs = (int)(Math.Floor((i + 0) * every) + 1); int rangeTo = (int)(Math.Floor((i + 1) * every) + 1); // Point a double pointAx = data[a].X; // enforce Number (value may be Date) double pointAy = data[a].Y; double maxArea = -1; for (; rangeOffs < rangeTo; rangeOffs++) { //计算面积 点1 点集2 虚拟的点3~~ double area = Math.Abs((pointAx - avgX) * (data[rangeOffs].Y - pointAy) - (pointAx - data[rangeOffs].X) * (avgY - pointAy) ) * 0.5; if (area > maxArea) { maxArea = area; maxAreaPoint = data[rangeOffs]; nextA = rangeOffs; //设置下一个点 } } sampled.Add(maxAreaPoint); a = nextA; // 进入下一次循环 } sampled.Add(data[dataLength - 1]); //默认添加尾点 return sampled; }
