Find a polygon union in C#

[polygon union]

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.)
    [polygon union]

  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.
        [polygon 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.

[polygon union][polygon union]

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

    [polygon union][polygon union]

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

    [polygon union][polygon union]

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

    [polygon union]

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

    [polygon union]

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

    [polygon union]

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

Download Example   Follow me on Twitter   RSS feed   Donate

About RodStephens

Rod Stephens is a software consultant and author who has written more than 30 books and 250 magazine articles covering C#, Visual Basic, Visual Basic for Applications, Delphi, and Java.
This entry was posted in algorithms, drawing, graphics, mathematics and tagged , , , , , , , , , , , , . Bookmark the permalink.

4 Responses to Find a polygon union in C#

  1. ruisonzhou says:

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

    Polygons[0] = new List<PointF>(new PointF[]
        new PointF(1765, 1200),
        new PointF(1765, 0),
        new PointF(2400, 0),
        new PointF(2400, 1200)
    Polygons[1] = new List<PointF>(new PointF[]
        new PointF(1175, 400),
        new PointF(1175, 0),
        new PointF(2395, 0),
        new PointF(2395, 400)

    would you tell me why?

    • RodStephens says:

      [polygon union]
      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:

          new PointF(1765, 1),
          new PointF(2400, 1),
  2. Telmo says:

    Thank you very much!
    Very nice code! It helped me a lot 😉

  3. Mostafa Hosseini says:

    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

Leave a Reply

Your email address will not be published. Required fields are marked *