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


Пока я придумал решение, которое базируется на rtree. В дереве хранится свободное пространство прямоугольниками:
Берем rtree-структуру, и размещаем на ней прямоугольник размером с лист. Это будет наше свободное место. Когда надо на листе разместить вновь поступивший прямоугольник, то надо пометить это пространство занятым. Мы удаляем из rtree этот лист, бьем его на пересекающиеся листы снизу,сверху, справа, слева от занятого места и засовываем эти 4 листа снова в rtree.

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


Навскидку, это работает. Но есть проблема в скорости - rtree работает медленно (использую sourceforge.net/projects/jsi/) как только прямоугольников становится много. И время растет нелинейно. 38прямогульников обрабатывается меньше чем за секунду.
51 поступивших прямоугольникв - 77сек на феном-3000, при этом размер rtree доходит до 1400000. И это, насколько понимаю, не столько проблема самого rtree, и не проблема java, сколько не очень хороший алгоритм. Cлишком много получается вставок и удалений. Плюс каждая вставка - это как правило удаление минимум 1 и вставка минимум 4 листов. Это если они не пересекаются. Количество листов растет лавинообразно.

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

mayton,

Для каждого прямоугольника - свои желаемые координаты. Т.е., это пары (прямоугольник, координаты). Таких пар - до тысячи, обычно - несколько сот.

mayton,

"Думаю что нужно искать границу для каждого множества Rectangles. И при постановке очередного прямоугольника ставить его в экстримальных точках границы."

не...видимо я некорректно объяснил задание. вобщем, за идею спасибо, я подумаю как ее можно приспособить для решения, но похоже, что это не то.

Нету такого, что много прямоугольников надо лепить к одной координате. Для каждого прямоугольника - своя координата.

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

Щас попытаюсь приложить картинку на которой видно как оно накладывается

Выяснил, что я не одинок. Похожие вопросы:

http://www.linux.org.ru/forum/development/9912322
http://www.gamedev.ru/code/forum/?id=157988

Загуглил.

Похоже, что нет. Оптимальный раскрой - это расположить поплотней, как показал mayton на картинке. А у мне, все же, чуток не то нужно.

Но все равно спасибо - посмотрю что там предлагается.