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.

Solution 1

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

Solution 2

You could use a Polygon Clipping algorithm to find the intersection between two polygons. However these tend to be complicated algorithms when all of the edge cases are taken into account.

One implementation of polygon clipping that you can use your favorite search engine to look for is Weiler-Atherton. wikipedia article on Weiler-Atherton

Alan Murta has a complete implementation of a polygon clipper GPC.

Edit:

Another approach is to first divide each polygon into a set of triangles, which are easier to deal with. The Two-Ears Theorem by Gary H. Meisters does the trick. This page at McGill does a good job of explaining triangle subdivision.

Solution 3

If you use C++, and don't want to create the algorithm yourself, you can use Boost.Geometry. It uses an adapted version of the Weiler-Atherton algorithm mentioned above.

Solution 4

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!

View more solutions

Comments

[Elazar Leibovich]

And how to I get a polygon representing the intersection area?

[Elazar Leibovich]

I googled for polygon clipping, and found those results as well. However, please note that these algorithms are meant to be efficient exact and complex. I'm aiming for a slow, possibly approximated algorithm which is SIMPLE.

[Mark Ransom]

Tracing the borders might be easier if you realize that each vertex will either be the vertex of one of the polygons, or an intersection of a line segment from each of them.

[Doug Ferguson]

I too wish there were a simple to use method. One would imagine that WPF and GDI+ do the sort of clipping that would be generally useful if the more primitive geometry operations were exposed through the API. When one starts simple, the program grows more complex over time as those difficult edge cases are taken into account.

[Elazar Leibovich]

I came to this unfortunate conclusion myself not long ago. Every solution is agonizingly complex. Thanks for the library!

[Angus Johnson]

Perhaps I should also mention that my Clipper library also compares very favorably with other clipping libraries: angusj.com/delphi/clipper.php#features

[GorillaApe]

@angus johnson what would you use for simple testing if a polygon interects with another or if its fully contained?

[sendreams]

@AngusJohnson, does your library support calculate two open path's intersection points? thanks

[Manfred Radlwimmer]

Update from 2018: Polyclipping has been renamed Clipper and is available as a NuGet package.

[Lake_Lagunita]

Hello @AngusJohnson, Is there an algorithm for clipping a polygon with polyline? I am trying to find a way to clip a polygon with polyline.