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

问题描述：

如果矩形（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

你是否假设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）

如果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其他情况下，以检查要出界等的

答

如果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）

答

for more扫描线算法可以工作的任意形状。你会得到不同的结果，这取决于您是否水平或垂直扫描

基本上你沿着每列扫描或下一列行，并将其分解成各形状之间的间隔，间隔或行（您例如垂直扫描匹配）相同的开始和结束可以合并。

答

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

答

给定一个大长方形与任意数量冲切出它的小矩形的，你可以使用一个贪心算法的大矩形的剩余区域分成更小的矩形。

挑选尚未被覆盖的最左边的最高点。
在那里开始一个矩形。
尽可能向下延伸。
然后尽可能向右延伸它。
将该矩形添加到您的收藏并重复。

这不能保证产生最小数量的矩形。

第一步是最复杂的一步。如果你不介意一点点随机性，更容易做的事情是挑选随机点，直到找到尚未覆盖的点;然后向左走直到你碰到一个边缘;然后上去，直到你碰到一个边缘。

答

对于这个（你的问题的后半部分）的一般解决方案，你应该使用corner-stitching data structure，这正好（和更多）。

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

相关推荐