2

如何快速找到一组多边形中的哪一个包含给定点？

我在POSTGis数据库中有一组多边形。我在 ruby​​ 端使用RGeo来操作、保存和从数据库中提取信息。

我从外部机器接收到一个点（x 和 y 坐标），并且需要知道该点位于我的哪个多边形内。我不能使用数据库，因为出于性能原因我需要在内存中完成此操作。

我相信我可能需要一个r-tree，但我并不完全想写一个。

RGeo提供了一种contains?方法，我可以使用它来确保一个点在感兴趣的多边形内，但我需要知道要检查哪个多边形。我有大约 1,000 个多边形，进行线性搜索的时间效率不足以满足我的需求。

4

1 回答 1

2

这有帮助吗？否则，有这个。

似乎neartree是搜索wrt ruby​​的更好选择。

希望这可以帮助！

编辑：如果您需要 rtree 的通用实现，也许 boost (c++) 库可以帮助这里有绑定。具有对您的用例有所帮助的方法的绑定：

intersects?
intersects_each?
intersects_rect?
intersects_rect_each?
于 2013-11-20T05:44:21.067 回答