Wie eine Fläche von kleinen Quadraten in größere Rechtecken zusammengesetzt teilen?

Question

Wo würde ich mich für Algorithmen zu suchen, die ein 2D-Gitter von Werten annehmen, die entweder 0 oder 1 als Eingabe und identifiziert dann alle möglichen nicht-überlappende Rechtecke in das?

In einer praktischeren Erklärung: Ich zeichne ein Raster, das durch eine Reihe von Quadraten dargestellt wird, und ich wünsche, einen Weg zu finden, wie viele benachbarten Quadrate in Rechtecke wie möglich zu kombinieren, um auf die Zeit zu verkürzen verbrachte auf dem Fahrrad durch jeden Platz und zeichnet es.

Maximale Effizienz ist nicht erforderlich, die Geschwindigkeit ist wichtiger.

Nachtrag: Anscheinend was ich suche scheint genannt Tesselation eine Technik zu sein. Jetzt brauche ich nur eine gute Beschreibung für diesen speziellen Fall zu finden.

Nachtrag 2: Die Grenze der „1“ Quadrate wird unregelmäßig und in einigen Fällen nicht einmal verbunden, wie die Verteilung von „1“ Quadraten wird völlig zufällig. Ich brauche diese unregelmäßigen Formen identifiziert und in regelmäßige Rechtecke aufgeteilt werden.

Richtige Antwort: , um die beste Balance zwischen Geschwindigkeit zu bekommen und Effizienz ist es optimal, die Rasterdaten zu verwenden, um einen Quad-Baum mit jedem Knoten einen Statuswert von entweder leer / teilweise gefüllt zu füllen, die / gefüllt.

Answer 1

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

Ich begann von dem linken oberen Feld und den leeren / gefüllt Flag gespeichert. Dann habe ich versucht, das Rechteck nach rechts zu erweitern, bis ich eine Box mit einer anderen Flagge getroffen. Ich tat das gleiche in der Abwärtsrichtung.

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

Hier finden Sie aktuelle diesen Artikel von Dr. Dobbs Portal auf ein maximales Rechteck in Ihrer Situation zu finden. Es ist eine sehr ausführliche Diskussion eines äußerst effizienten Algorithmus, und ich denke, dass es iteratives Wiederholen möglicherweise Ihr Problem lösen würde.

Answer 3

Wie Sie sind nicht für die minimale Anzahl von Plätzen suchen würde ich einen Kompromiss vorschlagen, mit noch Ihrem Algorithmus einfach hält.

Was ist die beste Lösung ist, hängt von Ihren Daten, sondern eine einfache Alternative ist nur Boxen entlang einer Reihe zu sammeln. Das heißt:

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

Wird ergeben:

skip 2
draw 3
skip 3
draw 4
skip 1

Damit 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 gibt Sie die ersten 1 finden und versuchen, das Feld in alle Richtungen zu erweitern. Erstellen Sie eine Liste von Kisten und deaktivieren Sie die 1: s., Wie Sie sie verwendet haben,

Answer 4

Sie sind also die Suche nach der rechteckigen Grenze des ‚ON‘ Quadrate?
Haben Sie die innere oder äußere Schranke wollen?
dh. Muss die Grenze nur ‚ON‘ Quadrate haben oder tun Sie das Rechteck alle ‚ON‘ Quadrate in einer Gruppe enthalten soll?

Answer 5

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