如何快速找到一组多边形中的哪一个包含给定点?
我有一个多边形集合 POSTGis数据库。我正在使用RGeo在 ruby 端操作、保存信息以及从数据库提取信息。
我从外部机器收到一个点(x 和 y 坐标),并且需要知道该点位于我的哪个多边形内。我无法使用数据库,因为出于性能原因我需要在内存中完成此操作。
我相信我可能需要 r-tree ,但我并不是很想写一个。
RGeo
提供了一个 contains?
方法,我可以使用该方法确保点位于感兴趣的多边形内,但我需要知道要检查哪个多边形。我有大约 1,000 个多边形,进行线性搜索的时间效率不足以满足我的需求。
最佳答案
看来,neartree 是一个更好的搜索 w.r.t 的东西。 ruby 。
希望这有帮助!
编辑:如果您需要 rtree 的通用实现,也许 boost (c++) 库可以帮助它有绑定(bind) here 。 它具有对您的用例有帮助的方法的绑定(bind):
intersects?
intersects_each?
intersects_rect?
intersects_rect_each?
关于ruby - Ruby 中多边形的点交点,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/20078290/