Нахождение наименьшего круга, который охватывает другие круги?

Question

Если круг определяется X, Y его центра и радиусом, то как я могу найти круг, который охватывает заданное количество кругов?Единственный круг, который является наименьшим возможным кругом, который может полностью содержать 2 или более кругов любого размера и местоположения.

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

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

Answer 1

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

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

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

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

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

3. Если (D + R1)> R2, то окружающий круг имеет радиус (D + R1 + R2) / 2

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

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

где тэта дается

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

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

Answer 2

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

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

Answer 3

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

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

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

Answer 4

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

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

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

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

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

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

Answer 5

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

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

Я бы рассмотрел итеративный двухтактный метод.

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

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

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

Рассмотрим четыре окружности радиуса 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{} означает нормализованный вектор, указывающий в том же направлении, что и аргумент.

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

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

Answer 7

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

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

3 параметра должны быть найдены x *, y *, r * для оптимальной окружности 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

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

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

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

let e_ij = (d_i - d_j) ^ 2

Затем определите e = \ sum e_ij для i! = J (в этой сумме есть n Выберите 2 слагаемых)

(x *, y *) = минимальное значение e

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

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

Answer 8

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

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

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

Answer 9

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