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

Я программист, являюсь ли я исключением, чем?

Марко Канту также описывает это в своей книге «Delphi 2009 handbook» - стр. 242. Он говорит, что это никогда не оправдано в исходном коде VCL.

Обычным методом является извлечение каждой цифры, а затем ее печать. Код я вам не дам, но это реализованная версия:

int d; // your number

/* While `d` is not zero */
/* Modulus `d` with 10 to extract the last digit */
/* Print it, with your space */
/* Divide by 10 to remove the last digit */
/* Repeat */

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

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

Для встраивания изображения можно использовать схему URI «data:» .

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

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

Если у вас есть объект одного типа и вы хотите заполнить свойства объекта другого типа с помощью свойств первого типа, у вас есть два варианта:

1. Вручную написать код, чтобы сделать такое сопоставление.
2. Используйте инструмент, который будет автоматически обрабатывать это для вас.

AutoMapper является примером 2.

Наиболее часто используется для сведения моделей в объекты передачи данных (или, в общем случае, для отображения через границы слоев). Что очень приятно в AutoMapper, так это то, что для обычных сценариев нет необходимости выполнять настройку ( convention over configuration ).

Отображение объектов между слоями. Хороший пример: Здесь

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

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

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

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

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

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

В соответствии с просьбой уточнить этап 2. Вызовите проверяемую позицию \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) . Симметрично по конструкции так, чтобы все расстояния лежали вдоль оси X.

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

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

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

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

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

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

KOffice поддерживает ODF и записывается на языке C++. Я подозреваю, что они могли решить все, что вы пытаетесь решить. http://www.koffice.org

Лучший способ - использовать комбинацию remove_if и стереть

s.erase(remove_if(s.begin(), s.end(), evenOddFunctor), s.end())

Это будет полезно http://en.wikibooks.org/wiki/More_C%2B%2B_Idioms/Erase-Remove

Также см. эффективный STL Скотта Мейерса

Изменить : Хотя мое решение неверно, я не удаляю его. Это может быть хорошим обучением для такого человека, как я, который не говорит о мутабельных/неизменных итераторах

Поэтому, если вам не нужна точная окружность, это приближение может сделать.

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

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

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

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

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

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

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

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

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

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

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

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

Каждый круг 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 * = max (d_i)

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

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

Чтобы облегчить все возможное, чтобы поделиться всего 2 круга, как мы можем найти (X *, Y *)?

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

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

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

(x *, y *) = arg min e

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

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