python region growth with polygons performance

Question

Я пытаюсь создать области полигонов при условии, что они касаются. В моем примере у меня есть примерный набор данных с 382 полигонами, которые необходимо сгруппировать (но полный набор данных содержит 6355 полигонов). (Я бы показал фотографию, но у меня нет достаточной репутации, чтобы сделать это.)

Я, хотя и делаю это грубую силу, но, конечно, это занимает очень много времени и не очень оптимально.

def groupBuildings(blds): 
    # blds is a list with shapely polygons 
    groups = [] 
    for bld in blds: 
     group = [] 
     group.append(bld) 
     for other in blds: 
      for any in group: 
       if any != other and any.intersects(other): 
        group.append(other) 
     groups.append(group) 
    return groups 

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

def groupBuildings(blds): 
    # blds is a list with shapely polygons 
    others = blds 
    groups = [] 
    while blds != []: 
     done = [] 
     group = [] 
     first = blds.pop(0) 
     done.append(first) 
     group.append(first) 
     for other in others: 
      if (other in blds) and first.touches(other): 
       group.append(other) 
       blds.remove(other) 

return groups 

Но я думаю, что проблема здесь в том, что у меня нет каких-либо ближайших соседей, так что я до сих пор перебирать каждое здание в два раза.

Итак, мой вопрос: являются ближайшими соседями, необходимыми для развития региона? Или есть другой способ сделать это эффективно?

Answer 1

Вам будет лучше всего использовать shapely.ops.cascaded_union() (docs here).

from shapely.geometry import Point, Polygon, MultiPolygon 
from shapely.ops import cascaded_union 
import numpy as np 
polygons = [Point(200*x,200*y).buffer(b) for x,y,b in np.random.random((6000,3))] 
multi = MultiPolygon(polygons) 
unioned = cascaded_union(multi) 

%%timeit 
unioned = cascaded_union(multi) 
# 2.8 seconds for me