在Python中高效处理笛卡尔坐标列表

Question

背景:

我正在编写一个程序来处理与各种规则形状的顶点网络相关的大量数据.我有一个工作的发生器,它根据一系列用户输入参数产生一个与所述形状的顶点相对应的笛卡尔坐标列表.然后将数据传递给过滤器,过滤器清除重复的条目,对数据和各种其他功能进行排序,从中将清理后的数据送到画布模块,画布模块循环并绘制顶点.

题:

我需要实现一个新的过滤器,有效地通过坐标循环,每对对每隔一对比较,即(x1,y1)- > (x2,y2)到(x1,y1)- > (xn,yn),(x2,y2)- > (x3,y3)到(x2,y2)- > (xn,yn)等,为所有条目,例如,如果之间的关系(x1,y1)和(x5,y5)配合[(x5-x1)^2+(y5-y1)^2]=vertex_spacing^2然后将两组坐标与它们各自的列表条目编号配对,并附加到一个新的列表中,其中一个条目具有以下形式:[(x1,y1), (x5,y5), 0, 4]例如.实现这一目标的最有效方法是什么？

我的尝试:

我在这里和各种指南上看了很多处理列表的方法.我尝试嵌套'for'和'if'循环,但发现虽然这种方法可以工作,但它会导致运行时间过长,并试图将问题分解为许多较小的for循环.

进一步说明:

这样做的最终目的是使用前端界面元素的结果坐标,并根据需要进行保存和导入.列表位置0和4的功能[(x1,y1), (x5,y5), 0, 4]是使接口能够对坐标进行分组,以便以后在画布对象中使用.该方法应该能够处理数千个坐标.

提前感谢您的帮助,我当然愿意改进我提供的措辞/信息和/或添加示例代码,如果不清楚我在问什么 - 我还是很新的!:)

Answer 1

你基本上检查的是:

对于每个顶点v,发现所有的顶点u,从而u是半径的圆圈vertex_spacing围绕v.

如果您的积分分布不是所有积分都很接近,我想到两种加速搜索的方法:

1. 加速此过程的最简单方法是按x坐标对点进行排序.这样,您可以跳过许多比较.举个简单的例子,假设x坐标是[1, 2, 10, 15, 18, 20, 21]和vertex_spacing = 5.您只需要比较第一个顶点和第二个顶点,因为所有其他顶点显然位于第一个顶点周围的圆圈之外.

   请注意,如果所有点都靠得很近,这种方法就没用了.换句话说,如果vertex_spacing = 25,你不能跳过任何比较.

2. 沿着相同的路线,您可以使用二维kd树.这相当于排序方法,但在两个方面.给定一个顶点(x, y)和vertex_spacing = v,你就必须检查所有点的范围内([x-v, x+v], [y-v, y+v]).使用与之前相同的示例,假设第一个点具有坐标(1, 0)而第二个点具有坐标(2, 10),则不需要将第一个顶点与任何东西进行比较.

这两种方法都是启发式方法,并没有对最坏情况下的运行时间进行任何改进(完全相反:你也有排序/构建kd树的开销),但如果顶点通常至少是vertex_space分开的,这可能会加速你的搜索很多.