A simple algorithm for polygon intersection

Question

I'm looking for a very simple algorithm for computing the polygon intersection/clipping. That is, given polygons P, Q, I wish to find polygon T which is contained in P and in Q, and I wish T to be maximal among all possible polygons.

I don't mind the run time (I have a few very small polygons), I can also afford getting an approximation of the polygons' intersection (that is, a polygon with less points, but which is still contained in the polygons' intersection).

But it is really important for me that the algorithm will be simple (cheaper testing) and preferably short (less code).

edit: please note, I wish to obtain a polygon which represent the intersection. I don't need only a boolean answer to the question of whether the two polygons intersect.

Answer 1

The way I worked about the same problem

1. breaking the polygon into line segments
2. find intersecting line using IntervalTrees or LineSweepAlgo
3. finding a closed path using GrahamScanAlgo to find a closed path with adjacent vertices
4. Cross Reference 3. with DinicAlgo to Dissolve them

note: my scenario was different given the polygons had a common vertice. But Hope this can help

Answer 2

I understand the original poster was looking for a simple solution, but unfortunately there really is no simple solution.

Nevertheless, I've recently created an open-source freeware clipping library (written in Delphi, C++ and C#) which clips all kinds of polygons (including self-intersecting ones). This library is pretty simple to use: http://sourceforge.net/projects/polyclipping/ .

Answer 3

Here's a simple-and-stupid approach: on input, discretize your polygons into a bitmap. To intersect, AND the bitmaps together. To produce output polygons, trace out the jaggy borders of the bitmap and smooth the jaggies using a polygon-approximation algorithm. (I don't remember if that link gives the most suitable algorithms, it's just the first Google hit. You might check out one of the tools out there to convert bitmap images to vector representations. Maybe you could call on them without reimplementing the algorithm?)

The most complex part would be tracing out the borders, I think.

Back in the early 90s I faced something like this problem at work, by the way. I muffed it: I came up with a (completely different) algorithm that would work on real-number coordinates, but seemed to run into a completely unfixable plethora of degenerate cases in the face of the realities of floating-point (and noisy input). Perhaps with the help of the internet I'd have done better!

Answer 4

You have not given us your representation of a polygon. So I am choosing (more like suggesting) one for you :)

Represent each polygon as one big convex polygon, and a list of smaller convex polygons which need to be 'subtracted' from that big convex polygon.

Now given two polygons in that representation, you can compute the intersection as:

Compute intersection of the big convex polygons to form the big polygon of the intersection. Then 'subtract' the intersections of all the smaller ones of both to get a list of subracted polygons.

You get a new polygon following the same representation.

Since convex polygon intersection is easy, this intersection finding should be easy too.

This seems like it should work, but I haven't given it more deeper thought as regards to correctness/time/space complexity.

Answer 5

Here's an approach based on triangulation that is pretty straightforward to implement and can be made to run in O(N²).

BTW, O(N²) is optimal for this problem. Imagine two polygons shaped like pitchfork blades intersecting at right angles. Each has a number of segments proportional to the number of tines; the number of polygons in the intersection is proportional to the square of the number of tines.

1. First, triangulate each polygon.

2. Compare all the triangles from P pairwise with all the triangles from Q to detect intersections. Any pair of intersecting triangles can be broken into smaller triangles each of which is in P, in Q, or in the intersection. (Whatever you used in step 1 can be reused to help with this.) Only keep triangles that are in the intersection.

3. Compute the neighbors of each triangle, by comparing them pairwise, and build an adjacency graph. This graph will contain one connected subgraph for each polygon in the intersection of P and Q.

4. For each such subgraph, pick a triangle, walk to the edge, and then walk around the edge, producing the segments bounding the corresponding output polygon.

Answer 6

This can be a huge approximation depending on your polygons, but here's one :

• Compute the center of mass for each polygon.
• Compute the min or max or average distance from each point of the polygon to the center of mass.
• If C1C2 (where C1/2 is the center of the first/second polygon) >= D1 + D2 (where D1/2 is the distance you computed for first/second polygon) then the two polygons "intersect".

Though, this should be very efficient as any transformation to the polygon applies in the very same way to the center of mass and the center-node distances can be computed only once.