我一直在尝试使用初始 mouseX 和 mouseY 值创建洪水填充函数。在尝试 4 路递归方法并失败后，我发现一篇文章建议使用数组来存储 4 路值并使用 .push() 函数对它们进行排队。当数组有值时，该函数将使用 .pop() 函数为 x 和 y 设置新值，然后依次测试并更改为所需的颜色。
在尝试使用这种方法进行洪水填充后，我仍然在努力获得速度方面的任何性能。我尝试添加一个额外的检查历史记录功能来存储访问过的像素的历史记录，并防止任何重复的 x,y 坐标被推回到队列中。但是(当使用控制台记录“找到匹配”时)该函数似乎找不到任何重复。
我非常感谢任何关于如何改进我迄今为止编写的代码的指导。或者也许是关于实现起来并不复杂的不同方法的建议。我很少使用 Stack Overflow，并且也希望获得有关如何格式化问题和代码以供将来引用的指导。感谢您抽出宝贵的时间。
使用我包含的 sketch.js，您可以看到填充函数在非常小的对象(第一个初始方 block )上是可以接受的，但随着大小的增加，性能逐渐停止。
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>
草图.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)
}
}
最佳答案
主要的性能瓶颈是get(x,y) is slow 。每次都要调用getImageData来查看 Canvas 的像素数据，大约需要4毫秒。
洪水填充算法必须检查每个像素一次，因此在 20x50 的正方形中，您必须检查 1000 个像素。如果每个像素检查需要 4 毫秒才能获取颜色数据，那就是 4 秒!
p5 建议一些 performance optimization techniques处理数据，其中之一是不要经常检查图像的像素。它建议提前缓存像素。幸运的是，p5 已经为您做到了这一点。
p5 创建 pixels 中图像所有颜色的数组大批。您可以使用 pixel 数组来代替使用 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) 的引用替换为这两个方法，并调用 loadPixels在 setup 方法中，您将看到速度的巨大提升。并且不要忘记在方法末尾调用 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 仅在用户松开鼠标后运行一次。
关于javascript - P5 洪水填充尝试，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/49226914/