math – A simple algorithm for polygon intersection

math – A simple algorithm for polygon intersection

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

Nevertheless, Ive 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/ .

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.

math – A simple algorithm for polygon intersection

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

Leave a Reply

Your email address will not be published.