suche Algorithmus, um Rechtecke inside eines Pfades zu finden

Rand kann sich nicht selber scheiden?

Die Optimale Lösung zu finden ist vmtl. NP-Hard.

Ich würde das iterativ angehen:

1. Oberste waagrechte Linie nehmen, nach unten schauen bis sie eine andere Linie berührt.
2. Gefundenes Rechteck speichern und aus dem Datensatz entfernen (Die Start-Linie durch die drei anderen Kanten des gefundenen Rechtecks ersetzen)
3. Daten normieren: Linien die aufeinanderliegen vereinigen, einsame Punkte (die mit 0°-Winkel) entfernen, fehlende Eckpunkte nachtragen, überflüssige Eckpunkte entfernen (also aneinanderstoßende Ecken, 180°, zusammenfassen)
4. Wenn noch Daten vorhanden: goto 1

Wenn du das in die "andere" Richtung machst, also z.B. von unten nach oben, kommt halt was anderes raus.

Schritt 3 ist vmtl. das Aufwändigste. Nicht kompliziert, aber eben viele verschiedene Fälle zu berücksichtigen. und das ggfs. mehrfach hintereinander, bis keine Optimierungen mehr gefunden werden.

Das Ganze ist also eine Form von Komprimierungsproblem, am Ende sollen die (bspw. diagonalen) Koordinaten von möglichst großen Rechtecken und derer möglichst wenige rauskommen?

Wie so oft, ist Wikipedia ein guter Startpunkt für weitere Recherchen:

https://en.wikipedia.org/wiki/Polygon_partition#Partitioning_a_rectilinear_polygon_into_rectangles

Da steht u.a.:

"Minimizing the number of components

The problem of minimizing the number of component rectangles is polynomial: several polynomial-time algorithms are known."

Das ist doch genau das, wonach du suchst. Du musst dir also nichts Neues ausdenken, sondern nur die bereits existierenden Algorithmen im Netz finden. Literaturstellen liefert der Wikipedia-Artikel ja auch.

Dafür muß man eben erstmal die richtigen Stichworte haben.

Guter Yalu, wie immer 💪

Danke für das Stichwort "rectangulation". Ich glaube das hier trifft genau meine Frage ... jetzt muss ich es nur noch verstehen :-(

https://math.uchicago.edu/~michaelklug/rectangles.pdf

Εrnst B. schrieb:

Rand kann sich nicht selber scheiden?

Die Optimale Lösung zu finden ist vmtl. NP-Hard.

Ich würde das iterativ angehen:

Danke für die Mühe, werde ich mal versuchen ...

Εrnst B. schrieb:

Die Optimale Lösung zu finden ist vmtl. NP-Hard.

Yalu X. schrieb:

The problem of minimizing the number of component rectangles is polynomial: several polynomial-time algorithms are known."

Das ist ja interessant. Da lag ich mit meiner Schätzung daneben, es ist nur NP-Hard wenn man es in die kleinste Anzahl Quadrate unterteilen will.

Ist natürlich alles rein akademisch, solange man nur eine Handvoll Eckpunkte hat.