隣接する矩形の境界を計算する

Question

いくつかのオーバーラップする矩形の外側境界を取得したいと考えています。

私は与えられた矩形の近傍を計算する関数を書いていますが、隣接する矩形の外側境界を取得する方法があるかどうかを確認したいと思います。 E、W、N、S：

def get_neighboring_rectangles (r, rectList): 
overlapDict = {} 
rminX, rmaxX, rminY, rmaxY = return_bbox_of_rectangle(r) 
for rectCheck,ri in rectList: 
    if r == rectCheck: continue 
    rcminX, rcmaxX, rcminY, rcmaxY = return_bbox_of_rectangle(rectCheck) 
    for d in ['E', 'W', 'N', 'S']: 
     if not ((rcmaxY < rminY or rcminY > rmaxY) or (rcmaxY == rminY) or (rcminY == rmaxY)): 
      if d == 'W' and rcmaxX == rminX: 
       if d not in overlapDict: overlapDict[d] = [] 
       overlapDict[d].append((rectCheck,ri)) 
      if d == 'E' and rcminX == rmaxX: 
       if d not in overlapDict: overlapDict[d] = [] 
       overlapDict[d].append((rectCheck,ri)) 
     if not ((rcmaxX < rminX or rcminX > rmaxX) or (rcmaxX == rminX) or (rcminX == rmaxX)): 
      if d == 'S' and rcmaxY == rminY: 
       if d not in overlapDict: overlapDict[d] = [] 
       overlapDict[d].append((rectCheck,ri)) 
      if d == 'N' and rcminY == rmaxY: 
       if d not in overlapDict: overlapDict[d] = [] 
       overlapDict[d].append((rectCheck,ri)) 
return overlapDict 

上記のプログラムは、各方向に隣人を返します。ここでは

は私が持っているものです。ここで

は、この機能が覆っている例である：

機能だけですぐ隣が何であるかを返しますが、私はすべて当接する矩形の外側の境界を返すための機能を持つようにしたい：

この場合

、入力がすべて3つの長方形の境界のリストのようになります。

[[(0,0) (7,0) (7,4) (0,4)] [(4,4) (7,4) (7,6) (4,6)] [(1,6) (7,6) (7,10) (1,10)]] 

期待出力 - [(0,0) (7,0) (7,10) (1,10) (1,6) (4,6) (4,4) (0,4)]

また、上記の3つの矩形に当接していない第四の矩形が存在し得ることに注意してください。四番目の境界は理想的にはそのまま返されるべきです。 （私は自分の隣人検出アルゴリズムを使って達成することができます）

私はこの問題にどのように近づくことができるかに関して少し迷っています。この種の機能を持つPythonライブラリはありますか？

Answer 1

カスタムソリューションを主張する場合、私は知らないが、ない場合は、おそらくshapelyパッケージには、このアプローチの実用的なツールを提供できます。

from shapely.geometry import MultiPolygon, Polygon, box 
from shapely.ops import unary_union 

L = [box(0, 0, 7, 4), box(4, 4, 7, 6), box(1, 6, 7, 10), box(100, 100, 110, 110)] 
P = unary_union(L) 
if P.geom_type == 'Polygon': 
    P = MultiPolygon([P]) 

for Q in P: 
    print(list(Q.exterior.coords)) 

これが与える：

[(110.0, 100.0), (110.0, 110.0), (100.0, 110.0), (100.0, 100.0), (110.0, 100.0)] 
[(7.0, 4.0), (7.0, 0.0), (0.0, 0.0), (0.0, 4.0), (4.0, 4.0), (4.0, 6.0), (1.0, 6.0), (1.0, 10.0), (7.0, 10.0), (7.0, 6.0), (7.0, 4.0)] 

を

ここでは、Lには、質問の矩形（ボックス）のリストと、他のものに触れない矩形（ボックス）のリストが含まれています。関数unary_unionはそれらすべての和集合を計算するので、一般的に結果は上のコードに示すようにコンポーネントに簡単にアクセスできるMultiPolygonです。たとえば、参照矩形などが含まれているコンポーネントをフィルタリングすることができます。