круги и проблема треугольников

Предположим, что центр окружностей находится в точке C0, C1 и C2; и радиус R.

Поскольку площадь треугольника составляет 0,5 * основание * высота, давайте сначала найдем максимальное основание, которое можно построить с помощью кругов. Основание = Макс {(| C0-C1 | + 2R), (| C1-C2 | + 2R, (| C2-C0 | + 2R}

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

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

Похоже, решение было бы найти самый большой круг Аполлония для трех кругов и затем вписать в него равносторонний треугольник. Доказательство оставлено в качестве упражнения;).

РЕДАКТИРОВАТЬ

У этого метода есть проблемы с коллинеарными кругами, как и у других решений, и он не работает.

Не оптимально, хорошо работает, когда все три не коллинеарны:

У меня нет доказательства (и поэтому я не знаю, гарантированно ли оно наибольшее). Возможно, я поработаю над ним. Но:

У нас есть три окружности радиусом R с позициями (от центра) P0, P1 и P2. Требуется найти такие вершины треугольника, чтобы площадь треугольника была максимальной, а вершины лежали в любой точке ребер окружности.

Найдем центр всех окружностей и назовем его C. Тогда C = (P0 + P1 + P2) / 3. Затем находим точку на каждой окружности, наиболее удаленную от C.

Находим векторы V0, V1 и V2, где V_i = P_i - C. Затем находим точки Q0, Q1 и Q2, где Q_i = norm(V_i) * R + P_i. Где norm обозначает нормализацию вектора, norm(V) = V / |V|.

Q0, Q1 и Q2 - вершины треугольника. Я предполагаю, что это оптимально, потому что это самое дальнее расстояние, на котором вершины могут находиться друг от друга. (Я думаю.)

Я создал приложение HTML5 Canvas , которое может быть полезно для людей, с которым можно поиграть.Он довольно простой (и код не очень красивый), но он позволяет вам перемещать три круга равного радиуса, а затем вычислять максимальный треугольник с использованием градиента / крутого спуска. Вы также можете сохранить растровые изображения диаграммы. На схеме также показан треугольник, вершинами которого являются центры окружностей и одна из высот. Edit1 : «высота» на самом деле просто отрезок прямой, проходящий через один из центров окружности и перпендикулярный противоположному краю треугольника, соединяющего центры. Он есть потому, что его используют некоторые из предложенных конструкций. Edit2 : метод наискорейшего спуска иногда застревает в локальном максимуме. Вы можете выйти из этого максимума, перемещая круг, пока черный треугольник не перевернется, а затем вернув круг в исходное положение. Работаем над поиском глобального максимума.

Это не будет работать в IE, потому что он не поддерживает холст, но большинство других «современных» браузеров должны работать.

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

Изменить: Я еще немного изучил геометрию и изложил свои выводы в отдельном ответе .

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

Тогда уравнения окружностей таковы:

(x1-h1)^2 + (y1-k1)^2 = r^2
(x2-h2)^2 + (y2-k2)^2 = r^2
(x3-h3)^2 + (y3-k3)^2 = r^2

Вершины вашего треугольника - это (x1, y1), (x2, y2) и (x3, y3). Длины сторон вашего треугольника равны

A = sqrt((x1-x2)^2 + (y1-y2)^2)
B = sqrt((x1-x3)^2 + (y1-y3)^2)
C = sqrt((x2-x3)^2 + (y2-y3)^2)

. Таким образом, площадь треугольника равна (используя формулу Герона )

S = (A+B+C)/2
area = sqrt(S(S-A)(S-B)(S-C))

Таким образом, площадь является функцией 6 переменных.

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

Итак, моя вторая мысль - выбрать точку на окружности с центром A следующим образом: построить линию BC, соединяющую центры двух других окружностей, затем построить линию AD, которая перпендикулярна BC и проходит через A. Одна вершина треугольник является пересечением AD и окружности с центром A. То же самое для других вершин. Я не могу это доказать, но я думаю, что он дает другие результаты, чем простой метод «дальше от центра всех кругов», и по какой-то причине мне кажется, что он лучше. Я знаю, не очень математичен, но я программист.

Пусть A, B, C будут вершинами вашего треугольника, и предположим, что они расположены так, как в вашем решении. Обратите внимание, что ключ Свойство вашей конструкции состоит в том, что каждая из вершин лежит на касательной к своей окружности, параллельной противоположной стороне треугольника. Очевидно, что сама окружность целиком лежит по одну сторону от касательной, и в оптимальном решении каждая касательная выходит из своей окружности на той же стороне, что и другие вершины.

Рассмотрим AB как «основание» треугольника, и пусть C плавает в его окружности. Если вы переместите C в другую позицию C 'внутри круга, вы получите еще один треугольник ABC' с тем же основанием, но меньшей высотой, следовательно, также с меньшей площадью:

рисунок 1 http: //control.ee.ethz .ch / ~ ramponif / stuff / circle1.png

По той же причине вы можете легко увидеть, что любое положение вершин, которое не соответствует вашей конструкции, не может быть оптимальным. Предположим, например, что каждая из вершин A ', B', C 'не лежит на касательной, параллельной стороне, соединяющей две другие.

Затем, построив касательную к окружности, которая содержит (скажем) C ', которая параллельна A'B' и оставляет окружность на той же стороне, что и A'B ', и перемещая C' в точку касания C, всегда можно построить треугольник A'B'C, который имеет то же основание, но большую высоту, а значит, и большую площадь:

рисунок 2 http://control.ee.ethz.ch/~ ramponif / stuff / circle2.png

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

Я считаю, что это задача выпуклой оптимизации (нет, это не так, см. ниже), и поэтому она может быть эффективно решена с помощью хорошо известных методов.

По сути, вы хотите решить задачу:

maximize:  area(v1,v2,v3) ~ |cross((v2-v1), (v3-v1))|
such that: v1 in C1, v2 in C2, v3 in C3   (i.e., v_i-c_i)^2 - r_i^2 <= 0)

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

