| Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате |
| Форум программистов > Алгоритмы > Размещение окружностей в прямоугольнике |
| Автор: nicki1987 28.6.2016, 14:25 |
| Добрый день. Дан прямоугольник шириной W и высотой H. Даны N1 окружностей диаметром D1, N2 окружностей диаметром D2...Nk окружностей диаметром Dk. N>=1, k>=1, D>0. Разместить окружности в прямоугольнике так, чтобы Окружности не пересекались между собой Окружности не пересекались с границами прямоугольника Окружности были распределены по всей площади прямоугольника. Т.е. например так, чтобы не было ситуации, когда все окружности "забились" в угол. Окружности располагались на как можно меньшем количестве горизонтальных/вертикальных осей. Т.е. чтобы была некая сетка осей. Предложить варианты размещения Буду рад любой помощи. Задача имеет прикладной смысл на практике - будут производиться электромонтажные коробки с отверстиями для ввода кабелей. |
| Автор: Akina 28.6.2016, 14:49 | ||
Ну задачка-то тянет на переборную.
И сколько в коробке тех отверстий? на одной стороне, понятно... десяток? два? ну вряд ли сотня... а такое проще руками раскидать. Если, конечно, отверстия не покрывают более половины площади грани - тут вообще уместить бы. |
| Автор: nicki1987 28.6.2016, 16:31 | ||||
Согласен. Но пока не укладывается в голове каким алгоритмом.
Отверстий может быть порядка 30-40 на одной грани (есть большие коробки). Как правило, конечно, 10-15. Руками можно, но стоит задача написать автоматический расстановщик (далее это будет перекладываться в чертеж автокад). Задача сведена к минимуму - расставить окружности по прямоугольнику. |
| Автор: Akina 28.6.2016, 18:05 | ||
Надеюсь, можно задвинуть приблизительно такой постулат - суммарная площадь кругов более чем на порядок превышает площадь прямоугольника? В этих условиях я вполне могу придумать вменяемый и рабочий алгоритм (оптимальности не жди). А если это соотношение типа 1/2, то даже мыслей никаких нет... |
| Автор: nicki1987 28.6.2016, 20:42 | ||
только тут наоборот. Все же окружности - это отверстия, а значит их площадь точно меньше площади прямоугольника. Постулат принимаем. Оптимальности не требуется. Рад принять любую помощь! Спасибо. |
| Автор: Akina 28.6.2016, 20:47 | ||
Отверстия, так на минуточку, всё-таки круги. Окружности - это их края, границы. Насчёт наоборота - да, второпях накосячил. Но в этой фразе главное - именно "на порядок". Не вдвое, не втрое, а минимум раз в десять, а то и больше. |
| Автор: ksnk 28.6.2016, 21:56 |
| А с технологией как? Окружность это что? Размер входящего кабеля? А соединительные гайки имеют размер? Отверстия должны отделяться друг от друга вполне на определенное расстояние, которое определяется прочностью материала коробки и прикладываемыми к узлу усилиями... |
| Автор: nicki1987 28.6.2016, 22:12 | ||||
Хорошо, условия приняты! я вижу на другом ресурсе тоже в моей теме отписался  надеюсь чего-нибудь совместными усилиями мы все же добьемся!
В данном случае задача уже сведена к минимуму и все отступы и критические расстояния заложены в размеры прямоугольника и диаметры окружностей, соответственно окружности могут касаться друг друга и стенок прямоугольника. |
| Автор: Akina 28.6.2016, 22:53 |
| Да. http://forum.sources.ru/index.php?showtopic=409076 |
