none
塗りつぶしによるスタックオーバーフローについて RRS feed

  • 質問

  • ネットで古い資料のC/C++のアルゴリズムの塗りつぶしを参考にして作成しました。
    画像サイズが大きいと、C#でスタックオーバーフローになりました。VisualStudioのデバッグの解決方法では無限再帰などを確認と表示されましたが、画像サイズが比較的に小さい場合はスタックオーバーフロにならず、保存もできます。したがって、スタックオーバーフローに達したのが原因と考えています。
    塗りつぶしのアルゴリズムで、塗りつぶした領域は塗りつぶさない。塗りつぶしの終端位置まで塗りつぶしたかどうかを調べる。塗る対象の色と塗りつぶす色が違う場合のみ塗りつぶす。この三点で塗りつぶしの無駄を省略して作成したはずですが、下記のアルゴリズムにおける不備はまだどこかにあるでしょうか。

    using System;
    using System.IO;
    using System.Collections.Generic;
    using System.Linq;
    using System.Text;

            /// <summary>
            /// データアドレス Bitmap画像のアドレス領域
            /// </summary>
            protected byte[] adr;

            public int stride;

            class Color
            {
                public byte A, R, G, B;

                public Color(byte a, byte r, byte g, byte b)
                {
                    A = a; R = r; G = g; B = b;
                }
            }

            class Point
            {
                public int X, Y;

                public Point(int x, int y)
                {
                    X = x; Y = y;
                }
            }

            /// <summary>
            /// Bitmapをマウス座標からアクセスした位置
            /// </summary>
            /// <param name="x"></param>
            /// <param name="y"></param>
            /// <returns></returns>
            protected int getArgbAdr(ref int x,ref int y)
            {
                return x * 4 + (stride * y);
            }

            /// <summary>
            /// 塗りつぶし
            /// </summary>
            /// <param name="x">マウス座標X</param>
            /// <param name="y">マウス座標Y</param>
            /// <param name="src">ペンの色</param>
            /// <param name="tar">塗潰す対象の領域の色</param>
            /// <param name="wide">このピクセル幅</param>
            /// <param name="hei">このピクセル高さ</param>
            protected void fillColor(int x, int y,
                ref byte[] src, ref byte[] tar,
                ref int wide, ref int hei)
            {
                // 塗りつぶすためにコピー作成
                fillAdr = new int[adr.Length];

                var srcCol=new Color(src[3], src[2], src[1], src[0]);
                var tarCol = new Color(tar[3], tar[2], tar[1], tar[0]);

                if (srcCol.A == tarCol.A &&
                    srcCol.R == tarCol.R &&
                    srcCol.G == tarCol.G &&
                    srcCol.B == tarCol.B)
                {

                }
                else
                    fillColor2(ref x, ref y,ref srcCol,ref tarCol, ref wide, ref hei);

                foreach (var list in FillList)
                {
                    int _x = list.Key.X;
                    int _y = list.Key.Y;

                    var endPt = list.Value;

                    if (endPt == -2 || endPt == -1)
                        SetPixel(ref _x, ref _y, ref srcCol);
                }
                FillList.Clear();
                FillEndList.Clear();

                fillAdr = null;
            }

            //塗りつぶす領域
            Dictionary<Point,int> FillList =
                new Dictionary<Point, int>();
            int[] fillAdr;
            // 塗りつぶしの終端位置
            Dictionary<Point, int> FillEndList =
                new Dictionary<Point, int>();
            void fillColor2(ref int x,ref int y,
                ref Color src,ref Color tar,
                ref int wide, ref int hei)
            {
                bool isFillOk = isFillEnable(ref x,ref y,ref tar);

                if (x < wide && y < hei && isFillOk)
                {
                    var fillPt = new Point(x, y);

                    var endCol = GetPixel(ref x, ref y);
                    if (endCol.A == tar.A &&
                        endCol.R == tar.R &&
                        endCol.G == tar.G &&
                        endCol.B == tar.B)
                    {
                        FillList.Add(fillPt, -1);// 塗りつぶす

                        var idx = getArgbAdr(ref x, ref y);
                        fillAdr[idx] = -1;

                        int Upp = y - 1;
                        if (hei > Upp && Upp >= 0)
                            if (isFillEnable(ref x, ref Upp, ref tar))
                                fillColor2(ref x, ref Upp,
                                    ref src, ref tar, ref wide, ref hei);

                        int migg = x + 1;
                        if (wide > migg)
                            if (isFillEnable(ref x, ref migg, ref tar))
                                fillColor2(ref migg, ref  y,
                                    ref src, ref tar, ref wide, ref hei);

                        int Downn = y + 1;
                        if (hei > Downn)
                            if (isFillEnable(ref x, ref Downn, ref tar))
                                fillColor2(ref x, ref Downn,
                                    ref src, ref tar, ref wide, ref hei);

                        int hidd = x - 1;
                        if (wide > hidd && hidd >= 0)
                            if (isFillEnable(ref x, ref hidd, ref tar))
                                fillColor2(ref hidd, ref  y,
                                    ref src, ref tar, ref wide, ref hei);
                    }
                }
            }

            /// <summary>
            /// 塗りつぶし可能
            /// </summary>
            /// <param name="x"></param>
            /// <param name="y"></param>
            /// <param name="tar">塗潰す対象の領域の色</param>
            /// <returns></returns>
            bool isFillEnable(ref int x, ref int y, ref Color tar)
            {
                bool isFillContain = false;
                var idx = getArgbAdr(ref x, ref y);
                if (idx < fillAdr.Length)
                {
                    var fillVal = fillAdr[idx];
                    if (fillVal == -2 || fillVal == -1)
                        isFillContain = true;//塗りつぶされている

                    bool isTarCol = false;
                    if (isFillContain == false)
                    {
                        var tarCol = GetPixel(ref x, ref y);
                        if (tarCol.A == tar.A &&
                            tarCol.R == tar.R &&
                            tarCol.G == tar.G &&
                            tarCol.B == tar.B)
                            isTarCol = true;// 塗りつぶしを許可
                        else
                        {
                            if (fillAdr[idx] == 0)
                            {
                                var fillPt = new Point(x, y);
                                FillEndList.Add(fillPt, -2);// 塗りつぶしの終端位置
                                FillList.Add(fillPt, -2);

                                fillAdr[idx] = -2;
                            }
                        }
                    }

                    if (isFillContain == false && isTarCol)
                        return true;
                }
                return false;
            }

    タッカ
    • 編集済み タッカ 2010年12月30日 1:40 無限再帰をスタックオーバーフローへ訂正
    2010年12月29日 16:24

