Как рассчитать медиальную ось?

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 - центры окружностей с радиусами r1 и r2.Медиальная ось (минус две центральные точки) фигуры, состоящей из двух окружностей, представляет собой набор точек M, удовлетворяющих

|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 по вашему выбору и решите уравнение (**) в y с помощью метода Ньютона с начальным предположением y = 0.Это полином, который вы можете вычислить точно, а также его производную (в y).

Answer 2

Медиальная ось в данном случае является гиперболой.

Для получения дополнительной информации см. эту статью , в частности следующую выдержку:

Центр любогоокружности, внешние по отношению к двум заданным окружностям, лежат на гиперболе, фокусы которой являются центрами заданных окружностей, а расстояние между вершинами 2a равно разности радиусов двух окружностей.

Таким образом, проблема уменьшаетсярисовать гиперболу, учитывая ее фокус и расстояние до вершины.

Answer 3

Если вы вставите круги в прямоугольную сетку (представьте себе изображение), то вы можете использовать преобразование расстояния этого изображения, чтобы вычислить вашу медиальную ось.Смотрите эту ссылку .Существует несколько алгоритмов O (nlogn) для вычисления карты расстояний на сетке изображений.