Welcher Flood-Fill-Algorithmus ist besser für die Leistung?

Question

Ich versuche, einen Algorithmus zu implementieren, der dem Flood-Fill ähnelt. Das Problem ist, dass ich mir nicht sicher bin, auf welche Weise ich ihn implementieren soll, z.B. rekursiv oder nicht rekursiv.
Ich weiß, dass jeder seine Mängel hat, aber einer von ihnen muss schneller sein als der andere. die rekursive öffnet neue Funktion auf dem Stapel, wenn die nicht-rekursive 4 neue Punkte jedes Mal zuweist.
Beispiel für das nicht-iterative :

Stack<Point> stack = new Stack<Point>();
    stack.Push(q);
    while (stack.Count > 0)
    {
        Point p = stack.Pop();
        int x = p.X;
        int y = p.Y;
        if (y < 0 || y > h - 1 || x < 0 || x > w - 1)
                continue;
        byte val = vals[y, x];
        if (val == SEED_COLOR)
        {
                vals[y, x] = COLOR;
                stack.Push(new Point(x + 1, y));
                stack.Push(new Point(x - 1, y));
                stack.Push(new Point(x, y + 1));
                stack.Push(new Point(x, y - 1));
        }
    }

edit : ich werde den folgenden Algorithmus auf eine 600X600 Pixel Karte anwenden. obwohl das Floodfill nicht auf die gesamte Karte angewendet werden wird, sollte es etwa 30% - 80% der Karte bei jeder Iteration abdecken. mein Ziel ist es, Kanten in einer Höhenkarte zu entdecken und diese Kanten für eine weitere Verwendung zu markieren.

Answer 1

Erstellen Sie eine Maske - ein paralleles 2-Dim-Array von Bytes. Ungeprüfte Bereiche haben den Wert 0, für die frische Grenze des überfluteten Bereichs wird der Wert 1 verwendet. Für das Innere des überfluteten Bereichs - Wert 2. Und behalten Sie auch die Liste der aktuellen Grenzpunkte.

An jedem Ende des äußeren Zyklus haben Sie die Maske mit dem markierten aktuellen Rand, dem Innen- und Außenbereich und dem Array der Randpunkte. Es wird also nur am Rand nach neuen Punkten gesucht. Und während Sie die erste Array-Liste der Randpunkte prüfen, erstellen Sie die zweite Rand-Array-Liste und die zweite Maske. Im nächsten Schritt erstellen Sie das erste Rand-Array und die erste Maske neu. Auf diese Weise können wir einfache while Zyklus anstelle einer Rekursion, denn die Datenstruktur, die Sie in jedem Schritt überprüfen, ist sehr einfach.

Übrigens haben Sie vergessen, die Koordinaten der neuen Punkte daraufhin zu überprüfen, ob sie auf dem gezeichneten Rand oder auf dem Rand des gesamten Rechtecks liegen.

Was das Durchlaufen aller benachbarten Punkte angeht, sehen Sie sich meinen Algorithmus an aquí

Answer 2

Computer verarbeiten XY-Schleifen und 2D-Arrays sehr effizient.

In diesem Video sehen Sie, was passiert, wenn Sie die rekursive Standardroutine in eine Schleife einfügen: https://www.youtube.com/watch?v=LvacRISl99Y

Anstatt eine komplexe Logik zu verwenden, um zuvor verifizierte Nachbarräume zu verfolgen, können Sie ein 2D-Array verwenden, das alle verifizierten Räume aufzeichnet. Das Lesen aus dem verifizierten Array erfordert 2-3 Anweisungen: WENN Pixel[23,23] verifiziert ist, DANN füllen Sie es und überprüfen seine Nachbarn.

Answer 3

Ein rekursives Flood-Fill kann den Stack überlaufen lassen, wenn das Bild komplex ist. Verwenden Sie die nicht-rekursive Flutfüllung.

Wenn Sie sich um die Zuweisungen kümmern, können Sie einen Punkt als gepackten Wert vom Typ long darstellen und einen eigenen LongStack programmieren, der die long-Werte intern in einem Array speichert.