已知某位置坐标和大量城市坐标(均用经纬度表示)，有没有高效的方法判断该位置处于哪个城市？

Question

如题，目标点和城市坐标都用经纬度表示，城市数量大约在30至50左右。有没有
什么高效的算法判断出该目标点位于哪个城市(不考虑不在其中的情况)？

城市的坐标只用一组经纬度表示，并没有城市大小和范围等信息

Answer 1

假设城市的范围是100km，你可以把城市所在位置的经纬度和相关区域以经纬度整数的形式存放在数据库里。
比如对应北京市，北纬39”26’至41”03’,东经115”25’至 117”30’
那么 
city x y
北京 115 39
北京 115 40
北京 115 41
北京 116 39
北京 116 40
...
北京 117 41
<别的城市类似>

这样，你有一个坐标，直接整除以后查表就可以了。

如果觉得1度（大约110km）还太粗糙，可以用0.5度，0.25度...
那么这个索引的数据大4倍、8倍。

像北京这么大的城市，用0.5精度的话，也就是几十个点，50个城市也就几千条数据，加上索引，很快的。