ポリゴンのパフォーマンスで成長するpythonの領域

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