P5 洪水填充尝试

Question

我一直在尝试使用初始的 mouseX 和 mouseY 值创建填充函数。在尝试使用 4 路递归方法失败后，我发现一篇文章建议使用数组存储 4 路值并使用 .push() 函数将它们排队。当数组有值时，该函数将使用 .pop() 函数为 x 和 y 设置新值，然后测试并更改为所需的颜色。

在尝试使用这种方法进行洪水填充后，我仍在努力获得与速度相关的任何性能。我试图包含一个额外的检查历史记录功能来存储访问过的像素的历史记录，并防止任何重复的 x、y 坐标被推回到队列中。但是（当使用控制台记录 "match found" 时）该函数似乎没有找到任何重复项。

对于如何改进我目前所写代码的任何指导，我将不胜感激。或者也许是关于实施起来并不复杂的不同方法的建议。我很少使用 Stack Overflow，也希望获得有关如何格式化问题和代码以供将来参考的指导。感谢您的宝贵时间。

使用我包含的 sketch.js，您可以看到填充函数在非常小的对象（第一个初始方块）上是可以接受的，但是随着大小的增加，性能逐渐停止。

index.html

<!DOCTYPE html>
<html>
  <head>
    <script src="p5.min.js"></script>
    <script src="sketch.js"></script>
    <style> body {padding: 0; margin: 0;} </style>
  </head>
  <body>
  </body>
</html>

sketch.js

var colorNew = [0,255,0,255];
function setup()
{
    createCanvas(500,500);
    squares();
}

function squares(){

    background(255); 
    noFill();
    stroke(0);
    rect(125,125,10,10);
    rect(125,125,20,20);
    rect(125,125,30,30);
    rect(125,125,40,40);
    rect(125,125,50,50);
    updatePixels();
}

function getPixData(xPos,yPos){    
    colorOld = get(xPos,yPos);
};

function checkValue(xPos,yPos,oldColor){    
    var currentPix
    currentPix = get(xPos,yPos);
    if(currentPix[0] == oldColor[0] && currentPix[1] == oldColor[1] && currentPix[2] == oldColor[2] && currentPix[3] == oldColor[3]){        
        return true;
    }    
};

function checkHistory(x1,y1,historyArray){    
    for (var i = 0 ; i < historyArray.length; i+=2){        
        if(x1 == historyArray[i] && y1 == historyArray[i+1]){            
            console.log("match found");           
            return false;                    
           }else {               
           console.log(historyArray.length)
           return true;             
            }
    } 
};


function floodFill (xPos,yPos){ 
    getPixData(mouseX,mouseY);    
    var stack = [];
    var historyList = [];
    stack.push(xPos,yPos);
    historyList.push(xPos,yPos);    
    console.log(stack);

    while(stack.length> 0){
        var yPos1 = stack.pop();
        var xPos1 = stack.pop();   
        set(xPos1,yPos1,colorNew); 
        updatePixels();

        if(xPos1+1 <= width && xPos1+1 > 0 ){
            if(checkValue(xPos1+1,yPos1,colorOld) && checkHistory(xPos1+1,yPos1,historyList)){
                stack.push(xPos1+1,yPos1);
                historyList.push(xPos1+1,yPos1);
                console.log("right checked")            
            }
        }

        if(xPos1+1 <= width && xPos1+1 > 0 ){
            if(checkValue(xPos1-1,yPos1,colorOld) && checkHistory(xPos1-1,yPos1,historyList)){
                stack.push(xPos1-1,yPos1);
                historyList.push(xPos1-1,yPos1);
                console.log("left checked");            
            }
        }
        if(yPos1+1 <= height && yPos1+1 > 0 ){
            if(checkValue(xPos1,yPos1+1,colorOld) && checkHistory(xPos1,yPos1+1,historyList)){
                stack.push(xPos1,yPos1+1);
                historyList.push(xPos1,yPos1+1);
                console.log("above checked");         
            }
        }

        if(yPos1-1 <= height && yPos1-1 > 0 ){
            if(checkValue(xPos1,yPos1-1,colorOld) && checkHistory(xPos1,yPos1-1,historyList)){
                stack.push(xPos1,yPos1-1);
                historyList.push(xPos1,yPos1-1);
                console.log("below checked");
            }
        }
    }      
    console.log(historyList);     
}

function draw()
{

    if(mouseIsPressed){
        floodFill(mouseX,mouseY)
    }

}

Answer 1

您的代码的行为肯定有问题。一些观察：

