Wo würde ich nach Algorithmen 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 praktischeren Erklärung: Ich zeichne ein Gitter, das durch eine Anzahl von Quadraten dargestellt wird, und ich möchte einen Weg finden, so viele benachbarte Quadrate wie möglich in Rechtecke zu kombinieren, um die verbrachte Zeit zu reduzieren wenn man durch jedes Quadrat fährt und es zeichnet.
Maximale Effizienz wird nicht benötigt, Geschwindigkeit ist wichtiger.
Nachtrag: Scheinbar scheint das, was ich suche, eine Technik namens Tesselation zu sein. Jetzt muss ich nur eine gute Beschreibung für diesen speziellen Fall finden.
Nachtrag 2: Die Grenze der "1" Quadrate ist unregelmäßig und in einigen Fällen nicht einmal zusammenhängend, da die Verteilung von "1" Quadraten völlig zufällig ist. Ich muss diese unregelmäßigen Formen identifizieren und in regelmäßige Rechtecke aufteilen.
Richtige Antwort: Um ein optimales Verhältnis zwischen Geschwindigkeit und Effizienz zu erzielen, ist es optimal, die Gitterdaten zu verwenden, um einen Quad-Tree zu füllen, wobei jeder Knoten einen Statuswert von leer / teilweise gefüllt hat. gefüllt.
Ich habe etwas Ähnliches für eine schnell-und-schmutzige Voxel-Visualisierung von 3D-Boxen mit OpenGL getan.
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 habe das gleiche in der Richtung nach unten gemacht.
Zeichne das Rechteck, wenn es gefüllt ist.
Wenn weitere Kästchen vorhanden sind, wiederholen Sie rekursiv die Prozedur für alle drei verbleibenden Rechtecke, die durch das letzte Rechteck induziert wurden: rechts, unten und unten rechts:
%Vor%Schaut euch diesen Artikel von Dr. Dobbs Portal an , um ein maximales Rechteck in eurer Situation zu finden. Es ist eine sehr detaillierte Diskussion eines extrem effizienten Algorithmus, und ich denke, dass eine Wiederholung iterativ möglicherweise Ihr Problem lösen würde.
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.
Was die beste Lösung ist, hängt von Ihren Daten ab, aber eine einfache Alternative besteht darin, nur Boxen entlang einer Reihe zu sammeln. Ie:
%Vor%führt zu:
%Vor%Dadurch wird die Anzahl der Aufrufe der Zeichnungsbox reduziert, ohne dass ein Caching erforderlich ist (d. h. Sie können Ihre Boxen im laufenden Betrieb erstellen).
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.
Sie suchen also nach der rechteckigen Grenze der 'ON'-Quadrate?
Willst du 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?
Tags und Links geometry rectangles 2d area