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

Question

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

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

Answer 1

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

Примеры в Haskell:

• QuadTree

• KD Tree

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

Answer 2

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

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

Answer 3

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

См. Пример https://github.com/mariusaeriksen/ocaml-rtree (в OCaml).

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

Answer 4

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