computational-geometry - 四叉树和kd树的区别

Question

四叉树和kd树的主要区别是什么？我知道他们在多个维度上分割点，但我不明白为什么我们会使用一个而不是另一个。我需要一个允许我计算给定区域中有多少点（2D 点）的结构。基本上，我正在尝试检测点簇。

Answer 1

区别（算法上）是：在四叉树中，到达节点的数据被分成固定（2^d）大小相等的单元格，而在 kdtrees 中，数据根据一些数据分析（例如中位数）被分成两个区域一些坐标）。由于维度的指数依赖性，四叉树不能很好地扩展到高维度。数据结构的查询时间复杂度也不同。

由于您对二维点感兴趣，因此任何一种数据结构都可能适合您。KD 树很容易查询范围，并且通常比四叉树更受欢迎。我建议你使用它们。