Определите штат США по координатам GPS без использования онлайн-сервиса
Я анализирую твиты и должен найти, в каком штате (в США) пользователь был по своим GPS-координатам. У меня не будет подключения к интернету, поэтому я не могу использовать онлайн-сервис, такой как Google Maps API для обратного геокодирования.
У кого-нибудь есть предложения? Я пишу сценарий на python, поэтому, если кто-то знает библиотеку python, которую я могу использовать, это было бы здорово. Или если кто-то может указать мне на исследовательскую работу или эффективный алгоритм, который я могу реализовать, чтобы выполните это, что также было бы очень полезно. Я нашел некоторые данные, которые представляют границы штатов в координатах GPS, но я не могу придумать эффективный способ определить, в каком состоянии находятся координаты пользователя.
2 ответа:
Используйте алгоритм точка-в-полигоне, чтобы определить, находится ли координата внутри состояния (представленного полигоном с координатами промежутка в виде точек). Практически говоря, не похоже, что вы сможете значительно улучшить, просто проверяя каждое состояние по одному, хотя некоторые оптимизации могут быть сделаны, если это слишком медленно.
Однако части Аляски находятся по обе стороны 180-го меридиана, что создает проблемы. Одним из решений было бы немного изменить координаты, добавив 30 градусный модуль 180 к долготе для каждой координаты GPS (координаты пользователя и координаты штата). Это имеет эффект перемещения 180-го меридиана примерно на 30 градусов к западу и должно быть достаточно для того, чтобы все США оказались по одну сторону 180-го меридиана.
Глядя на форму государств на карте logitude / latitude, становится очевидным, что, вероятно, 70% границ выровнены по осям long/lat. Другие следуют очень линейным или почти линейным путям. Похоже ,что "хорошо обработанное" дерево bsp должно быть самым быстрым способом решить, в каком состоянии находится местоположение.
Определение "хорошо обработанный" трудно установить, но я бы предложил вам попытаться сбалансировать исключающие состояния (все состояние находится на стороне A или B этой линии) с быстрой изоляции крупных населенных пунктов. В идеале, если вам нужно разделить государство линией, постарайтесь сделать так, чтобы крупные населенные пункты находились по одну сторону линии.
Включение рассредоточения населения в создание границ должно улучшить среднее время обращения. Учитывая, что довольно много штатов имеют границы, которые следуют за реками, некоторые из самых длинных путей в вашем дереве, вероятно, будут очень глубокими, но вы должны сэкономить значительное время на проверке каждого штата индивидуально.