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