Decken Sie ein konkaves Polygon mit einer Mindestanzahl von Rechtecken ab

Ich versuche, ein einfaches konkaves Polygon mit einem Minimum an Rechtecken zu bedecken. Meine Rechtecke können beliebig lang sein, aber sie haben maximale Breiten, und das Polygon hat niemals einen spitzen Winkel.

Ich dachte darüber nach, mein konkaves Polygon in Dreiecke zu zerlegen, die einen Satz minimal überlappender Rechtecke erzeugen, die jedes Dreieck minimal begrenzen, und diese Rechtecke dann zu größeren zusammenzuführen. Ich denke jedoch nicht, dass dies für kleine Kerben in den Kanten des Polygons funktioniert. Die Dreiecke, die durch die Reflexscheitelpunkte in diesen Kerben erzeugt werden, erzeugen die falschen Rechtecke. Ich suche nach Rechtecken, die Kerben überspannen / ignorieren.

Ich weiß nicht wirklich etwas über Computergeometrie, daher bin ich mir nicht sicher, wie ich anfangen soll, die Frage zu stellen.

Ich habe andere Beiträge gefunden, die ähnlich waren, aber nicht das, was ich brauche:

• Teilen Sie das Polygon in eine minimale Anzahl von Rechtecken und Dreiecken
• Bedecken eines beliebigen Polygons mit einer minimalen Anzahl von Quadraten
• Finden Sie Rechtecke so, dass sie die maximale Anzahl von Punkten abdecken$k$
• Algorithmus zum Finden der wenigsten Rechtecke, um eine Reihe von Rechtecken abzudecken

Einige Beispiele: Schwarz ist die Eingabe. Rot ist die akzeptable Ausgabe.

Ein weiteres Beispiel: Die zweite Ausgabe wird bevorzugt. Es ist jedoch wahrscheinlich notwendig, beide Ausgaben zu generieren und einen anderen Faktor zur Bestimmung der Präferenz zu verwenden, und nicht die Verantwortung dieses Algorithmus.

Polygone, die Kurven imitieren, sind äußerst selten. In diesem Szenario wird ein Großteil der Fläche der Rechtecke verschwendet. Dies ist jedoch akzeptabel, da jedes Rechteck die maximale Breitenbeschränkung einhält.

Außerdem habe ich festgestellt, dass dieser Artikel genau dem entspricht, was ich brauche:

• Bedeckung mit rechteckigen Stücken von Paul Iacob, Daniela Marinescu und Cristina Luca

Vielleicht ist eine bessere Frage: "Wie kann ich rechteckige Teile eines konkaven Polygons identifizieren?"

Hier ist ein Bild, das die gewünschte Implementierung zeigt:

Das Grün ist der tatsächliche Materialverbrauch. Die roten Rechtecke sind die Layouts. Das Blau ist der MBR des gesamten Polygons. Ich denke, ich sollte versuchen, kleine MBRs zu bekommen und sie auszufüllen. Die 2-3 grünen Rechtecke in der oberen linken Ecke, die in der Mitte des Polygons enden, sind teuer. Das möchte ich minimieren. Die grünen Rechtecke haben eine minimale und maximale Breite und Höhe, aber ich kann so viele Zeilen und Spalten verwenden, wie zum Abdecken eines Bereichs erforderlich sind. Auch hier muss ich die Anzahl der Rechtecke minimieren, die sich nicht über die Eingabe erstrecken. Ich kann auch die Form des grünen Rechtecks ​​ändern, um sie an kleine Stellen anzupassen, was ebenfalls sehr teuer ist. Mit anderen Worten, es ist ideal, so viele Rechtecke wie möglich so weit wie möglich zu überspannen.

Dies ist eine Variante der geometrischen Setabdeckung. Abhängig von den genauen Einstellungen können Sie möglicherweise eine gute Annäherung vornehmen. Das Problem ist natürlich NP-Hard. Die natürliche Huersitik besteht darin, einen gierigen Algorithmus zu verwenden (wählen Sie immer das Rechteck / den Streifen aus, das den größten noch nicht abgedeckten Bereich abdeckt. Die alternative Technik ist das Wiegen. Es gibt einige interessante theoretische Ergebnisse, aber ehrlich gesagt nichts, was in der Praxis zu nützlich sein sollte Eine interessante Hueristik, die Sie vielleicht ausprobieren möchten, besteht darin, Ihr Polygon zunächst in eine minimale Anzahl konvexer Formen zu zerlegen (mithilfe des dynamischen Programmieralgorithmus von Keil) und dann jedes konvexe Polygon separat abzudecken ...

Ich denke, dieses Papier kann hilfreich sein. Offensichtlich ist es nicht dasselbe Problem - tatsächlich ist es das umgekehrte Problem, ein Rechteck mit Polygonen zu bedecken -, aber einige der Ideen könnten ein Ausgangspunkt sein. Insbesondere ist dieses umgekehrte Problem NP-schwer und ich vermute, dass es auch Ihr Problem ist (obwohl es, soweit ich das beurteilen kann, keine offensichtliche Erweiterung der Reduzierung gibt).

E. Arkin, A. Efrat, G. Hart, I. Kostitsyna, A. Kroller, J. Mitchell und V. Polishchuk. Skandinavische Ausdünnung auf Kuchen: Auf der kleinsten Einheitsbox. Spaß mit Algorithmen . S. 16-27. 2012