Quadtree и k-d дерево: поиск точек в прямоугольнике и ближайших соседей

Quadtree и k-d дерево простыми словами: как искать точки в прямоугольнике и ближайших соседей быстрее перебора, отсечение поддеревьев, сложность, проклятие размерности. Код на Python.

14 мин чтенияструктуры данных · геометрия · деревья · python

Коротко

ПараметрРавномерная сеткаQuadtree (квадродерево)k-d дерево
Как делит плоскостьна одинаковые клеткиузел — квадрат, делится на 4 равные частиузел — точка, режет по медиане, оси по очереди
Подстраивается под плотностьнетда, глубже там, где точек многода, всегда сбалансировано по числу точек
ВставкаO(1)O(1)O(глубина)O(\text{глубина})просто, но дерево разбалансируется
Поиск в прямоугольникеклетки запросана практике O(log⁡n+k)O(\log n + k)O(n+k)O(\sqrt{n} + k) в худшем случае для 2D
Ближайший соседобход колец клетоквозможен, но неудобенестественный, в среднем O(log⁡n)O(\log n)
Где встречаетсяигры, простые геоиндексыкарты, тайлы, коллизии, Barnes–Hutscipy, sklearn, kNN, трассировка лучей
  • Обе структуры отвечают на вопрос «какие точки лежат рядом» без перебора всех nn точек.
  • Главный трюк один и тот же: у каждого узла есть область, и если область целиком мимо запроса, всё поддерево отбрасывается.
  • Quadtree делит пространство пополам по обеим осям сразу, k-d дерево делит множество точек пополам по одной оси за раз.
  • В размерностях выше 10–20 обе структуры деградируют почти до перебора. Это проклятие размерности, и для векторного поиска используют другие индексы.

Задача

На плоскости nn точек: рестораны, водители, юниты в игре, звёзды в симуляции. Приходят запросы двух типов:

  1. Range query: выдать все точки внутри прямоугольника (видимая часть карты, область выделения мышкой).
  2. Nearest neighbor: найти точку, ближайшую к заданной, или kk ближайших («пять кафе рядом со мной»).

Наивное решение — перебор, O(n)O(n) на запрос. Для тысячи точек это нормально. Для миллиона точек и тысяч запросов в секунду — нет.

В одномерном случае всё решается просто: отсортировать и искать бинарным поиском границы отрезка, это O(log⁡n+k)O(\log n + k), где kk — размер ответа. В двух измерениях одной сортировкой не обойтись: точки, близкие по xx, могут быть сколь угодно далеки по yy. Отсортировать по xx и отфильтровать по yy — значит пройти всю вертикальную полосу, а в ней может оказаться почти всё множество.

Первая идея: сетка

