Поиск полигонов

Question

Какой из них (kd tree, r-tree) подойдет для поиска и индексации многоугольника. Мой пример использования заключается в том, что мне дали несколько длинных точек (минимум 3 для правильного многоугольника), и из этих точек мне нужно найти самый маленький многоугольник. Под наименьшим я подразумеваю, что если внутри другого многоугольника есть многоугольник, то внутренний многоугольник должен быть возвращен. И если полигоны перекрываются, их не следует выбирать. Я думаю, что можно найти местоположение, а затем область, но я не уверен.

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

Спасибо

Answer 1

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

Kd-дерево работает с точками, поэтому многоугольники будет трудно проиндексировать.

R-Дерево также поддерживает добавление и удаление элементов данных. Насколько я помню, созданное дерево kd сложно обновлять для новых или изменяющихся данных.