|
|
|
nicki1987 |
|
|||
Новичок Профиль Группа: Участник Сообщений: 4 Регистрация: 28.6.2016 Репутация: нет Всего: нет |
Добрый день.
Дан прямоугольник шириной W и высотой H. Даны N1 окружностей диаметром D1, N2 окружностей диаметром D2...Nk окружностей диаметром Dk. N>=1, k>=1, D>0. Разместить окружности в прямоугольнике так, чтобы Окружности не пересекались между собой Окружности не пересекались с границами прямоугольника Окружности были распределены по всей площади прямоугольника. Т.е. например так, чтобы не было ситуации, когда все окружности "забились" в угол. Окружности располагались на как можно меньшем количестве горизонтальных/вертикальных осей. Т.е. чтобы была некая сетка осей. Предложить варианты размещения Буду рад любой помощи. Задача имеет прикладной смысл на практике - будут производиться электромонтажные коробки с отверстиями для ввода кабелей. |
|||
|
||||
Akina |
|
|||
Советчик Профиль Группа: Модератор Сообщений: 20570 Регистрация: 8.4.2004 Где: Зеленоград Репутация: 20 Всего: 453 |
Ну задачка-то тянет на переборную.
И сколько в коробке тех отверстий? на одной стороне, понятно... десяток? два? ну вряд ли сотня... а такое проще руками раскидать. Если, конечно, отверстия не покрывают более половины площади грани - тут вообще уместить бы. -------------------- О(б)суждение моих действий - в соответствующей теме, пожалуйста. Или в РМ. И высшая инстанция - Администрация форума. |
|||
|
||||
nicki1987 |
|
||||
Новичок Профиль Группа: Участник Сообщений: 4 Регистрация: 28.6.2016 Репутация: нет Всего: нет |
Согласен. Но пока не укладывается в голове каким алгоритмом.
Отверстий может быть порядка 30-40 на одной грани (есть большие коробки). Как правило, конечно, 10-15. Руками можно, но стоит задача написать автоматический расстановщик (далее это будет перекладываться в чертеж автокад). Задача сведена к минимуму - расставить окружности по прямоугольнику. |
||||
|
|||||
Akina |
|
|||
Советчик Профиль Группа: Модератор Сообщений: 20570 Регистрация: 8.4.2004 Где: Зеленоград Репутация: 20 Всего: 453 |
Надеюсь, можно задвинуть приблизительно такой постулат - суммарная площадь кругов более чем на порядок превышает площадь прямоугольника? В этих условиях я вполне могу придумать вменяемый и рабочий алгоритм (оптимальности не жди). А если это соотношение типа 1/2, то даже мыслей никаких нет... -------------------- О(б)суждение моих действий - в соответствующей теме, пожалуйста. Или в РМ. И высшая инстанция - Администрация форума. |
|||
|
||||
nicki1987 |
|
|||
Новичок Профиль Группа: Участник Сообщений: 4 Регистрация: 28.6.2016 Репутация: нет Всего: нет |
только тут наоборот. Все же окружности - это отверстия, а значит их площадь точно меньше площади прямоугольника. Постулат принимаем. Оптимальности не требуется. Рад принять любую помощь! Спасибо. |
|||
|
||||
Akina |
|
|||
Советчик Профиль Группа: Модератор Сообщений: 20570 Регистрация: 8.4.2004 Где: Зеленоград Репутация: 20 Всего: 453 |
Отверстия, так на минуточку, всё-таки круги. Окружности - это их края, границы. Насчёт наоборота - да, второпях накосячил. Но в этой фразе главное - именно "на порядок". Не вдвое, не втрое, а минимум раз в десять, а то и больше. -------------------- О(б)суждение моих действий - в соответствующей теме, пожалуйста. Или в РМ. И высшая инстанция - Администрация форума. |
|||
|
||||
ksnk |
|
|||
прохожий Профиль Группа: Комодератор Сообщений: 6855 Регистрация: 13.4.2007 Где: СПб Репутация: 7 Всего: 386 |
А с технологией как?
Окружность это что? Размер входящего кабеля? А соединительные гайки имеют размер? Отверстия должны отделяться друг от друга вполне на определенное расстояние, которое определяется прочностью материала коробки и прикладываемыми к узлу усилиями... -------------------- Человеку свойственно ошибаться, программисту свойственно ошибаться профессионально ! |
|||
|
||||
nicki1987 |
|
||||
Новичок Профиль Группа: Участник Сообщений: 4 Регистрация: 28.6.2016 Репутация: нет Всего: нет |
Хорошо, условия приняты! я вижу на другом ресурсе тоже в моей теме отписался надеюсь чего-нибудь совместными усилиями мы все же добьемся!
В данном случае задача уже сведена к минимуму и все отступы и критические расстояния заложены в размеры прямоугольника и диаметры окружностей, соответственно окружности могут касаться друг друга и стенок прямоугольника. |
||||
|
|||||
Akina |
|
|||
Советчик Профиль Группа: Модератор Сообщений: 20570 Регистрация: 8.4.2004 Где: Зеленоград Репутация: 20 Всего: 453 |
-------------------- О(б)суждение моих действий - в соответствующей теме, пожалуйста. Или в РМ. И высшая инстанция - Администрация форума. |
|||
|
||||
Правила форума "Алгоритмы" | |
|
Форум "Алгоритмы" предназначен для обсуждения вопросов, связанных только с алгоритмами и структурами данных, без привязки к конкретному языку программирования и/или программному продукту.
Если Вам понравилась атмосфера форума, заходите к нам чаще! С уважением, maxim1000. |
0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей) | |
0 Пользователей: | |
« Предыдущая тема | Алгоритмы | Следующая тема » |
|
По вопросам размещения рекламы пишите на vladimir(sobaka)vingrad.ru
Отказ от ответственности Powered by Invision Power Board(R) 1.3 © 2003 IPS, Inc. |