四叉树和kd树之间的主要区别是什么？我知道它们在多个维度上分割点，但我不明白为什么我们要使用一个而不是另一个。 我需要一个结构，允许我计算给定区域中有多少个点（2D 点）。 基本上，我正在尝试检测点簇。
差异（算法上）是：在四叉树中，到达节点的数据被分成固定的（2^d）、大小相等的单元，而在 kdtree 中，数据根据一些数据分析被分成两个区域（例如某个坐标的中值）。由于维度的指数依赖性，四叉树不能很好地扩展到高维度。数据结构的查询时间复杂度也有所不同。
由于您对 2D 点感兴趣，因此任何一种数据结构都可能适合您。 KD 树非常容易查询范围，并且通常优于四叉树。我建议你使用它们。
如果您希望在任意区域内进行聚类，请使用 KD 树。您最终将需要行走和搜索的节点更少。
使用四叉树，您可能需要移动网格以获得聚类点的最佳分桶，这可能并不简单。四叉树更适合广泛的传播，例如游戏中的碰撞检测，其中任何类型的聚类的保证都较少。