stackoverflow in recursion

2

i'm making kinda ms paint application, that draws conture and fill inside.I wrote recursive function that fills conture. It works fine ,but if conture is too big program throws stackoverflow exception. How can i solve this problem?? i even can't catch this exception((

using System;
using System.Collections.Generic;
using System.ComponentModel;
using System.Data;
using System.Drawing;
using System.Linq;
using System.Text;
using System.Windows.Forms;
using System.Runtime.InteropServices;

namespace WindowsFormsApplication1
{
    public partial class Form1 : Form
    {

[DllImport( "user32.dll" )]
static extern IntPtr GetDC( IntPtr hWnd );
[DllImport( "user32.dll" )]
static extern int ReleaseDC( IntPtr hWnd, IntPtr hDC );
[DllImport( "gdi32.dll" )]
static extern int GetPixel( IntPtr hDC, int x, int y );
[DllImport( "gdi32.dll" )]
static extern int SetPixel( IntPtr hDC, int x, int y, int color );

static public Color GetPixel( Control control, int x, int y )
{
    Color color = Color.Empty;
    if (control != null)
    {
        IntPtr hDC = GetDC( control.Handle );
        int colorRef = GetPixel( hDC, x, y );
        color = Color.FromArgb(
            (int)(colorRef & 0x000000FF),
            (int)(colorRef & 0x0000FF00) >> 8,
            (int)(colorRef & 0x00FF0000) >> 16 );
        ReleaseDC( control.Handle, hDC );
    }
    return color;
}
static public void SetPixel( Control control, int x, int y, Color color )
{
    if (control != null)
    {
        IntPtr hDC = GetDC( control.Handle );
        int argb = color.ToArgb();
        int colorRef =
            (int)((argb & 0x00FF0000) >> 16) |
            (int)(argb & 0x0000FF00) |
            (int)((argb & 0x000000FF) << 16);
        SetPixel( hDC, x, y, colorRef );
        ReleaseDC( control.Handle, hDC );
    }
}

        int oldX, oldY;
        public Form1()
        {
            InitializeComponent();
        }



        private void button1_Click(object sender, EventArgs e)
        {
            Graphics g = panel1.CreateGraphics();
            g.Clear(panel1.BackColor);
        }
        bool paint;

        private void Form1_Load(object sender, EventArgs e)
        {

        }

        private void panel1_MouseDown(object sender, MouseEventArgs e)
        {
            oldX = e.X;
            oldY = e.Y;
            paint = true;
        }

        private void panel1_MouseUp(object sender, MouseEventArgs e)
        {
            paint = false;
        }

        private void panel1_MouseMove(object sender, MouseEventArgs e)
        {
            if (paint)
            {
                Graphics g = panel1.CreateGraphics();
                Pen p = new Pen(Color.Black);
                g.DrawLine(p, oldX, oldY, e.X, e.Y);
                oldX = e.X;
                oldY = e.Y;
            }
        }

        private void panel1_MouseDoubleClick(object sender, MouseEventArgs e)
        {
            fill(e.X, e.Y, Color.Black, Color.Red);
            Color c = GetPixel(panel1, e.X, e.Y);
            ClearButton.BackColor = c;
            label1.Text = e.X + " " + e.Y;

        }
        private void fill(int x, int y, Color border, Color c) {

            Color PointedColor = GetPixel(panel1, x, y);

            try { 
                        if (PointedColor.R != border.R && PointedColor.G != border.G && PointedColor.B != border.B &&
                PointedColor.R != c.R && PointedColor.G != c.G && PointedColor.B != c.B &&
                x >= 0 && x < panel1.Size.Width && y >= 0 && y < panel1.Size.Height)
            {
                SetPixel(panel1, x, y, c);

                fill(x - 1, y, border, c);
                fill(x + 1, y, border, c);
                fill(x, y - 1, border, c);
                fill(x, y + 1, border, c);

            }

            }
            catch(System.StackOverflowException e)
            {
                label1.Text = e.Message;
            }

        }
    }
}
c#
stack-overflow
asked on Stack Overflow Feb 12, 2012 by Nate

2 Answers

2

You should use a non-recursive flood fill algorithm.

For a description see the wikipedia article

Bob Powell has some source code here.

Note that attempting to solve the issue of the current stack overflowing by creating a new thread every time is a very expensive solution: going with a simple non-recursive solution is definitely the better approach. Creating additional threads to overcome the stack issue is not the right use of threads. If you thought you could get better performance by using multiple threads, even then you should go with a non-recursive solution.

answered on Stack Overflow Feb 12, 2012 by Chris Taylor • edited Dec 30, 2020 by Andrew Morton
1

You are not allowed to catch a StackOverflowException by design:

Starting with the .NET Framework version 2.0, a StackOverflowException object cannot be caught by a try-catch block and the corresponding process is terminated by default. Consequently, users are advised to write their code to detect and prevent a stack overflow. For example, if your application depends on recursion, use a counter or a state condition to terminate the recursive loop.

I’m sure there are more efficient ways of achieving this. However, to start you off, you can convert your recursion to an iteration by reifying the call stack as a Stack<T>:

private void fill(int xInitial, int yInitial, Color border, Color c) 
{
    var remaining = new Stack<Tuple<int, int>>();
    remaining.Push(Tuple.Create(xInitial, yInitial));

    while (remaining.Any())
    {
        var next = remaining.Pop();
        int x = next.Item1;
        int y = next.Item2;

        Color PointedColor = GetPixel(panel1, x, y);

        if (PointedColor.R != border.R && 
            PointedColor.G != border.G && 
            PointedColor.B != border.B &&
            PointedColor.R != c.R && 
            PointedColor.G != c.G && 
            PointedColor.B != c.B &&
            x >= 0 && 
            x < panel1.Size.Width && 
            y >= 0 && 
            y < panel1.Size.Height)
        {
            SetPixel(panel1, x, y, c);
            remaining.Push(Tuple.Create(x - 1, y));
            remaining.Push(Tuple.Create(x + 1, y));
            remaining.Push(Tuple.Create(x, y - 1));
            remaining.Push(Tuple.Create(x, y + 1));
        }
    }
}
answered on Stack Overflow Feb 12, 2012 by Douglas • edited Feb 12, 2012 by Douglas

User contributions licensed under CC BY-SA 3.0