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

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 

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

Answer 2

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 

Answer 3

Это базовый алгоритм:

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

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

Answer 4

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

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 5

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

Донос может быть разложен на 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... :)