3

I'm creating a paint app with HTML canvas and I'm trying to implement a "paint bucket" tool that would detect any neighboring pixels with the same color as the pixel which was clicked upon, and fill it with a new color.

I'm getting an "Uncaught RangeError: Maximum call stack size exceeded", but I can't figure out what's wrong with my logic:

function fillTool(){
    theCanvas.mousedown(function(e){
        var baseColor = paintUtilities.getPixelColor(e.offsetX, e.offsetY);
        context.fillStyle = color;
        fillNeighbors(e.offsetX, e.offsetY, baseColor);
    });
}

function fillNeighbors(x, y, baseColor) {
    context.fillRect(x, y, 1, 1);
    if (x > 0 && paintUtilities.getPixelColor(x - 1, y) === baseColor) {
        fillNeighbors(x - 1, y, baseColor);
    }
    if (y > 0 && paintUtilities.getPixelColor(x, y - 1) === baseColor) {
        fillNeighbors(x, y - 1, baseColor);
    }
    if (x < theCanvas.attr("width") - 1 && paintUtilities.getPixelColor(x + 1, y) === baseColor) {
        fillNeighbors(x + 1, y, baseColor);
    }   
    if (y < theCanvas.attr("height") - 1 && paintUtilities.getPixelColor(x, y + 1) === baseColor) {
        fillNeighbors(x, y + 1, baseColor);
    }   

}
Noam
  • 587
  • 5
  • 11
  • 3
    Apparently `fillNeighbors` calls itself too many times. Hence one of your conditions might be incorrect. [Learn how to debug JavaScript](http://www.creativebloq.com/javascript/javascript-debugging-beginners-3122820), add some `console.log` statements, you'll figure it out. – Felix Kling May 15 '14 at 21:57
  • @FelixKling, obviously it does, but I don't see how it's going on infinitely – Noam May 15 '14 at 22:00
  • 1
    Because at some point you will end up with `x` being equal to the `width` - a coordinate that doesn't exist. `x` should only be allowed to go up to `width-1`. Same for `y` and `height`. – Niet the Dark Absol May 15 '14 at 22:01
  • Just log the variables and check their values. – Felix Kling May 15 '14 at 22:01
  • @Noam how big is the canvas? That is, what's the possible range of "x" and "y"? – Pointy May 15 '14 at 22:01
  • It might help to know what `paintUtilities` is. – Niet the Dark Absol May 15 '14 at 22:01
  • @Noam: It may not be infinite, but you've exceeded the "maximum call stack size." If that limit is 9,999 and you're painting 10,000 pixels (that's only a 100 x 100 pixel area), you've exceeded the recursion limit. You may need to break down the filling in of the pixels into smaller buckets, or find a different way to do it without recursion. – Cᴏʀʏ May 15 '14 at 22:02
  • 1
    Does [this answer](http://stackoverflow.com/a/2805230/551322) explain anything? – nrodic May 15 '14 at 22:02
  • You can break the loop with something like setTimeout(..,0). – Jonathan May 15 '14 at 22:03
  • Or use less recursion: [see here](http://stackoverflow.com/q/21630724/551322) – nrodic May 15 '14 at 22:04
  • @nrodic: Good link. Those limits are a lot lower than I thought they'd be. – Cᴏʀʏ May 15 '14 at 22:04
  • @Noam the way your code is written, I'm pretty sure it will use up as much stack as the number of pixels. That's almost certainly way beyond those limits linked in that other question. – Pointy May 15 '14 at 22:06
  • @nrodic good link indeed. My reaction is the same as Cory's. – Noam May 15 '14 at 22:07
  • 1
    In other words, there's nothing "wrong" with my logic, but my browser still can't handle so many function calls if I fill every individual pixel separately. Any other ideas for implementing this tool if not pixel by pixel? – Noam May 15 '14 at 22:10
  • 1
    You got yourself a Stack Overflow. – ArtOfCode May 15 '14 at 22:12
  • Noam: There is something wrong, see my updated answer below... – Hamza Kubba May 15 '14 at 22:14
  • 2
    @Noam [the Wikipedia article on flood fill](http://en.wikipedia.org/wiki/Flood_fill) has some ideas for basically building your own stack. – Pointy May 15 '14 at 22:17

2 Answers2

1

Actually on second look, I see the problem with your code, and it does have infinite recursion!

Let's say you start at x = 1, and x can go from 0 to 2. You first go left, and call the function recursively. That function will eventually go to the right! Then that cycle will repeat, forever. You need to track where you've visited, or pass the recursive function a direction to not go on, or something along those lines.

Hamza Kubba
  • 2,259
  • 14
  • 12
  • 1
    Except it also makes color checks - it won't recurse to a new position if that position has already been painted. – Pointy May 15 '14 at 22:17
  • For one thing, it will if the baseColor and the fillColor are the same. `console.log(x)` will probably show you that for whatever reason, this is already happening even if they're different. – Hamza Kubba May 15 '14 at 22:18
  • @HamzaKubba, I believe Pointy is right. And in a situation where the baseColor and the fillColor are the same, I will have a condition that won't start the color-fill to begin with – Noam May 15 '14 at 22:24
  • @Noam maybe `getPixelColor` doesn't give you an exact `===` match with the fill color, for reasons that could include rounding or antialiasing? Have you tried logging some values? – hobbs May 15 '14 at 23:03
0

Because it is a recursive function and in each if statement you call it again and again and again... that function has no base case.

Alek
  • 11
  • 5