Как быстро собрать список баллов, следуя соседнему критерию

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, как объяснено во вступлении, и он работает хорошо. Однако, когда я использую этот процесс в большом списке точек (который содержит, например, 1 млн. Точек), он замедляет обработку, а иногда я даже достигаю предела рекурсии.

Поэтому я хочу сгенерировать список S быстрее.

Answer 1

Я нашел интересную функцию из opencv, когда я ищу Quadtrees. Для обработки списка из 10000 баллов требуется ~ 80 мс L.

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

Answer 2

Я думаю, вы можете улучшить производительность, используя следующие идеи:

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)]]

Надеюсь, что это поможет вам, и прокомментируйте, если у вас есть дополнительные вопросы.:)