泛洪算法-忽略边缘 [英] floodfill algorithm - leaving out the edge

问题描述

到目前为止，我已经实现了Floodfill算法。我想对其进行调整，以免遗漏边缘。为了演示这一点，我上传了一张图片：

so far i have implemented a floodfill algorithm. I wanted to tweak it, so that it would leave out the edge. To demonstrate this i uploaded an image:

图片1是我要修改的图片。图片3是我的算法应该执行的操作。 图像2是我当前的结果。

Image 1 is the image that i want to modify. Image 3 is what my algorithm is supposed to do. Image 2 is my current result.

因此，在这种情况下，targetColor为白色，而replaceColor为绿色；

So in this case the targetColor is white and the replacementColor is green;

这是我到目前为止所做的伪代码。

Here is pseudocode of what i have done so far.

doFloodFill(x,y,targetColor,replacementcolor) {

    if (x and y not in bounds of image) {
       return
    }

    if (color(x,y) IS NOT targetColor) {
       return
    }

    if (color(x+1, y) IS NOT targetColorOfFloodFill AND color(x+1, y) IS NOT replacementColor OR
        color(x-1, y) IS NOT targetColorOfFloodFill AND color(x-1, y) IS NOT replacementColor OR
        color(x, y+1) IS NOT targetColorOfFloodFill AND color(x, y+1) IS NOT replacementColor OR
        color(y, y-1) IS NOT targetColorOfFloodFill AND color(x, y-1) IS NOT replacementColor) {
        return;
    }

    image.setColor(x, y, replacementColor)

    doFloodFill(x+3,y,targetcolor,replacementcolor)
    doFloodFill(x-3,y,targetcolor,replacementcolor)
    doFloodFill(x,y+3,targetcolor,replacementcolor)
    doFloodFill(x,y-3,targetcolor,replacementcolor)
}

此调整已实施到我的洪水填埋中。忽略它可以使FloodFill算法正常工作，而不会出现任何问题。实际的问题是：如何将边缘像素与区域内具有不同颜色的像素区分开？

This tweak is implemented into my floodfill. Leaving it out results in a working floodFill algorithm without any problems. The actual question would be: how can i differentiate an edge pixel from a pixel with different color within the area?

PS：我们可以假设x，y是从该区域内开始的。

推荐答案

我也会去补水。

还有另一个想法：

• 像往常一样充水


• 跟踪边框的一个像素：例如，最顶部的像素


• 然后像鼠标一样沿着边框寻找逃生并将其重新变为白色。

const canvas = document.querySelector('canvas');

const M = `
00000000000000000000
00000110011111110000
00001111111110000000
00011111111111100000
00111111111101110010
01111111101111110010
01111111111111110110
01111111111111111110
01111111111111111100
01111111111111111100
01111111111111111100
01111111111111111000
00111111111111111000
00111111111111110000
00011111111111100000
00000000000000000000
`.trim().split('\n').map(x=>x.trim().split('').map(x=>parseInt(x)))

const mat = ({ x, y }, v) => {
  if (v) {
    M[y][x] = v
  }
  return M[y][x]
}
const left = ({x,y}) => ({ x: y, y: -x })
const right = ({x,y}) => ({ x: -y, y: x })
const back = ({x, y}) => ({ x: -x, y: -y})
const front = (pos, { x, y }) => ({ x: pos.x + x, y: pos.y + y })
const splinter = { 
  pos: {
    x: 5, 
    y: 1
  },
  orig: {
    x: 5,
    y: 1
  },
  dir: { x: 1, y: 0 },
  atStart() {
    return this.pos.x === this.orig.x && this.pos.y === this.orig.y
  },
  move () {
    if (this.atStart() && mat(this.pos) === 2) { return false }
    // wall on left
    if (mat(front(this.pos, left(this.dir))) === 0) {
      // wall on front
      if (mat(front(this.pos, this.dir)) === 0) {
        // wall on right
        if (mat(front(this.pos, right(this.dir))) === 0) {
          this.dir = back(this.dir)
        } else {
          this.dir = right(this.dir)
        }
      }
      this.poop()
    } else {
      this.dir = left(this.dir)
    }
    this.moveForward()
    return true
  },
  moveForward () {
    this.pos.x += this.dir.x
    this.pos.y += this.dir.y
  },
  poop () {
    mat({ x: this.pos.x, y: this.pos.y }, 2)
  },
  sprite () {
    if (this.atStart()) { return 'X' }
    if (this.dir.x === -1 && this.dir.y === 0) { return '←' }
    if (this.dir.x === 1 && this.dir.y === 0) { return '→'}
    if (this.dir.x === 0 && this.dir.y === 1) { return '↓' }
    if (this.dir.x === 0 && this.dir.y === -1) { return '↑' }
  }
}

function redraw () {
  const ctx = canvas.getContext('2d')
  const dw = canvas.width / M[0].length
  const dh = canvas.height / M.length
  const fill = ({ x, y }, color) => {
    ctx.fillStyle = color
    ctx.fillRect(x * dw, y * dh, dw, dh)
  }
  const colors = {
    1: 'green',
    0: 'black',
    2: 'white'
  }
  M.forEach((row, i) => {
    row.forEach((el, j) => {
      fill({ x: j, y: i }, colors[el])
    })
  })
  const char = splinter.sprite()
  ctx.strokeText(char, (splinter.pos.x + 0.1) * dw, (splinter.pos.y + 0.8) * dh)
}
redraw()
document.querySelector('button').onclick = _ => {
  splinter.move(); redraw()
}
document.querySelector('button.allmoves').onclick = _ => {
  while(splinter.move()){}
  redraw()
}

canvas{background:#eeeeee;}

<canvas width="160" height="160"></canvas>
<button>move, rat</button>
<button class="allmoves">move for your life, rat</button>

这篇关于泛洪算法-忽略边缘的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！