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

Question

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

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

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

Answer 1

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

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

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

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

Answer 2

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

Reverse Geocoding

Answer 3

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

Answer 4

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

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

Answer 5

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

Чтобы воспользоваться услугой, отправьте запрос на 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 очень, но я использовал их Geocoding API, и это очень быстро. Соедините это с местным memcached, и пользователи понятия не имеют, что данные не являются локальными.

Answer 6

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

Answer 7

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

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

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

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

Answer 8

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

Answer 9

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

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

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

Answer 10

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

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

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

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

• Найди карту, которую вы хотите. Для американских местоположений перепись США предлагает чрезвычайно точные карты по адресу: http://www.census.gov/geo/www/tiger/tgrshp2010/tgrshp2010.html. Я не нашел глобальных карт, которые так же хороши, как карты переписи США, но они могут существовать.
• Найдите или напишите парсер для формата шейп-файла ESRI. У меня нет конкретной ссылки для этого, поскольку он сильно зависит от языка, но в Интернете есть множество парсеров, как бесплатных, так и коммерческих. Просто выполните поиск «парсинга шейп-файлов» вместе с вашим языком программирования.
• Загрузите карту в память. Цифровая карта состоит из списка полигонов, представленных списком пар lat/lon, обычно упорядоченным в направлении против часовой стрелки. Большинство карт разрешают вырезать (например, Лесото в Южной Африке), которые перечислены только как полигоны, где пары lat/lon указаны в направлении по часовой стрелке. По соображениям производительности и потребления памяти вы захотите использовать необработанные массивы с плавающей запятой (избегайте двойной точности, поскольку она отнимает память, и там, где это возможно, используйте встроенные массивы, чтобы избежать бокса).
• Далее вам понадобится код для ответа на вопрос, содержится ли заданная точка запроса в заданном полигоне. Вот отличное обсуждение проблемы «точка-в-полигоне»: How can I determine whether a 2D Point is within a Polygon?
• По моему опыту, метод грубой силы, предложенный в другом ответе (проверяющий каждую сущность), плохо работает на национальных или мировых картах. Вместо этого я настоятельно рекомендую быстрый пространственный индекс, который возвращает список потенциальных полигонов для заданного lat/lon. Здесь есть много вариантов. Многие люди предлагали индексы на основе дерева, но я предпочитаю индексы сетки, так как они быстрее, а современные серверы имеют большую память. Я написал единственный такой индекс, с которым я работал. Я знаю, что они существуют в библиотеках ГИС, но я нахожу, что большинство ГИС-кода чересчур сложны, медленны и трудны в использовании. Поэтому, учитывая запрос lat/lon, вы получаете список полигонов-кандидатов из пространственного индекса и используете функцию «точка-в-полигон», чтобы найти, кто из кандидатов содержит точку запроса.
• Также важно обрабатывать случаи, когда точка запроса не содержится в любом полигоне. В таком случае вы, вероятно, захотите найти ближайший такой полигон до заданного максимального расстояния. Для этого вам нужно убедиться, что ваш пространственный индекс может возвращать список ближайших полигонов, а не только список кандидатов, содержащих полигоны. Вам также понадобится код для вычисления расстояния между точкой запроса и сегментом линии lat/lon (это сложно, потому что lat/lon не является евклидовым пространством). Я не нашел хорошего обсуждения того, как это сделать в Интернете, поэтому я разработал свой собственный метод.Он работает, создавая линеаризованное пространство вокруг точки запроса (которое становится (0, 0) в новом пространстве), в котором относительная долгота повторно масштабируется так, что степень измененной долготы равна тому же расстоянию, что и степень (предполагает умножение относительной долготы на косинус широты). В этом линеаризованном пространстве вы найдете ближайшую точку на сегменте линии, используя стандартные методы (см. Shortest distance between a point and a line segment), а затем преобразуйте эту точку обратно в lat/lon и используйте формулу Хаверсина для вычисления расстояния между двумя точками (см. Calculate distance between two latitude-longitude points? (Haversine formula)).

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