Алгоритм «Bucket Fill» в Javascript или coffeescript

Question

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

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

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

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

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

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

Любые предложения?

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

Answer 1

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

Произнесите отправной точкой для изменения пикселя х/у от цвета 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

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

Здесь в Википедии: http://en.wikipedia.org/wiki/Flood_fill

Answer 3

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

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()