去除折线图中多余的点

Question

去除折线图中多余的点

mathcharts2dplotlinegraph

3

我正在尝试使用某个库绘制大量点。这些点按时间排序，它们的值可以被认为是不可预测的。

目前我的问题是，点的数量太多了，使得绘图库渲染时间过长。许多点是冗余的（也就是说，它们在由函数y = ax + b定义的同一条线上）。有没有一种方法来检测和去除冗余的点以加速渲染？

感谢您的时间。

- nc3b

可能需要更具体一些：您使用的是哪个库，点是如何存储的？ - slhck

@slhck 我正在寻找一个算法，我不认为库会影响它。这些点被存储为大量的 (x, y) 值列表。 - nc3b

1

你是真的想说“random”吗？还是你实际上想说“arbitrary”？或者是“unpredictable”？ - Lightness Races in Orbit

@Tomalak Geret'kal 谢谢您的纠正 :) - nc3b

3个回答

0

我在想法后遇到了这个编程问题。跳过图表中的冗余点。我相信我想出了一个更好、更简单的解决办法，很高兴将其作为我的第一个SO建议解决方案分享。我已经编写并测试了它，效果很好。它还考虑了屏幕比例因素。在这些图表点之间可能有100个值，但如果用户的图表尺寸较小，他们就无法看到这些值。

因此，在迭代数据/图表循环之前，在绘制/添加下一个数据点之前，查看前面的下一个值并计算屏幕比例（或值）的变化（但我认为由于上述原因，屏幕比例更好）。现在对于往后的下一个值做同样的操作（获取这些值只是通过查看您的数组/集合/列表等向前推进一步进行增量添加（可能是1/2）到当前的值而已），如果 2个值相同（或者根据自己的喜好可能存在非常小的变化），则可以通过在循环中简单地添加“continue”来跳过图表中的这一个点，跳过添加数据点，因为该点恰好位于其前后点之间的斜率上。

使用这种方法，我将一个具有963点的图表减少到427点，而绝对没有视觉变化。

我认为你可能需要多读几遍才能理解，但这比其他提到的最佳解决方案简单得多，更轻量级，并且对你的绘图没有任何视觉影响。

- user946207

-2

我可能会应用“最小二乘法”算法来获得最佳拟合直线。然后，您可以浏览您的点并向下过滤接近该直线的连续点。您只需要绘制异常值和将曲线带回最佳拟合直线的点。

编辑：您可能不需要使用“最小二乘法”;如果您的输入预计围绕“y = ax + b”徘徊，那么这已经是您的最佳拟合直线，您可以直接使用它。 :)

- Lightness Races in Orbit

这可能会起作用，但是我该如何选择定义y的点呢？这个图一直在上下波动:-? - nc3b

数据不是单一的一行...但有许多部分看起来是线性的，可以从中删除样本而不改变图表的含义。换句话说，y=mx+q仅适用于正在绘制的数据的某些部分。 - 6502

@nc3b：这就是“最小二乘法”算法为您所做的事情。去查一下吧！ - Lightness Races in Orbit

这个回答对于问题没有意义。OP所问的是一种在不可见形状改变的情况下简化图形的方法，而不是进行线性回归。LSQ拟合是一种强大的技术，但在这里不适用。 - 6502

@6502：我实际上已经多次实现了解决此问题的方案，它们无一例外地采用这种形式。要找到数据集的基线描述，必须应用最佳拟合直线。要找到最佳拟合直线，必须考虑所有点。LSQ专门为此目的而设计。我不明白为什么它不相关。 - Lightness Races in Orbit

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- 6502 · Accepted Answer

以下是针对1.5D图表的Ramer-Douglas-Peucker算法变体：

计算第一个点和最后一个点之间的直线方程
检查所有其他点，找到距离直线最远的点
如果最差的点低于您想要的容差，则输出单个段落
否则，使用最差的点作为分裂器，递归调用考虑两个子数组

在Python中，这可能是这样的：

def simplify(pts, eps):
    if len(pts) < 3:
        return pts
    x0, y0 = pts[0]
    x1, y1 = pts[-1]
    m = float(y1 - y0) / float(x1 - x0)
    q = y0 - m*x0
    worst_err = -1
    worst_index = -1
    for i in xrange(1, len(pts) - 1):
        x, y = pts[i]
        err = abs(m*x + q - y)
        if err > worst_err:
            worst_err = err
            worst_index = i
    if worst_err < eps:
        return [(x0, y0), (x1, y1)]
    else:
        first = simplify(pts[:worst_index+1], eps)
        second = simplify(pts[worst_index:], eps)
        return first + second[1:]

print simplify([(0,0), (10,10), (20,20), (30,30), (50,0)], 0.1)

输出结果为[(0, 0), (30, 30), (50, 0)]。

关于Python数组语法的一些可能不太明显的部分：

x[a:b]是从索引a到索引b（不包括）的数组部分
x[n:]是使用x中从索引n到结尾的元素构成的数组
x[:n]是使用x的前n个元素构成的数组
a+b，当a和b是数组时，表示连接
x[-1]是数组的最后一个元素

在具有100,000个点的图上使用递增的eps值运行此实现的结果示例可以在这里看到。