删除线图的冗余点

Question

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

我目前的问题是，点的数量过多使库需要很长时间才能渲染。许多点是多余的（也就是说，它们位于由函数 y = ax + b 定义的同一条线上）。有没有办法检测并删除冗余点以加快渲染速度？

谢谢您的宝贵时间。

Answer 1

以下是 Ramer-Douglas-Peucker< 的变体/a> 1.5d 图的算法：

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

在 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 a+b 的前 n 个元素组成的数组
• ] 是当 a 和 < 时 code>b 是数组，表示串联
• x[-1] 是数组的最后一个元素 在

具有 100,000 个点且 < 值不断增加的图上运行此实现的结果示例code>eps 可以在此处查看。

Answer 2

在我有了这个想法之后，我遇到了这个问题。跳过绘图上的冗余点。我相信我想出了一个更好、更简单的解决方案，并且我很高兴将其作为我提出的第一个解决方案进行分享。我已经对其进行了编码，并且它对我来说效果很好。它还考虑了屏幕比例。这些绘图点之间的值可能有 100 个点，但如果用户的图表尺寸较小，他们将看不到它们。

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

例如，使用这种方法，我将图表从 963 个点减少到 427 个点，视觉变化绝对为零。

我认为您可能需要阅读几次才能理解，但它比这里提到的其他最佳解决方案简单得多，重量轻得多，并且对您的情节的视觉效果为零。

Answer 3

我可能会应用“最小二乘”算法来获得最佳拟合线。然后，您可以遍历您的点并向下过滤靠近该线的连续点。您只需绘制离群值以及使曲线回到最佳拟合线的点。

编辑：您可能不需要使用“最小二乘法”；如果您的输入预计会像您所说的那样徘徊在“y=ax+b”附近，那么这已经是您的最佳拟合线，您可以使用它。 :)