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:

- 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.)

- 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`. - Starting at the point added to the union, move to the next point along the polygon (the blue polygon in Figure 1) and:
- 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:- Set
`current_point`to the point of intersection and add it to the union.

- 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.)

- Set

- See if the segment from the
- 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 polygon.

Download the example to see the details of how the code works.

hi RodStephens:

i am find the programe will in Infinite loop when i give the follow positions

would you tell me why?

thankyou

In this case the two polygons are rectangles as shown on the right. This is the case shown in Figure 11 above and it’s not handled by the program.

The program is probably following one rectangle into the overlapping edge and then getting stuck in a loop following the other rectangle’s edges.

If you change the points on the overlap a little, it should work. For example, if you change the second and third points in the first polygon to this:

Thank you very much!

Very nice code! It helped me a lot 😉

Thanks for your example about “Find a polygon union in C#”. I want to ask that have you any experience about Polygon overlay in GIS using by mapreduce(Hadoop). Thanks

Thank you very much. It’s a excellent code.