5

みなさん、FloodFill を実行する方法はいくつかあります。それらはすべて問題を引き起こします。3 つの方法をリストし、それぞれで何が起こるかを説明します。誰かが私にいくつかの指針を与えることができれば、それは素晴らしいことです. 同様の投稿をいくつか見たことがありますが、C#、Java、または VB.net (私が知っている唯一の言語) に関するものはありません。

これは、CellColor メンバー変数に Color を格納する PixelData というクラスがあることを前提としています。「ピクセル」と呼ばれるサイズの PixelData オブジェクトの 50x50 の配列があります。この場合は 50 の CANVAS_SIZE という定数もあります。私が試した3つの方法を紹介します。

これは再帰的です。スタックオーバーフローが非常に発生しやすいです。このメソッドの完了後に CanFill メンバーを有効にするタイマーを設定しようとしました。これでもオーバーフローは防げません:

private void FloodFill(Point node, Color targetColor, Color replaceColor)
{
  //perform bounds checking X
  if ((node.X >= CANVAS_SIZE) || (node.X < 0))
    return; //outside of bounds

  //perform bounds checking Y
  if ((node.Y >= CANVAS_SIZE) || (node.Y < 0))
    return; //ouside of bounds

  //check to see if the node is the target color
  if (pixels[node.X, node.Y].CellColor != targetColor)
    return; //return and do nothing
  else
  {
    pixels[node.X, node.Y].CellColor = replaceColor;

    //recurse
    //try to fill one step to the right
    FloodFill(new Point(node.X + 1, node.Y), targetColor, replaceColor);
    //try to fill one step to the left
    FloodFill(new Point(node.X - 1, node.Y), targetColor, replaceColor);
    //try to fill one step to the north
    FloodFill(new Point(node.X, node.Y - 1), targetColor, replaceColor);
    //try to fill one step to the south
    FloodFill(new Point(node.X, node.Y + 1), targetColor, replaceColor);

    //exit method
    return;
  }
}

次に、キュー ベースの塗りつぶしを使用するメソッドがあります。このメソッドは、実行時に OutOfMemory Exceptions を引き起こし、キャンバス全体を塗りつぶすと非常に遅くなります。キャンバスのごく一部を埋めるだけであれば、ある程度効果的です。

private void QueueFloodFill(Point node, Color targetColor, Color replaceColor)
{
  Queue<Point> points = new Queue<Point>();
  if (pixels[node.X, node.Y].CellColor != targetColor)
    return;

  points.Enqueue(node);

  while (points.Count > 0)
  {
    Point n = points.Dequeue();
    if (pixels[n.X, n.Y].CellColor == targetColor)
      pixels[n.X, n.Y].CellColor = replaceColor;

    if (n.X != 0)
    {
      if (pixels[n.X - 1, n.Y].CellColor == targetColor)
        points.Enqueue(new Point(n.X - 1, n.Y));
    }

    if (n.X != CANVAS_SIZE - 1)
    {
      if (pixels[n.X + 1, n.Y].CellColor == targetColor)
        points.Enqueue(new Point(n.X + 1, n.Y));
    }

    if (n.Y != 0)
    {
      if (pixels[n.X, n.Y - 1].CellColor == targetColor)
        points.Enqueue(new Point(n.X, n.Y - 1));
    }

    if (n.Y != CANVAS_SIZE - 1)
    {
      if (pixels[n.X, n.Y + 1].CellColor == targetColor)
        points.Enqueue(new Point(n.X, n.Y + 1));
    }
  }
  DrawCanvas();
  return;
}

私が試した最後の方法でも、キュー ベースのフラッドフィルを使用します。この方法は、以前のキュー ベースのフラッドフィルよりもはるかに高速ですが、最終的には実行時に OutOfMemory 例外が発生します。繰り返しますが、ユーザーがすばやくクリックするのを防ぐ FillDelay タイマーを設定しようとしましたが、それでも例外の発生は止まりません。これに関するもう 1 つのバグは、小さな領域を適切に塗りつぶすのに苦労することです。クラッシュしないようにするまで、これを修正しても意味がありません。

