By Elazar Leibovich


2010-02-16 10:38:43 8 Comments

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.

9 comments

@afiori 2020-05-18 22:18:16

If you do not care about predictable run time you could try by first splitting your polygons into unions of convex polygons and then pairwise computing the intersection between the sub-polygons.

This would give you a collection of convex polygons such that their union is exactly the intersection of your starting polygons.

@Ansh David 2015-08-20 15:17:46

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

@Dom 2015-05-26 13:43:26

I have no very simple solution, but here are the main steps for the real algorithm:

  1. Do a custom double linked list for the polygon vertices and edges. Using std::list won't do because you must swap next and previous pointers/offsets yourself for a special operation on the nodes. This is the only way to have simple code, and this will give good performance.
  2. Find the intersection points by comparing each pair of edges. Note that comparing each pair of edge will give O(N²) time, but improving the algorithm to O(N·logN) will be easy afterwards. For some pair of edges (say a→b and c→d), the intersection point is found by using the parameter (from 0 to 1) on edge a→b, which is given by tₐ=d₀/(d₀-d₁), where d₀ is (c-a)×(b-a) and d₁ is (d-a)×(b-a). × is the 2D cross product such as p×q=pₓ·qᵧ-pᵧ·qₓ. After having found tₐ, finding the intersection point is using it as a linear interpolation parameter on segment a→b: P=a+tₐ(b-a)
  3. Split each edge adding vertices (and nodes in your linked list) where the segments intersect.
  4. Then you must cross the nodes at the intersection points. This is the operation for which you needed to do a custom double linked list. You must swap some pair of next pointers (and update the previous pointers accordingly).

Then you have the raw result of the polygon intersection resolving algorithm. Normally, you will want to select some region according to the winding number of each region. Search for polygon winding number for an explanation on this.

If you want to make a O(N·logN) algorithm out of this O(N²) one, you must do exactly the same thing except that you do it inside of a line sweep algorithm. Look for Bentley Ottman algorithm. The inner algorithm will be the same, with the only difference that you will have a reduced number of edges to compare, inside of the loop.

@Angus Johnson 2010-06-06 11:28:06

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

@Elazar Leibovich 2010-06-06 12:34:15

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

@Angus Johnson 2010-06-06 18:20:20

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

@GorillaApe 2015-05-04 15:29:31

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

@sendreams 2015-06-28 03:58:18

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

@Manfred Radlwimmer 2018-02-21 12:54:13

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

@Barend 2010-02-21 10:15:14

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.

@Doug Ferguson 2010-02-16 13:05:37

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.

@Elazar Leibovich 2010-02-16 16:22:44

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.

@Doug Ferguson 2010-02-17 00:42:10

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.

@Darius Bacon 2010-02-16 23:04:23

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!

@Mark Ransom 2010-02-16 23:25:36

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.

@Aryabhatta 2010-02-16 17:44:40

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.

@Elazar Leibovich 2010-02-16 19:43:07

Wow! This is just what I had in mind, but: (1) the polygons are represented as series of CW segments, and converting it to convex-convex is nontrivial. (2) After substructing the first convex, I get a nonconvex shape I need to handle, and I'm not sure that substructing a convex from a polygon is much easier than finding the intersection between two polygons...

@Aryabhatta 2010-02-16 21:29:44

@Elazar: To convert line segement representation to Convex - Convex, you can do the following: 1) Form the convex hull. 2) For each side of the convex hull, if it is not inside, you can find a non-convex polygon you need to subtract. You can then 'triangulate' this non-convex polygon to get a union of convex shapes. As to your point 2): you don't actually have to do any actual subtracting if you work with that representation. I suppose for the convex hull + 'triangulation', there will be packages to do that already.

@ees 2016-11-22 19:03:32

This algorithm would fail on the "pitchfork blades instersecting at right angles" example in the following comment. Specifically, it would miss the cutouts it should add next to the crossbar of each pitchfork.

@fishinear 2017-01-05 15:46:30

Actually, the algorithm needs to subtract all the smaller polygons of both shapes, not their intersections. You might want to intersect them with the new hull, though.

@Sylvestre Equy 2010-02-16 10:55:53

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.

@Elazar Leibovich 2010-02-16 12:25:39

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

Related Questions

Sponsored Content

48 Answered Questions

6 Answered Questions

23 Answered Questions

4 Answered Questions

[SOLVED] Simple 2d polygon triangulation

2 Answered Questions

1 Answered Questions

4 Answered Questions

[SOLVED] Determining polygon intersection and containment

2 Answered Questions

Sponsored Content