Как я могу определить, содержится ли один прямоугольник внутри другого?

Question

У меня есть теоретическая сетка перекрывающихся прямоугольников, которая может выглядеть примерно так:

Но все, с чем мне нужно работать, это набор объектов Rectangle:

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, которое содержит прямоугольники, содержащиеся в нем в сетке.

Конечный результатдолжен позволить мне преобразовать такую ​​структуру в XML, что-то вроде:

<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 - всего лишь пример того, как яможет использовать такую ​​структуру.

Бит, на котором я застрял, заключается в том, как эффективно определить, какие прямоугольники принадлежат к какому.

ПРИМЕЧАНИЕ Никакие прямоугольники не содержатся частично внутри другогоони всегда полностью внутри другого.

РЕДАКТИРОВАТЬ Как правило, сотни прямоугольников, я должен просто пройти через каждый прямоугольник, чтобы увидеть, содержится ли он в другом?

РЕДАКТИРОВАТЬ Кто-топредложил Содержит (не мой лучший момент, пропуская это!), но я не уверен, как лучше построить DOM.Например, возьмем внука первого прямоугольника, родитель действительно содержит внука, но он не должен быть прямым потомком, он должен быть дочерним по отношению к первому потомку родителя.

Answer 1

Используйте Contains() из Rectangle.

Rectangle rect1, rect2;
// initialize them
if(rect1.Continas(rect2))
{
    // do...
}

UPDATE
Для дальнейшего использования ...
Интересно добавить, что Rectangle также имеет IntersectsWith(Rectangle rect) на случай, если вы хотите проверить, сталкивается ли прямоугольник с другим прямоугольником.

Answer 2

Как указывает @BeemerGuy, Rect.Contains скажет вам, содержит ли один прямоугольник другой.Построение иерархии немного сложнее ...

Существует решение O (N ^ 2), в котором для каждого прямоугольника вы просматриваете список других прямоугольников, чтобы увидеть, подходит ли он внутрь.«Владелец» каждого прямоугольника - это самый маленький прямоугольник, который его содержит.Псевдокод:

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) (в конце концов, это всего лишь операция сортировки), но оно было несколько более сложным.

Answer 3

Решение в среднем случае O (n log n):

Думайте о вашем наборе прямоугольников как о дереве, где родительские узлы "содержат" дочерние узлы - то же самое, что и DOMсостав.Вы будете строить дерево прямоугольником за один раз.

Сделайте фиктивный узел, который будет служить корнем вашего дерева.Затем для каждого из ваших прямоугольников («current_rect») начните с дочерних элементов корня и продолжайте работать до тех пор, пока не найдете, куда он идет:

parent_node = root_node
sibling_nodes = [children of parent_node]

for this_node in sibling_nodes:
    if current_rect contains this_node:
        move this_node: make it a child of current_rect instead of parent_node
    elseif this_node contains current_rect:
        parent_node = this_node
        sibling_nodes = [children of parent_node]
        restart the "for" loop using new set of sibling_nodes

make current_rect a child of parent_node

Отношение «содержит» спрашивает, содержит ли один прямоугольник другой.«Parent», «child» и «sibling» относятся к древовидной структуре.

EDITED : исправлена ​​ошибка, из-за которой некоторые узлы не перемещались в current_rect.

Answer 4

псевдокод:

for i = 0 to rectangles.length - 2
 for j = i + 1 to rectangles.length - 1
     if rectangles[i].Contains(rectangles[j])
        //code here
}}}

Answer 5

Убедитесь, что каждая точка в прямоугольнике находится в пределах других прямоугольников. В .NET класс Rectangle имеет метод .Contains (Point). Или вы можете проверить координаты угловой точки в свойствах .Left, .Right, .Top и .Bottom целевого прямоугольника.