11

背景：

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

问题：

我需要实现一个新的过滤器，它可以有效地循环遍历坐标，将每一对与其他每一对进行比较，即(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 in 的[(x1,y1), (x5,y5), 0, 4]作用是使界面能够对坐标进行分组，以供以后在画布对象中使用。该方法应该能够处理潜在的数千个坐标。

提前感谢您的帮助，我当然愿意改进我提供的措辞/信息和/或添加示例代码，如果不清楚我的要求是什么 - 我对此还是很陌生！:)

4

4 回答 4

6

你基本上检查的是：

对于每个顶点v，找到所有顶点u，这样就可以在周围u的半径圆上。vertex_spacingv

如果您的点分布不是所有点都靠得很近，我会想到两种加快搜索速度的方法：

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

    请注意，如果所有点都靠得很近，这种方法是没有用的。换句话说，如果vertex_spacing = 25，您不能跳过任何比较。

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

这两种方法都是启发式的，在最坏情况下的运行时间上没有任何改进（恰恰相反：你还有排序/构建 kd 树的开销），但如果顶点通常至少vertex_space分开，这可能会加快你搜索了很多。

于 2013-08-17T18:57:15.503 回答
4

我太慢了，无法击败 Heuster 对算法的描述，但这里是 sort-by-x-co-ordinate 方法的一个实现：

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 秒）。

编辑：我忘记添加ia以ib补偿枚举切片 - 现在已修复。

于 2013-08-17T19:08:45.007 回答
2

算法中最慢的部分是分别处理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
于 2013-08-18T00:42:14.013 回答
1

加快速度的一种方法是使用某种空间索引，以便排除明显相距很远的搜索点。这是一个可能有用的模块：http: //toblerity.org/rtree/。另见http://en.wikipedia.org/wiki/R-tree。

于 2013-08-17T19:03:37.817 回答