在 Python 中高效操作笛卡尔坐标列表

背景：

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

问题：

我需要实现一个新的过滤器，该过滤器可以有效地循环遍历坐标，将每一对与其他每一对进行比较，即(x1,y1)->(x2,y2) to (x1,y1)->(xn,yn), (x2,y2)->(x3,y3) to (x2,y2)->(xn,yn)等等对于所有条目，例如，如果之间的关系(x1,y1) and (x5,y5) fits [(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]是使接口能够对坐标进行分组，以便以后在画布对象中使用。该方法应该能够处理潜在的数千个坐标。

提前感谢您的任何帮助，如果不清楚我以任何方式询问什么，我当然愿意改进我提供的措辞/信息和/或添加示例代码 - 我对此仍然很陌生！ :)

您基本上要检查的是：

对于每个顶点v,找到所有顶点u这样u位于半径圆上vertex_spacing around v.

如果点的分布不是所有点都靠近，我想到两种方法来加速搜索：

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

   请注意，如果所有点都靠近，则此方法毫无用处。换句话说，如果vertex_spacing = 25，您不能跳过任何比较。

2. 同样，您可以使用二维k-d tree http://en.wikipedia.org/wiki/Kd_tree。这相当于排序方法，但是是二维的。给定一个顶点(x, y) and vertex_spacing = v，你必须检查范围内的所有点([x-v, x+v], [y-v, y+v])。使用与之前相同的示例，假设第一个点有坐标(1, 0)第二个(2, 10)，不需要将第一个顶点与任何东西进行比较。

这两种方法都是启发式的，并且不会对最坏情况的运行时间做出任何改进（恰恰相反：您还有排序/构建 k-d 树的开销），但如果顶点通常至少vertex_space除此之外，这可以大大加快您的搜索速度。