Я собираю небольшую библиотеку, которая потребляет данные географической информационной системы (ГИС) и позволяет быстро находить точки, объекты, близкие к объектам, и запросы прямой видимости. Большая часть этих данных будет состоять из больших ареальных объектов с огромным количеством вершин.Алгоритм быстрого поиска точек и линии визирования
Возможно, вариант R Tree может работать, хотя мне интересно, как они выполняются в точке в запросах. Я также подозреваю, что запросы на поисковые запросы будут уничтожать большую часть производительности.
Квадратное дерево с детьми с переменным размером - это следующее, что появляется на ум. Это позволило бы, возможно, установить связь между различными дочерними уровнями и ускорить линию запросов на сайт.
Kd деревья тоже приходят в голову, хотя, опять же, строка запросов сайта может оказаться проблематичной.
Итак, вопрос в том, какой алгоритм вы бы порекомендовали?
Да, это в классе алгоритмов пространственного разделения, на которые я смотрю. Октограмма была бы для 3-пространства, где эквивалентная квадтри была бы для 2-пространства. Существует также класс алгоритмов, которые лучше упорядочивают 2D (или N-d) данные для определенных классов проблем. Это то, что я созерцаю. – mousebird
R-Tree, если кто-то столкнется с этим вопросом. Они довольно приятные. Я думаю, что буду использовать их вместо квадрантов и настроенных сеток в будущем. – mousebird