폴리곤으로 성장하는 파이썬 영역

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