如何從矩形交集中提取矩形

-1

如果矩形（A）與另一個矩形（B）相交，我怎樣才能提取通過該交集創建的其他矩形（C，D，E & F）？如何從矩形交集中提取矩形

AAAAAAAAAAAAAA CCCFFFFDDDDDDD 
AAABBBBAAAAAAA CCCBBBBDDDDDDD 
AAABBBBAAAAAAA -> CCCBBBBDDDDDDD 
AAAAAAAAAAAAAA CCCEEEEDDDDDDD 
AAAAAAAAAAAAAA CCCEEEEDDDDDDD

而這可能被擴展，以提取從多個交叉點的矩形，如本實施例中相交A和乙& C和提取d，E，F & G＆

BBBBAAAAAAAAAA BBBBDDDDDDDDDD 
BBBBAAAAAAAAAA BBBBDDDDDDDDDD 
AAAAAACCCCCAAA -> EEEEEECCCCCFFF 
AAAAAACCCCCAAA EEEEEECCCCCFFF 
AAAAAAAAAAAAAA EEEEEEGGGGGFFF

來源

2010-02-01 Robert Sköld

你是否假設B完全包含在A中？ – TJB 2010-02-01 10:49:04

是的，它將被完全包含。 – 2010-02-01 11:01:44

問題的規範不明確。爲什麼'B'上面的整個空間（'A'的整個第一行）都不是一個矩形，而是整個左邊的空間（由此產生的「C」矩形）呢？ – 2010-02-01 14:11:17

如果答案TJB的問題是肯定的，那麼他們是：

（左，上，右，下）符號

C =（A.left，A.top，B 。左，A.bottom）

d =（B.right，A.top，A.right，A.bottom）

E =（B.left，B.bottom，B.right，A .bottom）

E =（B.left，A.top，B.right，B.top）

來源

2010-02-01 10:55:57

如果TJB問題的答案是否定的，那麼它幾乎是相同的： C和D只有在B.left> A.left或B.right A.頂部，分別） – Frank 2010-02-01 11:02:03

假設B在完全包含，這將是這樣的：

Rectangle[] GetSurrounding(Rectangle outer, Rectangle inner) 
{ 
    Rectangle left, top, right, bottom; // Initialize all of these... 
    left = new Rectangle(outer.Left, outer.Top, outer.Height, inner.Left - outer.Left); 
    top = new Rectangle(inner.Left, outer.Top, inner.Top - outer.Top, inner.Width); 
    // So on and so forth... 

    return new Rectangle[]{ left, top, right, bottom }; 
} 

// This assumes: 
Rectangle(x , y , height, width); // Constructor

另外，在決定天氣您將左右矩形拉伸爲全高或頂部和底部矩形，全寬度是任意的，並且需要是方法的常數決定或參數。其中矩形僅部分重疊將需要更多的邏輯尋找值的MAX/MIN其他情況下，以檢查要出界等的

來源

2010-02-01 10:56:48 TJB

如果A完全地含有B：

Rectange C = new Rectangle(A.X,A.Y,B.X-A.X,A.Height); 
Rectange D = new Rectangle(B.Right,A.Y,A.Right-B.Right,A.Height); 
Rectange E = new Rectangle(B.X,B.Bottom,B.Width,A.Bottom-A.Bottom); 
Rectange F = new Rectangle(B.X,A.Y,B.Width,B.Y-A.Y);

這是.NET ，我不確定你的代碼的語言，但我認爲大多數結構在不同的語言中看起來是相同的，在.NET中，System.Drawing.Rectangle的構造函數是（X，Y，Width，Height）

來源

2010-02-01 10:58:21

for more掃描線算法可以工作的任意形狀。你會得到不同的結果，這取決於您是否水平或垂直掃描

基本上你沿着每列掃描或下一列行，並將其分解成各形狀之間的間隔，間隔或行（您例如垂直掃描匹配）相同的開始和結束可以合併。

來源

2010-02-01 10:59:21

-1

for all rectangles A 
    for all corners C of A 
     for all other rectangles B 
     if C is inside B 
      for all corners D of B 
       if D is inside A 
        got rectangle C-D 
       endif 
      endfor 
     endif 
     endfor 
    endfor 
endfor

來源

2010-02-01 10:59:25 user231967

給定一個大長方形與任意數量衝切出它的小矩形的，你可以使用一個貪心算法的大矩形的剩餘區域分成更小的矩形。

挑選尚未被覆蓋的最左邊的最高點。
在那裏開始一個矩形。
儘可能向下延伸。
然後儘可能向右延伸它。
將該矩形添加到您的收藏並重復。

這不能保證產生最小數量的矩形。

第一步是最複雜的一步。如果你不介意一點點隨機性，更容易做的事情是挑選隨機點，直到找到尚未覆蓋的點;然後向左走直到你碰到一個邊緣;然後上去，直到你碰到一個邊緣。

來源

2010-02-01 13:50:26

對於這個（你的問題的後半部分）的一般解決方案，你應該使用corner-stitching data structure，這正好（和更多）。

來源

2010-12-08 04:36:22

如何從矩形交集中提取矩形

回答

相關問題