Title: Create a Contain FillMode for filling polygons in C#

The example Understand fill modes in C# showed how the Alternate and Winding FillMode values affect the result when you fill a self-intersecting polygon. In many cases, the Alternate FillMode leaves holes in a self-intersecting polygon while the Winding FillMode fills many of those holes. Sometimes, however, even the Winding FillMode leaves holes.

For example, the picture on the right shows a self-intersecting polygon that is not completely filled with either the Alternate or Winding FillMode.

This example explains how you can fill a polygon completely. I'll call this the Contain FillMode be cause it fills all of the area contained within parts of the polygon.

The example program is fairly long and some of the steps are annoyingly complicated. The basic idea is simple and the algorithm is still more or less understandable with some work, so that's what I'll describe here. You can download the example program to see the programming details.

The Basic Idea

The basic idea is simple. Start at a point on the outside edge of the polygon and work your way around it clockwise, following its outside edges.

It's easy to do this by hand, but there are a lot of details to consider when you want a program to do it.

Details

Before we can start at a point on the polygon's outside edge, we need to know how to find such a point. It turns out that this is relatively easy. Just find the upper-leftmost point. Loop through the polygon's vertices and pick the one with the smallest X coordinate. If there's a tie, pick the one that has the smallest Y coordinate.

That vertex must be on the polygon's outside edge because no other vertex can have a smaller X coordinate. Using the Y coordinate to break ties isn't necessary for this first step, but it makes the next step easier.

Now that we've found a point on the polygon's outside edge, start moving clockwise around the polygon. To do that, follow the edge that heads the most to the left from the current point. In a "normal" polygon, each vertex is part of exactly two edges, so it's relatively easy to pick the one that is most "to the left." In more complicated polygons, a vertex may be shared by several edges.

To determine how far to the left an edge lies, you can use the VectorAngle method described in my post Find the angle between two vectors in C#.

If you entered the current point along segment S, then we define "to the left" to mean the leftmost edge leaving that point as see when looking down segment S. For example, consider the polygon on the right and suppose you just came from point 1 to point 5. (Point 2 is actually also at that point, it's just drawn under the 5.) There are four possible edges leaving point 5 and they lead to points 0, 1, 3, and 4. When you look down the edge that we just followed 1 → 5, the leftmost choice leads to vertex 3.

As you continue following the edges around the outside of the polygon in this example, you eventually reach vertex 5 again, this time coming from vertex 4. Now when you look down the 4 → 5 segment, the leftmost edge leaving vertex 5 heads to vertex 0.

If you follow leftmost edges in this example, you end up following the arrows shown in the picture.

When you follow an edge, one of two things happens. Either you reach the edge's endpoint or the edge is intersected by another one of the polygon's edges.

If you reach the edge's endpoint, you simply repeat the process and head out along the leftmost edge.

If the edge you follow is intersected by another edge, you stop at the closest point of intersection. Then you repeat the process, this time following the leftmost piece of edge that meets at that position.

For example, consider the polygon shown at the top of this post and repeated on the right. Suppose you are at vertex 1 and you follow the edge that leads toward vertex 7. That edge is intersected by three other edges. You stop at the first one (marked 2) and then head out along the leftmost edge fragment at that point, which leads to vertex 3.

Note that the edge fragment that you follow might itself be intersected by other edges.

Now you simply repeat the process until you have surrounded the polygon.

The last question is, "How do you know when to stop?"

You might check to see if you have visited a vertex more than once. That would mean you had completed a loop, so maybe you should stop. As the picture on the right shows, however, that won't always work. In this example you need to visit vertex 5 twice to completely enclose the polygon. That approach also won't work if several edges all intersect at the same point and you end up visiting that point more than once.

Another idea would be to stop if you return to the start point. This is only slightly better than the preceding approach. The preceding approach fails if any vertex or intersection must be visited more than once. The new approach only fails if the start vertex must be visited multiple times.

A better approach is to stop if the program reaches the start point and heads out along the same edge that it followed during its first move. For example, consider the picture on the right. The program starts at vertex 3. (Vertex 0 is also there, it's just drawn underneath.) The algorithm initially heads toward vertex 1. Later we visit vertex 3 again but this time we head toward vertex 4. The program visits vertex 3 one more time and heads toward vertex 1 again. We started with the 3 → 1 edge, so we now know we are done. The program breaks out of its loop and we have finished wrapping the polygon.

Algorithm

1. Find the upper-leftmost vertex. Set to_point to that point.
2. Set from_point to a point 10 units above to_point. In other words:

   from_point = new PointF(to_point.X, to_point.Y - 10);

3. Repeat:
   1. Travel along segment S = from_point → to_point. There are two cases.
      1. If S intersects one or more edges:
         1. Find the closest point of intersection P.
         2. For each edge that intersects S at P:
            1. Find the endpoint of the edge that is leftmost as seen from from_point → to_point.
            2. Save the edge that has the most leftmost endpoint of all of these edges.
         3. Prepare to follow the new edge. To do that:
            1. Set new_from_point equal to P.
            2. Set new_to_point equal to the leftmost endpoint of the best edge.
      2. If S does not intersect any edges:
         1. Prepare to move to to_point. To do that:
            1. Set new_from_point equal to to_point.
            2. Examine the edges that leave to_point and find the one that has the leftmost endpoint. Set new_to_point equal to that leftmost endpoint.
   2. If next_from_point → next_to_point is the same edge that we originally followed at the start, then we are done so break out of the loop.
   3. If the result list is empty, then next_to_point is the second point that we will try to visit. Save it so we can know later if we try to cross this edge again. (So we can break out of the loop in the preceding step.)
   4. Officially move to the next point. To do that:
      1. Set from_point = next_from_point.
      2. Set to_point = next_to_point.
4. After the loop ends, return the result list.

It may take some thought to see how this all works, particularly with the initial conditions.

For example, initially we set to_point equal to the start point and we set from_point to be a point directly above the start point. When you pick the leftmost edge leaving from_point as seen along this artificial edge, you find the first edge clockwise from the start point.

Conclusion

The algorithm seems to work pretty well. It can handle polygons that require you to visit the same point multiple times, even if that point is the start point. It can even handle at least some cases where two edges coincide as in the picture on the right.

I won't guarantee that the example program can handle every weird special case. In fact, I know it cannot handle edges that overlap but do not completely coincide as in the picture on the right. For that polygon the program gets confused about which vertex it should visit when it traverses the overlapping edges and crashes.

There may be other odd cases that the program can't handle, but overall it does pretty well. Download the example program to see how the code works and to experiment with it. If you find other kinds of special cases that confuse the program, or if you take the time to fix any of those special cases, please let me know.

Download the example to experiment with it and to see additional details.