[gelöst] Das größte Rechteck
Verfasst: 26.02.2017, 13:15
Erstmal wollte ich jetzt in jede Achse einen Chunk durchgehen und schauen, dass ich diese Ebene dann durch möglichst wenig Rechtecke annähern kann.
Diese dürfen sich dabei gerne überlappen, sollten es sogar, zumindest an den Rändern, da ich beim Occlusiontest die einzelnen Occluder nicht mergen kann und die Patches, die dann auf den Kanten liegen nicht weg gecullt würden.
Aber soweit bin ich noch lange nicht, denn ich scheitere eigentlich schon an der Verteilung.
So sieht eine ausgewählte Ebene im Querschnitt aus. Jedes Quadrat ist ein gefüllter Voxel.
Mein erster Ansatz war nun, das ganze in Streifen zu betrachten und dann die Streifen, die gleich lang sind und nebeneinander liegen, zu mergen. Dabei kommt das hier raus:
Ich denke, das geht aber sicher noch besser. Dachte nun, dass man die Nachbarn wieder zersplitten könnte beim mergen, also z.B. die beiden Streifen ganz Links, die könnte man durch 2 Rechtecke darstellen, wobei dann eins sehr groß ist und das andere nur ein einzelnes kleines Quadrat oben. Aber eigentlich kommt mir das alles etwas schwierig vor. Eigentlich sollte es doch möglich sein, direkt das beste (falls es das überhaupt gibt) Ergebnis zu bekommen, wenn man zunächst das größtmögliche Rechteck sucht, dann dies herausnimmt und bei dem Rest wieder das größtmöglichste sucht.
Doch auch hier weiß ich irgendwie nicht, wie man das geschickt angehen kann? Selbst wenn man erstmal nur ein Rechteck herauspickt und es solange erweitert, bis es an die "Grenzen" stößt, gibt es da ja auch schon wieder mehrere Ergebnisse, je nachdem in welche Achsen man wie lange erweitert. Also meine Frage, gibt es da einen schlauen und einfachen Ansatz, wie man nun da das größte Rechteck finden kann?
EDIT:
Hier noch ein bemaltes Bild, wie es eigentlich am Ende aussehen sollte...
EDIT2:
Also allein wenn man sich wahllos ein Quadrat rausfischt und dazu mal schaut, welche größten Rechtecke dieses beinhalten, kommt man auf allerhand Lösungen.
Diese dürfen sich dabei gerne überlappen, sollten es sogar, zumindest an den Rändern, da ich beim Occlusiontest die einzelnen Occluder nicht mergen kann und die Patches, die dann auf den Kanten liegen nicht weg gecullt würden.
Aber soweit bin ich noch lange nicht, denn ich scheitere eigentlich schon an der Verteilung.
So sieht eine ausgewählte Ebene im Querschnitt aus. Jedes Quadrat ist ein gefüllter Voxel.
Mein erster Ansatz war nun, das ganze in Streifen zu betrachten und dann die Streifen, die gleich lang sind und nebeneinander liegen, zu mergen. Dabei kommt das hier raus:
Ich denke, das geht aber sicher noch besser. Dachte nun, dass man die Nachbarn wieder zersplitten könnte beim mergen, also z.B. die beiden Streifen ganz Links, die könnte man durch 2 Rechtecke darstellen, wobei dann eins sehr groß ist und das andere nur ein einzelnes kleines Quadrat oben. Aber eigentlich kommt mir das alles etwas schwierig vor. Eigentlich sollte es doch möglich sein, direkt das beste (falls es das überhaupt gibt) Ergebnis zu bekommen, wenn man zunächst das größtmögliche Rechteck sucht, dann dies herausnimmt und bei dem Rest wieder das größtmöglichste sucht.
Doch auch hier weiß ich irgendwie nicht, wie man das geschickt angehen kann? Selbst wenn man erstmal nur ein Rechteck herauspickt und es solange erweitert, bis es an die "Grenzen" stößt, gibt es da ja auch schon wieder mehrere Ergebnisse, je nachdem in welche Achsen man wie lange erweitert. Also meine Frage, gibt es da einen schlauen und einfachen Ansatz, wie man nun da das größte Rechteck finden kann?
EDIT:
Hier noch ein bemaltes Bild, wie es eigentlich am Ende aussehen sollte...
EDIT2:
Also allein wenn man sich wahllos ein Quadrat rausfischt und dazu mal schaut, welche größten Rechtecke dieses beinhalten, kommt man auf allerhand Lösungen.