Алгоритм быстрого поиска точки и обхода линии визирования
Я собираю небольшую библиотеку, которая использует данные Геоинформационной системы (GIS) и позволяет быстро находить объекты, объекты рядом с объектами и запросы линии прямой видимости. Большая часть этих данных будет состоять из больших площадных объектов с огромным количеством вершин.
Вариант R Tree мог бы работать, хотя мне интересно, как они работают на точке в площадных запросах. Я также подозреваю, что запросы линии прямой видимости уничтожат большую часть прироста производительности.
Следующее, что приходит на ум, - это четырехугольное дерево с потомками переменного размера. Это позволило бы связать между собой различные дочерние уровни и ускорить выполнение запросов к сайту.
Также на ум приходят деревья Kd, хотя опять-таки, ряд запросов к сайту может оказаться проблематичным.
Вопрос в том, какой алгоритм вы бы порекомендовали?