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

Question

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

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

Answer 1

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

Answer 2

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

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

Answer 3

R-деревья и R * -деревья также являются другим решением, которое легко реализовать.

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

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

Answer 4

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

Примеры в Haskell:

• квадрадерево

• KD Tree

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