database - 有效存储和查询 GPS 坐标

Question

我想创建一个大型 GPS 坐标数据库，可以通过说“返回 [此坐标] 'n' 米内的所有坐标”来查询。

我需要它尽可能高效，因此循环遍历数据库中的所有坐标并计算坐标是否在“n”米内不是理想的解决方案。

有更简单的解决方案吗？

谢谢

Answer 1

我通常使用纬度/经度进行此类查询。使用球面几何，您可以在特定点周围放置一个边界框。例如，假设您有一个点 (X,Y)，您希望 1 英里内的所有坐标（转换为米，我将作为练习留给读者）。您可以确定 (X-1,Y-1),(X+1,Y+1) 的边界框。然后使用 BETWEEN 运算符查询您的积分数据库（SELECT foo FROM bar WHERE LAT BETWEEN X-1 AND X+1 AND LON BETWEEN Y-1 AND Y+1）。然后你做你的细节距离计算来“圆角”你的边界框。

需要注意的是，经线在球体顶部更靠近，因此离赤道越远，结果就会出现偏差。但它仍然可以快速过滤您的结果集。

谷歌“大圆距离”进行计算。

编辑：每英里有 0.167469 度经度（实际上范围从 0.167469 到 0.014564），每英里有 0.014483 度纬度。所以你的边界框是(lat - (miles * 0.014483), lon - (miles * 0.167469)), (lat + (miles * 0.014483), lon + (miles * 0.167469))

Answer 2

SQL Server 2008 支持存储空间数据。我自己从未使用过它，但我知道您可以创建所需类型的查询。

Answer 3

许多数据库系统具有处理地理空间数据的功能。

这是 SQL Server 2008、PosGIS 和 MySQL http://www.bostongis.com/PrinterFriendly.aspx?content_name=sqlserver2008_postgis_mysql_compare之间的比较地理空间函数

Answer 4

GIS 数据库（例如带有 PostGIS 的 PostgreSQL）实际上为二维或三维区域搜索（空间索引）提供了数据结构。最简单的一种是网格索引，然后是不同的搜索树（kd-tree、quad-tree），其中 R-tree 是最常用的（一种用于更多维度的广义 B-tree）。这些方法似乎足够了。

一个基本的网格索引（将空间划分为网格单元，只在附近的单元中搜索）可以很容易地实现，并且可以显着减少搜索时间。搜索树实现起来有点困难，但是对于很多编程语言和数据库（如 PostGIS 或 Geopandas 等）有很多开源实现。将它们用于此类问题通常会得到回报。

Answer 5

跟进 Erich - 如果您选择使用 PostGIS (postgresql)，它是免费和开源的，您描述的查询是否非常快速，几乎可以在所有平台上运行，我是否提到它是免费的？

Answer 6

如果您想避免 GIS 扩展，我将这篇文章中的函数改编为 postgres sql：

create or replace function change_in_lat(miles numeric)
returns double precision as $$
with v as (select
    3960.0 as earth_radius,
    180 / pi() as radians_to_degrees
) select ( miles / earth_radius ) * radians_to_degrees from v;
$$ language sql
returns null on null input;

create or replace function change_in_long(lat numeric, miles numeric)
returns double precision as $$
with v as (select
    3960.0 as earth_radius,
    pi() / 180 as degrees_to_radians,
    180 / pi() as radians_to_degrees
) select (
    miles / (earth_radius * cos(lat * degrees_to_radians))
    ) * radians_to_degrees from v;
$$ language sql
returns null on null input;

使用那些你可以做一些围绕正方形的查询：

--find all "a"s within 25 miles of any "b"
select * from a join b on (
a.gpslat between
    b.gpslat - change_in_lat(25) and b.gpslat + change_in_lat(25)
and a.gpslong between
    b.gpslong - change_in_long(b.gpslat::numeric, 25)
    and b.gpslong + change_in_long(b.gpslat::numeric, 25)
);

如果您经常使用它，我相信将 between 语句转换为单个函数会很容易。不过，我从未对此进行任何实际的“半径范围内”查询。

对于更复杂的事情，您可能需要一个 GIS 扩展，就像其他答案所说的那样。PostGIS 很好，但我发现很多特定于 gis 的功能很难正确使用，除非您使用边界框索引，否则如果您的数据集足够大，您的空间查询可能需要一天的时间。但是对于所有花哨的东西来说，复杂性的权衡绝对是值得的，比如以 geojson 格式输出数据等。

Answer 7

如果您可以选择 DB，我会推荐与 rwwilden 相同的数据库，并使用具有空间数据功能的 SQL 2008。如果您不能使用该解决方案或包含空间查询的解决方案，您可以查看 Microsoft 自己的关于Hierarchical Triangular Mesh的论文并实现这些东西。MSSQL '05 的 SDK 还附带了一个开箱即用的 HTM 完整解决方案，因此您可以将其转换为您正在使用的任何平台。

编辑：

这是解释 HTM 和实现的更详细的文档。您当然可以转换为您选择的数据库。您可以在 SDK for 2005 中找到完整 HTM 实现的源代码。

Answer 8

我们可以使用 Geohash 算法。

geohash 的美妙之处在于它的构造方式。简而言之，geohashes 是一种网格空间索引，其中世界被递归地划分为越来越小的网格，每增加一个位。（https://www.mapzen.com/blog/geohashes-and-you/）

您可以在 Wikipedia ( https://en.wikipedia.org/wiki/Geohash ) 上找到它的描述。

我包括了下一个视频，以便快速直观。

https://www.youtube.com/watch?v=UaMzra18TD8

https://youtu.be/mx1mMdHBi5Q?t=1955

在下一篇文章中，您可以找到针对 AWS 数据库 DynamoDB 的这种算法的实现。 https://read.acloud.guru/location-based-search-results-with-dynamodb-and-geohash-267727e5d54f

请为 James Beswick 的文章鼓掌。