How to combine complex polygons?

Question

For 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)?

Example Dave uses an SQL server to create a join, but I need to do the same in the code. I am looking for a math formula or sample code in any language that displays actual math. I am trying to create maps that dynamically unite countries into regions. I asked the following question: Grouping geographic shapes

Answer 1

This is a very good question. I implemented the same algorithm in C # some time ago. The algorithm constructs the general contour of two polygons (i.e. creates a union without holes). Here it is.

---

Step 1. Create a graph that describes the polygons.

Input: first polygon (n points), second polygon (m points). Exit: schedule. The vertex is the polygon point of the intersection point.

We have to find the intersections. We pass through all sides of the polygon in both polygons [O (n * m)] and find any intersections.

• If no intersection is found, just add vertices and connect them to the edge.

• If any intersections are found, sort them by length to their starting point, add all the vertices (start, end and intersections) and connect them (already in sorted order) to the edge.

Step 2. Check the constructed graph

If we did not find intersection points when plotting, we have one of the following conditions:

• Polygon1 contains polygon2 - return polygon1
• Polygon2 contains polygon1 - return polygon2
• Polygon1 and polygon2 do not intersect. Return polygon1 and polygon2.

Step 3. Find the bottom left vertex.

Find the minimum x and y coordinates (minx, miny). Then find the minimum distance between (minx, miny) and the points of the polygon. This item will be bottom left.

Step 4. Build a common path.

We begin to move along the chart from the left point and continue until we return to it. At the beginning, we mark all edges as invisible. At each iteration, you must select the next point and mark it as having visited.

To select the next point, select the edge with the maximum inside angle in the counterclockwise direction.

I compute two vectors: vector1 for the current edge and vector2 for each next invisible edge (as shown in the picture).

For vectors I calculate:

• Scalar product (point product). It returns the value associated with the angle between the vectors.
• Vector product (cross product). It returns a new vector. If the z-coordinate of this vector is positive, the scalar product gives a right angle in counterclockwise direction. Else (the z-coordinate is negative), I calculate the angle between the vectors as 360 - the angle from the scalar product.

As a result, I get an edge (and the corresponding next vertex) with the maximum angle.

I add each vertex passed to the list of results. The list of results is a union polygon.

Notes

• This algorithm allows us to combine several polygons - to apply iteratively with polygonal pairs.
• If you have a path that consists of many curves and bezier lines, you must first smooth this path.

Answer 2

You need to determine which points lie inside . After deleting these points, you can insert one set of “external” points into another. Input points (for example, where you have an arrow in the picture on the right) is the place where you needed to remove points from input sets.

Answer 3

This is a complex, but well-understood topic, often referred to as "regularized Boolean operations on polygons." You can look at this MathOverflow answer , which includes the figure below (from the Alan Murtha trim library ), with the pink OP connection combined:

---

---

Answer 4

Good question! I have never done this before, but now I will crack it.

First: you need to know where these two forms overlap. To do this, you can look at each edge in polygon A and see where it intersects, and the edge in polygon B. In this example, there must be two intersection points.

Then: Make the connection form. You can take all the vertices in A and B, as well as the intersection points, and then exclude the vertices that are in the final form. To find these points, it looks like you could just find any vertex from A that is inside B, and any text from B that is inside A.

Answer 5

Try gpc .

Answer 6

The solution I saw using BSP trees is described here .

Basically, it describes the intersection in terms of the union of the edges of the polygon A that are inside the polygon B (including partial edges and calculated using the BSP Tree ). You can then define A / B as ~ (~ A / \ ~ B ), where ~ denotes the inverse of the polygon, / denotes a union and / \ denotes an intersection.

Answer 7

When grouping countries, I would hope that there will be no overlap - you can take a rather naive algorithm that searches for common vertices - a simple idea would be to iterate over points on one polygon, see if it divides at any of your other polygons the same next or previous paragraph to see if there is a match. Then just remove the common vertex to create a join.

Answer 8

I needed to solve the same problem today and found a solution with this lib: http://www.cs.man.ac.uk/~toby/alan/software/ .

It has many language implementations of the list here , including Java, Obj-C, C #, Lua, python, etc.