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.

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