如何通过遵循相邻的标准快速收集点列表

Question

我有一个点L=[[x1,y1],[x2,y2],...]的列表，我想建立一个列表S=[L1,L2,...]“表面”通过收集L的邻居点生成。 “表面”的类型与L的类型相同，也就是说，点列表（但是构成基于邻居链接的表面）。但是，我试图做的还不够快。

我使用了递归函数F(L, P)，它需要一个点L列表，以及起始点P=[x,y]（在调用函数时必须从列表L中删除）。然后，它查找P的所有邻居点，并在它们存在的每一个上回调函数（在从L中删除它们之后）。当测试的点不再具有邻居点时，到达基本情况。

因此，当达到所有基本情况时，F(L, P)返回构成与L1相关的surface的点P列表。然后我重复L剩余点的过程，依此类推，建立L2,L3,...。

def F(L,P):   
    nhList=[]
    leftP=[P[0]+1,P[1]]
    rightP=[P[0]-1,P[1]]
    upP=[P[0],P[1]-1]
    dwP=[P[0],P[1]+1] 

    if(upP in L):
        L.remove(upP)
        nhList.append(upP)
    if(dwP in L):
        L.remove(dwP)
        nhList.append(dwP)
    if(leftP in L):
        L.remove(leftP)
        nhList.append(leftP)
    if(rightP in L):
        L.remove(rightP)
        nhList.append(rightP)

    if(nhList!=[]):
        rtList=[P]
        for ad in nhList:
            e=F(L,ad)
            rtList+=e
        return rtList
    else:
        return [P]

L=[[0,0],[1,0],[5,3],[1,1],[5,4],[2,2]] # e.g.
S=[]
while(L!=[]):
    P=L.pop()
    S.append(F(L,P))
print(S)
# Returns [[2, 2]], [[5, 4], [5, 3]], [[1, 1], [1, 0], [0, 0]] as expected

我期望按照介绍中的说明检索列表S，它运行良好。但是，当我在更大的点列表（例如包含1M点）上使用此过程时，它会减慢处理速度，有时甚至达到递归限制。

因此，我希望更快地生成列表S。

Answer 1

我认为你可以通过以下想法来提升绩效：

1. 在大数据，以避免recursion limit，你可以使用iteration而不是recursion
2. 为了提高query中modify和L的性能，你可以将L预处理成set
3. 对于算法，BFS适用于此处。

这是我的解决方案：

from collections import deque

L = [[0, 0], [1, 0], [5, 3], [1, 1], [5, 4], [2, 2]]  # e.g.
# convert to set for query and modify performance, change list to immutable tuple.
L = set(map(tuple, L))

S = []
while L:
    # start from a random point
    start = L.pop()
    queue, visited, cur_s = deque([start]), set([start]), [start]

    while queue:
        node = queue.popleft()
        visited.add(node)
        i, j = node
        # find the 4-adjacent neighbors
        for neighbor in (i + 1, j), (i - 1, j), (i, j + 1), (i, j - 1):
            if neighbor in L and neighbor not in visited:
                queue.append(neighbor)
                cur_s.append(neighbor)
                L.remove(neighbor)
    S.append(cur_s)

print(S)

输出：

[[(5, 4), (5, 3)], [(0, 0), (1, 0), (1, 1)], [(2, 2)]]

希望对您有所帮助，并在您有其他问题时发表评论。 :)

Answer 2

当我寻找Quadtrees时，我从opencv中发现了一个有趣的函数。处理10.000点列表L需要大约80ms。

connectedComponents(InputArray image, OutputArray labels, int connectivity=8, int ltype=CV_32S)