Invertieren einer Reihe von Rechtecken auf einer 2D-Ebene

Question

Ich habe eine rechteckige Ebene der ganzzahligen Dimension. Innerhalb dieser Ebene habe ich eine Reihe von sich nicht schneidenden Rechtecken (von ganzzahliger Dimension und ganzzahligen Koordinaten).

Meine Frage ist, wie kann ich effizient die Umkehrung dieser Menge finden; das sind die Teile der Ebene, die nicht in einem Unterrechteck enthalten sind. Natürlich bildet diese Sammlung von Punkten eine Menge von Rechtecken - und an denen bin ich interessiert.

Meine aktuelle, naive Lösung verwendet eine boolesche Matrix (die Größe der Ebene) und funktioniert durch Setzen von a Punkt i, j auf 0, wenn es in einem Unterrechteck enthalten ist und 1 andernfalls. Dann iteriere ich durch jedes Element der Matrix und versuche, wenn es 1 ist (frei), ein Rechteck von dem Punkt nach außen zu "wachsen". Einzigartigkeit ist kein Problem (ein geeigneter Satz Rechtecke ist in Ordnung).

Gibt es Algorithmen, die ein solches Problem effektiver lösen können? (Ie, ohne auf eine boolesche Matrix zurückgreifen zu müssen.)

Answer 1

Ja, es ist ziemlich einfach ich habe eine fast identische Frage auf SO, bevor geantwortet haben, aber nicht in der Lage gewesen, es noch zu finden

Wie dem auch sei, im wesentlichen können Sie dies tun.

• Beginnen Sie mit einer Ausgabeliste, die einen einzelnen Ausgang rect enthält, der gleich dem ist Bereich von Interesse (etwas willkürlichen Begrenzungskasten, der den Bereich von Interesse definiert und enthält alle Eingangs Rects)
• für jeden Eingang rect
  • wenn der Eingang rect
    • einem der Rects in der Ausgabeliste schneidet löschen der alte Ausgang rect und erzeugt bis zu vier neuer Ausgabe Rects up, das die Differenz zwischen dem Schnittpunkt und dem ursprünglichen Ausgang rect
  repräsentiert

Optionaler abschließender Schritt: iteriere durch die Ausgabeliste, um nach Paaren von Rezepten zu suchen, die zu einem einzigen Rect zusammengeführt werden können (d. H. Recture-Paare, die eine gemeinsame Kante haben, können zu einem einzigen Rect kombiniert werden.

Answer 2

Ich vermute, Sie können irgendwo durch Ordnen der Rechtecke durch Y-Koordinate, und unter Verwendung einer Scan-Linie Ansatz. Ich kann oder nicht tatsächlich eine Implementierung zu konstruieren.

.

Answer 3

Dies ist relativ einfach, weil Ihre Rechtecke sich nicht schneiden. Das Ziel besteht im Wesentlichen aus einer Reihe von sich nicht überschneidenden Rechtecken, die die Ebene vollständig abdecken, wobei einige als ursprünglich markiert und einige als "invers" markiert sind.

Denken Sie in einem Top-Down-Scan (oder Links-rechts oder was auch immer). Sie haben eine aktuelle "Gezeitenlinie" Position. Bestimmen Sie, wo die Position der nächsten horizontalen Linie liegt, die nicht auf der Gezeitenlinie liegt. Dadurch erhalten Sie die Höhe Ihrer nächsten Gezeitenlinie.

Zwischen diesen Gezeitenlinien haben Sie einen Streifen, in dem jede vertikale Linie von einer Gezeitenlinie zur anderen (und vielleicht darüber hinaus in beiden Richtungen) reicht. Sie können die horizontalen Positionen dieser vertikalen Linien sortieren und diese verwenden, um Ihren Streifen in Rechtecke zu unterteilen und sie entweder als Teil eines ursprünglichen Rechtecks ​​oder als Teil eines umgekehrten Rechtecks ​​zu identifizieren.

Progress bis zum Ende, und Sie erhalten (wahrscheinlich zu viele zu kleine) Rechtecke, und wählen Sie diejenigen, die Sie wollen. Sie haben auch die Möglichkeit (mit jedem Schritt), kleine Rechtecke aus dem aktuellen Streifen mit einem Satz potenziell erweiterbarer Rechtecke von früher zu kombinieren.

Sie können dasselbe auch tun, wenn sich Ihre ursprünglichen Rechtecke überschneiden, aber es ist ein bisschen findiger.

Einzelheiten links als Übung für den Leser ;-)

Answer 4

Sie sollten für den raumfüllende Algorithmen einen Blick darauf werfen. Diese Algorithmen tendieren dazu, einen gegebenen Raum mit einigen geometrischen Figuren zu füllen. Es sollte nicht schwer sein, einen solchen Algorithmus an Ihre Bedürfnisse anzupassen.

Dieser Algorithmus startet von Grund auf (leerer Raum), also füllen Sie zuerst seine internen Daten mit Kästchen, die Sie bereits auf der 2D-Ebene haben. Dann lassen Sie Algorithmus den Rest erledigen - füllen Sie den verbleibenden Platz mit einem anderen Kästchen. Diese Felder machen eine Liste der invertierten Raumstücke deines Flugzeugs.

Sie behalten diese Felder in einer Liste und dann überprüfen, ob ein Punkt auf der invertierten Ebene ist ziemlich einfach. Sie durchlaufen einfach Ihre Liste und führen eine Überprüfung durch, wenn der Punkt in der Box liegt.

Hier ist ein site mit Buch von Algorithmen, die hilfreich sein könnten.

Answer 5

In Ordnung! Erste Implementierung! (Java), bezogen von @Paul's Antwort:

List<Rectangle> slice(Rectangle r, Rectangle mask) 
{ 
     List<Rectangle> rects = new ArrayList(); 

     mask = mask.intersection(r); 

     if(!mask.isEmpty()) 
     { 
       rects.add(new Rectangle(r.x, r.y, r.width, mask.y - r.y)); 
       rects.add(new Rectangle(r.x, mask.y + mask.height, r.width, (r.y + r.height) - (mask.y + mask.height))); 
       rects.add(new Rectangle(r.x, mask.y, mask.x - r.x, mask.height)); 
       rects.add(new Rectangle(mask.x + mask.width, mask.y, (r.x + r.width) - (mask.x + mask.width), mask.height)); 

       for (Iterator<Rectangle> iter = rects.iterator(); iter.hasNext();) 
         if(iter.next().isEmpty()) 
           iter.remove(); 
     } 
     else rects.add(r); 

     return rects; 
} 

List<Rectangle> inverse(Rectangle base, List<Rectangle> rects) 
{ 
     List<Rectangle> outputs = new ArrayList(); 
     outputs.add(base); 

     for(Rectangle r : rects) 
     { 
       List<Rectangle> newOutputs = new ArrayList(); 

       for(Rectangle output : outputs) 
       { 
         newOutputs.addAll(slice(output, r)); 
       } 

       outputs = newOutputs; 
     } 
     return outputs; 
} 

Möglicherweise Arbeitsbeispiel here