history 数组比应有的大很多。理论上你只添加每个像素一次，对吧？但是检查 history 数组的大小并注意它比像素数大得多。由于您将 x 和 y 值都添加到数组中，因此对于 10x10 的矩形，数组中应该有 200 个元素。但你最终得到的更多。

我也会避免像那样将 x 和 y 分量添加到数组中。相反，让每个索引都包含一个点对象。像这样：

stack.push({x:xPos,y:yPos});

这实际上并不能解决您的问题，但会使调试更容易。您的代码肯定包含错误。稍后我会尝试继续寻找更多内容，但希望这能让您走上正确的轨道。

Answer 2

主要的性能瓶颈是get(x,y) is slow。每次查看canvas的像素数据都要调用getImageData，大概需要4ms。

洪水填充算法必须检查每个像素一次，因此在 20x50 的正方形中，您必须检查 1000 个像素。如果每个像素检查需要 4 毫秒来获取颜色数据，那就是 4 秒！

p5 建议一些 performance optimization techniques 处理数据，其中之一是不要经常检查图像的像素。它建议提前缓存像素。幸运的是，p5 已经为您做到了。

p5 在 pixels 数组中创建图像所有颜色的数组。您可以使用 pixel 数组而不是使用 get 查看像素数据。该文档提供了如何 set/get 来自点 x,y:

的颜色数据的代码

function getPixData(x,y){
  var color = [];

  for (var i = 0; i < d; i++) {
    for (var j = 0; j < d; j++) {
      // loop over
      idx = 4 * ((y * d + j) * width * d + (x * d + i));
      color[0] = pixels[idx];
      color[1] = pixels[idx+1];
      color[2] = pixels[idx+2];
      color[3] = pixels[idx+3];
    }
  }

  return color;
};

function setPixData(x, y, colorNew) {
  for (var i = 0; i < d; i++) {
    for (var j = 0; j < d; j++) {
      // loop over
      idx = 4 * ((y * d + j) * width * d + (x * d + i));
      pixels[idx] = colorNew[0];
      pixels[idx+1] = colorNew[1];
      pixels[idx+2] = colorNew[2];
      pixels[idx+3] = colorNew[3];
    }
  }
}

如果将get(x,y)和set(x,y)的引用替换为这两个方法，并在setup方法中调用loadPixels，您将看到惊人的速度改进。并且不要忘记在方法结束时调用 updatePixels。

function floodFill (xPos,yPos){
    colorOld = getPixData(xPos, yPos);
    var stack = [];
    var historyList = [];
    stack.push(xPos,yPos);
    historyList.push(xPos,yPos);
    console.log(stack);

    while(stack.length> 0){
        var yPos1 = stack.pop();
        var xPos1 = stack.pop();
        setPixData(xPos1,yPos1,colorNew);

        if(xPos1+1 <= width && xPos1+1 > 0 ){
            if(checkValue(xPos1+1,yPos1,colorOld) && checkHistory(xPos1+1,yPos1,historyList)){
                stack.push(xPos1+1,yPos1);
                historyList.push(xPos1+1,yPos1);
                console.log("right checked")
            }
        }

        if(xPos1+1 <= width && xPos1+1 > 0 ){
            if(checkValue(xPos1-1,yPos1,colorOld) && checkHistory(xPos1-1,yPos1,historyList)){
                stack.push(xPos1-1,yPos1);
                historyList.push(xPos1-1,yPos1);
                console.log("left checked");
            }
        }
        if(yPos1+1 <= height && yPos1+1 > 0 ){
            if(checkValue(xPos1,yPos1+1,colorOld) && checkHistory(xPos1,yPos1+1,historyList)){
                stack.push(xPos1,yPos1+1);
                historyList.push(xPos1,yPos1+1);
                console.log("above checked");
            }
        }

        if(yPos1-1 <= height && yPos1-1 > 0 ){
            if(checkValue(xPos1,yPos1-1,colorOld) && checkHistory(xPos1,yPos1-1,historyList)){
                stack.push(xPos1,yPos1-1);
                historyList.push(xPos1,yPos1-1);
                console.log("below checked");
            }
        }
    }

    updatePixels();
    console.log(historyList);
}

此外，我建议将 draw 函数更改为使用 mouseClicked 而不是 mousePressed，因为 mousePressed 会在鼠标移动时持续运行按住，而 mouseClicked 只会在用户松开鼠标后运行一次。

P5 洪水填充尝试

P5 Flood Fill Attempt

javascript

stack

flood-fill

p5.js