Line(s) Equidistant From Two Convex Polygons In 2D

Question

Given two convex polygons in 2D space, how would you go about constructing the line segment(s ) which, at any point on the lines, is equidistant from the closest point of either convex polygon?

I'm looking towards an implementation of Voronoi diagrams for convex polygons instead of points, but I'm unsure how to even begin calculating the line for just two polygons. So I figured I'd take this one step at a time and start here.

Edit To try to make the question a little clearer, I want to bisect the plane (or a subset thereof).

Suppose we have polygon A on the left and polygon B on the right. There will be some line of bisection that divides the plane into points on the left and points on the right. Every point on the line is equally distance from either polygon. Every point left of the line is closer to polygon A than to polygon B. Every point right of the line is closest to polygon B.

Here's an image generated by a Matlab script I wrote that brute-forces an approximation:

The problem, I believe, is not as simple as examining the space in "between" the two polygons, since the line must extend beyond the area directly between the two shapes. And ideally I'd like to find a solution that generalizes to more than two shapes, which, to me, seems to complicate the problem a great deal more. Here's a (obviously very rough) approximation of how that might look:

Answer 1

Well, proceeding one step at a time I'd look at the closest points in the polygons themselves. Let's say a in A is the closest point to B and b in B is the closest point to A. You know the middle point of AB is in the desired segments.

What are the posibilities for a? It can be a vertex of A or it can be a point in one side. The same applies for b. What happens with the "equidistant-segments"? How to build them in each case?

Since those segments are equidistant to sides of the polygons, they have to be part of the line that bissects the angle of the lines containing the corresponding sides.

Answer 2

Am I understanding you correctly but assuming you're wanting the line that effectively bisects the space between 2 convex polygons? If so, then ...

1. find the line that joins the 2 polygons (P1 & P2)
   • find each polygon centre (P1.centre & P2.centre) by calculating the average X and Y coordinate.
   • find the vertex on each polygon that's closest to the other's centre (P1.vc & P2.vc)
2. given that P1.vc & P2.vc now define the line joining P1 & P2
   • find the midpoint (mp) of P1.vc & P2.vc

Bisecting line = perpendicular of the line joining P1.vc & P2.vc that passes through mp