Polygon Filling Method: Scan Line Algorithm

Scan line algorithm is a polygon fill method in which rightmost and the left most pixels of the seed pixel are marked and a horizontal line is drawn between them. The process is continued by locating more seed pixels upwards and downwards.

Scan Line Algorithm:

1. Read n, number of vertices of polygon.
2. Read x and y coordinates of all vertices  in array x[n] and y[n]
3. Find ymin and ymax.
4. Store initial x value (x1), y values y1 and y2 for two end points and x increment Δx from scan line to scan line for each edge in array edges [n] [4]
While check y1>y2, if not interchange y1 and y2 and corresponding x1 and x2 so that for each edge, y1 represents its maximum y co-ordinate and y2 represents its minimum y co-ordinate.
5. Sort the rows of array, edges [n] [4] in descending order of y1, descending order of y2, and ascending order of x2.
6. Set y = ymax
7. Find active edges and update active edge list:
If (y > y2 and y ≤ y1)
{edge is active}
{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:
xi+1 <– xi + Δx
where Δx = -(1/m) and m= (y2-y1)/(x2-x1) = slope of a line segment.
9. If x intersect is vertex i.e. x-intersect=x1 and y=y1 then apply vertex check to test whether to consider one intersect or two intersects. Store all x-intersects in the x-intersect array.
10. Sort x-intersect array in ascending order.
11. Extract pairs of intersects from the sorted x-intersect array.
12. Pass pairs of x values to line drawing routines to draw corresponding line segments.
13. Set y = y-1
14. Repeat Steps 7 to 13 until y ≥ ymin.
15. Stop.

Leave a Reply