Такая задача:

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

Можно попробывать сделать так:

//Создаем объект Geometry, который будет содержать мультигеометрию уже нарисованных объектов
Geometry unionOfProcessed = null;

// Берем след. объект карты f. 
f = getNextMapFeature();

// проверяем, что подпись для этого объекта не пересечется с уже нарисованными
if (unionOfProcessed == null || !unionOfProcessed.intersects(f.getGeometry()))
{
  if (unionOfProcessed == null)
  {
    unionOfProcessed = f.getGeometry();
  }
  else unionOfProcessed = unionOfProcessed.union(f.getGeometry()); 

  drawLabel(f.getGeometry(), getLabelString(f)); // где и что нарисовать
}

Это тормозит для моего количества данных.

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

Какую лучше использовать структуру данных для такого 'инкрементального' индексирования?
Посоветуйте java-библиотеку для этого?

???

Здравствуйте, RolandD, Вы писали:

RD>Такая задача:

RD>Делаю свой labeling. То есть для каждого объекта на карте необходимо рядом нарисовать некую подпись. Необходимо, чтобы уже нарисованные лейблы не перекрывались.

Предлагаю тебе разбить всю карту на квадраты (нужно подобрать это число вручную — чтобы не отъедало много памяти и не сильно тормозило одновременно) и при отрисовке запомнить в каком квадрате какой label расположен.
Тогда, при отрисовке новего лэйбла смотрим в какие квадраты он попадает, смотрим какие лейблы лежат в этих квадратах и смотрим пересечения только с ними.
Это все называется обратным индексом лэйблов по квадратам

Здравствуйте, RolandD, Вы писали:

RD>Делаю свой labeling. То есть для каждого объекта на карте необходимо рядом нарисовать некую подпись. Необходимо, чтобы уже нарисованные лейблы не перекрывались.

Думаю сначала нужно определиться с алгоритмом, а под него уже и структуру подбирать.
Если не двигать уже нарисованные, то очень быстро можно зайти в тупик. Скажем, нарисовав 20-30% (цифра от балды), уже не сможешь разместить новую подпись.

Здравствуйте, RolandD, Вы писали:

RD>Такая задача:

RD>Делаю свой labeling. То есть для каждого объекта на карте необходимо рядом нарисовать некую подпись. Необходимо, чтобы уже нарисованные лейблы не перекрывались.
RD> ...
RD>Я правильно понимаю, что нужно поддерживать некий пространственный индекс, по нему быстро искать уже отрисованные и смотреть не пересекаются ли они со следующим обьъектом, для которого хотим нарисовать подпись.

RD>Какую лучше использовать структуру данных для такого 'инкрементального' индексирования?

Проблемы явно две:

1. Как быстро определить, есль ли уже метка в некоторой позиции
   
2. Что делать, если она там уже есть

Первая проблема (быстрый поиск) решается сравнительно просто, например использованием kd-tree.

Вторую проблему вам придется решать самостоятельно. Не ставить метку вообще — сомнительное решение. Сдвигать уже существующие (как именно сдвигать?) — придется перебалансировать дерево поиска, что дорого. Возможно, есть смысл заранее выделять проблемные области (густые кластеры объектов) и работать с ними отдельно от остальной карты.