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

Question

我有一个点列表 L=[[x1,y1],[x2,y2],...]，我想通过收集 L 的相邻点来构建 "surface" 的列表 S=[L1,L2,...]。 "surface" 的类型与 L 的类型相同，即点列表（但构成基于邻域链接的表面）。但是，我尝试做的速度不够快。

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

因此，当达到所有基本情况时，F(L, P) returns 点列表 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，并且效果很好。但是，当我在更大的点列表（例如包含 1M 点）上使用此过程时，它会减慢处理速度，有时甚至会达到递归限制。

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

Answer 1

我认为您可以通过以下想法提高性能：

在大数据中为了避免recursion limit，可以使用iteration代替recursion
为了提高 query 和 modify 在 L 中的性能，您可以将 L 预处理为 set
对于算法，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 中发现了一个有趣的函数。处理 10.000 点列表需要大约 80 毫秒 L。

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

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

How to quickly gather a list of points by following adjacent criterium

python

surface

image-recognition

contour