Проверьте, соответствуют ли три круга внутри треугольника

Question

Я некоторое время думал о написании программы, которая говорит мне, могут ли три круга с заданными диаметрами поместиться внутри треугольника с заданными длинами сторон без наложения друг на друга (прикосновение в порядке).

Как можно подуматьоб этом?

Answer 1

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

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

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

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

Расстояние AS₁ равно r₁ / tan (½α), расстояние S₂B равно r₂ / tan (½β), а расстояние S₁S₂ равно √ ((r₁ + r₂) ² - (r₁ - r₂) ²) = 2√r₁r₂

Круги подходят, если AS₁ + S₁S₂ + S₂B ≤ AB.

---

В конфигурации (2) мы помещаем два круга в два из углов треугольника, а третий круг между этими двумя и одним из двух ребер, который не касается обоих кругов:

Определить, подойдут ли они, немного сложнее:

Чтобы найти длину AS₁, нам нужно пройти вокруг треугольника от угла C до точки T. Я оставлю детали этого в качестве упражнения.

Существует 18 способов упорядочить круги в этой конфигурации.

---

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

Answer 2

Просто предположение: ваша проблема может быть связана с проблемой кругов Апполония.

Я столкнулся с ним, пытаясь рекурсивно подогнать 3 круга в пределах 4-го без пересечения для некоторой фрактальной анимации, поэтому стоит попробовать.

Вы найдете подробное объяснение в Wolfram (эта проблема была решена только в 1968 году): http://mathworld.wolfram.com/ApolloniusProblem.html

Answer 3

Я думаю, что достаточно попробовать все 6 возможных перестановок (A1 B2 C3, A2 B1 C3, A1 B3 C2, A3 B1 C2, A2 B3 C1, A3 B2 C1).Если круг не касается двух ребер треугольника, то его расположение в некотором смысле является неоптимальным, и вы можете выделить больше места для двух других, сдвинув его в угол.Если возможно приклеить три круга в треугольнике без их наложения, то, вероятно, можно сдвинуть их в углы (для случая, когда все они заклинивают по краям, поднимите их все вместе и поверните на 60 градусов).Конечно, это не строгое доказательство, но я уверен, что оно работает.Кроме того, я полагаю, что решение всегда будет заключаться в том, чтобы расположить самые большие круги под самыми широкими углами, потому что это те, которые потенциально могут занимать самое центральное пространство треугольника.

Answer 4

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

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

Некоторые из лучших математиков мира регулярно участвуют в брате в stackoverflow, mathoverflow.org, так что вы можете попробовать опубликовать эту проблему там.

Спасибо за сообщение.