LINUX.ORG.RU

алгоритм поиска свободного места

 , ,


0

3

На ограниченном пространстве (прямоугольник, размеры: H,W) расположены объекты O1, O2, ...(прямоугольники, коорд. угла x,y, размер: h,w).

Между объектами могут быть свободные пространства, Е1, Е2, ...

Вопрос как искать такие свободные пространства (их координата [левый нижний угол] и размер)?

.------.-----------------.-----..
|      |*****************|     ||
| O5   |*   E3          *| O6  ||
|      |*               *|     ||
'------'*****************'-----'|
.------------------------------.|
|                              ||
|                              ||
|             O4               ||
|                              ||
|                              ||
'------------------------------'|
|************.-----.************|
|*   E1     *|     |*          *|
|************|     |*   E2     *|
.-----------.|     |*          *|
|           ||     |*          *|
|           ||     |*          *|
|           ||     |************|
|           || O2  |.---------. |
|   O1      ||     ||         | |
|           ||     ||   O3    | |
|           ||     ||         | |
'-----------''-----''---------'-'
★★★★★

Как насчёт чего-то BSP-подобного? Разбить пространство на прямоугольники по границам известных прямоугольников:

    |      |     |     |     |     |

--  .------.*****************.-----.  --
    |      |*    .     .    *|     |
    | O5   |*   E3     .    *| O6  |
    |      |*    .     .    *|     |
    |      |*****************|     |
--  '------+-----+-----+-----+-----'  --
    |      .     .     .     .     |
    |      .     .     .     .     |
    |      .     .O4   .     .     |
    |      .     .     .     .     |
    |      .     .     .     .     |
--  '------+-----+-----+-----+-----'  --
    *************|     |************
    *    E1.    *|     |*    .     *
    *************|     |*   E2     *
--  .------+-----+ . . |* . . . . .*  --
    |      .     |     |*    .     *
    |      .     |     |*    .     *
    |      .     |     |************
--  |. . . . . . |.O2 .+-----+-----.  --
    |   O1 .     |     |     !     | 
    |      .     |     |    O3     | 
    |      .     |     |     !     | 
--  '------------'-----'-----------'  --
    
    |      |     |     |     |     |
Потом пройтись по всем регионам, выкинуть те, которые принадлежат известным прямоугольниками. Оставшиеся образуют искомые пустые пространства. Смежные регионы объединить.

ilammy ★★★ ()
Ответ на: комментарий от ilammy

Вроде как звучит логично. Обдумаю реализацию. Спасибо.

sdio ★★★★★ ()
Ответ на: комментарий от ilammy

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

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

AIv ★★★★★ ()
Последнее исправление: AIv (всего исправлений: 1)

Так какая задача? Искать максимально большие свободные области? Покрыть всю свободную часть минимальным количеством? Оптимальным образом выделить свободную область заданного размера?

Waterlaz ★★★★★ ()
Ответ на: комментарий от sdio

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

Ты скажи сперва, что искать. Тогда и думать будем, как =)

Waterlaz ★★★★★ ()

Построй грубую битовую маску, сделай заливку — получишь области, где точно нет дырок и области, где дырки есть. Выделением связанных областей найдешь все "дырки". А потом пройдешься по границам "дырок" и уточнишь их координаты.

Eddy_Em ☆☆☆☆☆ ()
Ответ на: комментарий от ilammy

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

Eddy_Em ☆☆☆☆☆ ()

Вообще тут надо просто пройтися по комбинациям углов с отсечениями заведомо ненужных прямоугольников. Это будет отлично работать, если ты уверен, что все твои свободные зоны — прямоугольники. Но у тебя вообще неоднозначности возникают, когда свободное пространство не является прямоугольником(инвертируй свой пример, так что Ei обьекты, а Oi свободное пространство, тогда не ясно какое именно разбиение брать). Поэтому, нужны дополнительные ограничения, например, на количество прямоугольников, или удельную площадь, или соотношение сторон. И вот тогда это будет сложная задача. При некоторых ограничениях, по-моему, сложнее чем задача о ранце.

maggotroot ()

У меня есть 3 реализации алгоритма упаковки (2 на ruby и один на С), но у всех есть как достоинства так и недостатки. Все они «растровые», а не векторные, если так можно сказать. Поле представлено точками (или минимальными прямоугольниками). При установке объекта, точки «закрашиваются», ищется свободное место и устанавливается следующий максимально возможный объект (жадный алгоритм).

Все это худо-бедно работает, но по CPU и памяти это О(n^2) и для одного из вариантов на руби требуются гигабайты памяти для поля 5000х6000

Хотелось бы сделать по-уму.

sdio ★★★★★ ()
Ответ на: комментарий от sdio

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

maggotroot ()
Ответ на: комментарий от maggotroot

Зоны могут быть не прямоугольные, но из них надо выделить максимальные прямоугольные свободные зоны (объекты прямоугольные ведь)

sdio ★★★★★ ()
Ответ на: комментарий от sdio

Тебе надо разъяснить понятие «максимальные прямоугольные свободные зоны», иначе все еще очень не однозначно. Можешь сразу рассказать, в чем суть делать так как ты делаешь, если у тебя нету прямо поставленной задачи, где указано что такое «максимальная зона».

Если ты все еще не понял что я к тебе прикапываюсь, то вот пример. Надо делать так:

-------------
|   |*******|
| O1|*  E2 *|
|   |*     *|
|__ |*******|
|###########|
|#   E1    #|
|###########|
-------------
или так
-------------
|   |*******|
| O1|*  E2 *|
|   |*     *|
|__ |*     *|
|####*     *|
|#E1#*     *|
|####*******|
-------------

?

maggotroot ()
Ответ на: комментарий от maggotroot

Да я не понял чего ты прикопался.

С алгоритмической точки зрения эти два случая одинаковы, только условия разделения разные (1. по горизонтали; 2. по вертикали)

Можешь помочь, бери любой случай и помогай.

sdio ★★★★★ ()
Ответ на: комментарий от sasha1024

Хорошая реализация NP-полной задачи всегда интересна.

А вы с какой целью интересуетесь?

sdio ★★★★★ ()
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.