*假设我有 10,000 个圆(x，y，r) 值，我想找到一个点 (p1，p2) 位于哪个圆圈中，为了获得此查询的最快响应，我应该使用什么数据结构来存储这 10,000 个圆圈数据。 它是一个静态数据，意味着一次性构造，
但最常见的操作将是搜索查询。 和 它不会是基于范围的搜索或不是最近邻搜索
B树，B +树或R树或四叉树或线性插值搜索或任何位图类型怎么样，解决方案应该占用最少的内存，而很少的额外时间权衡是可以的。
您至少有三种选择：
- 使用边界体积层次结构 (BVH); 在这种情况下，我认为 2D 球体树(圆形树)将是要走的路;所以你构造了一个树，每个节点都是圆形的。每个节点可以包含子圈。您的输入圆圈将位于叶子上。这个路点搜索在时间上将是logN，但在空间上结构将是NlogN。但是，一般来说，BVH可能很难建造。
- 使用基于树的 N 元空间分区(二进制空间分区、qudtree、2D kd 树);这次你划分空间，每个空间可能包含一些球体。这些算法将具有与 BVH 相同的复杂性，但很可能效率低于 BVH - 我怀疑圆圈的大腿拟合度较小。但是，一些空间分区(例如四叉树)可能更容易构建。
- 使用空间哈希。也就是说，空间将被划分为精确大小的多维数据集(桶)，这些多维数据集经过哈希处理。基本上，当每个像素都有包含的圆圈列表时，您可以将其视为统一的像素网格(但巧妙地存储)。这在理论上给出了 O(1) 用于搜索。但空间的预测可能更复杂。理论上它是O(N)，但由于常量因子，它可能比BVH大 - 并且很可能取决于圆的面积和位置的分布(例如，具有圆的像素数)。