问哪种空间数据结构(算法)最适合(搜索)一组区域(空间数据)？

EN

可以使用R-Tree数据结构来解决此问题。

由于您不会插入/删除数据，并且可能有足够的时间对数据进行预处理，因此可以使用一些额外的内存来加快计算速度。预处理的基本思想：

1. 获取所有多边形点并确定包含它们的最小轴对齐边界矩形；基本上，这是X和Y的最小值和最大值。
2. 选择一个划分因子dX和dY，您将使用该因子创建搜索网格。为划分因子选择2的幂可以使多边形数据的计算速度稍快一些，以便它们的边界矩形最小值与(0,0)重合，并扩展矩形，以便它是每个dimension.
3. Consider每个栅格正方形中划分因子的整数倍，并生成与正方形相交的多边形的列表。为每个网格方块存储此列表。根据数据的性质(可以期望与正方形相交的多边形的数量)，有多种方法可以针对存储空间或速度对其进行优化。

现在，当您想要查找包含点的区域时：

1. 使用我们之前定义的原点平移点，并确定包含该点的网格正方形(如果您使用2的幂，这是一个移位操作；否则它在网格正方形的列表中为division.)
2. Look。如果为空，则没有包含多边形。如果不是，则必须考虑列表中的每个面并搜索intersection.

这对于分散且大多数不相交的多边形很有效，特别是如果您可以选择足够精细的栅格大小，以便每个正方形只有几个多边形。当你击中有许多相交多边形的正方形时，它将变得很慢。一种额外的优化是在正方形处为每个列出的多边形设置一个标志，以指示该正方形完全包含在多边形内；这允许您在许多情况下避免缓慢的包含测试，代价是每个多边形条目只有一位。如果栅格间距与多边形大小相比是很好的，这是特别有价值的，因为大多数正方形不会位于交叉点或边上。

如果需要更快的速度，可以开始在具有多边形引用的每个方块中存储边信息。您只需要针对实际与正方形区域相交的多边形边进行测试。这可以将工作量减少到每个多边形仅进行少量的边缘测试。