Самый быстрый способ найти местоположение (почтовый индекс, город, штат) по широте / долготе

Question

Мне нужно бесплатное решение (с открытым исходным кодом), которое, учитывая широту / долготу, может вернуть закрытый город / штат или почтовый индекс. mysql не вариант, небольшая облегченная база данных будет лучшей, если это возможно.

Обновления: нет веб-сервисов, с 50 миллионами показов в день, даже самый маленький аддон причиняет боль, поэтому добавление запроса на обслуживание уменьшит время отклика. Я бы предпочел не добавлять более 200 миллисекунд к запросу.

У меня есть база данных, lat / lon / zip / city / state в csv, это просто как хранить и, что более важно, как получить ее быстрее всего.

Answer 1

Это очень интересный вопрос со сложным ответом.

Вы упоминаете базу данных городов с широтой / долготой, но города не являются отдельными точками, и это может иметь большое значение в густонаселенных районах, где большие части города А могут быть ближе к «центру» города В, чем к центр города А. Возьмите большой город в окружении небольших пригородов. Отдаленные части большого города могут быть ближе к центрам пригорода, чем к центру самого большого города. Привязка к ближайшему центру города подразумевает карту с диаграммой центра города Вороного. Такая карта не будет похожа на карту городов.

Если вы хотите узнать город и штат для данного широты / долготы, вам нужно запросить правильную карту и указать точки в полигональных тестах, чтобы выяснить, в каком она находится. Это звучит вычислительно дорого, но на самом деле это Неплохо, если вы используете правильный пространственный индекс и осторожны в кодировании. Я запускаю веб-сайт, который продает API-доступ к этому и другим географическим запросам, и наш базовый механизм (написанный на Java) может вернуть содержащий или ближайший город в США со средним временем запроса 3e-4 секунды (более 3000 запросов). в секунду).

Несмотря на то, что мы продаем его, я с удовольствием объясню, как он работает, поскольку купить его у нас будет гораздо дешевле, чем построить его самостоятельно, даже с инструкциями. Итак, вот они:

• Найдите карту, которую вы хотите. Для населенных пунктов США перепись населения США предлагает чрезвычайно точные карты по адресу: http://www.census.gov/geo/www/tiger/tgrshp2010/tgrshp2010.html. Я не нашел глобальных карт, которые были бы столь же хороши, как карты переписи населения США, но они могут существовать.
• Найти или написать синтаксический анализатор для формата шейп-файла ESRI. У меня нет конкретной ссылки для этого, так как она сильно зависит от языка, но в Интернете есть множество парсеров, как бесплатных, так и коммерческих. Просто выполните поиск "анализатора шейп-файлов" вместе с вашим языком программирования.
• Загрузить карту в память. Цифровая карта состоит из списка многоугольников, представленных списком пар широта / долгота, обычно упорядоченных в направлении против часовой стрелки. Большинство карт допускают вырезы (например, Лесото в Южной Африке), которые просто перечислены как полигоны, где пары широта / долгота указаны по часовой стрелке. Из соображений производительности и потребления памяти вы можете использовать необработанные массивы с плавающей запятой (избегайте двойной точности, так как это приводит к бесполезному расходу памяти, и по возможности используйте собственные массивы, чтобы избежать упаковки).
• Далее вам потребуется код, чтобы ответить, содержится ли заданная точка запроса в заданном многоугольнике. Вот отличное обсуждение проблемы точки в многоугольнике: Как определить, находится ли 2D точка внутри многоугольника?
• По моему опыту, метод грубой силы, предложенный в другом ответе (проверка каждой сущности), плохо работает на национальных или мировых картах. Вместо этого я настоятельно рекомендую быстрый пространственный индекс, который возвращает список возможных полигонов для данного широты / долготы. Здесь много вариантов. Многие люди рекомендуют использовать древовидные индексы, но я предпочитаю сеточные индексы, поскольку они быстрее, а современные серверы, как правило, имеют много памяти. Я написал единственный такой индекс, с которым я работал. Я знаю, что они существуют в библиотеках ГИС, но я считаю, что большая часть кода ГИС слишком сложна, медленна и сложна в использовании. Таким образом, при заданном запросе широта / долгота вы получаете список полигонов-кандидатов из пространственного индекса и используете функцию точка-полигон, чтобы найти, какой из кандидатов содержит точку запроса.
• Также важно обрабатывать случаи, когда точка запроса не содержится ни в каком многоугольнике. В таком случае вы, вероятно, захотите найти ближайший такой многоугольник вплоть до указанного максимального расстояния. Для этого вам нужно убедиться, что ваш пространственный индекс может возвращать список соседних полигонов, а не просто список кандидатов, содержащих полигоны. Вам также понадобится код для вычисления расстояния между точкой запроса и сегментом линии широта / долгота (это сложно, поскольку широта / долгота не является евклидовым пространством). Я не нашел никакого хорошего обсуждения того, как сделать это онлайн, поэтому я разработал свой собственный метод. Он работает путем создания линеаризованного пространства вокруг точки запроса (которое становится (0, 0) в новом пространстве), в котором относительная долгота масштабируется так, что степень измененной долготы остается той же расстояние как градус широты (включает умножение относительной долготы на косинус широты). В этом линеаризованном пространстве вы найдете ближайшую точку на отрезке, используя стандартные методы (см. Наименьшее расстояние между точкой и отрезком линии ), а затем конвертируете эту точку обратно в широту / долготу и используйте формулу Хаверсайна вычислить расстояние между двумя точками (см. Рассчитать расстояние между двумя точками широты и долготы? (формула Haversine) ).

