What are the steps for flood fill algorithm for filling the polygon?

Answer 1

Scan conversion algorithm for polygon filling

1. read n, the 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 the initial x value(x1) y values y1 and y2 for 2 end points and x increment from scan line to scan line 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 its minimum y coordinate.

5. Sort the rows of array, edges [n][4] in descending 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:

8. If(y > y2 and y <=y1)

9. { edge is active}

10. Else

11. { edge is not active}

12. 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

13. where =and m=i.e slope of a line segment

14. 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 2 intersects. Store all x intersects in the x-intersects [ ] array.

15. Sort x-intersects [ ] array in the ascending order

16. Extract pairs of intersects from the sorted x-intersect [ ] array

17. Pass pairs of x values to line drawing routine to draw corresponding line segments

18. Set y=y-1

19. Repeat step 7 through 18 until y>=ymin

20. Stop