java - algorithm-- 如何高效地找到距离百万坐标最近的POI

Question

这是面试后我被要求实现这个——

所以我得到了欧几里德坐标中餐厅 POI 的列表(大约 2000 个)

然后我得到一个用户坐标列表(其中 100 万个)

我的任务是返回一个 POI 的特定半径 (10,15) 内有多少用户，其次，75% 的用户在 POI 的距离内所需的半径

距离是我可以计算出来的，但暴力破解意味着要检查 100 万个坐标中的 1000 个坐标，这需要非常非常长的时间。

什么是更有效的方法来做到这一点？

Answer 1

最好使用允许您对坐标进行空间索引并运行高效空间运算符的框架。 Mapinfo、空间感知数据库(Oracle Spatial - 生产使用可能需要额外许可)、ESRI、开源等。

通常的 Action 是

1. 将 POI 加载到空间索引容器(具有空间索引的表)中。
2. 在空间索引容器中加载用户
3. 将 POI 扩展为具有所需距离半径的圆形对象。
4. 为 POI 圈子内的用户进行空间加入/组合

这些空间连接/组合器可用于不同类型的空间运算符。

如果您只想在练习中生成结果，并且不能使用任何框架，我建议您采用一些简单的方法。

100 万用户实际上并不是特别大——它是可管理的——问题是这些点要根据 2000 个 POI 进行评估。我认为最好的方法是

1. 首先使用 2 x 半径作为边在 POI 周围生成边界正方形。
2. 这将使您能够相当快速地评估每个兴趣点对哪些点感兴趣。原则上只有大于、小于将用作运算符。
3. 为每个 POI 设置一组用户，您可以通过实际距离计算进一步缩小范围。

您可以利用各种智能索引和排序来加快速度。如果您有时间实现，评论中建议的 R-Tree 似乎非常适合。这将有助于您完成上述第二步。

一个更简单的方法 - 根据您的坐标布局方式(您的世界看起来如何)，将您的世界划分为更大的正方形，并首先为每个用户和每个 POI 确定他们属于哪个正方形。您可以快速确定 POI 同一方 block 内的所有用户，或任何相邻方 block 内的所有用户作为感兴趣的用户。想出一个智能索引/编号方案，也可以帮助您识别邻居。通过 Hashmaps 将用户列表索引到他们的方 block 。