Berechnen der Fläche (n) eines Rechtecks, die nicht überlappt werden

Question

Ich habe zwei Rechtecke, die durch Strukturen dargestellt werden, die die Koordinaten x1, y1, x2, y2 enthalten. Ein Rechteck kann als Elternteil, ein anderes als Kind betrachtet werden.

Ich weiß bereits, wie erkannt wird, wenn das untergeordnete Rechteck innerhalb des übergeordneten Rechtecks ​​ist; Was ich jetzt herausfinden möchte, ist der einfachste und schnellste Weg, um die rechteckigen Bereiche innerhalb des Elternteils zu bestimmen, die nicht vom Kindrechteck überlappt werden.

Betrachten Sie beispielsweise ein übergeordnetes Rechteck von 100 x 100 und ein untergeordnetes Rechteck von 50 x 50, das genau in der Mitte des übergeordneten Elements liegt. Dies würde bedeuten, dass es vier Rechtecke geben würde, die die vier Bereiche im Elternrechteck darstellen, die vom Kind nicht überlappt werden.

Natürlich könnte das Kind in der oberen linken, oberen rechten, unteren linken, unteren rechten Ecke sein, oder ein wenig nach links, ein wenig nach rechts, etc ... es könnte eins, zwei, drei oder vier Rechtecke, die die nicht überlappenden Bereiche darstellen.

Ich hatte einige Ideen für Implementierungen, um das herauszufinden, aber alle scheinen übermäßig komplex. Gibt es einen einfachen, schnellen Weg, das herauszufinden?

Answer 1

So könnte es bis zu 4 Rechtecke von nicht überlappten Bereich geben. Lassen Sie uns eine Liste von ihnen machen.

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 

Der einzige schwierige Teil ist die Beseitigung des Teils, in dem beispiel leftrect und toprect schneiden könnten. Ich habe 'trimmparent' als Zwischenschritt verwendet, um diesen Abschnitt von toprect zu schneiden.

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

Dies ist der grundlegende Algorithmus:

für jeden Punkt in dem Kind, wenn sie innerhalb der übergeordneten ist, zeigt das entsprechende Kind und Eltern die Diagonalen ein Rechteck bilden. Nun, für jede Seite des Kindes, wenn die zwei Punkte im Elternteil sind, bilden diese zwei Punkte und die übereinstimmenden Punkte an der Kante des Elternteils ein Rechteck. Wenn nur einer der Punkte am Rand des Kinds im Elternteil ist, bilden dieser Punkt und der Elternpunkt, der dem Kind-Kantenpunkt entspricht, nicht im Elternteil die Diagonale für ein Rechteck. Gib diese Rechtecke zurück.

Sie würden maximal acht Rechtecke erhalten (eines für jede Ecke, eines für jede Kante). Wenn Sie die minimal möglichen Rechtecke wünschen, sehen Sie, ob sie Kanten teilen, und wenn sie dies tun, kombinieren Sie sie.

Answer 4

Hier ist ein weiterer Weg, um den nicht-überlappenden Bereich der Mutter zu berechnen:

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

Aus Ihrer Beschreibung wird das Kind immer vollständig von der Mutter enthält. Daher wird der nicht überlappende Bereich immer ein rechteckiger Donut sein, obwohl er auf jeder der 4 Seiten degeneriert sein könnte, da eine Kindkante an einer Elternkante anliegen könnte, wobei der vollständig degenerierte Fall derselbe wie der Eltern ist .

Der Donut kann in 4 Rechtecke zerlegt werden. Die Dekomposition ist möglicherweise nicht eindeutig, was bedeutet, dass Sie abhängig davon, wie Sie die Dekomposition durchführen, unterschiedliche Rechtecke erhalten können. Von den 4 Rechtecken, verwerfen Sie die entarteten (diejenigen mit 0 Bereich) und Sie sind fertig.

Hier ist ein vertikal voreingenommen Zersetzung

// 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... :)