Gibt es einen Algorithmus zusammenhängende gefärbte Bereiche in einem Raster zu bestimmen?

Question

ein Grundraster Given (wie ein Stück Millimeterpapier), wobei jede Zelle zufällig gefüllt mit einem von n Farben wurde, gibt es einen altbewährten Algorithmus gibt, die mir sagen, was zusammenhängende Bereiche (Gruppen von Zellen der gleichen Farbe, die an der Seite verbunden sind) gibt es? Sagen wir mal n ist ein sinnvoller, wie 5.

Ich habe einige Ideen, aber sie alle fühlen sich schrecklich ineffizient.

Answer 1

Der beste Algorithmus ist O (Anzahl der Zellen), und ist nicht auf die Anzahl der Farben bezogen.

Dies kann durch Iterieren durch die Zellen erreicht werden, und jedes Mal ein Besuch, der als besucht markiert wurde nicht, machen einen Graph Traversal alle benachbarten Zellen in diesem Bereich zu finden, und das Iterieren dann weiter.

Edit:

Hier ist ein einfaches Pseudocodebeispiel einer Tiefensuche, die ein leicht Graph Traversal zu implementieren:

function visit(cell) {
    if cell.marked return
    cell.marked = true
    foreach neighbor in cell.neighbors {
        if cell.color == neighbor.color {
            visit(neighbor)
        }
    }
}

Answer 2

Neben rekursiv die rekursive Antwort, können Sie einen Stapel verwenden, wenn die Rekursion zu langsam ist:

function visit(cell) {
    stack = new stack
    stack.push cell

    while not stack.empty {
        cell = stack.pop
        if cell.marked continue
        cell.marked = true
        foreach neighbor in cell.neighbors {
            if cell.color == neighbor.color {
                stack.push neighbor
            }
        }
    }
}

Answer 3

Sie könnten versuchen, auf jedem Platz eine Flutfüllung zu tun. Als die Flut Aufstriche, die Gitterquadrate in einem Array oder etwas, aufzeichnen und in einer nicht verwendeten Farbe, Farbe, sagt -1.

Answer 4

Der Wikipedia-Artikel über Flußfüllen könnte nützlich sein, um Sie hier: http: //en.wikipedia. org / wiki / Flood_fill

Answer 5

Union-finden hier funktionieren würde, auch. Tatsächlich Sie Ihre Frage als Problem zu einem Graphen formulieren können: die Eckpunkte sind die Gitterzellen, und zwei Ecken benachbart sind, wenn ihre Gitterzellen die gleiche Farbe haben. Sie versuchen, die angeschlossenen Komponenten zu finden.

Die Art und Weise Sie eine Vereinigungs-Suche Datenstruktur verwenden würde, ist wie folgt: zuerst eine Vereinigungs-Suche erstellen Datenstruktur mit so vielen Elementen wie Sie Zellen haben. Dann durchlaufen die Zellen und union zwei benachbarte Zellen, wenn sie die gleiche Farbe haben. Am Ende läuft find auf jeder Zelle und speichern Sie die Antwort. Zellen mit dem gleichen find sind in dem gleichen angrenzenden farbigen Bereich.

Answer 6

Wenn Sie ein wenig mehr Feinkorn Kontrolle wollen, könnte man denken, über die A * Algorithmus und die Heuristik verwenden, um ähnlich farbige Fliesen sind.

Answer 7

Sie durchlaufen die Regionen in einer Scanlinie, links-rechts-oben-unten gehen. Für jede Zelle machen Sie eine Liste der Zellen als das gleiche Speicherobjekt zwischen den Zellen geteilt. Für jede Zelle, fügen Sie die aktuelle Zelle in die Liste (entweder mit ihm geteilt oder erstellt). Dann, wenn die Zelle nach rechts oder unten die gleiche Farbe ist, teilen Sie diese Liste mit dieser Zelle. Wenn die Zelle bereits eine Liste hat, können Sie die Listen kombinieren und den Verweis auf das List-Objekt in jeder Zelle in den Listen mit der neuen vereinigten Liste aufgeführten ersetzen.

Dann in jeder Zelle befindet sich ein Verweis auf eine Liste, die alle zusammenhängenden Zelle mit dieser Zelle enthält. Dies kombiniert treffend die Arbeit der Floodfill zwischen jeder Zelle. Anstatt es für jede Zelle zu wiederholen. Da Sie die Listen haben die Daten mit den fusionierten Daten ersetzt werden iteriert nur durch eine Liste. Es wird O (n * c), wobei n die Anzahl der Zellen, und c ist ein Maß dafür, wie die Graph angrenzt. Ein völlig unzusammenhängend Raster wird n Mal. Ein vollständig zusammenhängendes 1-Farbdiagramm mit be n ^ 2/2 ist.