math - 删除线图的冗余点

Question

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

我目前的问题是点数过多导致库渲染时间过长。许多点是多余的(也就是说 - 它们“位于”由函数 y = ax + b 定义的同一直线上)。有没有一种方法可以检测和删除冗余点以加快渲染速度？

感谢您的宝贵时间。

Answer 1

以下是 Ramer-Douglas-Peucker 的变体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
的前 n 个元素组成的数组
• a+b 当a和b为数组时表示拼接
• x[-1] 是数组的最后一个元素

可以看到在具有 100,000 个点且 eps 值递增的图形上运行此实现的结果示例 here .