Форум программистов [Powered by Invision Power Board]

Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате

Форум программистов > Алгоритмы > Определение размеров пустой области

Автор: SANCHO123 29.4.2012, 08:02

Здравствуйте!

У каждого прямоугольника есть координаты X,Y, длина и ширина.

Как определить определить расстояния (см. рисунок) ?

Автор: _Y_ 29.4.2012, 09:03

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

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

Для случая определения расстояния по вертикали:
Имеем набор прямоугольников, определяемых точками двух противоположных углов (xA,yA) - верхний левый, (xB,yB) - нижний правый. (X,Y) - координаты точки.
1. Исключаем из рассчета все прямоугольники, у которых xA>X, то есть лежащие правее точки.
2. Исключаем из рассчета все прямоугольники, у которых xB<X, то есть лежащие левее точки.
3. Дальше работаем только с оставшимися прямоугольниками.
4. Прямоугольники сортируем по yA, например.
5. Находим величины yA(i) лежащие ближе всего к Y с большей, например, стороны. Условия можно записать как Y<yA(i) и yA(i)-Y=min
6. Ответом будет разность yA(i) - yB(i-1)

Есть варианты:

Если после п.2 прямоугольников не осталось - пространство свободно по всей высоте.
Если найденый индекс i указывает первый элемент массива - пространство свободно до верха.
Если индекс i соответствующий условиям найти не удается - пространство свободно до низа.

При этом предполагается что (X,Y) заведомо взята на пустом пространстве или на стороне прямоугольника с этим пространством граничащей. Иначе надо добавлять проверки и другие операции после пункта 2.

Автор: SANCHO123 29.4.2012, 12:09

Цитата

По какому принципу выбирается линия вдоль которой проводится измерение?

От нижней стороны (случай прямоугольника 1), от правой стороны (случай прямоугольника 2 и 4).
Вертикально - область с наибольшей шириной. Горизонтально - область с наибольшей высотой.

Может быть есть вариант и лучше.
Задача: покрыть свободную область прямоугольниками.

Эта часть пустой области должна определяться от прямоугольника 1.
http://fastpic.ru/view/35/2012/0429/e873f3e6ede5eda4d448616d85bfb3f2.jpg.html

Эта от 4
http://fastpic.ru/view/37/2012/0429/0b97478a685796802a19b1bacdd8035a.jpg.html

http://fastpic.ru/view/36/2012/0429/2eb0c707909520724132643747e1c85b.jpg.html

Автор: _Y_ 29.4.2012, 14:47

Правильно ли я понимаю, что нужно найти область, в которую можно вписать следующий самый большой прямоугольник?

Тогда встает вопрос - критерий того что есть "самый большой"? Самый большой по площади? Или может по наибольшей стороне?

Автор: SANCHO123 29.4.2012, 18:52

Цитата

Нужно просто найти пустые области.

Сначала я хотел описать пустую область замкнутым полигоном. Но я не знаю как это сделать.
Потом решил описать пересекающимися прямоугольниками.

Автор: SANCHO123 29.4.2012, 19:21

А что если проверить каждую точку на принадлежность прямоугольникам?

Получится массив точек пустой области.

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

Автор: _Y_ 29.4.2012, 20:12

Цитата(SANCHO123 @ 29.4.2012, 19:21

)

А что если проверить каждую точку на принадлежность прямоугольникам?

В принципе можно конечно. Но будут две заморочки.
1. Это будет не самый быстрый в мире алгоритм.
2. Если в конечном счете нужны будут все-таки прямоугольники получится много частично накладывающихся прямоугольников. От каждой точки, попавшей в чистое поле можно построить прямоугольник по описанному выше алгоритму. Но прямоугольники от разных точек получатся разные.

Впрочем, если это не пугает, можно так и поступать:
Попозже подумаю как сделать такой алгоритм чуть более разумным.

Автор: SANCHO123 29.4.2012, 20:41

Цитата

Это будет не самый быстрый в мире алгоритм.

Его можно будет распараллелить?

Цитата

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

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

X,Y,W,H (столбец, строка, ширина, высота).

Пример:
00000
00000
10100
10100

Результат:
0,0,5,2
1,0,1,4
3,0,2,4

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

И спасибо за ответы smile

Автор: _Y_ 29.4.2012, 21:48

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

Имеем:
Поле точек-пикселей размером Xmax на Ymax
Массив прямоугольников M в котором каждый прямоугольник определяется точками (xA,yA),(xB,yB)

