[Shoorup]

Итак имеем несколько окружностей произвольного диаметра. Например 17,24,36,17мм Необходимо разместить эти окружности вплотную так, чтобы описанная окружность вокруг них была минимального диаметра. Этот диаметр и нужно вычислить. Окружности могут располагаться на плоскости произвольно.
Задачка явно школьная но у меня чего-то на ум ничего не приходит как такое можно вычислить.

[Кулик Алексей aka kpblc]

И где здесь программирование?

[gomer]

24 в 36, 17 в 24 -> d = 36

[Shoorup]

Сообщение от Кулик Алексей aka kpblc И где здесь программирование?

Тут надо алгоритм найти. А программировать я смогу
Круг в круг помещать нельзя. Груги могут только соприкасаться. Окружностей может быть сколько угодно и разных диаметров.

[zamtmn]

http://mathworld.wolfram.com/CirclePacking.html

[Shoorup]

zamtmn, спасибо за наводку. Но всеравно не то. У меня окружности имеют разные диаметры, а на приведенной ссылке одинаковые.

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

[zamtmn]

zamtmn, спасибо за наводку. Но всеравно не то. У меня окружности имеют разные диаметры, а на приведенной ссылке одинаковые.

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

[VVA]

Draw a minimum circle that contain select points
The minimum circle contain set of points, Thanks for Menzi's function

[Олег (jr.)]

Сообщение от Shoorup Тут надо алгоритм найти. А программировать я смогу Круг в круг помещать нельзя. Груги могут только соприкасаться. Окружностей может быть сколько угодно и разных диаметров.

Ну если сможешь, держи алгоритм
по-простому он называется "алгоритм заполнения рюкзака"
http://en.wikipedia.org/wiki/Knapsack_problem

[Елпанов Евгений]

Сообщение от Shoorup Честно говоря думал задачка простая и я просто в школе плохо учился ... но тут походу простого решения не получится. Для чего все эти расчеты: делаю трассу кабеля. Есть полиэтиленовые трубы с внутренним диаметром 97.4мм Есть кабели с наружным диаметром (разные). Ну и идет проверка на заполнение трубы. Если кабели не входят, беру запас. Думал автоматизировать каким лиспом. Например вводить только диаметры кабелей а в результате получать диаметр заполнения трубы и необходимость запаса... В общем придется "на глазок" по старинке...

Чтож ты сразу не сказал, что решение нужно не абсолютное и даже не важно знать, на сколько % решение отстоит от абсолютного? Если тебе нужно просто хорошее решение, то можно использовать любой алгоритм решения таких задач! Самый простой - жадный алгоритм, берем самые большие (одинаковые) диаметры и располагаем их наиболее компактно треугольником и далее приращивая по кругу треугольники. Потом берем следующий по размеру диаметр и проверяем возможность вставки внутрь получившихся треугольников, вставляем внутрь, остальные приращиваем снаружи. Потом берем следующий по размеру диаметр и все заново повторяем... В общем случае, жадный алгоритм один из самых простых в реализации и дает довольно хорошее заполнение в самых различных областях. Возможно, исходя из свойств твоих диаметров, ты сможешь улучшить алгоритм, применительно только к своей задаче.

Если нужно действительно хорошее заполнение, можно пойти по пути генетических алгоритмов. Суть генетического алгоритма - постепенное улучшение имеющегося заполнения. Т.е. применительно к твоей задаче, берем все диаметры и заполняем самым простым способом - как пример в строчку выставляем самые большие диаметры, над ними следующей строкой меньшие, дальше еще меньшие итд, получая таким образом некую пирамиду. Полученное заполнение имеет место быть, но качество изначально неудовлетворительное. Потом пишем несколько простых программ, которые перестановками кругов, могут уплотнить общее заполнение, например, если одна строка слишком длинна, то можно убрать одну окружность и переместить на другую строку или если круги стоят квадратом, то сместить их в треугольник. Уверен, недолго поразмышляв о задаче с перестановками, можно придумать целую кучу различных простых алгоритмов, которые могут немного улучшить размещение кругов. Далее, имея несколько программ по улучшению общего замощения, можно их последовательно выполнять, каждый раз проверяя, есть ли изменения в диаметре описанной окружности и какова величина изменения от перестановок. Если программа улучшает картину, мы оставляем изменения, если не улучшает или ухудшает - то отменяем. Таким образом, мы последовательно применяем все программы, постоянно проверяя результат и когда после цикла применения всех программ, результат перестанет улучшаться или шаг улучшения будет меньше выбранной нами величины, можно заканчивать вычисления.
Мне нравится такой подход тем, что действительно получается отличный результат и легкое улучшение программы (все алгоритмы довольно просты и по отдельности не занимают много места)...

[Shoorup]

Не могу сообразить как найти центр и как узнать диаметр красного круга. Всю голову сломал

[dyr]

Это милиментарно. В Corel.

[Shoorup]

А на бумаге?

[VVA]

Сообщение от Shoorup Не могу сообразить как найти центр

Центр массы, средняя точка, пересечение медиан треугольника.

[dyr]

Давай на бумаге:
1. Проводим три касательные до взаимного пересечения.
2. Вершины образовавшегося треугольника соединяем с центрами окружностей. Получим точки касания внутренних окружностей с внешней.
3. Определяем равноудаленную точку от точек касания окружностей. Это и будет центр внешней окружности.

[Shoorup]

Сообщение от dyr Давай на бумаге: 1. Проводим три касательные до взаимного пересечения. 2. Вершины образовавшегося треугольника соединяем с центрами окружностей. Получим точки касания внутренних окружностей с внешней. 3. Определяем равноудаленную точку от точек касания окружностей. Это и будет центр внешней окружности.

Если не сложно изобразите в AutoCADе. Что-то у меня не сходится
VVA, не знаю как применить к данной задаче этот lisp...

[VVA]

Shoorup, Я п посте #8 давал ссылки на лисп. Ты его смотрел?
На твоем примере поделил с помощью _divide круги точками и применил лисп из #8. Красный круг то, что он выдал

[dyr]

Вот на бумаге:

Рисунки по пунктам в #16. Равноудаленная точка определяется засечкой циркулем. С помощью САПР - построением одинаковых окружностей.

[Shoorup]

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

И все равно меня интересует геометрическое решение для данной задачки, ну или если хотите то просто формула.

Равноудаленная точка определяется засечкой циркулем. С помощью САПР - построением одинаковых окружностей.

А центр этих окружностей где? А радиус этих окружностей? Что-то я под вечер туплю...

[Vov.Ka]

склеить из кусков:
http://forum.dwg.ru/showpost.php?p=488808&postcount=135
а в следующем посте (136) описание