Структура данных для пространственных данных

Я ищу хорошую функциональную структуру данных для хранения пространственных (точечных) данных. Структура данных должна позволять простые эпсилонные запросы для уже присутствующих точек. Также мне нужно довольно часто изменять данные. Это означает, что точки могут перемещаться и должны быть обновлены в структуре данных. Вероятно, это можно обработать с помощью обычного удаления/добавления, но реальный ход может быть быстрее.

На данный момент я думаю об использовании quad/oct-trees (или выше), так как часть перемещения должна быть довольно простой. Однако известно, что квадранты хуже, чем балансировка. KD-Trees может быть другим выбором, но обновление кажется довольно неприятным. Также большинство реализаций пространственной структуры данных, которые я могу найти, являются только процедурами, и я использую функциональный язык.

Ответ 1

KD-деревья или деревья Quad/Oct являются разумным выбором.

Примеры в Haskell:

Оба довольно просто кодировать как чисто функциональные структуры данных.

Ответ 2

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

(Я думаю, что, кстати, ваши два предложения уже неплохие)

Ответ 3

Этот старый документ от Overmars и van Leeuwen описывает псевдоквартиру - квадрант, который также может балансировать как прогресс входов и удалений. Амортизированная стоимость вложений и исключений - это что-то вроде O(log^d(n)) и может быть даже продана против суммы балансировки (вы можете прочитать об этом больше в статье).

Ответ 4

R-Trees и R * -Trees - это еще одно решение, легко реализуемое.

См. https://github.com/mariusaeriksen/ocaml-rtree (в OCaml) для примера.

Я использовал их в моделировании эвакуации, шаг обновления не так медленен, как это.