回答

すべての返信

  • ソースは斜め読みしかしていませんが、本当にこんなに長いコードが必要なのでしょうか。

    DOBONさんのところで参考になりそうなリンクを貼っておきます。

    塗りつぶした図形を描く: .NET Tips: C#, VB.NET, Visual Studio

    領域を塗りつぶす: .NET Tips: C#, VB.NET, Visual Studio


    Blog:プログラマーな日々 http://d.hatena.ne.jp/JHashimoto/
    • 編集済み jhashimoto 2010年12月29日 18:39 リンク先の間違いを修正
    • 回答としてマーク タッカ 2010年12月30日 1:41
    2010年12月29日 18:36
  • 画像サイズが大きいと、C#でスタックオーバーフローになりました。VisualStudioのデバッグの解決方法では再帰などを確認と表示されましたが、画像サイズが比較的に小さい場合は再帰にならず、保存もできます。したがって、再帰が原因よりも、命令数の限界に達したのが原因と考えています。

    認識が間違っています。

    ×画像サイズが比較的に小さい場合は再帰にならず、保存もできます。

    ○画像サイズが比較的に小さい場合はスタックオーバーフローにならず、保存もできます。

    そもそも「再帰」とは何かをご存知でしょうか? 貼り付けられた範囲で言えば、fillColor2()メソッド内で再度 fillColor2()メソッドを呼び出していますが、こういう行為を再帰呼び出しと言います。

    引数にrefを多用していますが、この部分がC/C++からの移植で間違っているかもしれません。元のコードを見ないことにはわかりませんが。例えば、

    protected int getArgbAdr(int x, int y)
    {
      return x * 4 + (stride * y);
    }

    であるべきであり、また元のC/C++のコードもそうなっているはずです。そうなっていないとしたら参考にしたC/C++のコード自体、酷い作りだと思われます。

    2010年12月29日 23:25
  • 確かにそうですね。その辺のことを考慮して改良してみようと思います。
    タッカ
    2010年12月30日 1:09
  • 一応、refした理由はメソッドの引数に値型を入れた場合、値型は引数へコピーされるので、その無駄を省くためにrefしました。しかし、よく考えたら、計算した後に値型を生成するので意味はありませんでしたね。

    ご指摘にしたがってスタックオーバーフローに本文の方を訂正しました。寝る直前にコードを投稿したので、何が原因だったかな再帰だったかなっと考えていて書いたら本文の趣旨と食い違ってしまいました。


    タッカ
    2010年12月30日 1:37
  • 計算値をあらかじめ確保して、塗りつぶし領域を真に書き換えたら、うまくいきました。
    タッカ
    • 編集済み タッカ 2010年12月30日 6:29 訂正
    2010年12月30日 6:24