How do I find the overlapping area between two arbitrary polygons

Question

I'm trying to create a method that will take in two arbitrary lists of nodes, for a subject and a clipping polygon, and output either:

a) the area of the overlap
b) a list of nodes for the resulting (clipped) polygon so that I can calculate the area

I've found lots of examples which clip an arbitrary polygon using a rectangular window (which is fairly standard in graphics) but that's not what I need. I understand that it's fairly complex, particularly when you get holes, convex polygons and the like. The only simplifying assumption which I can make is that the arbitrary polygons will not contain any holes.

I'm not at all an expert in this field, so would something like the Sutherland-Hodgman algorithm work? Are there any libraries out there which already do this, or is my best bet to simply implement the algorithm as described in pseudo-code on Wikipedia?

Thanks for the help!

Answer 1

Are there any libraries out there which already do this ...

Polygon clipping is a complex task. I wouldn't recommend trying to do it yourself unless you want to spend many months on it. Wikipedia lists a number of clipping libraries (and IIRC in that list only Clipper is free for use in commercial applications): http://en.wikipedia.org/wiki/Boolean_operations_on_polygons#External_links

ps: I admit to a personal bias for Clipper since I'm the author :) More info here: http://angusj.com/delphi/clipper.php

Answer 2

Sounds like Weiler-Atherton is the one you need:

The algorithm requires polygons to be clockwise and not reentrant (self intersecting). The algorithm can support holes (as counter-clockwise polygons wholly inside their parent polygon), but requires additional algorithms to decide which polygons are holes.

Your polygons fit those criteria, right? I don't know about implementations, but it sounds like you would be better off implementing W-A than S-H if either of your polygons could be concave.

Answer 3

Try gpc.

Answer 4

I found that using the JavaGeom library worked very well. It integrates the code from the Java port of GPC (which is no longer available) and thus allows arbitrary polygon operations. Using SimplePolygon2D and Polygon2DUtils.intersection() I was able to get the desired operation.

Answer 5

I've tried a lot of different libraries and the one that worked best was the JTS Topological Suite which is pure Java and LGPL2 licensed.