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

Делаю свой 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-библиотеку для этого?

???