SQL中快速查找最近的值

Question

我可以帮助您进行翻译。这段文字是关于编程方面的内容，讲述了在SQLite数据库中存储了具有高度信息的经纬度坐标，并提供了一些示例数据。

latitude   longitude  altitude
------------------------------
48.003333  11.0       652    
48.036667  11.000833  651
48.280833  11.000833  533

现在我需要一些SQL查询，以给定的纬度/经度坐标为基础提供最接近的高度，例如，

给定的纬度/经度将是48.023445/11.000733，因此最接近的是具有48.036667/11.000833纬度/经度和651高度。我尝试在许多论坛上搜索，但没有找到有用的信息。无论哪里都只有一个变量或非常慢的查询示例。我需要这个查询非常快，并且看到了一些基于UNIONS的解决方案。我需要它快，因为我将在这个表上进行约150万次查询。我正在使用事务和索引。

- MartinS

---

你使用的是哪个数据库？PostgreSQL？ - piotrekkr

也许这可以帮助：https://dev59.com/xnNA5IYBdhLWcg3wVcJx，或者也许可以使用PostgreSQL + PostGIS（http://postgis.org/）。 - piotrekkr

@MartinŠevic 你的查询是否都是针对矩形区域中连续的点？如果是这种情况，你应该在问题中添加更多上下文。 - kmkaplan

好的，我有一张指定高度和宽度的图片。每个像素都有它自己的GPS坐标，我想要做的就是为每个像素分配海拔高度。 - MartinS

Answer 1

对于您的目的（接近所搜索的坐标），最好最小化使用平面距离公式。

(lat-latitude)*(lat-latitude) + (long-longitude)*(long-longitude)

- kmkaplan

Answer 2

在球面上，使用经度和纬度坐标计算两点之间的距离公式远非简单，可以在此处查看。如页面所述，如果两点相对较近，则可以使用简单的平面三角法，并仅使用点之间的欧几里得距离：

- SWeko

Answer 3

我会选择类似以下查询的内容：

select * from pos order by ((lat-48.00333)*(lat-48.00333)+(long-11.0)*(long-11.0)+(alt-652)*(alt-652));

SQLite不支持SQRT，但由于SQRT是单调的，因此您可以在距离公式中跳过它。

- Daniel Voina

---

但我不想计算距离，我只想为地图上的每个像素分配高度。每个像素都有自己的坐标，所以我只想搜索最接近的行，其中long=xx.xxxxx和lat=yy.yyyyyy。 - MartinS

据我所知，您正在尝试做类似于以下操作： 对于每个y 对于每个x 找到最接近点(x,y)的高度是这样吗？在这种情况下，扫描的时间复杂度为O(n^2)，因此这种查询效率相当低下。 - Daniel Voina

在这种情况下，我会在应用程序级别实现一些缓存。我将在内存中获取一个500 * 500点的窗口，并在此数据中搜索您点的高度。因此，您将在内存中获取更大的结果集并减少对DB的查询。如果发生缓存未命中，您将不得不获取另一个窗口，但惩罚会更低。查看此问题stackoverflow.com/questions/1006654/…（通过pitrekkr提供的url）的第二个答案，以获取一些不涉及空间索引的实现思路。 - Daniel Voina

我知道有点晚了，但是你帮了我。我想你应该知道这个。我制作了一个简单的缓存，将当前图片从数据库中读取的所有点逐一插入到CSV文件中。同时，在应用程序级别上，我编写了一个算法来计算我插入的每个点的确切行数（在数据库中每个记录之间有一个顺序）。因此，对于1800 * 900像素的文件，第一次加载大约需要一分钟。由于缓存，对此地图的任何其他加载都只需大约2-3秒钟。它非常有效，因为用户很少更改此文件。 - MartinS