И это все. Я строил и выключал такую ​​систему около полугода. По моим оценкам, в нем должно быть не менее трех человеко-месяцев серьезного кодирования, и это кто-то, знакомый с предметом (так что будьте осторожны, если вы принимаете решение купить или построить).

Answer 2

Грубая сила: предварительно загрузите все ваши данные в массив. Вычислите расстояние между вашей текущей точкой и каждой точкой в ​​массиве (есть метод для этого вычисления, который использует линейную алгебру вместо функций триггера, но я не помню, что это не так), чтобы найти ближайшую точку.

Пожалуйста, прочитайте это перед повторным голосованием : есть способы ускорить поиск грубой силы, как это, но я обнаружил, что они обычно не стоят проблем. Мало того, что я использовал этот подход прежде, чтобы найти ближайший почтовый индекс по широте / долготе, я использовал его в приложении для Windows Mobile (где вычислительная мощность не слишком велика) и все еще достигал времени поиска менее секунды. Пока вы избегаете использования триггерных функций, это не дорогой процесс.

Обновление: вы можете ускорить время поиска, распределяя данные почтового индекса в субрегионы (например, квадранты, например, северо-запад, юго-восток и т. Д.) И сохраняя идентификатор региона для каждой точки данных. Затем в поиске вы сначала определяете, в каком регионе находится ваше текущее местоположение, и сравниваете только эти точки данных.

Чтобы избежать граничных ошибок (например, когда ваше текущее местоположение находится вблизи края его региона, но на самом деле находится ближе всего к молнии в соседнем регионе), ваши регионы должны в некоторой степени перекрываться. Это означает, что некоторые из ваших zip-записей будут продублированы, поэтому ваш общий набор данных будет немного больше.

Answer 3

Используйте kd-tree для ускорения поиска ближайшего соседа. Там должно быть много бесплатных реализаций, доступных для вашей платформы.

Answer 4

вы должны проверить geonames . у них есть API, который возвращает XML и / или JSON. Также вы можете использовать их базу данных.

Answer 5

Это не с открытым исходным кодом, но, возможно, вы могли бы использовать API Карт Google:

Обратное геокодирование

Answer 6

Как далеко от вашего исходного местоположения вы ожидаете ближайший город? 50 миль? 200 миль? 500 миль? Если два города почти равноудалены, имеет ли значение, если ваш алгоритм выбирает точно более близкий? Вы можете использовать эту информацию, чтобы ускорить поиск.

