Bevor ich einen Nachmittag damit verbringe, dies selbst zu schreiben, dachte ich, ich würde fragen, ob bereits eine Implementierung verfügbar ist - auch nur als Referenz. Das erste Bild ist ein Beispiel für eine Bitmap-Maske, die ich in eine Liste von Rechtecken umwandeln möchte. Ein schlechter Algorithmus würde jedes festgelegte Pixel als 1x1-Rechteck zurückgeben. Ein guter Algorithmus würde wie das zweite Bild aussehen, in dem die Koordinaten der orangefarbenen und roten Rechtecke zurückgegeben werden. Die Tatsache, dass sich die Rechtecke überlappen, spielt keine Rolle, nur dass nur zwei zurückgegeben werden.
Zusammenfassend wäre das ideale Ergebnis diese beiden Rechtecke (x, y, w, h): [ { 3, 1, 2, 6 }, { 1, 3, 6, 2 } ]
Dieses Problem ist nicht genau spezifiziert. Da Sie ein einzelnes, vereinfachtes Beispiel angegeben haben, haben Sie einige der wichtigen logischen Möglichkeiten und Eckfälle hier übersehen (oder Sie haben sie nur nicht explizit ausgeschlossen). Da Sie beispielsweise die vorgeschlagene Anwendung hierfür nicht erwähnen, haben Sie nicht angegeben, was wichtiger ist: Aufteilen der gesamten Karte in exklusive Rechtecke mit einer ebenso großen Fläche (das Packing-Problem, das beliebig ist Anzahl der Lösungen) oder einfach kantenangepasste Rechtecke in x und y erhalten, wie Sie oben zu implizieren scheinen. Letzteres nehme ich an.
Stellen Sie sich den Fall vor, in dem Sie jede der 4 Kacheln ausfüllen, die sich unmittelbar in den Ecken der oben gezeichneten Bitmaske in Pluszeichenform befinden ([2, 2] ist die oberste). Was sind nun die optimalen Rechtecke? Wenn Sie nur Spalten betrachten, würden Sie schmalere, längere Bereiche mit schmaleren Seiten bevorzugen oder das große, breitere Quadrat, das sich jetzt in der Mitte des Bildes befindet, mit gedrungenen Quadraten oben und unten?
Unter der Annahme möglichst langer kantenangepasster Rechtecke ist dies eine Lösung für den ersten Versuch:
Wiederholen Sie die beiden obigen Schritte für Zeilen genau wie für Spalten (verwenden Sie stattdessen x0 und x1 und natürlich eine separate Liste).
Sie sollten jetzt einige Listen mit sauberen Rechtecken haben. Sie sind jedoch möglicherweise nicht optimal für Ihre Anwendung. In diesem Fall benötigen Sie ein Heuristiksystem, das eine effizientere Verpackung ermöglicht. Weitere Informationen finden Sie im Verpackungsproblem .
quelle