Mau*_*ndo 22 quadtree kdtree computational-geometry
四叉树和kd树之间的主要区别是什么？我知道他们在很多方面分裂了点,但我不明白为什么我们会使用一个而不是另一个.我需要一个允许我计算给定区域中有多少点(2D点)的结构.基本上,我试图检测点集群.
kil*_*gre 25
差异(算法上)是:在四叉树中,到达节点的数据被分成固定的(2 ^ d),相等大小的单元格,而在kdtrees中,数据基于某些数据分析被分成两个区域(例如,中值一些坐标).由于维度中的指数依赖性,四叉树不能很好地扩展到高维度.数据结构的查询时间复杂性也不同.
由于您对2D点感兴趣,因此数据结构可能对您有用.KD树很容易查询范围,并且通常优于四叉树.我建议你使用它们.