Scan Line Polygon filling Algorithm:-

Recursive algorithms for seed fill methods have got two difficulties:-

1. The first difficulty is that if some inside pixels are already displayed in fill colour then recursive branch terminates leaving further internal pixels unfilled.
2. Another difficulty with recursive seed fill methods is that it cannot be used for large polygons.

To avoid this problem more efficient method can be used. Such method fills horizontal pixels spans across scan lines, instead of proceeding to 4-connected or 8-connected neighbouring points.This is achieved by identifying the rightmost and leftmost pixels of the seed pixel and then drawing a horizontal line between these two boundary pixels. This procedure is repeated with changing the seed pixel above and below the line just drawn until complete polygon is filled. With this efficient method we have to stack only a beginning position for each horizontal pixel span, instead of stacking all unprocessed neighbouring positions around the current position.

The figure (a) illustrates the scan line algorithm for filling of polygon. For each scan line crossing a polygon, this algorithm locates the intersection points of the scan line with the polygon edges. These intersection points are then sorted from left to right, and the corresponding positions between each intersection pair are set to the specified fill colour.

In figure (a), we can see that there are two stretches of interior pixels from x =6 to x = 9 and x = 12 to x 15.The scan line algorithm first finds the largest and smallest y values of the polygon. It then starts with the largest y value and works its way down, scanning from left to right, in the manner of a raster display.

The important task in the scan line algorithm is to find the intersection points of the scan line with the polygon boundary.When intersection points are even,they are sorted from left to right,paired and pixels between paired points are set to the fill colour.But in some cases intersection point is a vertex. When scan line intersects polygon vertex a special handling is required to find the exact intersection points To handle such cases, we must look at the other endpoints of the two line segments of the polygon which meet at this vertex. If these points lie on the same (up or down) side of the scan line, then the point in question counts as an even number of intersections. If they lie on opposite sides of the scan line, then the point is counted as single intersection. This is illustrated in figure (b).

As shown in the figure (b), each scan line intersects the vertex or vertices of the polygon. For scan line 1, the other end points (B and D) of the two line segments of the polygon lie on the same side of the scan line, hence there are two intersections resulting two pairs: 1-2 and 3-4. Intersections points 2 and 3 are actually same points. For scan line 2, the other endpoints (D and F) of the two line segments of the polygon lie on the opposite sides of the scan line, hence there is a single intersection resulting two pairs: 1 -2 and 3 - 4. For scan line 3, two vertices are the intersection points. For vertex F the other end points E and C of the two line segments of the polygon lie on the same side of the scan line whereas for vertex H, the other endpoints G and I of the two line segments of the polygon lie on the opposite side of the scan line.Therefore, at vertex F there are two intersections and at vertex H there is only one intersection. This results two pairs: 1 -2 and 3-4 and points 2 and 3 are actually same points.

We have seen that it is necessary to calculate x intersection points for scan line with every polygon side. We can simplify these calculations by using Coherence Properties. A coherence property of a scene is a property of a scene by which we can relate one part of a scene with the other parts of a scene. Here, we can use a slope of an edge as a coherence Property. By using this property we can determine the x intersection value on the lower scan line if the x intersection value for current scan line is known. This is given as,

Where m is the slope of the edge.

As we scan from top to bottom value of y coordinates between the two scan line changes by 1.

Many times it is not necessary to compute the x intersections for scan line with every polygon side. We need to consider only the polygon sides with endpoints straddling the current scan line. See figure (c).

It will be easier to identify which polygon sides should be tested for x-intersection. if we first sort the sides in order of their maximum y value. Once the sides are sorted we can process the scan lines from the top of the polygon to its bottom producing an active edge list for each scan line crossing the polygon boundaries. The active edge list for a scan line contains all edges crossed by that scan line. The figure (d) shows sorted edges of the polygon with active edges.

A scan line algorithm for filling a polygon begins by ordering the polygon sides on the largest y value.It begins with the largest y value and scans down the polygon. For each y, it determines which sides can be intersected and finds the x values of these intersection points.It then sorts, pairs and passes these x values to a line drawing routine.

Scan Line Conversion Algorithm for Polygon Filling:-

1. Read n, the number or vertices or polygon. 
2. Read x and y coordinates of all vertices in array x[n] and y[n]. 
3. Find ymin and ymax. 
4. Store the initial x value (x1) y values y1 and y2 for two endpoints and x increment ∆x from scanline to scanline for  each edge in the array edges[n][4]. 
while doing this check that y1 > y2, if not interchange y1 and y2 and corresponding x1 and x2 so that for each edge, y1 represents its maximum y coordinate and y2 represents it minimum y co-ordinate. 
5. Sort the rows or array,edges [n][4] in descending order of y1,descending order of y2 and ascending order of x2. 
6. Set y=ymax. 
7. Find the active edges and update active edge list: 
      if(y > y2 and y ≤ y1) 
          { edge is active }
      else 
          { edge is not active }
8. Compute the x intersects for all active edges for current y value [initially x-intersect is x1 and x intersects for successive y values can be given as 
              xi + 1 <-- xi  + ∆x

          Where ∆x = 1/m   and m =  (y2 – y1 )/(x2- x1)      i.e. slope of a line segment 
9. if x intersect is vertex i.e. x-intersect = x1, and y = y1, then apply vertex test to check whether to consider one intersect or two intersects. Store all x intersects in the x-intersect [ ] array. 
10. Sort x-intersect [ ] array in the ascending order, 
11. Extract pairs of intersects from the sorted x-intersect [ ] array. 
12. Pass pairs or x values to line drawing routine to draw corresponding line segments 
13.Set y = y - 1 
14. Repeat steps 7 through 13 until y ≥ ymin
15. Stop 

In step 7, we have checked for y ≤ y1, and not simply y < y1. Hence step 9 becomes redundant.

.