我怎样才能确定一个矩形在另一个完全包含？ [英] How can I determine if one rectangle is completely contained within another?

问题描述

我有重叠的矩形，可能是这个样子的理论格：

I have a theoretical grid of overlapping rectangles that might look something like this:

但是，所有我一起工作是矩形对象的集合：

But all I have to work with is a collection of Rectangle objects:

var shapes = new List<Rectangle>();
shapes.Add(new Rectangle(10, 10, 580, 380));
shapes.Add(new Rectangle(15, 20, 555, 100));
shapes.Add(new Rectangle(35, 50, 40, 75));
// ...

我想要做的是建立一个类似DOM的结构，其中每个矩形具有ChildRectangles属性，它包含了对电网它所包含的矩形。

What I'd like to do is build a DOM-like structure where each rectangle has a ChildRectangles property, which contains the rectangles that are contained within it on the grid.

最终的结果应该让我这样的结构转换成XML，沿着线的东西：

The end result should allow me to convert such a structure into XML, something along the lines of:

<grid>
  <shape rectangle="10, 10, 580, 380">
    <shape rectangle="5, 10, 555, 100">
      <shape rectangle="20, 30, 40, 75"/>
    </shape>
  </shape>
  <shape rectangle="etc..."/>
</grid>

但是，这主要是DOM的结构在内存中，我想，输出XML是如何我可能会使用这样的结构只是一个例子。

But it's mainly that DOM-like structure in memory that I want, the output XML is just an example of how I might use such a structure.

我卡上的位是如何有效地判断哪些矩形属于其中。

The bit I'm stuck on is how to efficiently determine which rectangles belong in which.

注意否矩形部分内的另一个包含在另一个，他们总是完全。

NOTE No rectangles are partially contained within another, they're always completely inside another.

修改有通常是几百个长方形的，我应该通过各种矩形只是想迭代，看看它是否包含在另一个？

EDIT There will typically be hundreds of rectangles, should I just iterate through every rectangle to see if it's contained by another?

修改有人曾建议包含（不是我最好的时刻，缺少的！），但我不知道如何以最佳方式构建DOM。例如，拿第一个矩形的孙子，父母确实包含了孙子，但它不应该是一个直接的孩子，应该是父母的第一个孩子的孩子。

EDIT Someone has suggested Contains (not my finest moment, missing that!), but I'm not sure how best to build the DOM. For example, take the grandchild of the first rectangle, the parent does indeed contain the grandchild, but it shouldn't be a direct child, it should be the child of the parent's first child.

推荐答案

由于@BeemerGuy指出， Rect.Contains 会告诉你一矩形是否包含另一个。构建层次结构有点更多地参与...

As @BeemerGuy points out, Rect.Contains will tell you whether one rectangle contains another. Building the hierarchy is a bit more involved...

有一个O（N ^ 2）解决方案，其中每个矩形您搜索其他矩形的列表，看它是否适合里面。每个长方形的主人是包含它的最小矩形。伪code：

There's an O(N^2) solution in which for each rectangle you search the list of other rectangles to see if it fits inside. The "owner" of each rectangle is the smallest rectangle that contains it. Pseudocode:

foreach (rect in rectangles)
{
    owner = null
    foreach (possible_owner in rectangles)
    {
        if (possible_owner != rect)
        {
            if (possible_owner.contains(rect))
            {
                if (owner === null || owner.Contains(possible_owner))
                {
                    owner = possible_owner;
                }
            }
        }
    }
    // at this point you can record that `owner` contains `rect`
}

这不是非常有效的，但也可能是不够快你的目的。我是pretty的肯定，我已经看到了一个为O（n log n）的解决方案（这只是一个排序操作的，毕竟），但它是稍微复杂一些。

It's not terribly efficient, but it might be "fast enough" for your purposes. I'm pretty sure I've seen an O(n log n) solution (it is just a sorting operation, after all), but it was somewhat more complex.

这篇关于我怎样才能确定一个矩形在另一个完全包含？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！