Самый быстрый пространственный индекс для двумерных данных, после создания нет обновлений

Question

• У меня большая коллекция 2D-объектов, пока только строки.
• Мне нужно предложение алгоритма, как создать самый быстрый пространственный индекс для этой коллекции, чтобы я мог собрать все объекты, которые находятся внутри некоторых границ.
• После того, как построенный индекс не будет обновлен.
• Распределение объектов в этой базе данных не является пространственно равномерным.
• Реализация алгоритма в C #.
• Обновление: текущееиспользуется для дорожного графика какой-то страны, поэтому линии маленькие, от одного перекрестка до другого, большая плотность в населенных пунктах.Я думаю, что это дает хорошее представление о данных.

Очевидно, что для достижения этой цели существует множество методов индексирования, но мне потребуется более быстрый.

Answer 1

Проверьте quadtree .... и DotSpatial для обработки пространственного типа, включая реализацию quadtree.

Answer 2

Вы также можете попробовать R-дерево . Доступна реализация C # на http://sourceforge.net/projects/cspatialindexrt/.

R-деревья должны иметь такую ​​же производительность, что и дерево сегментов, и приведенная выше реализация должна быть автономной и довольно независимой от множества дополнительных ссылок на код, но я не проверял это.

Answer 3

Вы можете использовать Дерево сегментов , если вы хотите сохранить двумерные строки, а ваши запросы - это двумерные запросы диапазона.запрос O (log ^ 2 N).

Answer 4

На этом нет серебряной пули.Это зависит от типа данных (т. Е. Только точек, только линий, треугольников, сеток, любой их комбинации и т. Д.) И типа запроса (точка внутри многоугольника, пересечение линий, ближайшие соседи, любая геометрия внутри круга илии т. д.).

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

По моему опыту, структура данных достаточно общая, чтобы справляться с большинством геометрических объектов и может обрабатывать несколько типов запросов. Я бы рекомендовал AABBДерево:

https://doc.cgal.org/latest/AABB_tree/index.html