Размещение окружностей в прямоугольнике

[nicki1987]

Добрый день.
Дан прямоугольник шириной W и высотой H. Даны N1 окружностей диаметром D1, N2 окружностей диаметром D2...Nk окружностей диаметром Dk. N>=1, k>=1, D>0. Разместить окружности в прямоугольнике так, чтобы
Окружности не пересекались между собой
Окружности не пересекались с границами прямоугольника
Окружности были распределены по всей площади прямоугольника. Т.е. например так, чтобы не было ситуации, когда все окружности "забились" в угол.
Окружности располагались на как можно меньшем количестве горизонтальных/вертикальных осей. Т.е. чтобы была некая сетка осей.
Предложить варианты размещения

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

[AVA12]

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

[nicki1987]

Цитата

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

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

Цитата

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

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

Цитата

Самое простое решение: расположить центры окружностей на сетке, окружности отсортировать по диаметру, разместить их "змейкой", подвигать линии сетки, чтобы окружности разместились более-менее равномерно

А вот с этого момента поподробнее По какому алгоритму располагать на сетке? что значит "змейкой"? и как распределить равномерно?

Сообщение отредактировано: nicki1987 - 28.06.16, 13:40

[AVA12]

"Змейкой" - это значит, что первый ряд заполняется слева направо, второй - справа налево, третий - опять слева направо и т. д. Алгоритм видится примерно такой:

1. Сортируем окружности по убыванию диаметров.
2. Размещаем первый ряд окружностей вдоль длинной стороны прямоугольника, столько, сколько сможем. Для определенности используем ландшафтную ориентацию прямоугольника. Все центры окружностей кладем на одну горизонтальную линию. После размещения равномерно расталкиваем окружности по горизонтали. Теперь центры окружностей задают вертикальные линии сетки.
3. Размещаем следующий ряд "змейкой", центры опять кладем на одну горизонтальную линию, каждый центр на соответствующей вертикальной линии сетки. По завершении ряда максимально прижимаем его к предыдущему ряду. Повторяем операцию, пока не закончатся окружности.
4. Если вдруг между двумя окружностями ряда оказывается достаточно места, то размещаем посередине между ними очередную окружность, ее центр задает новую вертикальную линию сетки для следующих рядов.
5. После того, как все окружности размещены, равномерно расталкиваем ряды.

P. S. "Равномерно расталкиваем" означает: у нас есть N объектов, с суммарной шириной L, которые нужно равномерно разместить на ширине M, M >= L. Тогда добавляем между объектами промежутки шириной (M - L)/(N - 1).

[Akina]

Цитата AVA12 @ 28.06.16, 16:17

1. Сортируем окружности по убыванию диаметров.

Уже плохо. То есть хорошо с точки зрения технологии, но плохо с точки зрения приближения к оптимальности.
По-хорошему, нужно "через один", причём чтобы максимум разности диаметров пар соседних кругов был минимален.

[nicki1987]

Цитата

"Змейкой" - это значит, что первый ряд заполняется слева направо, второй - справа налево, третий - опять слева направо и т. д. Алгоритм видится примерно такой:

1. Сортируем окружности по убыванию диаметров.
2. Размещаем первый ряд окружностей вдоль длинной стороны прямоугольника, столько, сколько сможем. Для определенности используем ландшафтную ориентацию прямоугольника. Все центры окружностей кладем на одну горизонтальную линию. После размещения равномерно расталкиваем окружности по горизонтали. Теперь центры окружностей задают вертикальные линии сетки.
3. Размещаем следующий ряд "змейкой", центры опять кладем на одну горизонтальную линию, каждый центр на соответствующей вертикальной линии сетки. По завершении ряда максимально прижимаем его к предыдущему ряду. Повторяем операцию, пока не закончатся окружности.
4. Если вдруг между двумя окружностями ряда оказывается достаточно места, то размещаем посередине между ними очередную окружность, ее центр задает новую вертикальную линию сетки для следующих рядов.
5. После того, как все окружности размещены, равномерно расталкиваем ряды.

P. S. "Равномерно расталкиваем" означает: у нас есть N объектов, с суммарной шириной L, которые нужно равномерно разместить на ширине M, M >= L. Тогда добавляем между объектами промежутки шириной (M - L)/(N - 1).

Подход интересный. Мне он в голову не приходил. Пока, конечно, непонятно возникнут-ли трудности с его программированием. На первый взгляд смущает "равномерное расталкивание". Все же если сначала идут большие диаметры, то снизу под, например, первым из них может оказаться маленький диаметр, как и весь ряд. Тогда при равномерном расталкивании маленького ряда оси сместятся в другом порядке, отличном от осей больших диаметров.

[AVA12]

Цитата

хорошо с точки зрения технологии, но плохо с точки зрения приближения к оптимальности

Перфекционизм - зло! У нас здесь практическая задача, так что сгодится достаточно хорошее решение.

Цитата

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

Так ведь на последнем шаге расталкиваются ряды, а не окружности!

[Akina]

Цитата AVA12 @ 28.06.16, 20:09

У нас здесь практическая задача, так что сгодится достаточно хорошее решение.

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

[Pavlovsky]

Разобьём прямоугольник на квадраты, сеткой с шагом равным минимальному диаметру окружности. Каждая окружность будет помещаться в некоторый квадрат KxK шагов сетки. Тогда задача превращается в заполнение прямоугольника квадратами. Если у нас достаточно окружностей помещающихся в квадрат 1x1, то задача решается всегда.

Для более плотной упаковки можно вместо квадратов помещать окружность в набор квадратов напоминающих восьмиугольник.

А можно еще вместо вертикально-горизонтальной сетки использовать гексональную сетку.

[nicki1987]

Цитата

Пока что неизвестно,каков критерий этой самой "хорошести".

Хорошесть - это минимум осей и равномерное распределение по площади.
Вот варианты, которые предлагает одна программа. Все они имеют место быть. Как видно, в основном она предлагает 2-3 основных варианта, потом они отражаются по осям, либо смещаются к какой-либо стороне и получается в четыре раза больше. Инженер/заказчик уже сам решит какой вариант подойдет для конкретного размещения коробки. Количество и размеры отверстий накидал навскидку.

[Pavlovsky]

Цитата nicki1987 @ 29.06.16, 06:37

Вот варианты, которые предлагает одна программа.

Дык сетка гексональная! И размещаем мы в ней шестиугольники!

[nicki1987]

Цитата

И размещаем мы в ней шестиугольники!

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

Цитата

Разобьём прямоугольник на квадраты, сеткой с шагом равным минимальному диаметру окружности. Каждая окружность будет помещаться в некоторый квадрат KxK шагов сетки. Тогда задача превращается в заполнение прямоугольника квадратами. Если у нас достаточно окружностей помещающихся в квадрат 1x1, то задача решается всегда.

Для более плотной упаковки можно вместо квадратов помещать окружность в набор квадратов напоминающих восьмиугольник.

А можно еще вместо вертикально-горизонтальной сетки использовать гексональную сетку.

Хорошо. пусть так. Какой алгритм использовать? гексогональная сетка еще больше меня расстраивает, т.к. в голове не укладывается с какой стороны подойти к задаче

[AVA12]

Цитата

Вот варианты, которые предлагает одна программа.

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

Цитата

Дык сетка гексональная!

Не, это, скорее, две наложенные со смещением прямоугольные сетки.

[foreach]

Ваша программа случайно не DipTrace? Она натолкнула на мысль.

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

[nicki1987]

Цитата

Ваша программа случайно не DipTrace? Она натолкнула на мысль.

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

Нет не DipTrace. И задача - написать свою программу