Title: Find a polygon union in C#

This example begins with two sample polygons pre-defined. Left-click to create the points for your own blue polygon and right-click to create the points for your own green polygon. Double-click to finish drawing a polygon. When two polygons are defined, the program displays them and their union.

The example's code is fairly long and involved so it isn't shown here, but the algorithm is reasonably straightforward. The basic idea is to move counterclockwise around the edges of one of the polygons. When the edge you're traversing hits an edge on the other polygon, you switch to that polygon and continue moving around its edges.
Here are the steps a bit more precisely:

1. Orient both polygons counterclockwise. (In other words, as you traverse the list of points representing the polygon, the points should move counterclockwise around the polygon.)
2. Start at a vertex known to be on one polygon and not inside the other. This example uses the leftmost vertex as shown in Figure 1. Add that point to the union and call it the current_point.
3. Starting at the point added to the union, move to the next point along the polygon (the blue polygon in Figure 1) and:
   1. See if the segment from the current_point to the polygon's next vertex intersects any of the other polygon's edges. If so, find the intersection that is closest to the current_point and:
      1. Set current_point to the point of intersection and add it to the union.
      2. Switch polygons so you're now following the other polygon's edges counterclockwise as shown in Figure 2. (You're now following the green polygon in Figure 2.)
4. Continue moving around the polygon edges (Figures 3 and 4 show the next two steps) until you return the starting point.

Note that there are several special cases that the program doesn't handle including:

• If either polygon is self-intersecting (Figure 5).
• If either polygon contains a hole (Figure 6).
  

• If the polygon union contains a hole (Figure 7).
• If the polygons don't overlap (Figure 8).
  

• If one polygon edge intersects another at a vertex (Figure 9). In that case you need to decide whether to ignore the intersection and continue along the current polygon or switch polygons.
  

• If the polygons share a vertex (Figure 10). This is really a different version of the case shown in Figure 9.
  

• If one polygon edge coincides with another either partly or fully (Figure 11). Again you need to decide whether to continue along the current polygon or switch polygons.
  

• Possibly others

Some of these, such as those shown in Figures 9, 10, and 11, seem solvable with a bit of extra work. Others, such as those shown in Figures 5 and 6, would probably require a new method for representing polygons.

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