1. Задаем начальное значение Y=0
2. Копируем из массива M во временный массив m все члены, соответствующие условию (yA<Y)AND(yB>Y). То есть выбираем все прямоугольники лежащие на горизонтали с координатой Y.
3. Сортируем массив  m по xA
4. Ищем "зазор" в массиве  m, т.е. любую пару соседних прямоугольников, для которой xB(i)< xA(i+1), где i - индекс прямоугольника в массиве m. Зазорами также будут случаи 0< xA(1) и xB(max)<Xmax.
5. Если ни одного зазора не найдено значит прямоугольники плотно упакованы вдоль выбранной горизонтали. Идем к пунту 7.
6. Если зазор найден - строим в нем прямоугольник. Добавляем этот прямоугольник в массивы  M и  m. Возвращаемся к пункту. 3.
7. Выбираем новую горизонталь Y=Y+1.
8. Если Ymax<Y рассчет окончен. Если нет - возвращаемся к пунту 2 для обработки новой горизонтали.

Поле должно заполняться не-накладывающимися друг на друга прямоугольниками. Условие - исходные прямоугольники тоже не накладываются друг на друга.

Алгортим можно оптимизировать конечно. Это я так - навскидку придумал.

Автор: SANCHO123 29.4.2012, 22:21

Хороший алгоритм. Спасибо smile

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

Автор: _Y_ 30.4.2012, 21:55

Цитата(SANCHO123 @ 29.4.2012, 22:21

)

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

Не понял я что-то. Может как-то другими словами до меня лучше дойдет. При чем здесь вероятность?

Автор: SANCHO123 30.4.2012, 22:13

Я нарисую.

При таком расположении по предложенному алгоритму будет 3 области, правильно?
http://fastpic.ru/view/33/2012/0430/45751280ecfb59437ad6eef52be21ecb.jpg.html

Но не в одну из этих областей не поместиться прямоугольник изображенный зеленым цветом:
http://fastpic.ru/view/37/2012/0430/128130841b88912fa0e265ae81c590fa.jpg.html

В случае перекрывающихся прямоугольников он поместится
http://fastpic.ru/view/35/2012/0430/8ee9e3ed61a4926a6ff4ab1a797f1d7b.jpg.html

Автор: SANCHO123 30.4.2012, 22:28

Решил попробовать самое простое в реализации решение: выделение прямоугольных областей из матрицы. Алгоритм получится очень очень медленным.

Х=0...(W-1)
begin
Поиск последовательности нулей по вертикали.
Если найдена такая последовательность, запомнить координаты начала и конца.
Проверить, если ли такая же последовательность левее (с такими же значениями Y начала и конца)
Если есть - проверить еще левее, если нет -запомнить координаты.
Перейти к следующей последовательности.
end

Аналогично по горизонтали.
\\\\
Получается очень много прямоугольников лежат в друг друге.
После работы алгоритма эти прямоугольники нужно удалить. Проверка на принадлежность очень простая, но для большего количества прямоугольников данная операция занимает много времени. Потому таких прямоугольников не должно быть (желательно).

Автор: Mirkes 1.5.2012, 05:31

Если я правильно понимаю, речь идет о решении задачи оптимальной упаковки. Я этой задачей специально не занимался, но как-то раз оппонировал диссертацию на эту тему. В большинстве случаев делают так.
1. В начале есть пустая область - весь контейнер.
2. При добавлении нового груза (прямоугольника) все пустые области, содержащие этот груз либо
    2.1. исчезают - вся область закрыта прямоугольником
    2.2. уменьшаются - крайняя часть одной из областей закрыта грузом
    2.3. разбивается на несколько пустых областей - угол груза попал в пустую область.
3. После первичной обработки проводится объединение некоторых пустых областей.
4. переход к следующему грузу.

Большинство алгоритмов различаются именно способом учета пустых областей.
Думаю, что для начала будет полезно ознакомиться с имеющимся опытом в данной области.

Автор: _Y_ 1.5.2012, 15:15

Цитата(SANCHO123 @ 30.4.2012, 22:13)

Нет, это не то, о чем я думал. Ведь могут быть и такие варианты:
user posted image

То есть алгоритм находит только первое попавшееся место, в которое можно вставить прямоугольник (красная линия - она вообще-то должна идти по верху свободного места, но так ее виднее). А уж как от него тянуть этот прямоугольник вниз - дело ваше. Но хотите - придумаю.

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

Автор: _Y_ 1.5.2012, 17:39

ЗЫ: Еще точнее - алгоритм находит позицию с наименьшим Y, в которую удобно вставить верхний край прямоугольника. Если зазоров на одном уровне несколько - одну из таких позиций. А уж как прямоугольник строить это отдельно надо придумывать. (слово "удобно" здесь не означает "обязательно")

Автор: SANCHO123 3.5.2012, 18:09

Придумал. Спасибо smile

Автор: Mirkes 3.5.2012, 18:24

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

Автор: _Y_ 3.5.2012, 21:09

Цитата(Mirkes @ 3.5.2012, 18:24

)

Почему не держать области сразу

Мне кажется задача и состоит именно в поиске областей. А уж как заполнять их - дело вкуса.

Автор: SANCHO123 4.5.2012, 14:24

Цитата

Мне кажется задача и состоит именно в поиске областей. А уж как заполнять их - дело вкуса.

Именно так.

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