>Background：
我正在编写一个程序，用于处理与各种规则形状的顶点网络相关的大量数据。我有一个工作生成器，它根据一系列用户输入参数生成对应于所述形状顶点的笛卡尔坐标列表。然后将数据传递给过滤器，过滤器清除重复条目，对数据进行排序和各种其他功能，从那里清理的数据被馈送到画布模块，该模块循环并绘制顶点。
问题：
我需要实现一个新的过滤器，有效地循环遍历坐标，将每对与其他每对进行比较，即 (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]使接口能够对坐标进行分组，以便以后在画布对象中使用。该方法应该能够处理潜在的数千个坐标。
提前感谢您的任何帮助，如果不清楚我以任何方式要求什么，我当然愿意改进我提供的措辞/信息和/或添加示例代码 - 我对此仍然很陌生！ :)
你基本上要检查的是：
如果你的点对于每个顶点
v，找到所有顶点，u使得u位于半径vertex_spacing围绕v的圆上。
的分布使得并非所有点都靠近在一起，我想到两种方法来加快搜索速度：
加快此过程的最简单方法是按 x 坐标对点进行排序。这样，您可以跳过许多比较。作为一个简单的示例，假设 x 坐标是
[1, 2, 10, 15, 18, 20, 21]和vertex_spacing = 5。您只需要将第一个顶点与第二个顶点进行比较，因为所有其他顶点显然都在第一个顶点周围的圆圈之外。请注意，如果所有点都靠近在一起，则此方法毫无用处。换句话说，如果
vertex_spacing = 25，则不能跳过任何比较。同样，您可以使用二维 k-d 树。这等效于排序方法，但在两个维度上。给定一个顶点
(x, y)和vertex_spacing = v，你必须检查范围中的所有点([x-v, x+v], [y-v, y+v])。使用与之前相同的示例，假设第一个点具有坐标(1, 0)，第二个点(2, 10)，则无需将第一个顶点与任何东西进行比较。
这两种方法都是启发式的，并没有对最坏情况的运行时间进行任何改进(恰恰相反：你也有排序/构建k-d树的开销(，但如果顶点通常至少相距vertex_space，这可能会大大加快你的搜索速度。
我太慢了，无法击败Heuster对算法的描述，但这里是按x坐标排序方法的实现：
def pairs(coords, vertex_spacing):
results = []
vsquared = vertex_spacing * vertex_spacing
coords = sorted(coords)
for ia, (xa, ya) in enumerate(coords):
for ib, (xb, yb) in enumerate(coords[ia:]):
dx = xb - xa
if dx > vertex_spacing:
break
dy = yb - ya
if dx * dx + dy * dy == vsquared:
results.append([(xa, ya), (xb, yb), ia, ia + ib])
return results
。这是在行动：
>>> coords = list((x, y) for x in range(100) for y in range(100))
>>> p = pairs(coords, 5)
>>> from random import choice
>>> choice(p)
[(93, 36), (96, 40), 9336, 9640]
>>> choice(p)
[(9, 57), (13, 54), 957, 1354]
>>> choice(p)
[(46, 69), (46, 74), 4669, 4674]
在我的机器上，pairs(coords, 5)检查 10,000 个坐标对需要 1.5 秒(检查 2,500 个坐标对需要 0.15 秒(。
编辑：我忘了向ib添加ia以补偿对切片的枚举 - 现已修复。
算法中最慢的部分是单独处理 x 和 y 坐标以及斜边计算。 这两者都可以通过使用 Python 的原生复数类型来加速：
>>> from itertools import starmap
>>> parray = list(starmap(complex, [(5, 1), (8.5, 3), (3.75, 4.25)]))
>>> a = parray[0]
>>> b = parray[1]
>>> a
(5+1j)
>>> b
(8.5+3j)
>>> a-b
(-3.5-2j)
>>> abs(a-b)
4.031128874149275
加快速度的一种方法是使用某种空间索引，以便排除明显相距很远的搜索点。下面是一个可能有用的模块：http://toblerity.org/rtree/。另请参阅 http://en.wikipedia.org/wiki/R-tree。