10

フラッドフィルに似たアルゴリズムを実装しようとしています。問題は、それをどのように実装すべきかわからないことです。たとえば、再帰的-非再帰的です。
それぞれに欠陥があることは知っていますが、そのうちの1つは他の1つよりも高速である必要があります。非再帰が毎回4つの新しいポイントを割り当てると、再帰はスタック上で新しい関数を開きます。
非反復の例：

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));
        }
    }

編集：600X600ピクセルのマップに次のアルゴリズムを適用します。塗りつぶしはマップ全体に適用されるわけではありませんが、反復ごとにマップの約30％〜80％をカバーする必要があります。私のポイントは、高さマップでエッジを検出し、さらに使用するためにそれらのエッジにマークを付けることです。

4

3 に答える 3

2

マスクを作成します - バイトの並列 2-dim 配列。未チェックの領域のバイトは 0 で、浸水領域の新しい境界の場合は値 1 になります。浸水領域の内側の場合は値 2 になります。また、現在の境界点のリストも保持します。

外側のサイクルの任意の端に、マークされた現在の境界線、内側と外側の領域、および境界点の配列を持つマスクがあります。そのため、境界でのみ新しいポイントを確認します。また、境界点の最初の配列リストを確認しながら、2 番目の境界配列リストと 2 番目のマスクを作成しています。次のステップでは、最初の境界配列とマスクを再作成します。このようにするwhileと、再帰の代わりに単純なサイクルを使用できます。これは、任意のステップでチェックするデータ構造が非常に単純であるためです。

ところで、描画された境界線または長方形全体の境界線上にある新しいポイントの座標を確認するのを忘れました。

隣接するすべてのポイントの循環については、ここで私のアルゴリズムを見てください

于 2012-02-16T20:39:07.723 に答える
0

イメージが複雑な場合、再帰的なフラッド フィルはスタックをオーバーフローさせる可能性があります。非再帰的なフラッド フィルを使用します。

割り当てが気になる場合は、ポイントを long 型のパックされた値として表現し、long 値を内部的に配列に格納する独自の LongStack をコーディングできます。

于 2012-02-16T20:43:20.860 に答える