How to calculate the medial axis?

Question

Does anyone know how to calculate the medial axis for two given curves?

Medial axis: http://en.wikipedia.org/wiki/Medial_axis

Here is the shape I need to calculate it for:

I drew in the medial axis myself, the dark black line, but I need to be able to calculate it dynamically.

Here is the applet and code of what I have done so far: http://www.prism.gatech.edu/~jstrauss6/3451/sample/

The known variables are: -pt A, B, C, D -radii of red, green, and black circles -pt Q and R (just outside the picture), the black circles.

Answer 1

Let C1 and C2 be centers of circles with radii r1 and r2. The medial axis (minus the two center points) of the figure made of the two circles is the set of points M satisfying

|M - C1| - r1 = |M - C2| - r2

which implies

|M - C1| - |M - C2| = r1 - r2
|M - C1|^2 + |M - C2|^2 - (r1 - r2)^2 = 2 * |M - C1||M - C2|
(|M - C1|^2 + |M - C2|^2 - (r1 - r2)^2)^2 = 4 * |M - C1|^2 |M - C2|^2  (**)

so the medial axis is a fourth degree algebraic curve.

Let us say that C1 and C2 are on the y axis, and suppose that the point (0,0) lies on the medial axis (so C1 = (0, -r1 - x) and C2 = (0, r2 + x) for some x you can compute from your data). This is something you can always transform into.

Now, you want the curve y = f(x) which parametrizes the median axis. For this, pick the x of your choice, and solve equation (**) in y with Newton's method, with initial guess y = 0. This is a polynomial you can compute exactly, as well as its derivative (in y).

Answer 2

The medial axis is in this case a hyberbola.

For more information see this article, particularly the following excerpt:

The center of any circles externally tangent to two given circles lies on a hyperbola, whose foci are the centers of the given circles and where the vertex distance 2a equals the difference in radii of the two circles.

So the problem reduces to drawing a hyperbola, given its foci and vertex distance.

Answer 3

If you embed the circles on a rectangular grid (think image), then you can use the distance transform of this image to compute your medial axis. See this link. Several O(nlogn) algorithms exist for computing the distance map on an image grid.