如何通过经纬度进行高效的多点搜索

Question

我是一个iOS应用程序，拥有旅行计划功能。例如，我使用Google方向API从纽约到波士顿获取路线。我有50个不同的经纬度来在地图上绘制折线。之后，我需要获取沿途可以参观的地方。

Google方向API提供给我：

latitude = "30.308399"; longitude = "-89.748299";
latitude = "30.310930"; longitude = "-89.818604";
latitude = "30.350050"; longitude = "-89.916054";
latitude = "30.432850"; longitude = "-90.098549";
....

目前每个点我都会在mysql数据库中搜索以获取最近的地点:

选择 id、标题、类型id、服务id、纬度、经度、状态、城市、邮政编码和地址， （3959 * acos(cos(radians(31.72723)) * cos(radians(latitude)) * cos(radians(longitude) - radians(-106.3047)) + sin( radians(31.72723)) * sin(radians(latitude)))) AS distance from places距离<=10 order by distance ASC限制10

但是，如果这次旅行是从纽约到旧金山，我将有800个点，我需要对数据库进行800次查询，总共需要超过2秒的时间。而且我有7个不同的表格，需要14秒。

如果要怎么做才最好呢？

- Dark Matter

---

数据库中有多少个点数？ - Толя

总共有7张表，共有80k个位置。 - Dark Matter

你需要让数据库中的地点更有组织性。可以通过运行k-means聚类并将它们分成不同的簇来实现。然后，你可以通过每个簇进行搜索，而不是搜索每个地点。簇的大小应该取决于缩放级别。 - Shivam

可能是重复的问题：算法：查找距离给定的Lat Lng位置一定距离内的所有纬度经度位置。 - raisercostin

Answer 1

以下是加快查询速度的一种方法：

(1) 在表中为纬度和经度建立索引。

(2) 在查询中，首先只选择那些距离路线上点足够近而且有趣的水平和垂直距离内的地点。按纬度范围和经度范围进行选择。

(3) 然后按距离对这些点进行排序，可以在查询内部或外部进行。

- xpda

Answer 2

我能提供的最好建议是 Voronoi图。但它很难实现。

注： 由于您只有80k个点，您可以将所有这些点缓存在应用程序中，并从应用程序返回所需的点。

- Толя

Answer 3

尝试加入最小距离限制，例如 Distance > 100 等。

这被称为锥形扫描。您可以从低分辨率开始，随着接近目标逐渐增加分辨率。

- Srikant Krishna

---

什么都没变，他仍然需要计算距离。 - Толя

仍需总共向数据库发起5,600个查询。 - Dark Matter

他不会收到成百上千个数据点，可能只有几十个。这将加快他的查询速度。这是直观的解决方案-对于非常大的距离，首先进行“宽范围”扫描，然后缩短距离。 - Srikant Krishna

他仅选择前10个。要应用你的SQL查询，仍需计算到每个点的距离。 - Толя