Polygon filling algorithm

This presentation contains -
- Polygon Filling Algorithm
- Inside Test - Even Odd Test
- Scanline Polygon Filling Algorithm
- Seed Filling Approach
- Boundary Fill Algorihtm
- Edge Fill Algorithm
- 4-connected polygon
- 8-connected polygon
- Flood Fill Algorithm

1. Polygon Filling Algorithm Presented by Asst. Prof. Aparna Joshi

2. Polygon Filling Algorithm An ordered list of vertices forms a  polygon . Polygon Filling :- The pixels that fall on the border of the  polygon  are determined and the pixels that fall inside are determined in order to color the  polygon . Polygons are easier to fill since they have linear boundaries. Filling the polygon means highlighting all the pixels which lie inside the polygon with any color other than the background color.

3. Polygon Filling There are two basic approaches used to fill the polygon.

4. Point Inside Test – Even-Odd Method Once the polygon is entered in the display file, we can draw the outline of the polygon. To show polygon as a solid object we have to set the pixel inside the polygon as well as pixels on the boundary of it. Now the question is how to determine whether or not a point is inside of a polygon. One simple method of doing this is to draw a line segment and count how many intersections of the line segment with the polygon boundary occur. If there are an odd number of intersections, then the point is inside, otherwise it is outside. This method is called the even-odd method of determining polygon inside points . This inside test or Even-Odd method is used in scan line method of polygon filling.

5. Scanline Polygon Filling Algorithm Scanline filling is basically filling up of polygons using horizontal lines or scanlines. The purpose of the SLPF algorithm is to fill (color) the interior pixels of a polygon given only the vertices of the figure. This algorithm works by intersecting scanline with polygon edges and fills the polygon between pairs of intersections. These intersection points are then sorted from left to right, and the corresponding positions between each intersection pair are set to the specified fill color.

6. Scanline Polygon Filling Algorithm Step 1  − Find out the Ymin and Ymax from the given polygon. Step 2  − Scanline intersects with each edge of the polygon from Ymin to Ymax. Name each intersection point of the polygon. As per the figure shown above, they are named as p0, p1, p2, p3 . Step 3  − Sort the intersection point in the increasing order of X coordinate i.e . (p0,p1),(p1,p2) and (p2,p3). Step 4  − Fill all those pair of coordinates that are inside polygons and ignore the alternate pairs.

7. Special cases of polygon vertices: If both lines intersecting at the vertex are on the same side of the scanline, consider it as two points. If lines intersecting at the vertex are at opposite sides of the scanline, consider it as only one point.

8. Basic Terms Spatial Coherence :- The adjacent pixels are likely to have the same characteristics in polygons. This property is called spatial coherence. Scan line Coherence :- Adjacent pixels on a scan line are likely to have the same characteristics. This is called scan line coherence.

9. Seed Filling Approach One way to fill a polygon is to start from a given “seed”, point known to be inside the polygon and highlight outward from this point i.e. neighboring pixels until we encounter the boundary pixels. Seed fill approach is of two types – Boundary Fill ( Edge Fill algorithm ) and Flood Fill (Seed Fill )

10. Boundary Fill Algorithm / Edge Fill Algorithm : This algorithm picks a point inside an object and starts to fill until it hits the boundary of the object. The color of the boundary and the color that we fill should be different for this algorithm to work. In this algorithm, we assume that color of the boundary is same for the entire object. Then starting with some seed, any point inside the polygon we examine the neighboring pixels to check whether the boundary pixel is reached. If boundary pixels are not reached, pixels are highlighted and the process is continued until boundary pixels are reached . The boundary fill algorithm can be implementd by 4-connected pixels or 8-connected pixels. (a) Four Connected Region (b) Eight Connected Region

11. Boundary Fill / Edge Fill Algorithm Boundary Fill Algorithm starts at a pixel inside the polygon to be filled and paints the interior proceeding outwards towards the boundary. This algorithm works only if the color with which the region has to be filled and the color of the boundary of the region are different . If the boundary is of one single color, this approach proceeds outwards pixel by pixel until it hits the boundary of the region. Boundary Fill Algorithm is recursive in nature.  It takes an interior point(x, y), a fill color, and a boundary color as the input. The algorithm starts by checking the color of (x, y). If it’s color is not equal to the fill color and the boundary color, then it is painted with the fill color and the function is called for all the neighbours of (x, y ). If a point is found to be of fill color or of boundary color, the function does not call its neighbours and returns. This process continues until all points up to the boundary color for the region have been tested.

12. 4-Connected Polygon In this technique, 4-connected pixels are used as shown in figure. We are putting the pixels – above, below, to the right and to the left of the current pixels and this process will continue until we find a boundary with different color.

13. 4-Connected Polygon Filling Algorithm

14. 8-Connected Polygon   More complex figures are filled using this approach. The pixels to be tested are the 8 neighboring pixels, the pixel on the right, left, above, below and the 4 diagonal pixels . Areas filled by this method are called 8-connected.

15. 8-Connected Polygon Algorithm

16. Flood Fill Algorithm or Seed fill Algorithm Sometimes it is required to fill in an area that is not defined within a single color boundary. In such cases we can fill areas by replacing a specified interior color instead of searching for a boundary color. This approach is called a flood-fill algorithm. Like boundary fill algorithm, here we start with some seed and examine the neighboring pixels. However, here pixels are checked for a specified interior color instead of boundary color and they are replaced by new color. Using either a 4-connected or 8-connected approach, we can stop through pixel positions until all interior point have been filled. Recursive algorithm for seed fill methods have difficulty as - The first difficulty is that if some inside pixels are already displayed in fill color then recursive branch terminates, leaving further internal pixels unfilled. To avoid this difficulty, we have to first change the color of any internal pixels that are initially set to the fill color before applying the seed fill procedures

17. 4-connected pixels Vs 8-connected pixels 4-connected pixels Vs 8-connected pixels : Let us take a figure with the boundary color as GREEN and the fill color as RED. The 4-connected method fails to fill this figure completely. This figure will be efficiently filled using the 8-connected technique .

18. Flood Fill Vs Boundary Fill In Flood fill, all the connected pixels of a selected color get replaced by a fill color. On the other hand, in Boundary fill, the program stops when a given color boundary is found.

19. Questions on Polygon Filling Algorithm 1. Explain boundary fill algorithm in detail 2. Explain the steps required to fill the polygon using flood fill technique. 3. What are the steps involved in filling a polygon using the scanline method ? 4. Explain the boundary fill method for 4-connected region to fill a polygon. 5. Write a short note on polygon filling. 6. Explain the scanline algorithm for polygon filling. 7. Describe any one method to test whether the point is inside a polygon. 8. Write a boundary fill procedure to fill 4-connected region. 9. When eight-way symmetry is used to obtain a full circle from pixel coordinates generated for the 0 to 45 or the line 90 to 45 octant, certain pixels are set or plotted twice. This phenomenon is sometimes referred to as overstrike. Identify the locations where overstrike occurs.  At locations resulted from the initial coordinates (r, 0) or (0, r) since (0, r) = (-0, r), (0,-r) = (-0, -r), (r, 0 ) = (r, -0) and (-r, 0 ) = ( -r, -0) 10. What is 4-connected and 8-connected method ?

20. Thank You