有两个现实生活中的问题，我正在努力寻找答案：
-
Restaurant Service ：当我使用我的食物订购应用程序（如FoodPand，Zomato等）时，该应用程序会在我登录时检测到我的位置并相应地建议附近的餐馆（可能在范围内足够好以便所选餐厅可以提供食物） .
-
Cab Service ：当我使用出租车服务（如Uber或Ola）时，当我尝试预订出租车并建议当时可用的附近出租车时，他们也会检测到我的位置 .
Question : 如何找到最近的餐馆和最近的出租车？他们实际使用哪种特定算法？由于两种情况都不同，因为搜索数据在一种情况下是静态的，而在另一种情
My Take on the question :
-
在对这个主题进行了一些头脑风暴之后，我开始知道由于餐馆是固定的实体，我们可以将它们映射到KD树（允许存储空间索引） . 根据客户的位置，我们可以在KD树上搜索，找出附近的一组餐馆 . KD树的创建花费O（n）时间并且搜索花费O（logn）时间，n是树中的n个数量 . 这种方法对我来说似乎很好，因为我不知道有什么比这更好的方法，我仍在寻找答案 .
-
在驾驶室服务的情况下，驾驶室的位置不是静止的（与餐厅服务不同） . 因此，为每个更改的驾驶室位置创建KD树似乎是一个开销 . 考虑到驾驶室的当前位置，我怎么能找到最近的5个出租车？驾驶室实际使用哪种算法？
Any insight will be highly appreciated.
附： ：我还遇到了K最近邻搜索算法，它再次导致了KD树 .
1 回答
存在称为Quadtree的数据结构作为2D动态k-D树的解决方案 . 但实际上，实际实现可能不涉及繁重的数据结构 . 您可能会想到更简单的方法，这可能会超出动态k-D树：
将 Map 划分为矩形网格
当驾驶室更改其' location(post request containing GPS coordinates), check if it is still in the rectangle otherwise change rectangle'的内部信息时
当用户想要找到最近的驾驶室时，只需在网格中找到它的矩形并找到最近的一个用穷举搜索
你可能会想“为什么？” . 实际上，在上面的简单方法中，添加并发和并行化会更容易，而修改k-d树可能非常困难 .