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, 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

- Find the upper-leftmost vertex. Set
`to_point`to that point. - 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);

- Repeat:
- Travel along segment S =
`from_point → to_point`. There are two cases.- If S intersects one or more edges:
- Find the closest point of intersection P.
- For each edge that intersects S at P:
- Find the endpoint of the edge that is leftmost as seen from
`from_point → to_point`. - Save the edge that has the most leftmost endpoint of all of these edges.

- Find the endpoint of the edge that is leftmost as seen from
- Prepare to follow the new edge. To do that:
- Set
`new_from_point`equal to P. - Set
`new_to_point`equal to the leftmost endpoint of the best edge.

- Set

- If S does not intersect any edges:
- Prepare to move to
`to_point`. To do that:- Set
`new_from_point`equal to`to_point`. - 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.

- Set

- Prepare to move to

- If S intersects one or more edges:
- 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. - 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.) - Officially move to the next point. To do that:
- Set
`from_point = next_from_point`. - Set
`to_point = next_to_point`.

- Set

- Travel along segment S =
- 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 post a comment below.

Thanks for the continued drawing/graphic articles. Can this be applied in some manner to a set of lines with known endpoints to find connections that create a closed polygon so it can be filled with a new polygon? Location would be chosen with a mouse click inside closed area to be filled with the new pologon.

I’m not sure exactly what you mean.

If the segments intersect, then you could follow them clockwise to create a “polygon,” although it will probably just be a skeleton-like sort of thing.

You could find the convex hull of the end points. That would give you an enclosing polygon.

Or perhaps you could identify groups of points that are close to each other and wrap each of those in a convex hull.