For non selfintersecting polygons, filling the area described by it is simple.If the polygons do intersect, there are many ways to fill the area described by the polygon. Actually only the polygon (list of points) itself does not make clear what should be filled and what not.

It only divides the 2D surface in pieces, which i call enclosed area, where each enclosed area is surrounded by a few of the polygon segments.

Depending on the filling method in use, one will decide if such an enclosed area should be filled or not.

2 filling methods are known, i like to discuss a third method, just for better understanding.

Alternate Filling

The most simple method is called alternate filling, using a scanline, or a ray, coming from the outside of the polygon, every crossing segment with the scanline switches filling on or off. So the first segment will always mean that after that segment filling will be on. The second one will always turn filling off. And so on.

In this method the direction of the segments, going left or right, is not important. Also the order in which the polygon points/segments are drawn is not important.

When passing a segment it is enough to know what filling the area had that we are leaving, based on that the filling for the coming area is known.

Figure 1 ( alternate filling )

Figure 2 ( alternate filling )

Winding Rule Filling

This method is called winding rule filling. Using a scanline, or a ray, coming from the outside of the polygon, every crossing segment with the scanline switches filling on or off, depending on the direction (going left or right) of the segment. So the first segment will always mean that after that segment filling will be on. The direction of the first segment is remembered, if the second segmenet has the same direction, filling will stay on, else it will be switched off.

If the thrid segment has the same direction as the first and second, filling will be 2 levels deep. So not only the direction of the segments, but also the number going left and right is used to decide what is filled or not.

If we arrive in an area that is not filled, an eqaul number of left and right going segments were passed, this which means filling depth is zero.

In this case the next segment on the scanline will switch filling on, no matter what the direction of the segment is.

When passing a segment it is NOT enough to know what filling the area had that we are leaving. The depth of that area needs to be known to decide what the filling of the coming area will be.

In pseudo code:

Coming from +infinity on the scanline:

depth = 0

for each segment passed on the scanline 
{
   if (segment is going left)

      depth--

   else # it is going right

      depth++

   if (depth == 0)

      filled=OFF

   else 

      filled=ON
}

In this method the direction of the segments, going left or right, is important. Also the number of segments going left and right is used.

The order in which the polygon points/segments are drawn is not important.

Although figure3 and figure5 would have the same filling using alternate filling, figure4 shows a difference.

Figure 3 ( winding rule filling )

Figure 4 ( winding rule filling )

Figure 5 ( winding rule filling )

Twisted Paper filling

The above to filling methods are easy to use in algorithms based on scanlines. But they also give less desired result in certain cases.

For Instance in figure 5, A and C could have used alternate filling, and B and C when using winding rule filling.

If we think the polygon to be a flat piece of material that is stretchable, certain pieces may start overlapping. A and B could be such a polygon,

and in that case B is really the preferred filling method. So in certain cases winding rule is more satisfatory compared to alternate filling.

If we think the polygon to be a flat piece of material that is stretchable, and next to this the color on one site is different from the color on the other side.

Also the material can be folded and twisted. If we paste such a folded/twisted piece of material on a 2D surface (projection on 2D), we could end up with a polygon like in C and D. In that case the filling in D would be preferred, and this filling can not be achived with winding rule or alternate filling. In figure 6 the twist in the paper is shown, after the twist the back of the material which had a different color, becomes visible, before the twist the front was visible.

Unfortunately this third method of filling, can NOT be based on scanlines in combination with segment directions. The drawing order of the points needs to be taken into account also. I have not found a simple algorithm to reach this type of filling.

Figure 5 ( alternate/winding rule compared totwisted paper filling )

Figure 6 (paper filling)

Linked holes

A common method to makes holes part of a polygon, is to connect the hole to the outside with to extra segments. Based on the filling method the holes can be displayed as being empty. A strange situation arises when two such holes start overlapping each other (see figure 7). All above described filling methods will give the same result. The overlapping part of the two holes is filled. This behaviour can best be explained if we decide that the polygon is a 2D projection of twisted paper.

In that case the overlapping part is in reality not a hole, but just the backside of the material.

I we want the overlapping holes to be filled as holes anyway, this method of linking holes in to the outer contour of the polygon can not be used.

There will be only one solution, the two holes must first be merged into one polygon that describes the hole, and this polygon needs to be linked into the outer contour in the end (see figure 8).

Polygon Filling Methods