题
我正在尝试使用一些库来绘制大量点。这些点按时间排序,并且它们的值可以被认为是不可预测的。
我目前的问题是,点的数量过多使库需要很长时间才能渲染。许多点是多余的(也就是说,它们位于由函数 y = ax + b 定义的同一条线上)。有没有办法检测并删除冗余点以加快渲染速度?
感谢您的时间。
解决方案
下面是一个变体 拉默-道格拉斯-普克 1.5d 图的算法:
- 计算第一个点和最后一个点之间的直线方程
- 检查所有其他点以找出距线最远的点
- 如果最差点低于您想要的容差,则输出单个段
- 否则递归调用考虑两个子数组,使用最差点作为分割器
在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]
是首先使用的数组n
要点x
a+b
什么时候a
和b
是数组意味着串联x[-1]
是数组的最后一个元素
在具有 100,000 个点且值不断增加的图表上运行此实现的结果示例 eps
看得到 这里.
其他提示
我可能会应用“最小二乘”算法以获得最佳拟合线。然后,您可以浏览靠近线路的连续点和连续的点。您只需要绘制异常值,而将曲线恢复到最佳拟合线的点。
编辑: 您可能不需要使用“最小二乘”;如您所说,如果您的输入预计会徘徊在“ y = ax+b”周围,那么这已经是您的最佳拟合线,您可以使用它。 :)
不隶属于 StackOverflow