private void RevisedQueueFloodFill(Point node, Color targetColor, Color replaceColor)
{
  Queue<Point> q = new Queue<Point>();
  if (pixels[node.X, node.Y].CellColor != targetColor)
    return;

  q.Enqueue(node);
  while (q.Count > 0)
  {
    Point n = q.Dequeue();
    if (pixels[n.X, n.Y].CellColor == targetColor)
    {
      Point e = n;
      Point w = n;
      while ((w.X != 0) && (pixels[w.X, w.Y].CellColor == targetColor))
      {
        pixels[w.X, w.Y].CellColor = replaceColor;
        w = new Point(w.X - 1, w.Y);
      }

      while ((e.X != CANVAS_SIZE - 1) && (pixels[e.X, e.Y].CellColor == targetColor))
      {
        pixels[e.X, e.Y].CellColor = replaceColor;
        e = new Point(e.X + 1, e.Y);
      }

      for (int i = w.X; i <= e.X; i++)
      {
        Point x = new Point(i, e.Y);
        if (e.Y + 1 != CANVAS_SIZE - 1)
        {
          if (pixels[x.X, x.Y + 1].CellColor == targetColor)
            q.Enqueue(new Point(x.X, x.Y + 1));
        }
        if (e.Y - 1 != -1)
        {
          if (pixels[x.X, x.Y - 1].CellColor == targetColor)
            q.Enqueue(new Point(x.X, x.Y - 1));
        }
      }
    }
  }
}

みんなの助けに感謝します！これらのメソッドはすべて、wikipedia の疑似コードに基づいています。

編集：

RevisedQueueFloodFill を選択し、提案​​どおりに変更して、ループ内で変数が宣言されないようにしました。OutOfMemory は引き続き生成されます。filldelay タイマーを使用しても。

private void RevisedQueueFloodFill(Point node, Color targetColor, Color replaceColor)
{
  Queue<Point> q = new Queue<Point>();

  if (pixels[node.X, node.Y].CellColor != targetColor)
    return;

  q.Enqueue(node);

  Point n, e, w, x;
  while (q.Count > 0)
  {
    n = q.Dequeue();
    if (pixels[n.X, n.Y].CellColor == targetColor)
    {
      e = n;
      w = n;
      while ((w.X != 0) && (pixels[w.X, w.Y].CellColor == targetColor))
      {
        pixels[w.X, w.Y].CellColor = replaceColor;
        w = new Point(w.X - 1, w.Y);
      }

      while ((e.X != CANVAS_SIZE - 1) && (pixels[e.X, e.Y].CellColor == targetColor))
      {
        pixels[e.X, e.Y].CellColor = replaceColor;
        e = new Point(e.X + 1, e.Y);
      }

      for (int i = w.X; i <= e.X; i++)
      {
        x = new Point(i, e.Y);
        if (e.Y + 1 != CANVAS_SIZE - 1)
        {
          if (pixels[x.X, x.Y + 1].CellColor == targetColor)
            q.Enqueue(new Point(x.X, x.Y + 1));
        }
        if (e.Y - 1 != -1)
        {
          if (pixels[x.X, x.Y - 1].CellColor == targetColor)
            q.Enqueue(new Point(x.X, x.Y - 1));
        }
      }
    }
  }
}
4

4 に答える 4

1

わかりましたいくつかのこと：

  1. C# には、数千の深さの再帰制限 (スタック サイズによって決定される) があります。これは、スタック オーバーフローを引き起こさずに下向きの再帰で DEEPER に進むことができないことを意味します。メソッドが返されるとすぐに、そのポインターはスタックからポップされます。あなたの問題は OutOfMemoryException と同じではありません。スタックは、実際のメモリではなくポインターを保持するため、何千ものポインターを保持することを意図していません。

  2. ガベージ コレクションは、メモリ不足の例外の原因です。ループ内で変数を宣言するのをやめる必要があります。ガベージ コレクターはこれらを「まだスコープ内」と見なし、ループがすべての反復を完了するまでメモリ領域を解放しません。ただし、同じメモリアドレスを使用すると、毎回上書きされるだけで、メモリはほとんど使用されません。

明確にするために：

for (int i = w.X; i <= e.X; i++)
{
    Point x = new Point(i, e.Y);
}

次のようにする必要があります。

Point x;

for(int i = w.X; i<= e.X; i++)
{
   x = new Point(i, e.Y);
}

これにより、必要に応じてメモリアドレスが再利用されます。

それが役立つことを願っています!

于 2011-08-04T20:20:21.747 に答える
1

