algorithm - 用于查找多个坐标（纬度/经度）动态和静态之间距离的算法

Question

我正在 Flutter 中制作一个应用程序，它将具有一些混合功能，例如分类应用程序/Tinder。我需要一个关于如何实现这一点的逻辑或一些建议。请耐心听我的解释。

用例： 用户 A：发布关于出售他的电视的广告并将他的地址添加到广告中 -（经纬度） 用户 B：在同一个应用程序中，他正在寻找电视广告，但他将搜索半径设置为 5 公里。（我们从他的设备中获得了用户 B 的位置。纬度/经度）

• 现在在我的 items_db 表中，电视广告信息与位置一起保存
• 向用户 B 显示他附近的电视；我可以计算项目和用户之间的距离（使用 Google APi）
• 但是为了向他展示他附近的所有电视，我必须首先计算用户与 Classified/items_db 中所有可用项目之间的距离，以找出其中有多少实际上在他应用的 5km 过滤器下。
• 现在我们谈论的是 1 个用户：但是如果我有 1000 个用户，那么我将不得不计算所有项目与所有用户位置之间的距离，然后只向他显示那些在他们指定范围内的项目（即 5 公里或 10公里）

这似乎太大或太糟糕，无法像那样实施。所以我的问题是我们如何做到这一点？

---

如果这还不够清楚，请在此处使用 Tinder 作为示例：

当我在 Tinder 中选择“仅显示 2 公里半径内的人”时。那么 Tinder 是如何知道这一点的呢？我的意思是为了弄清楚谁在2公里之外；他们首先必须计算所有可用用户的距离，以便查看哪些可以显示给符合 2 公里标准的最终用户！那里是怎么做的？

标签： algorithmflutterlogicdistancetinder

Answer 1

您当然可以检查每对点之间的距离，但这不是您唯一的选择。

通常，您想要的是找到每个点的最近邻居。也就是说，您只想找到某个设定距离内的其他点。通常这称为最近邻搜索。没有单一的最佳方法可以做到这一点，实际上性能可能会根据您的确切数据而有很大差异，但可能值得考虑的两种方法是局部敏感哈希，它使用哈希函数尝试将相似的点放在相同的存储桶（甚至在靠近的存储桶中），因此您只需要检查这些存储桶即可找到邻居和kd 树，这是一种考虑最近邻搜索而设计的数据结构。