User Tools

Site Tools


λ Flood fill - scanline

======= Algorithm ======= <syntax js> function addNextLine(r, minX, maxX, newY, isNext, downwards, ranges) { var rMinX = minX; var inRange = false; for (var x=minX; x<=maxX; x++) { // skip testing, if testing previous line within previous range var empty = (isNext || (x<r.xMin || x>r.xMax)) && test(x, newY); if (!inRange && empty) { rMinX = x; inRange = true; } else if(inRange && !empty) { ranges.push({xMin:rMinX, xMax:x-1, y:newY, downward:downwards, extendLeft:rMinX===minX, extendRight:false}); inRange = false; } if (inRange) { paint(x, newY); } // skip if (!isNext && x===r.xMin) { x = r.xMax; } } if (inRange) { ranges.push({xMin:rMinX, xMax:x-1, y:newY, downward:downwards, extendLeft:rMinX===minX, extendRight:true}); } } function floodFillScanline(x, y, width, height, allowDiagonals) { // initalise the stack of ranges, downward is initially unknown var ranges = [{xMin:x, xMax:x, y:y, downward:null, extendLeft:true, extendRight:true}]; paint(x, y); while (ranges.length) { var r = ranges.pop(); // extend the range left var minX = r.xMin; var y = r.y; if (r.extendLeft) { while(minX > 0 && test(minX-1, y)) { minX--; paint(minX, y); } } // extend the range right var maxX = r.xMax; if (r.extendRight) { while(maxX < width-1 && test(maxX+1, y)) { maxX++; paint(maxX, y); } } if (allowDiagonals) { // extend range looked at for next lines if (minX > 0) minX--; if (maxX < width-1) maxX++; } else { // extend range ignored from previous line r.xMin--; r.xMax++; } // add ranges for the line above and the line below if (y < height) { var up = r.downward === false; addNextLine(r, minX, maxX, y+1, !up, true, ranges); } if (y > 0) { var down = r.downward === true; addNextLine(r, minX, maxX, y-1, !down, false, ranges); } } } </syntax> ======= Support ======= <syntax js> function run(diagonals) { reset(); floodFillScanline(15, 15, 50, 50, diagonals); } </syntax> ======= Tests ======= <syntax js> </syntax> ======= Options ======= <syntax js> { "title":"Flood fill - scanline" }</syntax> ======= Visualisation ======= <syntax html> <html> <head> <script> var canvas, ctx; var width = 50, height = 50; var map = [], drawMap = [], tests = []; // Run-length encoding of a smiley face var rle = [[50],[50],[50],[50],[50],[50],[19,11,20],[17,2,11,4,16],[16,1,17,2,14],[14,2,20,1,13], [13,1,23,2,11],[12,1,26,1,10],[11,1,27,1,10],[11,1,17,2,9,1,9],[10,1,20,2,8,1,8],[10,1,22,1,7,1,8], [10,1,23,1,7,1,7],[9,1,10,4,11,1,6,1,7],[9,1,8,3,2,2,10,1,6,1,7],[8,1,9,1,5,1,11,1,5,1,7], [8,1,9,1,5,1,11,1,5,1,7],[8,1,9,1,5,1,11,1,5,1,7],[8,1,9,1,5,1,11,1,5,1,7],[8,1,9,2,3,2,11,1,5,1,7], [8,1,10,5,12,1,5,1,7],[8,1,27,1,5,1,7],[8,1,27,1,5,1,7],[8,1,10,5,12,1,5,1,7], [8,1,10,1,3,2,11,1,5,1,7],[8,1,9,2,4,1,11,1,5,1,7],[8,1,9,1,5,1,10,1,6,1,7], [8,1,9,1,5,1,10,1,5,1,8],[9,1,8,1,5,1,9,1,6,1,8],[9,1,8,2,3,2,9,1,5,1,9],[10,1,8,5,9,1,5,1,10], [11,1,20,1,6,1,10],[11,1,18,2,6,1,11],[12,1,16,1,7,1,12],[13,2,20,2,13],[15,1,18,1,15], [16,1,15,2,16],[17,2,11,2,18],[19,11,20],[50],[50],[50],[50],[50],[50],[50]]; function loadRLE() { for(var i=0; i<width; i++) { var value = 0; var y = 0; map[i] = []; drawMap[i] = []; for(var j=0; j<rle[i].length; j++) { for(var k=0; k<rle[i][j]; k++) { map[i].push(value); drawMap[i].push(value); } value = value? 0 : 1; } } } function globals() { return { paint: paint, test: test, reset: reset }; } function args() { return document.getElementById("diagonals").checked; } function update(n, x) { // nothing } function reset() { clearMap(); loadRLE(); draw(); } function init() { canvas = document.getElementById("canvas"); ctx = canvas.getContext("2d"); reset(); } function paint(x, y) { map[x][y] = 2; drawCell(x, y); } function test(x, y) { if (x<0 || y<0 || x>=width || y>=height) return false; tests[x][y]++; if (document.getElementById("showTests").checked) { drawCell(x, y); } return (map[x][y] === 0); } function clearMap() { for(var i=0; i<width; i++) { map[i] = []; tests[i] = []; for(var j=0; j<height; j++) { map[i][j] = tests[i][j] = 0; } } draw(); } function drawCell(i, j) { if (document.getElementById("showTests").checked) { if (tests[i][j] > 0) { ctx.fillStyle = testColour(tests[i][j]); ctx.fillRect(i*4, j*4, 4, 4); } } else if(map[i][j] > 1) { var v = 50*(map[i][j]-2); ctx.fillStyle = "rgb("+v+","+(255-v)+",0)"; ctx.fillRect(i*4, j*4, 4, 4); } else if(map[i][j]) { ctx.fillStyle = '#333'; ctx.fillRect(i*4, j*4, 4, 4); } } function draw() { ctx.fillStyle = '#EEE'; ctx.fillRect(0,0,500,500); ctx.fillStyle = '#333'; for(var i=0;i<width;i++) { for(var j=0;j<height;j++) { drawCell(i, j); } } if (document.getElementById("showTests").checked) { for(var i=0; i<8; i++) { ctx.fillStyle = testColour(1+i); ctx.fillRect(i*16, 0, 16, 16); } ctx.strokeRect(-0.5, -0.5, 8*16, 16); } } function testColour(val) { val--; val = Math.floor(512*Math.acos(1-val/3.5)/Math.PI); return "rgb("+Math.min(255, val)+","+Math.min(255, 512-val)+",0)"; } </script> </head> <body onload="init()" style="height:850px"> <canvas id="canvas" style="margin-right:10px;border:2px grey solid" width=200 height=200></canvas> <div><input type="checkbox" id="showTests" onclick="draw()">Show pixels tested</div> <div><input type="checkbox" id="diagonals">Allow diagonals</div> </body> </html> </syntax>

algorithm/flood-fill_scanline.txt · Last modified: 2015/02/02 08:28 (external edit)