如何按照相邻标准快速收集点列表

Question

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

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

因此，当达到所有基本情况时，F(L, P)返回一个点L1列表，这些点构成与P相关联的surface。然后对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，而且效果很好。然而，当我在一个更大的点列表上使用这个过程时（例如包含1百万个点），它会减慢处理速度，有时甚至会达到递归限制。你知道吗

因此，我希望更快地生成列表。你知道吗

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

在寻找四叉树时，我从opencv中发现了一个有趣的函数。处理一个10000点列表L需要80毫秒。你知道吗

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