Разница между квадтри и kd-деревом

В чем основное отличие квадранта от kd-дерева? Я понимаю, что они разделяют точки во многих измерениях, но я не понимаю, почему мы будем использовать один над другим. Мне нужна структура, которая позволяет мне подсчитать, сколько точек (2D точек) находится в данном регионе. В основном, я пытаюсь обнаружить кластеры точек.

Ответы

Ответ 1

Разница (алгоритмически) заключается в следующем: в квадрантах данные, достигающие a node, разбиваются на фиксированные (2 ^ d) ячейки с равным размером, тогда как в kdtrees данные разбиваются на две области на основе некоторых данных анализ (например, медиана некоторой координаты). Квадтрисы плохо масштабируются до больших размеров из-за экспоненциальной зависимости в размерности. Структуры данных также различаются по сложности запросов.

Поскольку вас интересуют 2D-точки, структура данных может работать на вас. Деревья KD очень легко запрашивают диапазоны, и они обычно предпочитаются над квадрантами. Я предлагаю вам использовать их.