Алгоритм размещения надписей на карте

[deMax]

Есть географическая карта на ней размещены объекты (на карте обозначаются кружочками), как создать к ним подписи чтобы подписи не пересекались друг с другом и не перекрывали сами объекты?

[ecspertiza]

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

1. Проверяем сколько областей на карте, если 0 то добавляем безболезненно.
2. Областей больше ноля, знаем координаты и размеры новой области, проверяем по уже существующим с какими пересекается, если не пересекается, добавляем на карту.
3. Если есть пересечение с соседними областями, то начинаем изменять координаты новой области. Например точка на карте соответствовала левому нижнему углу, перемещаем зону таким образом, что бы точка на карте соответствовала правому нижнему углу, затем опять проверяем пересечения. Таким образом мы можем проверить все 4ре угла, если всеравно есть пересечения, то на откуп программисту, можно поставить как угодно, тут уж ничего не поделаешь.

4. Для оптимизации, можно сначала найти области с которыми возможно пересечение и затем уже проверять только по ним.

[deMax]

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

[deMax]

Может есть готовые алгоритмы или схожие задачи? Желательно быстрый алгоритм, хотя расчет и будет произведен один раз.

[alex312]

Сам я не силен, но вот есть библиотечка - http://www.cgal.org/  , поройся в доках, может что и подойдет.