geometry - 如何计算中轴？

Question

有谁知道如何计算两条给定曲线的中轴？

中轴：http ://en.wikipedia.org/wiki/Medial_axis

这是我需要计算的形状：

我自己画了中轴，深黑线，但我需要能够动态计算它。

这是我到目前为止所做的小程序和代码：http: //www.prism.gatech.edu/~jstrauss6/3451/sample/

已知变量是： -pt A、B、C、D - 红色、绿色和黑色圆圈的半径 -pt Q 和 R（就在图片之外），黑色圆圈。

Answer 1

设C1和为半径为和C2的圆心。由两个圆组成的图形的中轴（减去两个中心点）是满足的点集r1r2M

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

这意味着

|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  (**)

所以中轴是四次代数曲线。

让我们说C1和C2位于 y 轴上，并假设点 (0,0) 位于中轴上（因此C1 = (0, -r1 - x)，C2 = (0, r2 + x)对于某些人来说x，您可以根据数据进行计算）。这是你可以随时转变的东西。

y = f(x)现在，您需要参数化中轴的曲线。为此，选择x您的选择，并使用牛顿法求解方程，初始猜测(**)为。这是一个可以精确计算的多项式，以及它的导数（in ）。yy = 0y

Answer 2

在这种情况下，中轴是双曲线。

有关更多信息，请参阅本文，尤其是以下摘录：

与两个给定圆外切的任何圆的中心位于双曲线上，双曲线的焦点是给定圆的中心，并且顶点距离 2a 等于两个圆的半径差。

因此，考虑到它的焦点和顶点距离，问题简化为绘制双曲线。

Answer 3

如果您将圆圈嵌入矩形网格（想想图像），那么您可以使用该图像的距离变换来计算您的中轴。请参阅此链接。存在几种用于计算图像网格上的距离​​图的 O(nlogn) 算法。