Разбиваем плоскость на клетки s×ss \times s, каждую точку кладём в словарь по ключу (x // s, y // s). Запрос в прямоугольнике просматривает только клетки, которые он задевает.

Это работает отлично, пока точки распределены равномерно. Реальные данные устроены иначе: в центре Москвы ресторанов в сотни раз больше, чем в Подмосковье. Мелкая сетка даёт миллионы пустых клеток за городом, крупная — клетки с тысячами точек в центре, которые снова перебираются линейно. Нужна структура, которая сама мельчит там, где плотно. Это и есть quadtree.

Quadtree

Корень отвечает за весь квадрат карты. Пока в узле мало точек (не больше CAPACITY), он хранит их списком. Когда точек становится больше, узел делится на четыре равных квадранта, и точки разъезжаются по детям.

В итоге в плотных районах дерево глубокое и листья маленькие, а пустые районы покрыты одним большим листом. Такую разновидность называют point-region quadtree: границы делений фиксированы (середина квадрата), а не зависят от самих точек.

Реализация

class Rect: def __init__(self, x0, y0, x1, y1): self.x0, self.y0, self.x1, self.y1 = x0, y0, x1, y1 def contains(self, x, y): return self.x0 <= x < self.x1 and self.y0 <= y < self.y1 def intersects(self, other): return not (other.x0 >= self.x1 or other.x1 <= self.x0 or other.y0 >= self.y1 or other.y1 <= self.y0) class QuadTree: CAPACITY = 4 MAX_DEPTH = 16 def __init__(self, box, depth=0): self.box = box self.depth = depth self.points = [] self.children = None def insert(self, x, y): if not self.box.contains(x, y): return False if self.children is None: self.points.append((x, y)) if len(self.points) > self.CAPACITY and self.depth < self.MAX_DEPTH: self._split() return True return any(child.insert(x, y) for child in self.children) def _split(self): b = self.box mx, my = (b.x0 + b.x1) / 2, (b.y0 + b.y1) / 2 d = self.depth + 1 self.children = [ QuadTree(Rect(b.x0, b.y0, mx, my), d), QuadTree(Rect(mx, b.y0, b.x1, my), d), QuadTree(Rect(b.x0, my, mx, b.y1), d), QuadTree(Rect(mx, my, b.x1, b.y1), d), ] points, self.points = self.points, [] for x, y in points: self.insert(x, y) def query(self, area, found=None): if found is None: found = [] if not self.box.intersects(area): return found # весь узел мимо — отсекаем поддерево for x, y in self.points: if area.contains(x, y): found.append((x, y)) if self.children: for child in self.children: child.query(area, found) return found

Пара деталей, на которых легко ошибиться:

  • Прямоугольники полуоткрытые: x0 <= x < x1. Тогда точка ровно на линии раздела попадает ровно в один квадрант, а не в два и не в ноль.
  • В insert используется any(...): он останавливается на первом ребёнке, который принял точку.
  • MAX_DEPTH обязателен, об этом ниже.

Проверка против перебора

import random random.seed(42) tree = QuadTree(Rect(0, 0, 1000, 1000)) points = [(random.uniform(0, 1000), random.uniform(0, 1000)) for _ in range(10_000)] for x, y in points: tree.insert(x, y) area = Rect(100, 100, 150, 180) fast = sorted(tree.query(area)) slow = sorted(p for p in points if area.contains(*p)) print(len(fast), fast == slow)
51 True

Если добавить в query счётчик вызовов, получится, что для этого запроса дерево посетило 89 узлов из 6957 и проверило только точки в их листьях, а не все 10 000. Глубина дерева на равномерных данных — 8: каждый уровень делит сторону квадрата пополам, а 48=65 5364^8 = 65\,536 клеток с запасом хватает на 10 000 точек по 4 в листе.

Сложность

Для quadtree нет такой аккуратной гарантии, как для сбалансированных деревьев. Глубина зависит не от nn, а от того, насколько близко лежат точки: если сторона корня DD, а минимальное расстояние между точками dd, то глубина порядка log⁡2(D/d)\log_2 (D / d). Две точки на расстоянии в миллиметр на карте мира дадут глубину около 35.

На реальных данных поиск в небольшом прямоугольнике ведёт себя как O(log⁡n+k)O(\log n + k): спуск до нужного масштаба плюс просмотр найденного. Вставка — O(глубина)O(\text{глубина}), удаление — найти лист и убрать точку, при желании слить четыре опустевших листа обратно в один.

Дубликаты и бесконечное деление

Положите в дерево пять одинаковых точек при CAPACITY = 4. Узел переполнится и разделится, все пять точек уедут в один квадрант, он тоже переполнится, и так до бесконечности, пока не кончится стек. Именно поэтому в коде стоит MAX_DEPTH: на этой глубине лист просто хранит больше CAPACITY точек. С десятью точками (500, 500) наше дерево дорастает ровно до глубины 16 и останавливается.

Альтернатива — хранить в листе не точки, а пары «точка → список объектов», тогда совпадающие координаты занимают одно место.

k-d дерево

Quadtree делит пространство, не глядя на точки: середина квадрата может оказаться где угодно относительно данных. k-d дерево (Джон Бентли, 1975) поступает наоборот: каждый узел — это одна из точек, и разрез проходит через неё.

Построение рекурсивное:

  1. На глубине 0 сортируем точки по xx, берём медиану — это корень. Всё левее идёт в левое поддерево, правее — в правое.
  2. На глубине 1 так же делим каждую половину, но по yy.
  3. Дальше оси чередуются: x,y,x,y,…x, y, x, y, \dots В kk-мерном случае — по кругу через все kk координат, отсюда и название.

Медиана гарантирует баланс: глубина ровно ⌈log⁡2(n+1)⌉\lceil \log_2 (n + 1) \rceil, независимо от распределения. По сути это двоичное дерево поиска, у которого ключ сравнения меняется от уровня к уровню.

Построение и поиск в прямоугольнике

class Node: __slots__ = ("point", "axis", "left", "right") def __init__(self, point, axis, left, right): self.point, self.axis, self.left, self.right = point, axis, left, right def build(points, depth=0): if not points: return None axis = depth % 2 # 0 — режем по x, 1 — по y points = sorted(points, key=lambda p: p[axis]) mid = len(points) // 2 return Node( points[mid], axis, build(points[:mid], depth + 1), build(points[mid + 1:], depth + 1), ) def range_search(node, x0, y0, x1, y1, found): if node is None: return found x, y = node.point if x0 <= x <= x1 and y0 <= y <= y1: found.append(node.point) lo, hi = (x0, x1) if node.axis == 0 else (y0, y1) coord = node.point[node.axis] if lo <= coord: # слева от разреза есть часть запроса range_search(node.left, x0, y0, x1, y1, found) if coord <= hi: # и справа тоже range_search(node.right, x0, y0, x1, y1, found) return found

Сортировка на каждом уровне даёт построение за O(nlog⁡2n)O(n \log^2 n). Если искать медиану быстрым выбором за линейное время, выйдет O(nlog⁡n)O(n \log n). Для собеседования достаточно версии с сортировкой, главное — сказать, как её ускорить.

Поиск в прямоугольнике спускается в поддерево, только если запрос пересекает его полуплоскость. Для 2D доказано, что в худшем случае посещается O(n+k)O(\sqrt{n} + k) узлов, а в общем kk-мерном случае — O(n1−1/k+ответ)O(n^{1 - 1/k} + \text{ответ}). Корень из nn появляется потому, что вертикальная граница запроса пересекает не больше O(n)O(\sqrt{n}) областей дерева.

Ближайший сосед

Ради этой операции k-d деревья чаще всего и строят. Алгоритм — обход с отсечением (branch and bound):

  1. Спускаемся в ту половину, где лежит точка запроса, как при обычном поиске в дереве. Каждый посещённый узел — кандидат в ответ.
  2. На обратном пути в каждом узле спрашиваем: может ли в другой половине найтись точка ближе текущего лучшего? Расстояние от запроса до разделяющей прямой — diff = target[axis] - point[axis]. Если diff² >= best², круг вокруг запроса радиусом best не дотягивается до другой половины, и её можно не смотреть.
def dist2(a, b): return (a[0] - b[0]) ** 2 + (a[1] - b[1]) ** 2 def nearest(root, target): best = [None, float("inf")] # точка и квадрат расстояния def visit(node): if node is None: return d = dist2(node.point, target) if d < best[1]: best[0], best[1] = node.point, d diff = target[node.axis] - node.point[node.axis] near, far = (node.left, node.right) if diff < 0 else (node.right, node.left) visit(near) if diff * diff < best[1]: # круг пересекает разделяющую прямую visit(far) visit(root) return best[0]

Порядок важен: сначала ближняя половина, потом дальняя. Ближняя быстро даёт хорошего кандидата, и радиус best сжимается, а с маленьким радиусом дальние ветки отсекаются почти всегда. Если обходить в фиксированном порядке «левый, правый», отсечений будет гораздо меньше.

Все расстояния сравниваются в квадратах — sqrt не нужен, и нет погрешностей округления.

k ближайших соседей

Обобщение на kk соседей — та же схема плюс куча на kk элементов. Держим max-кучу кандидатов: на вершине самый дальний из найденных. Новый узел попадает в кучу, если она не заполнена или он ближе вершины. Отсекаем дальнюю половину, только когда куча полна и разделяющая прямая дальше вершины.

import heapq def k_nearest(root, target, k): heap = [] # max-куча через минус: (-dist2, point) def visit(node): if node is None: return d = dist2(node.point, target) if len(heap) < k: heapq.heappush(heap, (-d, node.point)) elif d < -heap[0][0]: heapq.heapreplace(heap, (-d, node.point)) diff = target[node.axis] - node.point[node.axis] near, far = (node.left, node.right) if diff < 0 else (node.right, node.left) visit(near) if len(heap) < k or diff * diff < -heap[0][0]: visit(far) visit(root) return [p for _, p in sorted(heap, reverse=True)]

Проверяем все три операции против перебора на 20 000 случайных точек и 300 запросах:

import random random.seed(7) points = [(random.uniform(0, 1000), random.uniform(0, 1000)) for _ in range(20_000)] root = build(points) ok = True for _ in range(300): q = (random.uniform(-100, 1100), random.uniform(-100, 1100)) brute = min(points, key=lambda p: dist2(p, q)) ok &= dist2(nearest(root, q), q) == dist2(brute, q) k5 = k_nearest(root, q, 5) b5 = sorted(points, key=lambda p: dist2(p, q))[:5] ok &= [dist2(p, q) for p in k5] == [dist2(p, q) for p in b5] x0, y0 = random.uniform(0, 900), random.uniform(0, 900) r = sorted(range_search(root, x0, y0, x0 + 80, y0 + 50, [])) br = sorted(p for p in points if x0 <= p[0] <= x0 + 80 and y0 <= p[1] <= y0 + 50) ok &= r == br print("всё сходится с перебором:", ok)
всё сходится с перебором: True

Запросы специально берутся и за пределами квадрата точек: на них часто ломаются реализации, в которых отсечение считается от границ области, а не от разделяющей прямой.

Сложность поиска соседа

В среднем, на случайных данных малой размерности, поиск ближайшего соседа посещает O(log⁡n)O(\log n) узлов. В худшем случае — O(n)O(n): например, если все точки лежат на окружности, а запрос в её центре, то все они на одинаковом расстоянии, и отсечь ничего нельзя.

Проклятие размерности

k-d дерево формально работает в любой размерности, но эффективность быстро тает. Посчитаем, сколько узлов в среднем посещает nearest на 20 000 случайных точках в единичном кубе разной размерности (тот же код, только ось выбирается как depth % dim):

d= 2: посещено в среднем 22 из 20000 узлов d= 3: посещено в среднем 34 из 20000 узлов d= 5: посещено в среднем 138 из 20000 узлов d=10: посещено в среднем 3848 из 20000 узлов d=20: посещено в среднем 19954 из 20000 узлов

В двумерном случае посещается 0,1% дерева, в 20-мерном — фактически всё. Причина в геометрии: в высокой размерности расстояния от запроса до всех точек становятся почти одинаковыми, и шар вокруг лучшего кандидата пересекает почти каждую разделяющую плоскость. Практическое правило: k-d дерево имеет смысл, когда n≫2dn \gg 2^d. При d=20d = 20 это уже миллионы точек, и то с оговорками.

Поэтому для эмбеддингов размерности 384 или 1536 k-d деревья не используют. Там работают приближённые методы: HNSW, IVF, product quantization. Они жертвуют гарантией точного ответа ради скорости.

Quadtree или k-d дерево

Quadtree удобнее, когда данные меняются. Вставка и удаление локальны, дерево не нужно перестраивать: границы квадрантов не зависят от точек. Структура естественно ложится на тайлы карты — уровень дерева соответствует уровню зума, путь от корня записывается строкой из цифр 0–3 (так устроены quadkey в Bing Maps). Ещё одна классика — алгоритм Barnes–Hut для симуляции гравитации: далёкую группу звёзд в узле quadtree (в 3D — octree) заменяют одной точкой в центре масс, и вместо O(n2)O(n^2) попарных сил получается O(nlog⁡n)O(n \log n).

k-d дерево лучше для статичных наборов и поиска соседей. Оно сбалансировано по построению, хранит ровно nn узлов, а nearest neighbor в нём пишется в двадцать строк. Вставлять в него можно, но баланс портится, поэтому на практике дерево периодически перестраивают целиком. Готовые реализации — scipy.spatial.KDTree и sklearn.neighbors.KDTree.

R-дерево — третий родственник, который стоит упомянуть. Оно группирует не точки, а прямоугольники (bounding box) и хорошо работает с объектами, у которых есть размер: здания, дороги, полигоны. На нём построены пространственные индексы в базах данных — GiST-индексы в PostGIS, R-tree в SQLite. Кстати, в PostgreSQL есть и индекс SP-GiST с готовыми классами операторов для quadtree и k-d дерева по точкам. Как такие индексы живут на диске, хорошо видно на примере B-дерева и статьи про индексы в базах данных.

НужноВыбор
Точки двигаются, много вставок и удаленийquadtree или сетка
Статичный набор, поиск k ближайшихk-d дерево
Объекты с размером, хранение в БДR-дерево
Размерность выше 15–20приближённый поиск (HNSW и аналоги)
Распределённый геоиндекс в системном дизайнеgeohash, S2, H3 — ячейка как ключ

Типичные ошибки

Нет ограничения глубины в quadtree. Совпадающие точки делят узел бесконечно. Нужен MAX_DEPTH или хранение дубликатов в одном слоте.

Закрытые прямоугольники при делении. Если contains проверяет x <= x1 для всех четырёх квадрантов, точка на линии раздела попадёт в два ребёнка или будет вставлена дважды. Квадранты должны быть полуоткрытыми. При этом сам запрос пользователя можно делать закрытым — это разные прямоугольники.

Отсечение по неправильному расстоянию. В k-d дереве отсекают по расстоянию до разделяющей прямой этого узла (diff²), а не до точки узла. Расстояние до точки всегда не меньше, и с ним вы пропустите ветку, где лежит настоящий ответ.

Неверный порядок обхода. Сначала ближняя половина, потом дальняя. Фиксированный порядок даёт правильный ответ, но отсекает в разы хуже.

Сравнение с <= вместо < при отсечении. Это не ломает поиск одного соседа, но если нужны все точки на одинаковом расстоянии, с < вы потеряете часть. Решите заранее, что делать с равенством, и скажите об этом вслух.

Географические координаты как плоские. Градус долготы на широте Москвы — около 63 км, а на экваторе — 111 км. Дерево по (lat, lon) строить можно, но расстояния нужно считать по формуле гаверсинуса или переводить точки в проекцию. Ещё одна ловушка — линия перемены дат, где долгота прыгает с 180 на −180.

k-d дерево для эмбеддингов. В размерности 768 оно медленнее перебора из-за накладных расходов на обход.

Где это спрашивают на собеседованиях

Алгоритмическая секция. Прямых задач на k-d дерево на LeetCode почти нет, но рядом есть:

  • K Closest Points to Origin (LeetCode 973) — решается кучей за O(nlog⁡k)O(n \log k) или быстрым выбором за O(n)O(n) в среднем. Хороший повод спросить: «а если запросов много и точки не меняются?» Ответ — построить k-d дерево один раз.
  • Construct Quad Tree (LeetCode 427) — построить quadtree по бинарной матрице, где лист — однородный квадрат. Это та же идея деления на четыре квадранта, только для растра.
  • Задача о ближайшей паре точек — родственная геометрия, решается «разделяй и властвуй» за O(nlog⁡n)O(n \log n).

Системный дизайн. «Спроектируйте Yelp», «найдите водителей рядом», «покажите друзей на карте». Здесь quadtree — один из стандартных ответов наравне с geohash. Как это выглядит в полном дизайне с потоком GPS-координат, разобрано в статье про сервис такси. Ожидаемые темы:

  • почему не WHERE lat BETWEEN ... AND lon BETWEEN ... с обычными индексами (каждый индекс сужает только по одной оси);
  • как quadtree адаптируется к плотности и что делать с ёмкостью листа;
  • как обновлять дерево при постоянно двигающихся объектах (часто ответ — перестраивать периодически или перейти на сетку ячеек);
  • как шардировать: по поддеревьям или по ячейкам geohash.

Вопросы вглубь, которые любят задавать:

  1. Почему поиск соседа в k-d дереве в худшем случае линейный? Приведите пример.
  2. Чем point-region quadtree отличается от k-d дерева по способу деления?
  3. Что изменится в 3D? (Quadtree превращается в octree с восемью детьми, k-d дерево — просто три оси по кругу.)
  4. Как найти все точки в радиусе rr? (Range query по описанному квадрату и фильтр по расстоянию, либо отсечение по diff² > r².)

Что запомнить

  • Пространственный индекс — это дерево, где у каждого узла есть область, и поддерево отсекается, если область не пересекает запрос.
  • Quadtree делит квадрат на четыре равные части, подстраивается под плотность, удобно для динамики и тайлов. Не забывайте про ограничение глубины.
  • k-d дерево режет множество точек по медиане, чередуя оси. Сбалансировано, поиск в прямоугольнике за O(n+k)O(\sqrt{n} + k), ближайший сосед в среднем за O(log⁡n)O(\log n).
  • В поиске соседа сначала идите в ближнюю половину, отсекайте по расстоянию до разделяющей прямой, сравнивайте квадраты расстояний.
  • Выше 10–20 измерений деревья деградируют до перебора — там нужен приближённый поиск.

Потренироваться в спокойной обстановке

Все задачи