Edit: grad(area(v1,v2,v3))(v_i) = rot90(vec(vj,vk)), где vec(a,b) - двумерный вектор, начинающийся в a и заканчивающийся в b, а rot90 означает положительный поворот на 90 градусов, предполагая, что (vi,vj,vk) ориентированы положительно.

Edit 2: Задача не является выпуклой, что должно быть очевидно, учитывая коллинеарный случай; два вырожденных решения - верный признак невыпуклости. Тем не менее, конфигурация, начинающаяся в центрах окружностей, должна находиться в глобально оптимальном локальном максимуме.

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

Построение:

(1) Постройте треугольник так, чтобы каждая его сторона была касательной к двум окружностям, и, следовательно, каждая окружность имела точку касания на двух сторонах треугольника.

(2) Проведите хорду между этими двумя точками касания на каждой окружности.

(3) Найдите точку на границе окружности на продолженном луче, проходящем из центра окружности через середину хорды. На каждой из трех окружностей должно быть по одной такой точке.

(4) Соедините три точки из (3), чтобы получился треугольник.

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

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

Некоторые начальные мысли.

1. Определение Требуемый треугольник назовем максимальным треугольником . Обратите внимание, что это может быть не уникальным: если все круги имеют один и тот же центр, тогда существует бесконечно много максимальных треугольников, полученных вращением вокруг центра, а если центры коллинеарны, тогда будет два максимальных треугольника, каждый из которых является зеркальным отражением. другого.
2. Определение Треугольник (возможно, вырожденно, точка или прямая), вершины которого являются центрами окружностей, назовем внутренним треугольником .
3. Наблюдение Решение может быть выражено в виде трех углов, указывающих, где на окружности каждого круга должен находиться треугольник.
4. Наблюдение Учитывая две внешние вершины, мы можем определить третью вершину, которая дает максимальную площадь: нарисуйте высоту треугольника между двумя внешними вершинами и центром другого круга. Эта линия пересекает окружность в двух местах; более удаленная точка - это максимальный выбор третьей вершины. ( Исправлен неверный алгоритм, Аргумент Федерико может быть адаптирован, чтобы показать правильность этого наблюдения )
5. Следствие Задача сводится от задачи в трех углах к одной в два.
6. Гипотеза Представьте, что диаграмма представляет собой доску с тремя булавками в трех центрах окружностей. Представьте также замкнутую петлю из веревки, длина которой равна периметру внутреннего треугольника плюс радиус круга, и мы помещаем эту петлю вокруг булавок.Возьмите воображаемую ручку и нарисуйте фигуру петли, где петля всегда тугая. Я предполагаю, что все точки максимального треугольника будут лежать на этой петлеобразной фигуре, и что в случае, когда внутренний треугольник не вырожден, вершинами максимального треугольника будут три точки, в которых петляющая фигура пересекает одну из окружностей. окружности. Множество контрпримеров.

Еще нужно подражать, когда у меня будет время подумать об этом.