Если вы можете разумно предположить, что разница расстояний мала (~ 250 миль или около того, вероятно, достаточно близко, чтобы считаться «маленькой»), и ваш расчет расстояния может быть немного «нечетким», тогда вы можете оптимизировать проверка грубой силы путем ограничения вашего пространства поиска до +/- 5 лат от источника (~ 70 миль за лат, так что это дает вам около 350 миль к северу и югу) и +/- 5 длин (при условии, что вы не не ищите города на полюсах, это где-то от ~ 350 миль на экваторе до ~ 100 миль в северной Канаде). Отрегулируйте эти диапазоны в соответствии с тем, что вы считаете подходящим для вашей проблемной области.

Хотя функции триггера помогут вам точно определить расстояние, для меньших расстояний, таких как эти пифагорейские, обычно достаточно близко для ответа «наилучшего предположения», с x = 69,1 * (sourcelat - citylat) и y = 53.0 * (источник - сити).

Answer 7

Посмотрите в базе данных geonames.org исходные данные.

Для легкой базы данных sqlite - хороший выбор.

geonames также выполняет веб-сервис, но если вы хотите сделать это самостоятельно без веб-вызова (и звучит так, как если бы вы это делали), вам понадобится локальная база данных. Затем вам нужно просто выполнить правильные расчеты триггера, чтобы вычислить расстояние большого круга (google that) между парой точек широты и долготы, а затем упорядочить результаты по расстоянию. Вы также можете использовать ограничивающий прямоугольник или радиус, если вы хотите ограничить радиус поиска перед выполнением расчетов.

Если ваша локальная база данных может быть основана на SQL (то есть sqllite3), то все это сводится к SQL-запросу, который добавляет кучу триггерных вычислений для вычисления столбца «distance» и, возможно, также аналогичное предложение «where» поиск в радиусе или ограничительной рамке. Рассчитав столбец расстояний в вашем запросе, можно легко заказать расстояние и добавить любые другие критерии, которые вам нравятся. Если вы знаете ruby ​​/ rails и хотите увидеть хороший пример того, как это делается, посмотрите на исходный код плагина GeoKit rails.

Answer 8

Yahoo! Placemaker - это бесплатный веб-сервис, который может сделать это. Он может искать географические названия («Нью-Йорк», «Букингемский дворец»), но он также может искать широты и долготы с помощью микроформата Geo .

Для использования сервиса вы отправляете запрос POST, и он возвращает XML:

Небольшой пример командной строки (я скрыл свой идентификатор приложения Yahoo!; вам нужно зарегистрировать свой собственный):

$ curl -X POST -ddocumentContent='<div class="geo">GEO: <span class="latitude">37.386013</span>, <span class="longitude">-122.082932</span></div>' -ddocumentType='text/html' -dappid='your_yahoo_app_id' http://wherein.yahooapis.com/v1/document

Возвращает очень подробный XML-документ, часть которого:

<type>Town</type>
<name><![CDATA[Los Altos, CA, US]]></name>

Он также содержит следующие данные:

<type>Zip</type>
<name><![CDATA[94024, Los Altos, CA, US]]></name>

Я не очень часто использовал Placemaker, но я использовал их API геокодирования , и это очень быстро. Соедините это с локальным memcached, и пользователи не будут знать, что данные не локальны.

Answer 9

Если у вас есть как long, так и lat для zip и текущего местоположения, вы можете просто рассчитать радиус и найти точки внутри этого круга. Если вы установите предполагаемую границу каждого диапазона почтового индекса, вы можете ускорить поиск.

Если вы можете использовать SQL 2008 (стандартный или экспресс), вы можете использовать Пространственные данные типы.

Answer 10

Другой поток рекомендует mod_geoip через MaxMind. Он работает на уровне Apache, даже не доходя до PHP / .NET / Java. Maxmind apis: Apache против PHP