For advertisement here, contact at:

Scan Line Seed Fill Algorithm !

A seed pixel on a span is popped from a stack containing the seed pixel.

The span containing the seed pixel is filled to the right and left of seed pixel along a scan line until a boundary is found.

The algorithm remembers the extreme left and the extreme right pixel in the span as xleft and xright.

In the range of xleft ≤ x ≤ xright the scan lines immediately above & immediately below the current scan line are examined to see if they completely contain either boundary pixels or previously filled points. If these scan lines do not contain either boundary or previously filled pixels, then in the range Xleft ≥ x ≥ Xright the extreme right pixel in 0each span is marked as a seed pixel and pushed onto the stack.

The Seed Fill Algorithms assume that at least one pixel is interior to a polygon or region is known. The algorithm then attempts to find and color or fill all other pixels interior to the region.

The method of the seed fill is to start with a seed and recursively check neighboring points to fill in the polygon.

1).Start with a point known to be contained within the polygon. This is the seed.

2).Set the buffer for this seed and draw it.

3).Check each neighbor point. A neighbor point is a point for which the x and/or y values are exactly one greater or less than the current point's values. For each neighbor that is not a boundary point and is not already set, recursively call this function.

The following will demonstrate this method. The polygon below is outlined by black pixels. Start with the point (23, 11), as the seed. This is filled in blue. The buffer would be set so as not to draw this pixel again.

Then each neighbor would be checked. For example, let's check point (24, 10). This point is in the polygon, so we would recursively call the seed fill algorithm on it. At that point, the pixel would be drawn.

Then the neighbors of point (24, 10) would be checked. If we checked pointer (25, 9), we would see that it is a border point and not draw it or recursively call the seed fill algorithm. You can see that this method would lead to a slightly different polygon than one filled with the scan-line method. The top and left edges would not be drawn in the seed fill since no edges are drawn.

Back to

MCA Cource
KU's MCA Course


Survey of Computer Graphics Applications Interactive & Passive Graphics Introduction to GKS Primitives Display Processors

Graphic Devices

Display Systems-Refresh CRTs Raster Scan Monitors Random Scan Monitors Grey shades Interlacing Beam Penetration & Shadow Mask Monitors Look Up Tables Plasma Panel Flat-Panel Displays LED LCD VGA SVGA Hard Copy Devices Printers Plotters Interactive Input Devices Keyboard Mouse Digitizing Tablet Light Pen Touch Panels Image Scanners Voice systems Joy Stick Track Ball

Drawing Geometry

Coordinate System Resolution Homogeneous Coordinate System scan conversion DDA Symmetrical DDA Simple DDA Bresenhams Line Algorithm Circle Drawing Algorithm Polar Coordinates Bresenhams Circle Algorithm Ellipse

2-D Transformations

Transformations Translation Rotation Scaling Mirror Reflection Shearing Zooming Panning Postioning Pointing Rubber Band Methods Dragging Tweening

Graphic Operations

Clipping Points Clipping Line Clipping Sutherland-Cohen Algorithm Midpoint Sub-Division Algorithm Polygon Clipping Sutherland Hodgman Algorithm Window & Viewport Windowing Transformation Stack Based Fill Algorithm Scan-Line Seed Fill Algorithm

3-D Graphics

3D Modelling of Objects 3D display Techniques Coordinate System 3D Transformation Matrices For Translation, Scaling & Rotation Parallel Projection Perspective Projection Hidden Surface Removal Z-Buffer Back Face Scan-Line Depth-Sorting Area Subdivision Shading-Modelling Light Intensities Gouraud Shading Phong Shading


Hypertext or Hypermedia Multimedia Applications Authoring Hardware Components Windows paint brush

Post Your Answer

Post your answer at: