Ich habe eine rechteckige Ebene mit ganzzahliger Dimension. Innerhalb dieser Ebene habe ich eine Reihe von sich nicht überschneidenden Rechtecken (von ganzzahligen Dimensionen und ganzzahligen Koordinaten).
Meine Frage ist, wie ich die Umkehrung dieser Menge effizient finden kann; 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 arbeitet, indem sie einen Punkt i, j auf 0 setzt, wenn sie in einem Unterrechteck enthalten ist, und andernfalls auf 1. 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". Eindeutigkeit ist kein Problem (ein geeigneter Satz von Rechtecken 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.
Ja, das ist ziemlich einfach. Ich habe schon eine fast identische Frage zu SO beantwortet, konnte sie aber noch nicht finden.
Wie auch immer, im Wesentlichen können Sie das tun:
Optionaler abschließender Schritt: iteriere durch die Ausgabeliste und suche nach Paaren von Rekreten, die zu einem einzigen Rect zusammengeführt werden können (d. h. Paare von Recs, die eine gemeinsame Kante teilen, können zu einem einzigen Rect kombiniert werden).
Sie sollten nach den raumfüllenden Algorithmen suchen. 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.
Ein solcher Algorithmus beginnt bei Null (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 prüfen dann, ob ein Punkt auf der invertierten Ebene liegt, ist ziemlich einfach. Sie durchlaufen einfach Ihre Liste und führen eine Überprüfung durch, wenn der Punkt in der Box liegt.
Hier ist eine Seite mit vielen Algorithmen, die hilfreich sein könnten.
Dies ist relativ einfach, weil sich Ihre Rechtecke 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 und einige als "invers" markiert sind.
Denken Sie an einen Scan von oben nach unten (oder von links nach 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.
Gehen Sie bis zum Ende vor, und Sie erhalten (wahrscheinlich zu viele zu kleine) Rechtecke und können die gewünschten auswählen. 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 dann tun, wenn sich Ihre ursprünglichen Rechtecke überschneiden, aber es ist etwas fummeliger.
Details links als Übung für den Leser; -)
Tags und Links algorithm rectangles