四叉树和kd树之间的主要区别是什么？我了解它们在多个维度上划分了点，但我不明白为什么我们要在一个之上使用一个。
我需要一个允许我计算给定区域中有多少个点(2D点)的结构。
基本上，我正在尝试检测点的群集。
最佳答案
区别(从算法上)是:在四叉树中，到达节点的数据被分成固定大小(2 ^ d)的相等大小的单元格，而在kdtree中，基于某些数据分析(例如中位数)，数据被分为两个区域坐标)。由于四叉树在维度上的指数依赖性，因此无法很好地缩放到高维度。数据结构的查询时间复杂度也有所不同。
由于您对2D点感兴趣，因此任何一种数据结构都可以为您工作。 KD树非常容易查询范围，并且通常比四叉树更可取。我建议您使用它们。
关于computational-geometry - 四叉树和kd树之间的区别，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/13487953/