Algorithmus, um den optimalen Weg zu finden, eine Ebene mit farbigen Rechtecken abzudecken
Angenommen, ich öffne MS Paint, zeichne eine Reihe fester Rechtecke, speichere sie als PNG und gebe sie dir:
Jetzt musst du herausfinden, wie ich diese Rechtecke gezeichnet habe. Für dieses Bild würde Ihr Algorithmus Anweisungen wie
generieren- Zeichnen Sie das grüne Rechteck (füllen Sie den gesamten Raum aus)
- Zeichnen Sie das rosa Rechteck
- Zeichnen Sie das gelbe Rechteck
- Zeichnen Sie das blaue Rechteck
Oder mit anderen Worten, wenn ich ein Bild gebe, möchte ich es mit den wenigsten Rechteckbefehlen erzeugen. Ein Rechteckbefehl zeichnet ein ausgefülltes Rechteck anhand seiner Position, Länge, Breite und Farbe. Wie kann ich dieses Problem angehen?
Der Algorithmus sollte robust genug sein, um Bilder zu verarbeiten, die nicht nur durch Rechtecke gezeichnet werden, sondern auch komplexe Bilder wie Fotos .
3 Antworten
Sie müssten den Schnittpunkt von zwei Figuren finden, an jedem Punkt, an dem sie sich schneiden, finden Sie heraus, welcher sichtbar ist. Für diesen Punkt bekommst du den, der oben ist.
Sie sind sich dessen wahrscheinlich bewusst, aber ich bin mir ziemlich sicher, dass dieses Problem selbst bei 2 Farben NP-vollständig ist. Siehe den Abschnitt über orthogonale Polygone hier . Die Abdeckungsprobleme, die sie betrachten, sind ähnlich, aber nicht genau dasselbe.
Heuristisch vermute ich, dass die Suche nach großen einfarbigen Rechtecken Sie nicht zu weit vom Optimalen entfernt. Sobald Sie dies getan haben, versuchen Sie, angrenzende Rechtecke der gleichen Farbe zusammenzufassen, indem Sie ein benachbartes verschiedenfarbiges Rechteck in der z-Reihenfolge vorwärts bewegen.
Es ist ein mehrstufiger Prozess.
Beginnen Sie mit diesen Listen: R und S. R sind die Rechtecke (das Rechteck wird verwendet, um das endgültige Bild in der richtigen Reihenfolge zu erstellen). S ist der Abschnitt (jeder Bereich von gleichfarbigen Pixeln).
1) Erkennen Sie "perfekte" Formen; ein beliebiges Rechteck, dessen Farbe gefunden wurde, NEIN, AUSSER das Rechteck. Es muss mindestens 1 sein, da das letzte Rechteck nicht überlappt werden konnte. Fügen Sie es dem ENDE von R hinzu.
2) Fahren Sie fort (1), bis keine perfekten Formen mehr übrig sind.
3) Der nächste Teil ist knifflig. Für jeden Abschnitt: Wenn dieser Abschnitt plus ein kollektiver Teil aller Rechtecke in R ein perfektes Rechteck bildet, fügen Sie dieses Rechteck an den Anfang der Liste ein, vor allen anderen vorhandenen Rechtecken in R.
4) Wiederholen Sie (3) bis es keine mehr gibt.
Dann bist du fertig.
Tags und Links algorithm