问题描述

我有一个重叠矩形的理论网格，可能看起来像这样:

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

但我只需要处理一组 Rectangle 对象:

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) 解决方案，您可以针对每个矩形搜索其他矩形的列表以查看它是否适合其中.每个矩形的所有者"是包含它的最小矩形.伪代码:

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`
}

它的效率不是很高，但对于您的目的来说它可能足够快".我很确定我已经看到了一个 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.

这篇关于如何确定一个矩形是否完全包含在另一个矩形中?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持跟版网！