Paint bucket getting "Maximum Call Stack Size Exceeded" error-CodePudding

This is the code of the paint bucket tool in my drawing app using the p5.js library. The function self.floodFill always get "Maximum Call Stack Size Exceeded" because of recursion and I want to know the way to fix it. I am thinking if changing the function to a no recursion function would help or not. Any help would be appreciated.

function BucketTool(){
    var self = this;
    //set an icon and a name for the object
    self.icon = "assets/bucket.jpg";
    self.name = "Bucket";
    var d = pixelDensity();
    
    var oldColor;
    var searchDirections = [[1,0],[-1,0],[0,1],[0,-1]];
    
    var pixelsToFill = [];
    var positionArray = new Array(2);
    
    self.checkBoundary = function(currentX, currentY, localOldColor) {
        if (self.getPixelAtXYPosition(currentX,currentY).toString() != localOldColor.toString() || currentX < 0 || currentY < 0 || currentX > width || currentY > height || pixelsToFill.indexOf(currentX " " currentY) != -1) {
            return false;
        }
        return true;
    };
    
    self.floodFill = function(currentX, currentY, localOldColor, localSearchDirections) {
        if (self.checkBoundary(currentX, currentY, localOldColor)){
            pixelsToFill.push(currentX " " currentY);
        } else {
            return;
        }
        for (var i = 0; i < searchDirections.length; i  ){
            self.floodFill(currentX   searchDirections[i][0], currentY   searchDirections[i][1], localOldColor, localSearchDirections);
        }
    };
    
    self.getPixelAtXYPosition = function(x, y) {
        var colour = [];
        for (var i = 0; i < d; i  ) {
          for (var j = 0; j < d; j  ) {
            // loop over
            index = 4 * ((y * d   j) * width * d   (x * d   i));
            colour[0] = pixels[index];
            colour[1] = pixels[index 1];
            colour[2] = pixels[index 2];
            colour[3] = pixels[index 3];
          }
        }
        return colour;
    }
    
    self.drawTheNeededPixels = function(){
        for(var i = 0; i < pixelsToFill.length; i  ){
            positionArray = pixelsToFill[i].split(" ");
            point(positionArray[0],positionArray[1]);
        }
    }
    
    self.draw = function () {
        if(mouseIsPressed){
            pixelsToFill = [];
            
            loadPixels();
            
            oldColor = self.getPixelAtXYPosition(mouseX, mouseY);
            
            self.floodFill(mouseX, mouseY, oldColor, searchDirections);
            
            self.drawTheNeededPixels();
        }
        
    };
    
}

CodePudding user response：

This problem is well documented on the wikipedia page and the shortfalls of the different types of algorithms to perform flood filling. You've gone for the stack-based recursive implementation.

To prevent a stackoverflow — Maximum Call Stack Exceeded — the first step would be to use a data structure. Using queues/stacks rather than having the function call itself.

The code below creates an empty stack where we put a new object containing the x and y where the user has chosen to fill. This is then added to the pixelsToFill array. We then loop the stack until it's completely empty, at which point we are ready to display the filled pixels.

In the while loop we pop an element off the stack and then find its children — the directions up, down, left, right denoted by the searchDirections array you created. If we've not seen the child before and it's within the boundary we add it to the pixelsToFill array and add it to the stack to repeat the process:

self.floodFill = function (currentX, currentY, localOldColor, localSearchDirections) {
    let stack = [];
    stack.push({ x: currentX, y: currentY });
    pixelsToFill.push(currentX   " "   currentY);
    while (stack.length > 0) {
      let current = stack.pop();
      for (var i = 0; i < searchDirections.length; i  ) {
        let child = {
          x: current.x   searchDirections[i][0],
          y: current.y   searchDirections[i][1],
          localOldColor,
        };
        if (self.checkBoundary(child.x, child.y, localOldColor)) {
          pixelsToFill.push(child.x   " "   child.y);    
          stack.push(child);
        }
      }
    }
  };

This code may stop the stackoverflow but there are still a lot of optimisations that can be made. Once again, it's worth checking out the Wikipedia page and potentially take a look at Span filling.

let bucketTool;
function setup() {
  createCanvas(400, 400);
  bucketTool = new BucketTool();
}

function draw() {
  background(220);
  strokeWeight(5);
  circle(width / 2, height / 2, 100);
  frameRate(1);
  bucketTool.draw();
}

function BucketTool() {
  var self = this;
  //set an icon and a name for the object
  // self.icon = "assets/bucket.jpg";
  // self.name = "Bucket";
  var d = pixelDensity();

  var oldColor;
  var searchDirections = [
    [1, 0],
    [-1, 0],
    [0, 1],
    [0, -1],
  ];

  var pixelsToFill = [];
  var positionArray = new Array(2);

  self.checkBoundary = function (currentX, currentY, localOldColor) {
    if (
      self.getPixelAtXYPosition(currentX, currentY).toString() !=
        localOldColor.toString() ||
      currentX < 0 ||
      currentY < 0 ||
      currentX > width ||
      currentY > height ||
      pixelsToFill.indexOf(currentX " " currentY) != -1
    ) {
      return false;
    }
    return true;
  };

  self.floodFill = function (currentX, currentY, localOldColor, localSearchDirections) {
    let stack = [];
    stack.push({ x: currentX, y: currentY });
    pixelsToFill.push(currentX   " "   currentY);
    while (stack.length > 0) {
      let current = stack.pop();
      for (var i = 0; i < searchDirections.length; i  ) {
        let child = {
          x: current.x   searchDirections[i][0],
          y: current.y   searchDirections[i][1],
          localOldColor,
        };
        if (self.checkBoundary(child.x, child.y, localOldColor)) {
          pixelsToFill.push(child.x   " "   child.y);    
          stack.push(child);
        }
      }
    }
  };

  self.getPixelAtXYPosition = function (x, y) {
    var colour = [];
    for (var i = 0; i < d; i  ) {
      for (var j = 0; j < d; j  ) {
        // loop over
        index = 4 * ((y * d   j) * width * d   (x * d   i));
        colour[0] = pixels[index];
        colour[1] = pixels[index   1];
        colour[2] = pixels[index   2];
        colour[3] = pixels[index   3];
      }
    }
    return colour;
  };

  self.drawTheNeededPixels = function () {
    for (var i = 0; i < pixelsToFill.length; i  ) {
      positionArray = pixelsToFill[i].split(" ");
      point(positionArray[0], positionArray[1]);
    }
  };

  self.draw = function () {
    if (mouseIsPressed) {
      pixelsToFill = [];

      loadPixels();

      oldColor = self.getPixelAtXYPosition(mouseX, mouseY);
      self.floodFill(mouseX, mouseY, oldColor, searchDirections);

      console.log(pixelsToFill.length);
      self.drawTheNeededPixels();
    }
  };
}

html, body {
  margin: 0;
  padding: 0;
}
canvas {
  display: block;
}

<!DOCTYPE html>
<html lang="en">
  <head>
    <script src="https://cdnjs.cloudflare.com/ajax/libs/p5.js/1.4.1/p5.js"></script>
    <script src="https://cdnjs.cloudflare.com/ajax/libs/p5.js/1.4.1/addons/p5.sound.min.js"></script>
    <link rel="stylesheet" type="text/css" href="style.css">
    <meta charset="utf-8" />

  </head>
  <body>
    <main>
    </main>
    <script src="sketch.js"></script>
  </body>
</html>