Проблемы с кругами и треугольниками

У меня есть интересная проблема, которую я пытался решить за последнее время:

У меня есть 3 круга на плоскости 2D xy, каждый с тем же известным радиусом. Я знаю координаты каждого из трех центров (они произвольны и могут быть где угодно).

Каков наибольший треугольник, который можно нарисовать так, чтобы каждая вершина треугольника находилась на отдельном круге, каковы координаты этих вершин?

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

Решение, которое мы придумали, предполагает сначала создание треугольника вокруг трех центров окружности. Затем мы смотрим на каждый круг индивидуально и вычисляем уравнение линии, проходящей через центр круга и перпендикулярно противоположному краю. Затем мы вычисляем две точки пересечения круга. Затем это делается для следующих двух кругов с результатом 6 баллов. Мы перебираем 8 возможных трехточечных треугольников, создаваемых этими 6 точками (ограничение состоит в том, что каждая точка большого треугольника должна быть на отдельном круге) и найти максимальный размер.

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

Мне интересно, если кто-то столкнулся с проблемой, подобной этому, и если да, то как вы ее разрешили?

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

Наконец, да, это для школьной работы, хотя это НЕ домашнее задание/задание/проект. Это часть моей дипломной работы (притом очень маленькая часть, но по-прежнему технически ее часть).

Спасибо за вашу помощь.

Edit: Heres новый алгоритм, который я придумал немного назад.

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

Этот алгоритм будет иметь дело с коллинеарным случаем, если вы рисуете свои линии в одном "направлении" относительно трех точек.

Из нескольких случайных испытаний я попытался использовать программное обеспечение САПР для определения геометрии для меня, этот метод, по-видимому, превосходит все другие ранее описанные методы. Однако уже доказано, что это не оптимальное решение одним из счетчиков Victor примеры.

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

Ответ 1

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

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

Изображение было произведено с использованием пробной версии отличной программы для рабочего стола Geometry Expressions. На диаграмме показаны три круга, центрированные в точках A, E и C. Они имеют равные радиусы, но картина действительно не зависит от равных радиусов, поэтому решение обобщается на круги разных радиусов. Линии MN, NO и OM касаются окружностей и касаются кругов в точках I, H и G соответственно. Последние точки образуют внутренний треугольник IHG, который является треугольником, размер которого мы хотим максимизировать.

Существует также внешний треугольник MNO, который является homethetic внутреннему треугольнику, что означает, что его стороны параллельны таковым IHG.

@Federico заметил, что IHG имеет максимальную площадь, потому что перемещение любой из ее вершин вдоль соответствующего круга приведет к треугольнику, который имеет ту же основу, но меньшую высоту, поэтому меньшую площадь. Чтобы выразить это в несколько более технических терминах, если треугольник параметризуется под углами t1, t2, t3 на трех кругах (как указывает @Charles Stewart, и как используется в моем приложении наискорейшего спуска), то градиент области от (t1,t2,t3) равен (0,0,0), а область экстремальна (максимальна на диаграмме).

Итак, как вычисляется эта диаграмма? Я заранее догадаюсь, что у меня не совсем полная история, но вот начало. С учетом трех кругов выберите точку M. Нарисуйте касательные к кругам, центрированным на E и C, и обозначим касательные точки как G и I. Нарисуйте касательную OHN к окружности с центром в A, которая параллельна GI. Это довольно простые операции как алгебраически, так и геометрически.

Но мы еще не закончили. До сих пор мы имеем только условие, что OHN параллельна GI. У нас нет гарантии, что MGO параллельна IH или что MIN параллельна GH. Поэтому нам нужно вернуться и уточнить M. В интерактивной геометрии программа не имеет большого значения, чтобы установить это, а затем переместите M до тех пор, пока не будут выполнены последние параллельные условия (например, глазными яблоками). Выражения геометрии создали диаграмму, но я использовал немного обмана, чтобы заставить ее сделать это, потому что ее решатель ограничений был, по-видимому, недостаточно силен, чтобы выполнять эту работу. Алгебраические выражения для G, I и H достаточно просты, поэтому их можно было бы решить для M на основе того, что MIHG является параллелограммом, явно или численно.

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

Что это. Этот ответ не совсем завершен, поскольку он оставляет окончательный расчет M несколько открытым. Но он сводится к двумерному пространству поиска или решению ornery, но не к значительному уравнению.

Наконец, я должен не соглашаться с выводом @Federico, что это подтверждает, что решение, предложенное OP, является оптимальным. Правда, если вы перпендикуляры от центров окружности к противоположному краю внутреннего треугольника, то эти перпендикуляры пересекают круг, чтобы дать вам треугольную вершину. Например. H лежит на линии через A перпендикулярно к GI), но это не то же самое, что в исходном предлагаемом решении (которое должно было проходить через A и перпендикулярно к EC - вообще EC не параллельна GI).

Ответ 2

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

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

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

Изменить: Я посмотрел на геометрию немного больше и написал свои выводы в отдельном ответе.

Ответ 3

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

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

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

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

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

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

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

Ответ 4

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

Вы действительно хотите решить проблему:

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)

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

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

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

Ответ 5

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

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

Мы имеем три круга с радиусом 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 (V) = V/| V |.

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

Ответ 6

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

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

(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)

Таким образом, область треугольника (используя формулу Heron)

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

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

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

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

Ответ 7

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

Так как площадь треугольника равна * 5 * base * height, пусть сначала найдет максимальную базу, которая может быть построена с кругами. Base = Max {(| C0-C1 | + 2R), (| C1-C2 | + 2R, (| C2-C0 | + 2R}

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

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

Ответ 8

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

ИЗМЕНИТЬ

Этот метод также имеет проблемы для коллинеарных кругов, таких как другие решения, и не работает.

Ответ 9

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

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

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

Ответ 10

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

Строительство:

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

(2) Нарисуйте хорду между этими двумя касательными точками на каждом круге

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

(4) Подключите их три точки (3) к треугольнику.

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

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