Поиск наименьшего круга, охватывающего другие круги?

Ответ 1

Его называют минимальным окружным кругом ( "MEC" ) или иногда "наименьшим окружением".

Хороший сайт: http://www.personal.kent.edu/~rmuhamma/Compgeometry/MyCG/CG-Applets/Center/centercli.htm

Ответ 2

Учитывая два круга, с центрами [x1, y1], [x2, y2] и радиусами R1 и R2. Каков центр окружного круга?

Предположим, что R1 не больше R2. Если второй круг меньше, просто замените их.

• Вычислить расстояние между центрами окружностей.

  D = sqrt ((x1-x2) ^ 2 + (y1-y2) ^ 2)

• Первый круг лежит внутри второго круга? Таким образом, если (D + R1) <= R2, то мы закончили. Верните большой круг в круг окружности с центром [x1, x2] с радиусом R2.

• Если (D + R1) > R2, то окружная окружность имеет радиус (D + R1 + R2)/2

В этом последнем случае центр охватывающей окружности должен лежать вдоль линии, соединяющей два центра. Таким образом, мы можем написать новый центр как

center = (1-theta)*[x1,y1] + theta*[x2,y2]

где theta дается выражением

theta = 1/2 + (R2 - R1)/(2*D)

Заметим, что theta всегда будет положительным числом, так как мы заверили, что (D + R1) > R2. Аналогично, мы должны быть в состоянии обеспечить, чтобы theta никогда не превышала 1. Эти два условия гарантируют, что охватывающий центр лежит строго между двумя исходными центрами окружности.

Ответ 3

Так как мое неточное решение не понравилось. Это способ получить точное решение. Но его медленный (O (N ^ 4)?) И ​​вычислительно противный. (В отличие от неточного метода)

Сначала вам нужно знать, что, учитывая три круга, мы можем найти окружность, касательную к ним, чем содержащую все три. Это один из кругов Аполлония. Вы можете получить алгоритм из mathworld.

Далее вы можете показать, что наименьшая окружная окружность для N кругов тангенциальна по меньшей мере к 3 из N кругов.

Чтобы найти этот круг, мы делаем следующее

• через все тройки кругов - O (N ^ 3)
• найдите замкнутый круг Аполлония из этих трех окружностей - вычислительно противный
• если он охватывает все круги, добавить его в список потенциалов - проверка O (N)
• Решение потенциально с наименьшим радиусом

Могут быть некоторые приемы, чтобы ускорить это, но он должен дать точное решение. Некоторые из "трюков" для получения алгоритма Smallest Enclosing Circle для линейного времени могут быть применимы здесь, но я подозреваю, что они не будут тривиальными адаптациями.

Ответ 4

Проблема, которую вы имеете под рукой, называется наименьшей охватывающей сферой сфер. Я написал свой тезис об этом, см. "Самый маленький охватывающий шар шаров" , ETH Zurich.

Вы можете найти очень эффективную реализацию С++ в Библиотека алгоритмов вычислительной геометрии (CGAL) в пакете Ограничение томов. (Нет необходимости использовать все CGAL, просто извлеките необходимые исходные файлы и файлы заголовков, и вы работаете.)

Примечание.. Если вы ищете алгоритм вычисления самой маленькой охватывающей сферы только точек, есть другие реализации там, см. этот пост.

Ответ 5

Я собираюсь рекомендовать против этого, теперь
См. Обсуждение ниже.

Оригинальные мысли

Я бы рассмотрел итеративный метод push-pull.

• Угадайте, где разместить центр (простейшим будет среднее положение всех центров)
• Вычислить векторы в самую дальнюю точку на каждом круге. Они всегда находятся в направлении к центру этого круга и имеют длину distance_to_center_of_circle[i]+radius_of_circle[i] и образуют векторную сумму по мере продвижения. Также обратите внимание, что нужный радиус в текущем местоположении является максимальным из этих длин.
• Предложите шаг (скажем) 1/5 или 1/10 векторной суммы из 2 и повторите вычисления из 2 для новой точки
• Если новая точка нуждается в меньшем круге, чем в старом, сделайте новую точку текущей точкой, иначе разделите разницу, уменьшите размер предлагаемого шага (скажем, половину).
• goto 3

Вы закончите, когда он остановится [+].

Ники ткнул его, пока...

В соответствии с просьбой уточнить второй шаг. Вызовите проверяемую позицию \vec{P} (векторное количество). [+] Вызовите центры каждой окружности \vec{p}_i (также векторные величины), а радиус каждой окружности - r_i. Составьте сумму \sum_i=1^n \hat{p_i - P}*|(p_i-P)|+r_i). [+++] Каждый элемент суммы указывает в направлении от текущей точки оценки к центру рассматриваемого круга, но длиннее на r_i. Сама сумма представляет собой векторную величину.

Радиус R должен заключить весь круг из P в max(|p_i-P|_r_i).

Патологический случай

Я не думаю, что конкретный случай, который был поднят, является проблемой, но он поставил меня на случай, когда этот алгоритм терпит неудачу. Неудача - это неспособность улучшить решение, а не одно из расходящихся, но все же...

Рассмотрим четыре круга радиуса 1, расположенные в

