根据GPS坐标确定美国州名，无需在线服务

Question

我正在分析推特上的内容，需要根据用户的GPS坐标找出他们所在的美国哪个州。因为我没有网络连接，所以不能使用像谷歌地图API这样的在线服务来进行反向地理编码。

有没有人有什么建议？我在用Python写这个脚本，如果有人知道可以用的Python库，那就太好了。或者如果有人能给我指个方向，比如研究论文或者高效的算法，让我能实现这个功能，那也会很有帮助。我找到了一些表示州边界的GPS坐标数据，但我想不出一个有效的方法来判断用户的坐标在哪个州。

Answer 1

这可能有点晚，但对某些人来说可能会有用。这是一个用Python写的解决方案。你可以去这个链接下载一个关于美国各州的geojson文件。

然后试试这个。

导入需要的库，并从GeoJSON文件中加载数据

import json
import pandas as pd
from shapely.geometry import Polygon, Point, MultiPolygon

data = json.load(open('GeoJson/gz_2010_us_040_00_20m.json'))
df = pd.DataFrame(data["features"])

从GeoJSON中提取所需的字段

df['Location'] = df['properties'].apply(lambda x: x['NAME'])
df['Type'] = df['geometry'].apply(lambda x: x['type'])
df['Coordinates'] = df['geometry'].apply(lambda x: x['coordinates'])

根据州的类型创建多边形或多重多边形对象

df_new = pd.DataFrame()

for idx, row in df.iterrows():

    if row['Type'] == 'MultiPolygon':
        list_of_polys = []
        df_row = row['Coordinates']
        for ll in df_row:
            list_of_polys.append(Polygon(ll[0]))
        poly = MultiPolygon(list_of_polys)

    elif row['Type'] == 'Polygon':
        df_row = row['Coordinates']
        poly = Polygon(df_row[0])

    else:
        poly = None

    row['Polygon'] = poly
    df_new = df_new.append(row)

删除我们不需要的列

df_selection = df_new.drop(columns=['type', 'properties', 'geometry','Coordinates'] )

输入一个示例的经纬度，看看结果 - 如果第一次结果不对，可以试着交换一下经纬度的位置 ;-)

point = Point(-81.47, 27.494) #Example GPS location for somewhere in Florida
state = df_selection.apply(lambda row: row['Location'] if row['Polygon'].contains(point) else None, axis=1).dropna()
print(state)

Answer 2

看着经纬度地图上的州的形状，可以明显看出大约70%的边界都是和经纬度的轴线对齐的。其他的边界则是比较直或者接近直的路径。似乎使用一个“精心设计”的二叉空间划分树，是判断一个地点属于哪个州的最快方法。

什么是“精心设计”的定义很难确定，但我建议你在排除州（整个州在这条线的A边或B边）和快速找到大城市之间找到一个平衡。理想情况下，如果你需要用一条线来划分一个州，尽量让大城市都在这条线的一边。

在创建边界时考虑人口分布，应该能提高你平均情况下的效率。考虑到有不少州的边界是沿着河流走的，你的树中一些最长的路径可能会非常深，但你应该能节省大量时间，而不是一个个州去检查。

Answer 3

使用一个点在多边形内的算法来判断一个坐标点是否在某个州的范围内（这个州用一组坐标点表示成一个多边形）。简单来说，逐个检查每个州的方式似乎没什么太大改进的空间，不过如果速度太慢，还是可以做一些优化。

不过，阿拉斯加的部分地区位于180度经线的两侧，这就会造成一些问题。一个解决办法是对每个GPS坐标（用户坐标和州坐标）的经度稍微调整一下，具体做法是加上30度，然后对180取余。这么做的效果是把180度经线向西移动了大约30度，这样就能确保整个美国都在180度经线的一侧了。