Wie teilt man einen Bereich aus kleinen Quadraten in größere Rechtecke auf?

Question

Wohin würde ich gehen, um nach Algorithmen zu suchen, die ein 2-dimensionales Gitter mit Werten annehmen, die entweder 0 oder 1 sind und dann alle möglichen nicht überlappenden Rechtecke identifizieren?

In einer praktischen Erklärung: Ich zeichne ein Raster, das durch eine Anzahl von Quadraten dargestellt wird, und ich möchte einen Weg finden, so viele benachbarte Quadrate in Rechtecke wie möglich zu kombinieren, um die Zeit zu reduzieren verbringe es, durch jeden Platz zu radeln und ihn zu zeichnen.

Maximale Effizienz wird nicht benötigt, Geschwindigkeit ist wichtiger.

Nachtrag: Offensichtlich scheint das, was ich suche, eine Technik namens Tesselation zu sein. Jetzt muss ich nur eine gute Beschreibung für diesen speziellen Fall finden.

Addendum 2: Die Grenze der "1" Quadrate wird unregelmäßig sein und in einigen Fällen nicht einmal verbunden, da die Verteilung der "1" Quadrate völlig zufällig sein wird. Ich muss diese unregelmäßigen Formen identifizieren und in regelmäßige Rechtecke aufteilen.

Richtige Antwort: Um das beste Verhältnis zwischen Geschwindigkeit und Effizienz zu erzielen, ist es optimal, die Rasterdaten zum Füllen eines Quadbaums zu verwenden, wobei jeder Knoten einen Statuswert von leer/teilweise gefüllt/gefüllt hat.

Answer 1

Ich habe etwas ähnliches für eine schnell-und-dreckige Voxel-Visualisierung von 3D-Boxen mit OpenGL gemacht.

Ich begann von der oberen linken Box und speicherte die leere/gefüllte Flagge. Dann habe ich versucht, das Rechteck nach rechts zu erweitern, bis ich eine Box mit einer anderen Flagge traf. Ich machte das gleiche in der Richtung nach unten.

Zeichnen Sie das Rechteck, wenn es gefüllt ist.

Wenn es Boxen remaing, rekursiv wiederholen Sie den Vorgang für alle drei remaing Rechtecke durch das letzte Rechteck induziert, die richtig sind, unten und rechts unten:

xxxx 1111 
xxxx 1111 
xxxx 1111 

2222 3333 
2222 3333 
2222 3333 

Answer 2

Sie suchen also nach der rechteckigen Grenze der 'ON' Quadrate?
Möchten Sie die innere oder äußere Grenze?
dh. Muss die Grenze nur 'ON' Quadrate haben oder soll das Rechteck alle 'ON' Quadrate in einer Gruppe enthalten?

Answer 3

Da Sie nicht nach der Mindestanzahl von Quadraten suchen, würde ich vorschlagen, einen Kompromiss zu verwenden, der Ihren Algorithmus immer noch einfach hält.

Die beste Lösung hängt von Ihren Daten ab, aber eine einfache Alternative besteht darin, nur Boxen entlang einer Reihe zu sammeln. Das heißt:

0 0 1 1 1 0 0 0 1 1 1 1 0 

bewirkt:

skip 2 
draw 3 
skip 3 
draw 4 
skip 1 

Dadurch wird die Anzahl der Anrufe reduzieren Box von Caching, ohne dass zu ziehen (das heißt Sie Ihre Boxen on the fly bauen).

Wenn Sie größere Boxen erstellen möchten, würde ich einen Backtracking-Algorithmus vorschlagen, dort finden Sie die erste 1 und versuchen, die Box in alle Richtungen zu erweitern. Erstellen Sie eine Liste von Boxen und löschen Sie die 1: s wie Sie sie verwendet haben.

Answer 4

Werfen Sie einen Blick auf this article from Dr Dobb's Portal auf einen maximalen finden Rechteck in Ihrer Situation. Es ist eine sehr detaillierte Diskussion eines extrem effizienten Algorithmus, und ich denke, dass iteratives Wiederholen Ihr Problem lösen könnte.

Answer 5

Ich hatte ein ähnliches Problem zu lösen, unterstützt mein Algorithmus gezackte Arrays, ich habe es ausführlich getestet und kommentiert, aber es ist langsamer als joel-in-Gos Vorschlag: https://stackoverflow.com/a/13802336