For every edge of the polygon, find out it’s intersection with all the scan lines (This is a fairly straight forward process, because beginning with one tip of the edge, every incremental value of y gives the next scan line and hence a DDA type algorithm can be written to compute all such intersections very fast and quite efficiency. However, we leave this portion to the student). Build a list of all those (x,y) intersections
Sort the list so that the intersections of each scan line are at one place. Then sort them again with respect to the x coordinate values. (Understanding this concept is central to the algorithm). To simplify the operations, in stage 1, we simply computed the intersections of every edge with every (intersecting) scan line. This gives a fairly large number of (unordered) points. Now sort these points w.r.t. their y-values, i.e. the scan line values. Assuming that the first scan line has a y value of 1, we get the list of it’s intersections with every edge. Then of the scan line with value 2 and soon. At this stage, looking at the previous example, we have the intersections of ‘a’ listed first, then intersection of ‘b’ and then of ‘c’ Now sort these intersections separately w.r.t. x points. Then the points a1 and a2 appear in the order, similarly of b and c)
Remove the intersection points in pairs. The first of these points indicate the beginning of the series of pixels that should lie inside the polygon and the second one ends the series. (a1 and a2 in this case) . (In the case of the scan line b, we get two pairs of intersections, since we have two sets of pixels inside the polygon for that scan line, while an intermediate set lies outside). This information can be used to display the pictures.
