#python #algorithm #gps #reverse-geocoding
#python #алгоритм #gps #обратное геокодирование
Вопрос:
Я анализирую твиты и мне нужно определить, в каком штате (в США) находился пользователь, по их координатам GPS. У меня не будет доступного подключения к Интернету, поэтому я не смогу использовать онлайн-сервис, такой как Google Maps API, для обратного геокодирования.
У кого-нибудь есть какие-либо предложения? Я пишу скрипт на python, поэтому, если кто-нибудь знает библиотеку python, которую я могу использовать, это было бы здорово. Или, если кто-нибудь может указать мне на исследовательскую работу или эффективный алгоритм, который я могу реализовать для достижения этой цели, что также было бы очень полезно. Я нашел некоторые данные, которые представляют границы штата в координатах GPS, но я не могу придумать эффективный способ определить, в каком состоянии находятся координаты пользователя.
Комментарии:
1. Используйте алгоритм point in polygon, чтобы определить, находится ли координата внутри штата (представленного полигоном с координатами GSP в виде точек). Не похоже, что вы смогли бы это слишком сильно улучшить, практически говоря.
2. @Nuclearman Спасибо, что указали мне правильное направление; это именно то, что я искал. Вы можете написать свой комментарий в качестве ответа, и я приму его.
3. Обычно я публикую подобные короткие ответы в виде комментариев, поскольку это своего рода вопрос о том, находится ли плакат в той же ситуации, что и вы, или плакат действительно ищет что-то более подробное. Я полагаю, что проще удалить неточный комментарий, чем отредактировать / удалить неточный (с точки зрения спрашивающего) ответ.
Ответ №1:
Используйте алгоритм «точка в полигоне», чтобы определить, находится ли координата внутри штата (представленного полигоном с координатами промежутков в виде точек). С практической точки зрения, не похоже, что вы смогли бы значительно улучшить ситуацию, просто проверяя каждое состояние по очереди, хотя некоторые оптимизации могут быть сделаны, если это слишком медленно.
Однако части Аляски находятся по обе стороны от 180-го меридиана, что создает проблемы. Одним из решений было бы немного сместить координаты, добавив 30 градусов по модулю 180 к долготе для каждой координаты GPS (координаты пользователя и координаты штата). Это приводит к перемещению 180-го меридиана примерно на 30 градусов к западу, и этого должно быть достаточно, чтобы гарантировать, что все США находятся по одну сторону от 180-го меридиана.
Комментарии:
1. Как насчет Аляски? Будет ли какая-либо ошибка при отображении координат GPS, скажем, во Флориде, по сравнению с Аляской.
2. Очень мало шансов перепутать местоположения Аляски и Флориды, они хорошо разделены по широте и долготе. Требуется небольшая осторожность с Аляской, которая имеет местоположения по обе стороны от /- 180 долготы.
3. @HighPerformanceMark: Должно быть, пропустил это, глядя на мой глобус, или острова крошечные. Отредактировал мой ответ.
Ответ №2:
Глядя на форму штатов на карте широты, становится очевидным, что, вероятно, 70% границ выровнены по длинным / широтным осям. Другие следуют очень линейным или почти линейным путям. Похоже, что «хорошо обработанное» дерево bsp должно быть самым быстрым способом определить, в каком состоянии находится местоположение.
Определение «хорошо проработанный» трудно установить, но я бы посоветовал вам попытаться сбалансировать устранение штатов (весь штат находится на стороне A или B этой строки) с быстрой изоляцией крупных населенных пунктов. В идеале, если вам нужно разделить штат линией, попробуйте сделать так, чтобы крупные населенные пункты находились по одну сторону линии.
Включение рассредоточения населения при создании границ должно улучшить среднее время обращения. Учитывая, что границы многих штатов проходят по рекам, некоторые из самых длинных путей в вашем дереве, вероятно, будут очень глубокими, но вы должны сэкономить значительное время на проверке каждого штата в отдельности.
Ответ №3:
Это немного запоздало, но может быть полезно для некоторых. Это решение на python. Перейдите по этой [ссылке] (https://eric.clst.org/tech/usgeojson /) и загрузите файл 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'])
Создание объектов Polygon или MultiPolygon в зависимости от типа штатов.
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)