Альтернативные методы индексации для операций с точками

Обычно используется пространственный индекс ограничивающего прямоугольника для повышения производительности при работе с большим количеством объектов. Где выполняются операции с отдельными геометриями с большим количеством вершин, существуют ли какие-либо подобные стратегии оптимизации?

Например, существуют ли какие-либо структуры данных, которые могут ускорить точку в полигоне или операциях объединения?

OK только для точки в полигоне:

Я думаю, что проблема основана на «фрактальной природе» двумерных объектов и неопределенном и несбалансированном распределении пространственной информации. Если у вас есть регулярная сетка, легко рассчитать положение или отношение ячейки. Но у изолинии модели местности могут быть несложные части на одной стороне и математически сложные на другой стороне (морфологически активные части, такие как гребни, долины ...).

Индексирование пытается обрабатывать две вещи:

1. Быстрая процедура, которая дает вам набор корзин, в которых вы собираете объекты, которые вы можете выделить пространственно (корзины!). И BBox легко рассчитать и обрабатывать.

2. Набор отношений (перекрытие, касание), чтобы различать или связывать пространственные вещи (объекты).

К сожалению, BBoxы не дадут вам подсказки, сколько точек в каждом BBox, как объекты имеют форму (отверстия, выпуклые, ...) и как локально распределяется информация (90% точек в левом верхнем углу BBox). Таким образом, вы можете найти быстрые члены операции на уровне объекта и потерять много времени в построении отношений теста.

Чтобы использовать более нерегулярный подход, триангуляция IMO в сочетании с и quadtree является одной из стратегий, где вы можете сблизить часть индекса и построение отношений индекса (объединение == построение отношений).

Для примера Point-in-Polygon-Test можно построить неправильный кеш, используя:

1. ! ограниченная триангуляция Делоне для вашего полискрытия с дополнительными точками границы сетки для обнаружения вне обложки
2. поместите это в схему индексации квадродеревьев с не более чем N треугольниками на блок (фрактальные сегменты)
3. найти набор треугольников, к которому принадлежит точка - лист в дереве квадрантов
4. найти треугольник, в котором лежит точка (тестовая часть по макс. N треугольникам)
5. и попросить идентификаторы полигонов вершин треугольника
6. если идентификатор является уникальным, точка принадлежит многоугольнику, если не она находится снаружи

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

Некоторые инструменты и ссылки:

Треугольник - триангуляция ограничивающего многоугольника

Quadtrees - с примерами источников

Stony Brook Repository - Структуры данных и дискретная геометрия