通过GPS坐标查找最近的城市-算法

Question

我获得了我所在位置的坐标（55.1858, -162.7211）。我想找到我所在的城市（或附近），如果它存在于我的数据集中。数据集（数万个坐标）包含我感兴趣的所有城市，以及与该城市相对应的一个或多个坐标（取决于城市的大小）：

Cold Bay, Alaska, 55.1858,-162.7211
False Pass, Alaska,54.8542,-163.4113
King Cove, Alaska, 55.0628,-162.3056
...

找到我所在的城市（不使用任何API，Google Maps等。）的最佳算法是什么（最好是JavaScript）？

我有一些想法，但它们可能都不是最好的，因为它们都是蛮力方法：

1. 围绕我的一定距离的坐标绘制一个半径，然后遍历数据集以查找是否有任何现有坐标在该半径内。如果是一个或多个，则遍历它们，并通过它们的距离查看我最接近的一个。
2. 以某种方式，开始将我的坐标四舍五入到小数点后第一位，并在每次四舍五入后检查数据集中是否存在这组新的四舍五入坐标。

我觉得这些想法真是个坏主意，希望能为这类搜索提供一些有关好的算法的指导或建议。

Answer 1

这并不奇怪：它只是搜索。

保留按纬度和经度排序的城市列表，然后对您的当前位置执行二进制搜索。对于一个10,000个城市的数据库，您正在寻找12或13个递归步骤，最坏的情况。

您不太可能获得完全匹配，但这无关紧要，因为您将在最后一步获得最接近的匹配：确定不再需要递归后，只需使用<和>即可找出哪个候选词（左侧或右侧）最接近您的输入。

Answer 2

您可以使用Google Maps地理编码的api来获取城市，您可以调查此答案

How can I get city name from a latitude and longitude point?