从一大组坐标中选择一些看起来均匀分布在该区域的坐标

Question

我有一个包含区域和纬度/经度位置列的 MySQL 表。每个区域都有很多位置，例如20.000。有没有办法只选择几个，比如 100，看起来在地图上分布得比较均匀？

分布不一定要完美，查询速度更重要。如果直接使用 MySQL 无法做到这一点，则可以使用一种非常快速的算法来选择均匀分布的位置。

提前致谢。

编辑：回答评论中的一些请求。数据没有任何可以使用的东西，它只是面积和位置坐标，例如：

+-------+--------------+----------+-----------+------------+--------+--------+
| id    | area         | postcode | lat       | lon        | colour | size   |
+-------+--------------+----------+-----------+------------+--------+--------+
| 16895 | Athens       |    10431 | 37.983917 | 23.7293599 | red    | big    |
| 16995 | Athens       |    11523 | 37.883917 | 23.8293599 | green  | medium |
| 16996 | Athens       |    10432 | 37.783917 | 23.7293599 | yellow | small  |
| 17000 | Thessaloniki |    54453 | 40.783917 | 22.7293599 | green  | small  |
+-------+--------------+----------+-----------+------------+--------+--------+

还有一些具有特征的列，但这些列仅用于过滤。

我确实尝试同时获取 nth 行，它似乎可以工作，尽管有点慢

SET @a = 0;
select * from `locations` where (@a := @a + 1) % 200 = 0

使用 random() 也可以，但也有点慢。

编辑2：事实证明，在表格上添加邮政编码很容易。有了这个，按邮政编码分组似乎给出了一个赏心悦目的结果。唯一的问题是，有非常大的区域，大约有 3000 个不同的邮政编码，而仅获取 100 个可能最终会导致其中许多显示在一个地方，因此可能需要在 PHP 中进一步处理。

Edit3，在评论中回答@RickJames 的问题，以便它们位于一个位置：

1. 请定义“均匀分布”——纬度均匀分布？没有两个人彼此“亲近”吗？ ETC。
   • “均匀分布”这个词选得不好。我们只是想显示该区域中的一些位置，但这些位置并非全部集中在一个地方
2. “区域”是矩形吗？六边形？还是不公正地划分选区？
   • 它们可以大致被认为是矩形，但这并不重要。我错过了重要的事情，我们还需要显示多个区域的位置。区域可能彼此相距较远或相邻（但不重叠）。在这种情况下，我们希望将 100 个样本分配到各个区域。
3. “每个区域 100 个”是否固定？或者可以是“大约100”
   • 它不是固定的，大约是 100，但如果它看起来不太好，我们可以更改它
4. 表上是否有 AUTO_INCRMENT id？数字上有差距吗？
   • 是的，有一个 AUTO_INCRMENT id 并且可以有间隙
5. 问题是否从“每个地区 100 个”更改为“每个邮政编码 1 个”？
   • 不，问题仍然是一样的，“每个区域显示 100 个，但并非所有区域都在同一个位置”，如何完成并不重要
6. 输出中的总行数和所需的行数是多少？
   • 总行数取决于区域和标准，一个区域最多可达 40k。如果总数超过 1000，我们希望仅显示随机的 100。如果 1000 或更少，我们可以只显示所有内容
7. 每次运行查询时是否都需要不同的示例？
   • 相同的样本或不同的样本（即使具有相同的标准）都可以
8. 您愿意在表格中添加一列吗？
   • 这不取决于我，但如果我有充分的论据，那么我们很可能可以添加一个新列

Answer 1

这是一种可以满足目标的方法。

1. 对表格进行预处理，创建一个新表格，以删除“重复”的项目。
2. 如果新表足够小，对其进行完整扫描可能会足够快。

至于“重复项”，请将此视为发现两个项目落在同一位置的粗略方法：

SELECT  ROUND(latitude * 5),
         ROUND(longitude * 3),
         MIN(id) AS id_to_keep
     FROM tbl
     GROUP BY 1,2

“5”和“3”可以向上（或向下）调整，以保留更多（或更少）的 id。由于纬度/经度的排列方式，“5”和“3”是不同的；这个比例可能适用于大多数温带地区。 （在赤道附近使用相同的数量，在更高纬度使用更大的配给。）

有一个小缺陷...两个非常接近的项目可能会跨越由 ROUNDs 创建的边界。

原表有多少行？上述查询生成了多少行？ ( SELECT COUNT(*) FROM ( ... ) x; )