我有一组多边形区域(地理围栏)。这组数据是固定的;所以不需要插入和删除数据。哪种数据结构可用于搜索查询点(经度、纬度)所在的区域?
注意:我已经为一组点成功实现了 KD-Tree(实际上是 2D-Tree)。但它不适用于这个问题。然后我实现了一个 R-Tree;它解决了问题,但速度很慢(或者我的实现很糟糕)。
谢谢
注意:我从事过 R-Tree 实现,现在可以正常工作。
由于您没有插入/删除并且可能有足够的时间来预处理数据,因此您可以使用一些额外的内存来加快计算速度。预处理的基本思想:
现在,当您要查找包含点的区域时:
这适用于展开且大部分不相交的多边形,特别是如果您可以选择足够精细的网格大小以使每个正方形只有几个多边形。如果你碰到有很多相交多边形的正方形,它会很慢。另一个优化是在正方形上为每个列出的多边形设置一个标志,以指示该正方形完全包含在多边形内;这允许您在许多情况下以每个多边形条目的单个位为代价来避免缓慢的包含测试。如果您的网格间距与多边形大小相比很好,这尤其有价值,因为大多数正方形不会位于交叉点或边缘。
如果您需要更快的速度,您可以开始使用多边形参考在每个正方形存储边缘信息。您只需要针对实际与正方形区域相交的多边形边缘进行测试。这可以将工作量减少到每个多边形仅进行少量边缘测试。
R -Tree数据结构可以用来解决这个问题。