哪种空间数据结构(算法)最适合在一组区域(空间数据)中进行搜索
本文关键字：空间 数据 区域 一组 搜索 算法 数据结构 | 更新日期: 2023-09-27 18:14:02
我有一组多边形区域(地理围栏)。这组数据是固定的;因此不需要插入和删除数据。哪种数据结构可用于搜索查询点(经度、纬度)所在的区域?
注意:我已经成功地为一组点实现了KD-Tree(实际上是2D-Tree)。但它对这个问题不起作用。我已经实现了一个r树;它解决了问题，但速度很慢(或者我的实现很糟糕)。
谢谢
注意:我已经完成了R-Tree的实现，它现在工作得很好。
由于没有插入/删除，并且可能有足够的时间来预处理数据，因此可以使用一些额外的内存来加快计算速度。预处理的基本思想:
- 取所有多边形点并确定包含它们的最小轴对齐的边界矩形;这是X和y的最小值和最大值
- 选择将用于创建搜索网格的分区因子dX和dY。为分配因子选择2的幂可以使以后的计算稍微快一些。
- 平移多边形数据，使它们的边界矩形最小值与(0,0)一致，并展开矩形，使其是每个维度的分区因子的整数倍。
- 考虑每个网格正方形，并列出与该正方形相交的多边形。为每个网格正方形存储此列表。根据数据的性质(你可以期望有多少多边形与一个正方形相交)，有各种方法可以优化存储空间或速度。
现在，当你想找到包含一个点的区域:
- 使用我们之前定义的原点平移该点，并确定包含该点的网格正方形(如果使用2的幂，这是移位操作;)
- 看网格正方形的列表。如果它为空，则没有包含多边形。如果没有，你必须考虑列表中的每个多边形并搜索交集。
这对于分散的和大多数不相交的多边形很有效，特别是如果你可以选择一个足够精细的网格大小，使得每个正方形只有几个多边形。当你击中有很多相交多边形的正方形时，它会很慢。一个额外的优化是在一个正方形上为每个列出的多边形设置一个标志，以表明该正方形完全包含在该多边形中;这允许您在许多情况下以每个多边形条目的单个比特为代价来避免缓慢的包含测试。如果你的网格间距与多边形尺寸相比很好，这是特别有价值的，因为大多数正方形不会位于交叉点或边缘。
如果你需要更快的速度，你可以开始在每个多边形参考的正方形上存储边缘信息。你只需要测试与正方形相交的多边形边缘。这可以将工作量减少到每个多边形只有少量的边缘测试。
R-Tree数据结构可用于此问题。