实现产品的精准捕捉时，当几何数据大了之后，普通的遍历比较很快就会遇到性能问题，这时候通常都是通过建立空间索引的方式实现快速查询。
目的
常用处理方式
- 最朴素的方法：遍历计算再排序
- 针对复杂图形，如不规则多边形，则先转换为简单的包围盒判断，再进一步做复杂判断
- 网格查表法（Grid Index）：将要考虑的空间铺好网格，一遍快速锁定区间。适合做近邻搜索
- 建立空间索引
当面对大规模的空间数据时，一个最有效也是最重要的方法就是空间索引（Spatial Index）。
空间索引是一组算法，目的编排几何数据以实现高效查询，如查询该区域所有建筑，找到 1000 个离这里最近的加油站。
空间索引的算法优劣，主要在于如何减少无关数据的访问次数。
空间数据有两种基本查询类型：最近邻查询和范围查询。
原理
考虑到数据更改的频率通常远低于查询，因此将数据处理到索引中的初始成本是为之后的即时搜索付出的合理代价。
几乎所有的空间数据结构都共享相同的原理来实现高效的搜索：分支和边界。这意味着以树状结构排列数据，如果它们不符合我们的搜索条件，就可以立即丢弃分支。
Minimun Bounding Rectangle(MBR)：MBR 本身通过 x、y 坐标容易计算，计算 MBR 相交也十分简单高效，十分适用于应用在索引结构中。
通用规则
- 点索引可以使用网格索引 KDTree（k-dimensional tree）
- 线面索引使用 STRTree（Sort-Tile-Recursive Tree 递归网格排序） 或者 QuadTree
K-d tree
K-d tree（k-dimension tree）类似于 R-tree，但不是在每个树级别将点分成几个盒子，而是将它们分成两半（围绕中位数点），左和右，或上和下，在每个级别上交替使用 x 和 y 分割。
K-d tree 和 R-tree 相比
- 只能包含点，不能包含矩形
- 静态的，不支持增删点
- 很容易实现，且非常快
R-tree
了解 R 树，我们需要先了解一下 B 树，因为 R 树是 B 树向多维空间发展的另一种形式。
R 树与 B 树最显著的区别在于 R 树在非一维空间使用 MBR 描述节点的上下界，无法像 B 树节点一样准确适应子节点的分布。虽然通过通过 MBR 提高了计算和求交的效率，不过这也势必牺牲了空间利用率（父节点包含了空白区域）及查询效率（兄弟节点 MBR 可能会重叠）。
B 树是一棵平衡树，它是把一维直线分为若干段线段，当我们查找满足某个要求的点的时候，只要去查找它所属的线段即可。这种思想其实就是先找一个大的空间，再逐步缩小所要查找的空间，最终在一个自己设定的最小不可分空间内找出满足要求的解。
R-tree 特点（R 表示 Rectangle）
- 由单个根、内部节点和叶节点组成，所有叶子节点都位于同一层，因此 R 树为平衡树
- 根包含指向空间域中的最大区域的指针
- 父节点包含指向子节点的指针，其中子节点的区域与父节点的区域完全重叠
- 叶子节点包含到当前对象的 MBR 数据
- 子节点数量有限制即存在节点分裂和合并
Quad-tree
QuadTree 依次将每个子空间分成 4 份，直到不需要再分位置，支持点，也支持矩形，用于表示任何几何对象。
四叉树（Quad-tree）与 R-Tree 比较
- 四叉树需要平铺层优化，而 R-Tree 不需要任何此类优化
- 四叉树可以在现有的 B-Tree 上实现，而 R-Tree 遵循与 B-Tree 不同的结构
- 四叉树空间索引创建速度比 R-Tree 快
- 对于最近邻居查询，R-Tree 比四叉树快，而对于窗口查询，四叉树比 R-Tree 快
范围查询
当在 R-tree 上执行查询时，我们可以从树的顶层开始，然后向下遍历，忽略所有不与查询框相交的框。对于一个小的查询框，这意味着在树的每一层上只需要搜索几个矩形框即可。
邻近查询
邻近搜索稍微困难一些。对于一个特定的查询点，我们如何知道在哪个树节点上搜索最近的点？我们可以做一个半径查询，但是我们不知道如何选择半径的大小，因为最近的点可能会很远。做很多半径增加的半径查询，希望得到一些结果是低效的。
为了在空间树中搜索最近的邻居，我们将利用另一种简洁的数据结构——优先级队列。 它会维护一个有序列表，并以非常快的方式取出最小的项目。
考虑到当我们在一组特定的盒子中搜索 K 个最近的点时，离查询点更近的盒子更有可能有我们要找的点。为了充分利用这一点，我们从顶层开始搜索，按照从最近到最远的顺序将最大的盒子排列成一个队列。
接下来，我们打开最近的盒子，将其从队列中移除，并将其所有子盒子（较小的盒子）放回到队列中，与较大的盒子放在一起。
每次打开最近的盒子，把它的子盒子放回队列中。当从队列中移除的最近的项目是一个实际点时，它保证是最近的点。从队列顶部开始的第二个点将是第二个最近的点，依此类推。
这是因为我们尚未打开的所有盒子只包含比这个盒子距离远的点，所以我们从队列中取出的任何点都比其他盒子中的点更近。
如果我们的空间树平衡性较好，那么在搜索过程中，只需要处理少数几个矩形框即可，而其余的矩形框都没有打开，这使得这个算法非常快。