(-4, 1)
(-5, 0)
(-4, 1)
( 5, 0)

и начальное положение (-1, 0). Симметричный по дизайну, так что все расстояния лежат вдоль оси х.

Правильное решение (0, 0) с радиусом 6, но вектор, вычисленный на шаге 2, составляет около:: вычисляет яростно:: (-.63, 0), указывая в неправильном направлении, что приводит к тому, чтобы никогда не находить улучшение по отношению к началу координат.

Теперь приведенный выше алгоритм будет фактическим выбрать (-2, 0) для начальной точки, которая дает начальную векторную сумму:: вычисляет яростно:: около +1.1. Таким образом, плохой выбор размера шага на (3) приведет к менее оптимальному решению.:: вздыхать::

Возможное решение:

• В (3) бросить случайную долю между (скажем +1/5 и -1/5), возможно, взвешенной по отношению к положительному размеру.
• В (4), если шаг отклонен, просто вернитесь к шагу три, не изменяя пределы размера шага.

Однако на данный момент это не намного лучше, чем чистое случайное блуждание, и у вас нет простого условия знать, когда он сходится. Мех.

[+] Или, конечно, замедляет ваше удовлетворение. [++] Использование латексной нотации. [+++] Здесь \hat{} означает нормализованный вектор, указывающий в том же направлении, что и аргумент.

Ответ 6

Я взял то, что некоторые из вас сказали, и вот решение, которое я обнаружил:

public static Circle MinimalEnclosingCircle(Circle A, Circle B) {
            double angle = Math.Atan2(B.Y - A.Y, B.X - A.X);
            Point a = new Point((int)(B.X + Math.Cos(angle) * B.Radius), (int)(B.Y + Math.Sin(angle) * B.Radius));
            angle += Math.PI;
            Point b = new Point((int)(A.X + Math.Cos(angle) * A.Radius), (int)(A.Y + Math.Sin(angle) * A.Radius));
            int rad = (int)Math.Sqrt(Math.Pow(a.X - b.X, 2) + Math.Pow(a.Y - b.Y, 2)) / 2;
            if (rad < A.Radius) {
                return A;
            } else if (rad < B.Radius) {
                return B;
            } else {
                return new Circle((int)((a.X + b.X) / 2), (int)((a.Y + b.Y) / 2), rad);
            }
        }

Круг определяется центром X, Y его центра и радиусом, все являются ints. Там есть конструктор Circle (int X, int Y, int Radius). Выйдя из некоторых старых концепций триггеров, я решил, что лучший способ - найти 2 точки на кругах, которые находятся на расстоянии друг от друга. Как только у меня это будет, средняя точка будет центром, а половина расстояния будет радиусом, и, следовательно, мне будет достаточно, чтобы определить новый круг. Если я хочу охватить 3 или более круга, я сначала запустил это на 2 круга, затем запустил это на появляющемся окружении и другом круге и так далее до тех пор, пока не будет охвачен последний круг. Там может быть более эффективный способ сделать это, но сейчас это работает, и я доволен этим.

Мне кажется странным отвечать на мой вопрос, но я не мог прийти к этому решению без всяких идей и ссылок. Спасибо всем.

Ответ 7

Просто понять уравнения circle и получить уравнение (или ряд) для поиска ответа, а затем начать реализацию. Возможно, мы сможем помочь вам в этом, если вы что-то сделали.

Ответ 8

Итак, если вам не нужен точный круг, это может сделать приближение.

• Возьмите среднее из всех ваших центров кругов, назовите это точка X
• Пусть R1 - максимальное расстояние от X до центра окружности.
• Пусть R2 - максимальный радиус окружностей

Все круги должны находиться внутри круга с центром в X с радиусом R1 + R2

Ответ 9

Это не тривиальная проблема. Я не прочитал все ответы выше, поэтому, если я повторю то, что кто-то уже сказал, это моя проблема.

Каждый круг c_i определяется тремя параметрами x_i, y_i, r_i

Для оптимальной окружности C *

C * таков, что он содержит c_i для всех i

Пусть d_i = || (x, y) - (x_i, y_i) || + r_i

Тогда, если r - радиус круга, который содержит все c_i, то r >= d_i для всех i

Мы хотим, чтобы r было как можно меньше

Итак, r * = max (d_i)

Таким образом, мы хотим минимизировать максимум d_i

So (x *, y *) задаются аргументом arg min max (d_i). И один раз (x *, y *) найдутся, r * можно легко вычислить и будет равно max (d_i). Это минимаксная проблема.

Чтобы упростить понимание, рассмотрим только 2 круга, как мы можем найти (x *, y *)?

(x *, y *) можно найти, найдя (x, y), которые минимизируют (d_1 - d_2) ^ 2. В общем случае

пусть e_ij = (d_i - d_j) ^ 2

Затем определим e =\sum e_ij для я!= j (найдутся n) Из 2-х членов в этой сумме)

(x *, y *) = arg min e

И это то, что нужно решить.

Совет: если r_i = 0 для всех i, то это сводится к традиционной минимальной проблеме окружного круга, когда вход представляет собой кучу точек, и мы хотим найти минимальный круг, который покрывает все из них.