按彼此的接近程度对坐标进行分组

Question

我正在构建一个 REST API，所以答案不能包括谷歌地图或 javascript 的东西。在我们的应用程序中，我们有一个包含帖子的表格，如下所示：

  ID |   latitude   | longitude   | other_sutff
   1 | 50.4371243   |  5.9681102  |    ...
   2 | 50.3305477   |  6.9420498  |    ...
   3 | -33.4510148  | 149.5519662 |    ...

我们有一个带有地图的视图，其中显示了世界各地的所有帖子。希望我们会有很多帖子，在地图上显示成千上万的标记是荒谬的。所以我们想按距离对它们进行分组，这样我们就可以按大陆有 2-3 个标记。

要清楚，我们需要这个： 图片来自https://github.com/googlemaps/js-marker-clusterer

我做了一些研究，发现 k-means 似乎是解决方案的一部分。因为我的数学真的很差，所以我尝试了几个像这样的 php 库：https : //github.com/bdelespierre/php-kmeans，这似乎做得不错。但是，有一个缺点：每次加载地图时我都必须解析所有表。在性能方面，这很糟糕。

所以我想知道是否有人已经解决了这个问题，或者是否有更好的解决方案。

Answer 1

我一直在寻找，我找到了 KMeans 的替代方案：GEOHASH

维基百科会比我更好地解释它是什么：Wiki geohash

但总而言之，世界地图分为 32 个单元格，每个单元格都有一个字母数字字符。每个单元格也分为 32 个单元格，以此类推，共 12 个级别。因此，如果我GROUP BY对哈希的第一个字母执行 a ，我将获得最低缩放级别的集群，如果我想要更高的精度，我只需要按哈希的前 N ​​个字母进行分组。

所以，我所做的只是在我的表中添加一个字段并生成与我的坐标相对应的哈希：

ID |   latitude   | longitude   | geohash      | other_sutff
 1 | 50.4371243   |  5.9681102  | csyqm73ymkh2 |     ...
 2 | 50.3305477   |  6.9420498  | p24k1mmh98eu |     ...
 3 | -33.4510148  | 149.5519662 | 8x2s9674nd57 |     ...

现在，如果我想获得我的集群，我只需要做一个简单的查询：

SELECT count(*) as nb_markers FROM mtable GROUP BY SUBSTRING(geohash,1,2); 

在子字符串中，2 是精度级别，必须在 1 到 12 之间

PS：Lib我用来生成我的哈希