Алгоритм "Bucket Fill" в Javascript или Coffeescript

Question

Я пишу небольшое приложение coffeescript / js, которое позволяет пользователю создавать иконки (16x16 пикселей или 32X32 пикселей).Значок на самом деле представляет собой двумерный массив с цветными ячейками.Ячейка может иметь цвет или быть пустой.

Я хочу, чтобы пользователь мог заполнять пустые ячейки инструментом "заливка".

Это означает, что

• если пользователь щелкает пустую ячейку, все ячейки, которые являются пустыми рядом с ячейкой, по которой щелкнули, будут заполнены выбранным цветом, пока она не достигнет цветной ячейки

• если пользователь нажимает на цветную ячейку, все ячейки, расположенные рядом с ячейкой, на которую щелкнули, и которая имеет одинаковый цвет, будут заполнены, но не пустые и не цветные (с другим цветом).

Приложение уже позволяет пользователю заполнять ячейки одну за другой выбранным цветом или удалять цветные ячейки с помощью инструмента «Перо».

Есть предложения?

(ps: я не использую HTML-холст для рисования)

Answer 1

Поскольку это только 16x16 или 32x32, вы можете использовать рекурсивное решение:

Скажем, ваша отправная точка - изменить пиксель x / y с цвета A на цвет B (A или B могут быть пустыми).

В псевдокоде:

function floodfill(x,y,A,B) {
  if ((x<0) || (x>15) || (y<0) || (y>15)) return;
  if (get_color(x,y)!=A) return;
  set_color(x,y,B);
  floodfill(x-1,y-1,A,B);
  floodfill(x-1,y,A,B);
  floodfill(x-1,y+1,A,B);
  floodfill(x,y-1,A,B);
  floodfill(x,y+1,A,B);
  floodfill(x+1,y-1,A,B);
  floodfill(x+1,y,A,B);
  floodfill(x+1,y+1,A,B);
}

Answer 2

Хорошо, вот как я решаю свою проблему в coffeescript.Это пример использования холста.скрипт должен запускаться на любой странице, где есть элемент canvas с идентификатором canvas, мне пришлось создать свой собственный стек из-за проблем переполнения стека.

log = ->
  console.log arguments

class Point
  constructor:(@x,@y)->

class BucketFiller
  MAXITERATION:100000
  factor:1
  fill : (ctx,pixel, colCible, colRep)->
    P = []
    max = @MAXITERATION
    if @getColorAtPixel(ctx,pixel)!=colCible then return null
    P.push(pixel)
    while  P.length > 0 and max >=0
      --max
      currentpixel = P.pop()
      @fillRect(ctx,currentpixel.x,currentpixel.y,@factor,@factor,colRep)
      if @isInCanvas(ctx,currentpixel)
        if @getColorAtPixel(ctx,@up(currentpixel)) == colCible then P.push(@up(currentpixel))
        if @getColorAtPixel(ctx,@down(currentpixel)) == colCible then P.push(@down(currentpixel))
        if @getColorAtPixel(ctx,@right(currentpixel)) == colCible then P.push(@right(currentpixel))
        if @getColorAtPixel(ctx,@left(currentpixel)) == colCible then P.push(@left(currentpixel))
    return

  fillRect:(ctx,x,y,width,height,color)->
    ctx.fillStyle = color
    ctx.fillRect(x,y,width,height)
    return
  down :(pixel)->
    return {x:pixel.x,y:pixel.y-@factor}

  up:(pixel)->
    return {x:pixel.x,y:pixel.y+@factor}

  right :(pixel)->
    return {x:pixel.x+@factor,y:pixel.y}

  left :(pixel)->
    return {x:pixel.x-@factor,y:pixel.y}

  getColorAtPixel:(ctx,pixel)->
    try
      imageData = ctx.getImageData(pixel.x,pixel.y,1,1)
    catch e
      return null
    return @rgbArrayToCssColorString(imageData.data)

  rgbArrayToCssColorString:(array)->
    result = "rgb(#{array[0]},#{array[1]},#{array[2]})"
    return result

  isInCanvas : (ctx,pixel)->
    result = ((0 <= pixel.x <= ctx.canvas.width) and (0 <= pixel.y <= ctx.canvas.height))
    return result

main=->
    buckfiller = new BucketFiller()
    log("start")
    canvas  = document.getElementById("canvas")
    ctx = canvas.getContext("2d")
    penPosition = new Point(2,10)
    fillColor = "rgb(255,0,0)"
    colCible = buckfiller.getColorAtPixel(ctx,penPosition)
    try
      buckfiller.fill(ctx,penPosition,colCible,fillColor)
    catch e
      log e

window.onload=->
  main()

Answer 3

Я не совсем уверен, какой тип предложений вы ищете, но вы должны взглянуть на алгоритмы заливки.

Вот это в Википедии: http://en.wikipedia.org/wiki/Flood_fill