これが機能するかどうかはわかりませんが、私自身の疑いでは、すべての「新しい」演算子が原因で必要以上に多くのメモリが使用されており、おそらくアルゴリズムの集中的な性質のために、ガベージ コレクターは機能しませんでした。キックインするチャンスはありますか？

すべての Point 変数が再利用されるようにアルゴリズムを書き直しましたが、現在これをテストする方法がありません。

コードの最初の数行を自由に変更することもできましたが、これは、実際にはできるのに、ほとんどのフラッドフィル アルゴリズムでは、ユーザーがターゲットの色を指定する必要があることがわかっているためです。引数で指定されたポイントからターゲット カラーを自動的に取得するだけです。

とにかく、これを使ってみるか、それ以外の場合はただ笑ってください:

private void RevisedQueueFloodFill(Point node, Color replaceColor)
{
    Color targetColor = pixels[node.X, node.Y].CellColor;
    if (targetColor == replaceColor) return;

    Queue<Point> q = new Queue<Point>();
    q.Enqueue(node);

    Point n, t, u;

    while (q.Count > 0)
    {
        n = q.Dequeue();
        if (pixels[n.X, n.Y].CellColor == targetColor)
        {

            t = n;
            while ((t.X > 0) && (pixels[t.X, t.Y].CellColor == targetColor))
            {
                pixels[t.X, t.Y].CellColor = replaceColor;
                t.X--;
            }
            int XMin = t.X + 1;


            t = n;
            t.X++;
            while ((t.X < CANVAS_SIZE - 1) &&
                   (pixels[t.X, t.Y].CellColor == targetColor))
            {
                pixels[t.X, t.Y].CellColor = replaceColor;
                t.X++;
            }
            int XMax = t.X - 1;

            t = n;
            t.Y++;

            u = n;
            u.Y--;

            for (int i = XMin; i <= XMax; i++)
            {
                t.X = i;
                u.X = i;

                if ((t.Y < CANVAS_SIZE - 1) &&
                    (pixels[t.X, t.Y].CellColor == targetColor)) q.Enqueue(t);

                if ((u.Y >= 0) &&
                    (pixels[u.X, u.Y].CellColor == targetColor)) q.Enqueue(u);
            }
        }
    }
}
于 2011-09-01T17:16:18.443 に答える
0

ここでの基本的なアルゴリズムの問​​題は、ポイントへの複数の訪問をキューに入れ、幅優先検索を行うことです。これは、パスごとに同じポイントの複数のコピーを作成することを意味します。これは、ターゲット カラーでなくても (既に置き換えられている)、各ポイントが広がる (より多くのポイントをキューに入れる) ことができるため、指数関数的に累積されます。

(デキュー時ではなく) エンキューと同時に色を設定して、キューに 2 回追加することはありません。

于 2011-09-01T18:57:07.817 に答える
0

3 番目の方法では、現在のポイントのすぐ西と東のピクセルを確認する必要があります。チェックする代わりに、チェックpixels[w.X, w.Y]する必要がありpixels[w.X - 1, w.Y]、代わりに. これがあなたの3番目の方法に対する私の見解です：pixels[e.X, e.Y]pixels[e.X + 1, e.Y]

private void RevisedQueueFloodFill(Point node, Color targetColor, Color replaceColor)
{
    if (pixels[node.X, node.Y].CellColor != targetColor) return;

    Queue<Point> Q = new Queue<Point>();
    Q.Enqueue(node);

    while (Q.Count != 0)
    {
        Point n = Q.Dequeue();
        if (pixels[n.X, n.Y].CellColor == targetColor)
        {
            int y = n.Y;
            int w = n.X;
            int e = n.X;
            while (w > 0 && pixels[w - 1, y].CellColor == targetColor) w--;
            while (e < CANVAS_SIZE - 1 && pixels[e + 1, y].CellColor == targetColor) e++;

            for (int x = w; x <= e; x++)
            {
                pixels[x, y].CellColor = replaceColor;
                if (y > 0 && pixels[x, y - 1].CellColor == targetColor)
                {
                    Q.Enqueue(new Point(x, y - 1));
                }
                if (y < CANVAS_SIZE - 1 && pixels[x, y + 1].CellColor == targetColor)
                {
                    Q.Enqueue(new Point(x, y + 1));
                }
            }
        }
    }
}
于 2011-08-08T22:32:31.603 に答える