Find separating line between two polygons

Question

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.

Answer 1

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.

Answer 2

Let's say you have a polygon A with points A1,A2,A3,...,AN and a polygon B with points B1,B2,B3,...,BM.

What you could do is to describe a line from the point AX to BX for every possible combination (A1 & B1, A1 & B2, ... AN & BM).

Such line could be described in the parametric format: SomePoint = InicialPoint + Direction * t and will be a possible candidate to a "separating-line". Keep it!

Now what you gotta do is to DESCRIBE ANOTHER vector from each point of each polygon to this candidate line. Each of those lines will have it's direction vector.

If the cross product of the direction vector of each line with the candidate's direction vector have the same direction (Z-positive or Z-negative), it means those points are in the same side of the separating line (still candidate).

Now check for all lines you described for each point of each polygon. You can figure out if all points of polygon A are in one side and all points in the polygon B are in the other side... then you found the line you want. If not, you gotta try a next candidate line (AX-BX). If you don't find any of these combination with all possible candidate lines, it means you have an intersection between the polygons.

I am not sure if it's the best/fastest algorithm but I'm sure it works.