Расчет площади (ов) прямоугольника, которые не перекрываются

Question

У меня есть два прямоугольника, представленные структурами, которые содержат координаты x1, y1, x2, y2. Один прямоугольник можно считать родительским, а другой дочерним.

Я уже знаю, как определить, находится ли дочерний прямоугольник внутри родительского прямоугольника; то, что я сейчас пытаюсь выяснить, - это самый простой и быстрый способ определить прямоугольные области внутри родительского элемента, которые не перекрываются дочерним прямоугольником.

Например, рассмотрим родительский прямоугольник 100x100 и дочерний прямоугольник 50x50, расположенный точно в центре родительского элемента. Это будет означать, что будет четыре прямоугольника, представляющих четыре области в родительском прямоугольнике, которые не перекрываются дочерним элементом.

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

У меня были некоторые идеи для реализаций, чтобы понять это, но все они кажутся слишком сложными. Есть ли простой, быстрый способ выяснить это?

Answer 1

Таким образом, может быть до 4 прямоугольников неперекрытой области. Составим их список.

leftrect = rightrect = toprect = bottomrect = None
trimmedparent = duplicate(parent)

if parent.x1 < child.x1:
    leftrect = duplicate(parent)
    leftrect.x2 = child.x1
    trimmedparent.x1 = child.x1

if parent.x2 > child.x2:
    rightrect = duplicate(parent)
    rightrect.x1 = child.x2
    trimmedparent.x2 = child.x2

if parent.y1 < child.y1:
    toprect = duplicate(trimmedparent)
    toprect.y2 = child.y1

if parent.y2 > child.y2:
    bottomrect = duplicate(trimmedparent)
    bottomrect.y1 = child.y2

Единственная сложная часть - это устранение части, где, например, могут пересекаться, например, влево и вверх. Я использовал «trimmedparent» в качестве промежуточного шага, чтобы обрезать этот раздел сверху.

Answer 2

По вашему описанию, ребенок всегда целиком содержится родителем. Таким образом, неперекрывающаяся область всегда будет прямоугольным пончиком, хотя она может быть вырожденной на любой из 4 сторон, поскольку дочерний край может упираться в родительский край, а полностью вырожденный случай, когда дочерний элемент совпадает с родительским. ,

Пончик можно разложить на 4 прямоугольника. Разложение может быть не уникальным, то есть вы можете получить разные прямоугольники в зависимости от того, как вы выполняете разложение. Из 4 прямоугольников отбросьте вырожденные (те, которые имеют площадь 0), и все готово.

Вот вертикальное смещение

// assume the child is known to be in the parent bounds at this point
// assume parent and child are normalized
std::vector<CRect> rects;
CRect rect( parent.x1(), parent.y1(), child.x1(), parent.y2() ); // left
if ( rect.area() > 0.0 ) rects.push_back(rect);
rect.set( child.x1(), parent.y1(), child.x2(), child.y1() ); // bottom
if ( rect.area() > 0.0 ) rects.push_back(rect);
rect.set( child.x1(), child.y2(), child.x2(), parent.y2() ) ); // top
if ( rect.area() > 0.0 ) rects.push_back(rect);
rect.set( child.x2(), parent.y1(), parent.x2(), parent.y2() ) ); // right
if ( rect.area() > 0.0 ) rects.push_back(rect);

// yes, this could be written without all the code replication... :)

Answer 3

Вот еще один способ вычислить неперекрывающуюся область родителя:

Function max(ByVal v1 As Double, ByVal v2 As Double) As Double
    If v1 > v2 Then
        Return v1
    Else
        Return v2
    End If
End Function

Function min(ByVal v1 As Double, ByVal v2 As Double) As Double
    If v1 > v2 Then
        Return v2
    Else
        Return v1
    End If
End Function

Function IntervalOverLap(ByVal p1 As Double, ByVal p2 As Double, ByVal c1 As Double, ByVal c2 As Double) As Double
    'determine how much of the parent(p1 to p2) segment '
    ' is overlapped by the child(c1 to c2) segment      '

    'sort to standard direction  '
    Dim ph As Double = max(p1, p2)
    Dim pl As Double = min(p1, p2)
    Dim ch As Double = max(c1, c2)
    Dim cl As Double = min(c1, c2)

    'restrict the child to within the parent '
    ch = min(ph, max(pl, ch))
    cl = max(pl, min(cl, ph))

    'return the overlapped length  '
    Return (ch - cl)
End Function

Function NonOverLappedArea(ByVal parent As Rectangle, ByVal child As Rectangle) As Double
    'return the area of the parent        '
    ' that is not overlapped by the child '
    Return IntervalOverLap(parent.X1, parent.X2, child.X1, child.X2) _
        * IntervalOverLap(parent.Y1, parent.Y2, child.Y1, child.Y2)
End Function

Answer 4

Это основной алгоритм:

Для каждой точки дочернего элемента, если она находится внутри родительского элемента, соответствующий дочерний элемент и родительский элемент образуют диагональ прямоугольника. Теперь для каждой стороны дочернего элемента, если две точки находятся в родительском элементе, эти две точки и совпадающие точки на краю родительского элемента образуют прямоугольник. Если только одна из точек на ребре дочернего элемента находится в родительском элементе, эта точка и родительская точка, соответствующие дочернему ребру, не принадлежащему родительскому элементу, образуют диагональ прямоугольника. Верните эти прямоугольники.

Вы получите максимум восемь прямоугольников (по одному на каждый угол, по одному на каждый край). Если вы хотите минимально возможные прямоугольники, посмотрите, имеют ли они общие ребра, и если они имеют, объедините их.

Answer 5

parent = Rectangle.new(x1,y1,mx1,my1)
child = Rectangle.new(x2,y2,mx2,my2)

rects = []
if (parent.contains(child))
  rects.push Rectangle.new(parent.x, parent.y, parent.mx, child.y) if child.y>parent.y
  rects.push Rectangle.new(parent.x, child.my, parent.mx, parent.my) if child.my<parent.my
  rects.push Rectangle.new(parent.x, parent.y, child.x, pareny.my) if child.x>parent.x
  rects.push Rectangle.new(child.mx, parent.y, parent.mx, parent.my) if child.mx<parent.mx
end