algorithm - 如何快速确定一个点在哪个经纬度范围内

Question

假设我有一些 (lng, lat) 坐标。我也有一个很大的范围列表，

[ {东北：{lng，lat}，西南：{lng，lat}} ...]

我怎样才能最有效地确定 (lng, lat) 点进入哪个桶？

另外，从设计的角度来看。将“范围列表”放在 mysql、monodb 等数据库或 memcached、redis 等数据库上是否更有意义？

谢谢你。

Answer 1

您需要细分范围列表。您可以查看四键。它类似于四叉树。它使用莫顿曲线。您可以非常快速地计算范围和点的四键。但是您也可以尝试使用矩形树。您也可以使用区间树。

Answer 2

SQL 数据库可能是一个很好的答案。如果您想象一个类似 的表，在所有 lat/long 列上都有索引，那么您可以通过准备和执行查询（例如使用所需的 lat/long 坐标）(bucketId, latNe, longNe, latSw, longSw)来非常有效地得到答案。SELECT bucketId FROM bucketTable WHERE latNe > ? AND longNe < ? AND latSe < ? AND longSe > ?

Answer 3

R-Tree就是为这种事情设计的数据结构 。Boost包含了它的一个实现。和CGAL一样。大多数现代数据库本身也支持这种东西。