如何在python中找到矩形交點？

具有平行於軸的矩形的列表形式(minx, miny, maxx, maxy)：如何在python中找到矩形交點？

rectangles = [ 
    Rectangle(90,40,110,70), 
    Rectangle(10,40,40,70), 
    Rectangle(75,60,95,80), 
    Rectangle(30,20,60,50), 
    Rectangle(100,20,130,50), 
    Rectangle(70,10,85,40) 
]

我需要得到矩形的組，其中每個矩形具有至少一個其它相交的列表：

[ 
    (Rectangle(10,40,40,70), Rectangle(30,20,60,50)), 
    (Rectangle(70,10,85,40)), 
    (Rectangle(75,60,95,80), Rectangle(90,40,110,70), Rectangle(100,20,130,50)) 
]

該算法可以不要太天真，它需要很快。

我的嘗試：

發現Python要間隔樹的實現 - 我無法找到什麼好...
我嘗試這樣做回購：https://github.com/booo/rectangleintersection/blob/master/rectangleIntersection.py，其工作原理與上面的例子，但無法與真正的世界數據。
我通過scikit image和Shapely文檔讀取，但沒有找到矩形交叉的算法。

來源

2014-01-07 mnowotka

每個矩形中的四個值是什麼？絕對不是2D平面上的一個點。 –

@PhamTrung：minx，miny，max，maxy – mnowotka

那麼這些矩形與Ox和Oy軸平行嗎？ –

相交矩形可以被看作是圖中的連接節點，並且可以將「過渡性」相交矩形設置爲Connected Components。要找出哪些矩形相交，我們首先執行Plane Sweep。爲了使這個速度相當快，我們需要一個Interval Tree。 Banyan提供一個：

from collections import defaultdict 
from itertools import chain 
from banyan import SortedDict, OverlappingIntervalsUpdator 

def closed_regions(rects): 

    # Sweep Line Algorithm to set up adjacency sets: 
    neighbors = defaultdict(set) 
    status = SortedDict(updator=OverlappingIntervalsUpdator) 
    events = sorted(chain.from_iterable(
      ((r.left, False, r), (r.right, True, r)) for r in set(rects))) 
    for _, is_right, rect in events: 
     for interval in status.overlap(rect.vertical): 
      neighbors[rect].update(status[interval]) 
     if is_right: 
      status.get(rect.vertical, set()).discard(rect) 
     else: 
      status.setdefault(rect.vertical, set()).add(rect) 

    # Connected Components Algorithm for graphs: 
    seen = set() 
    def component(node, neighbors=neighbors, seen=seen, see=seen.add): 
     todo = set([node]) 
     next_todo = todo.pop 
     while todo: 
      node = next_todo() 
      see(node) 
      todo |= neighbors[node] - seen 
      yield node 
    for node in neighbors: 
     if node not in seen: 
      yield component(node)

rect.vertical BTW是元組(rect.top, rect.bottom)。

時間複雜度是O(n log n + k)，其中n是實際交叉點的數量和k。所以它非常接近最優。

編輯：由於出現了一些混淆，我需要補充的是矩形預計有left <= right和top <= bottom。 IOW，它們所在座標系的原點位於左上角，而不是幾何中通常的左下角。

來源

2014-01-31 07:34:06 pillmuncher

謝謝，我一定會試一試！ – mnowotka

我能說什麼，它不工作... https://gist.github.com/mnowotka/8729240 – mnowotka

關於你的鏈接：'horizontal'應該是'（self.left，self.right）'。但最主要的問題是我的代碼假定一個計算機圖形座標系，原點位於左上角，而不是數學幾何中的左下角。所以'Rectanle .__ init __（）'的參數列表應該是'self，left，top，right，bottom'，'left <= right'和'top <= bottom'。我測試它是這樣的，它似乎工作。 – pillmuncher

如何在python中找到矩形交點？

回答

相關問題