Search code examples
geometrycomputational-geometrymedial-axis

How to calculate the medial axis?

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: alt text

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.

Solution

  • 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).