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

Question

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

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

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

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

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

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

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

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

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

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

Редактировать: Вот новый алгоритм, который я придумал недавно.

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

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

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

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

Answer 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 несколько открытым.Но оно сводится либо к двумерному пространству поиска, либо к решению не совсем правильного уравнения.

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

Answer 2

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

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

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

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

Answer 3

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

Рассмотрим AB как "основание" треугольника,и пусть С плывет по своему кругу.Если вы переместите 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

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

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

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

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

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

Answer 5

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

Конструкция:

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

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

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

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

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

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

Answer 6

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

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

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

Answer 7

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

EDIT

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

Answer 8

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

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

)

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

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

Answer 9

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

Тогда уравнения кругов:

(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. Аналогично для других вершин. Я не могу доказать это, но я думаю, что это дает другие результаты, чем простой метод «самый дальний от центра всех кругов», и по какой-то причине мне это кажется лучше. Я знаю, не очень математично, но тогда я программист.

Answer 10

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

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

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

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

Найти векторы V0 , V1 и V2 , где V _i = P _i - С . Затем найдите точки Q0 , Q1 и Q2 , где Q _i = норма (V _i ) * R + P _i . Где норма указывает на нормализацию вектора, норма (V) = V / | V | .

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