Ausführen der Optimal-Flutfüllung auf einem Gitter, während es sich auf nur nicht überschneidende Felder beschränkt

Ich muss ein Gitter optimieren, indem ich die Anzahl der "Elemente" in ihm nehme und es so weit wie möglich minimiere. Wenn ich Element sage, beziehe ich mich auf einen Abschnitt innerhalb dieses Gitters. Hier ist im Wesentlichen, wie "Eingabe" in einem visuellen Sinn aussehen könnte:

Die erste Lösung, die mir in den Sinn kommt, wäre ein Flood-Fill-Algorithmus, allerdings habe ich eine Einschränkung: Alle Elemente müssen vier Seiten haben, daher müssen alle Elemente rechteckig sein.

Meine erste, begrenzte, einfache Methode bestand darin, Element für Element durch das Eingaberaster zu durchlaufen und zu prüfen, ob das zuletzt neu erstellte Element die gleiche Farbe hatte und das gleiche Alpha wie das Element hatte, das dann erstellt werden sollte - if Anstatt also das neue Element zu erstellen, wird nur die Größe des letzten Elements geändert, um den Block weiter zu verkleinern.

Hier ist ein Pseudo-Code-Beispiel für das, was ich mache:

Als Ergebnis bekomme ich das (vorausgesetzt, ich gebe das vorherige Gitter ein):

In diesem Fall habe ich die Anzahl der Elemente von 64 auf 20 verringert.

Das ist gut, aber meine "Eingabegitter" sind normalerweise nicht 8x8 . Ein Beispiel für ein realistischeres Gitter als Eingabe ergibt 10201 Elemente vor der Optimierung (mit meiner aktuellen Methode) und 957 nach.

Da diese Methode offensichtlich stark von der Struktur des Gitters selbst abhängt, können diese Zahlen sehr unterschiedlich sein. Meine Hoffnung ist es, die Elemente so gut wie möglich für ein gegebenes Input-Grid zu minimieren.

Momentan nähere ich mich ihm aus einer Richtung (vertikal optimiert), aber ich möchte es auch horizontal optimieren. Ein Ergebnis einer solchen Operation muss nicht perfekt sein, aber hier stelle ich mir das optimale Endgitter für das erste Eingabegitter vor:

In diesem Fall reduziert sich die Anzahl der Elemente von 20 auf nur 14 - was auf meinen größeren Rastern sehr hilfreich sein könnte.

Ich kann einfach nicht an einen Weg denken, einen Flutalgorithmus so zu verwenden, dass ich jeden Elementraum im Eingangsgitter berücksichtigen und alle resultierenden Elemente rechteckig / vierseitig halten kann.

Ich dachte mir, ich könnte es wahrscheinlich brutal erzwingen, und während CPU-Auslastung / Geschwindigkeit nicht das größte Problem ist, muss ich dies auf sehr großen Gittern mit tausenden von Elementen ausführen, die so verschwendet werden Ressourcen, die versuchen, etwas in solch großem Stil zu erzwingen, sind nicht realistisch - ich denke nicht.