suche Algorithmus, um Rechtecke inside eines Pfades zu finden

[Frank E. (Firma: Q3) (qualidat)]

Gegeben ist ein Pfad mit ausschließlich 90-Grad-Ecken (im Bild schwarz). 
Gesucht wird nun ein Algorithmus, der die Fläche des Pfades vollständig 
in Rechtecke bzw. Quadrate abbildet. Minimum wäre schön, aber nicht 
wirklich zwingend.

Mir genügt auch der Name eines entsprechenden Algorithmus, den kann ich 
dann selber suchen, mir fehlen aber die richtigen Suchbegriffe. Danke.

[Εrnst B. (ernst)]

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.

[Abdul K. (ehydra)]

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?

[Yalu X. (yalu) (Moderator)]

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.

[Abdul K. (ehydra)]

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

Guter Yalu, wie immer 💪

[Frank E. (Firma: Q3) (qualidat)]

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

[Frank E. (Firma: Q3) (qualidat)]

Ε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. (ernst)]

Ε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.