User Tools

Site Tools


Differences

This shows you the differences between two versions of the page.

Link to this comparison view

Next revision
Previous revision
flood-fill [2012/11/05 22:23]
will created
flood-fill [2015/02/02 08:28] (current)
Line 7: Line 7:
 [algorithm flood-fill] [algorithm flood-fill]
  
-An optimised version of this algorithm maintains a stack of scanlines rather than pixels to test. This saves a lot of pixel tests over the basic algorithm.+An optimised version of this algorithm maintains a stack of scanlines rather than pixels to test. This saves a lot of pixel tests over the basic algorithm. The scanline flood fill algorithm works by scanning a line, and adding ranges on the next/​previous lines to a stack. For a shape with no loops or thin walls which are filled on both sides the scanline algorithm will only test each pixel once. It achieves this by skipping testing the range of pixels that the current line was filled from. 
 + 
 +A rough outline of the algorithm is: 
 +  - Add the starting range [x, y] to a stack. 
 +  - While there is a range to fill: 
 +    - Extend the current range left and right. 
 +    - Add new ranges on the previous and next lines that overlap the current range to the stack. Skip testing the range of pixels that the current range was created from.
  
 [algorithm flood-fill scanline] [algorithm flood-fill scanline]
flood-fill.txt · Last modified: 2015/02/02 08:28 (external edit)