Union of complex polygons

Question

Given two polygons:

POLYGON((1 0, 1 8, 6 4, 1 0))
POLYGON((4 1, 3 5, 4 9, 9 5, 4 1),(4 5, 5 7, 6 7, 4 4, 4 5))

How can I calculate the union (combined polygon)?

Dave's example uses SQL server to produce the union, but I need to accomplish the same in code. I'm looking for a mathematical formula or code example in any language that exposes the actual math. I am attempting to produce maps that combine countries dynamically into regions. I asked a related question here: http://stackoverflow.com/questions/2653812/grouping-geographical-shapes

Answer 1

You need to determine which points lie inside. After removing these points, you can insert one set of "outside" points into the other. Your insertion points (e.g. where you have the arrow in the picture on the right) are where you had to remove points from the input sets.

Answer 2

Good question! I've never attempted this before, but I'll take a crack at it now.

First: You need to know where these two shapes overlap. To do this, you could look at every edge in Polygon A and see where it intersects and edge in Polygon B. In this example, there should be two points of intersection.

Then: Make the union shape. You can take all of the vertices in A and B, and also the points of intersection, and then exclude the vertices that contained by the final shape. To find these points, it looks like you could just find any vertex of A that is inside B, and any vertext of B that is inside A.

Answer 3

When grouping countries, I'd hope there be no overlap -- you could take a fairly naive algorithm that looks for shared vertices - a simple view would be to iterate through the points on one polygon, see if it's on any of your other polygons, and shares the same next or previous point to see if there is a match. Then just remove the shared vertex to create your union

Answer 4

Try gpc.

Answer 5

A solution I've seen using BSP trees is described here.

Basically, it describes intersection in terms of a union of the edges of polygon A that are inside polygon B (including partial edges, and calculated using a BSP tree). Then, you can define A \/ B as ~(~A /\ ~B), where ~ denotes reversing the winding of the polygon, \/ denotes union and /\ denotes intersection.