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

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

    |      |     |     |     |     |

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

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

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

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

См. задача о ранце.

нет

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

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

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

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

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

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

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

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

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

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

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

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

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

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

-------------
|   |*******|
| O1|*  E2 *|
|   |*     *|
|__ |*******|
|###########|
|#   E1    #|
|###########|
-------------

-------------
|   |*******|
| O1|*  E2 *|
|   |*     *|
|__ |*     *|
|####*     *|
|#E1#*     *|
|####*******|
-------------

?

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

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

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

Ещё актуально? :)

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

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