R-дерево: различия между версиями

R-деревья широко использовались на практике благодаря своей простоте, возможности хранения пространственных объектов различных форм и способности отвечать на различные запросы. Они применяются в таких областях, как географические информационные системы (ГИС), САПР, машинное зрение и робототехника. Если объекты не являются параллельными осям гиперкубами, их часто можно аппроксимировать минимальными ограничивающими прямоугольниками и затем построить R-дерево на основе этих прямоугольников. При поиске ответа на оконный запрос вначале R-дерево используется для локализации всех пересекающихся ограничивающих прямоугольников, после чего следует этап фильтрации с точной проверкой объектов. R-дерево также можно использовать для выполнения запросов других типов – например, объединенных запросов по шаблону, запросов о ближайших соседях и т.п. В объединенных запросах каждый объект o множества S ассоциирован с весом <math>w(o) \in \mathbb{R} \;</math>; задача состоит в вычислении <math>\sum w(o) \;</math>, где сумма берется по всем объектам, пересекающим диапазон вопроса Q. Алгоритм запроса точно тот же, что и раньше, за тем исключением, что он подсчитывает сумму при обходе R-дерева и может пропускать целое поддерево с корнем в вершине u, если R(u) полностью содержится в Q. Для нахождения ближайшего соседа точки запроса q поддерживается очередь приоритетов; в ней хранятся все вершины u, которые могут содержать объект, находящийся ближе к найденному до настоящего момента ближайшему соседу. Приоритетом u в очереди является расстояние между q и R(u). Поиск прекращается, когда текущий ближайший сосед оказывается ближе самого высокого элемента в очереди приоритетов. Однако пока неизвестны границы для наихудшего случая для ответа на подобные вопросы при помощи R-деревьев, хотя на практике они работают очень хорошо.