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

User · Answer

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.

User · Answer

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

User · Answer

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

User · Answer

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

User · Answer

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

User · Answer

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

User · Answer

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

User · Answer

I have no very simple solution  but here are the main steps for the real algorithm    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  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  d0  d0-d1   where d0 is  c-a    b-a  and d1 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  Split each edge adding vertices  and nodes in your linked list  where the segments intersect  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

User · Answer

The way I worked about the same problem   breaking the polygon into line segments find intersecting line using IntervalTrees or LineSweepAlgo finding a closed path using GrahamScanAlgo to find a closed path with adjacent vertices 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

[math] A simple algorithm for polygon intersection

Examples related to math

Examples related to geometry

Examples related to 2d

Examples related to polygon