Search code examples
computational-geometry

Find separating line between two polygons

Is there a simple algorithm that finds a separating line between two polygons such that they lie on either side of the line? Or preferably does anyone know of a library that does this sort of thing? Any help would be appreciated

EDIT:

My solution:

I used JTS: http://www.vividsolutions.com/jts/JTSHome.htm

Created two Polygons using this library and ran DistanceOp to find the two nearest points between the polygons (not necessarily vertices). Then simply calculated a perpendicular line to the line that connects them.

Solution

  • Let A and B be your two polygons. First find the convex hull of each, C(A) and C(B). Clearly a line that separates A from B also separates C(A) from C(B). Let a be a point on C(A) and b a point on C(B). One can walk a and b around the boundaries until a separating line through a and b is found. This can be accomplished in linear time, but I will not describe that now.