python - 快速实现查找重复坐标

Question

我正在尝试编写一个在 3D 数组中查找重复坐标 (x, y, z) 的程序。脚本应该用给定的容差标记一个或多个重复点 - 一个点可能有多个重复。我发现了许多不同的方法，其中包括使用排序方法。
为了尝试代码，我创建了以下测试数据集:

21.9799629872016 57.4044376777929 0
22.7807110172432 57.6921361034533 0
28.660840151287 61.5676757599822 0
28.6608401512 61.56767575998 0
30.6654296288019 56.2221038199424 0
20.3752036442253 49.1392209993897 0
32.8036584048178 43.927288357851 0
35.8105426210901 51.9456462679106 0
40.8888359641279 58.6944308422108 0
40.88883596412 70.6944308422108 0
41.0892949118794 58.1598736482068 0
39.6860822776189 64.775018924006 0
39.1515250836149 64.8418385732565 0
8.21402748063493 63.5054455882466 0
8.2140275006 63.5074455882 0
8.21404548063493 63.5064455882466 0
8.2143214806 63.5084455882 0

我想出的代码是:

# given tolerance
tol = 0.01

# initialize empty list for the found duplicates
duplicates = []

# loop over all nodes
for i in range(0,len(nodes)):
    # current node
    curr_node = nodes[i]
    # create difference vector
    diff = nodes - curr_node
    
    # get all duplicate indices (the node itself is found as well)
    condition = np.where((abs(diff[:,0])<tol) & (abs(diff[:,1])<tol) & (abs(diff[:,2])<tol))

    # check if more than one entry is present. If larger than 1, duplicate points exist
    if len(condition[0]) > 1:
        # loop over all found duplicate points
        for j in range(0,len(condition[0])):
            # add duplicate if not already marked as duplicate
            if j>0 and condition[0][j] not in duplicates:
                duplicates.append(condition[0][j] )

此代码返回我期望的内容:

duplicates = [3, 14, 15, 16]

但是，代码非常慢。对于 300,000 点，大约需要 10 分钟。我想知道是否有任何更快的方法来实现这一点。

Answer 1

您可以在 tolerance 的网格中放置点-大小的立方体。然后，对于每个点，您只需要检查来自同一个立方体的点 + 26 个相邻的点，而不是所有其他点。

# compute the grid

for p in points:
    cube = (
        int(p[0] / tolerance),
        int(p[1] / tolerance),
        int(p[2] / tolerance))
    grid[cube].append(p)

# check

for p in points:
    cube = as above
    for adj in adjacent_cubes(cube)
       for p2 in grid[adj]
           check_distance(p, p2)