Najszybszy sposób na znalezienie lokalizacji (zip, miasto, stan) z podaniem szerokości/długości geograficznej

Question

Potrzebuję darmowego rozwiązania (open-source), które z uwagi na lat/lng może zwrócić szafę city/state lub zip. mysql nie jest opcją, mała, lekka baza danych byłaby najlepsza, jeśli to możliwe.

Aktualizacje: brak usług internetowych, z 50 milionami wyświetleń dziennie nawet najmniejszy addon boli, więc dodanie żądania usługi zabije czas odpowiedzi. Wolałbym nie dodawać więcej niż 200 milisekund na żądanie.

Mam bazę danych, lat/lon/zip/city/state w csv, to tylko sposób przechowywania, a co ważniejsze, jak ją odzyskać najszybciej.

Answer 1

Brutalna siła: wstępne załadowanie wszystkich danych do tablicy. Oblicz odległość między twoim bieżącym punktem a każdym punktem w tablicy (istnieje metoda wykonania tego obliczenia, która używa algebry liniowej zamiast funkcji triggera, ale nie pamiętam, co to jest offhand), aby znaleźć najbliższy punkt.

Przeczytaj to przed głosowaniem w dół:: istnieją sposoby na przyspieszenie wyszukiwania w trybie brute force, ale okazało się, że zazwyczaj nie są one warte problemów. Nie tylko wykorzystałem to podejście wcześniej, aby znaleźć najbliższy zip z szerokości/długości geograficznej, użyłem go w aplikacji Windows Mobile (gdzie moc obliczeniowa nie jest dokładnie przytłaczająca) i wciąż osiągnięto podsekundowe czasy wyszukiwania. Tak długo, jak unikasz używania funkcji trygonometrycznych, nie jest to kosztowny proces.

Aktualizacja: można przyspieszyć czas wyszukiwania, przypisując dane zip do podregionów (kwadraty, na przykład północny zachód, południowy-wschód itd.) I zapisując identyfikator regionu dla każdego punktu danych. W wyszukiwaniu najpierw należy określić region, w którym znajduje się bieżąca lokalizacja, i porównać tylko z tymi punktami danych.

Aby uniknąć błędów brzegowych (np. Gdy bieżąca lokalizacja znajduje się blisko krawędzi regionu, ale jest najbardziej zbliżona do zip w sąsiednim regionie), twoje regiony powinny w pewnym stopniu się pokrywać. Oznacza to, że niektóre z twoich rekordów zip zostaną zduplikowane, więc Twój ogólny zbiór danych będzie nieco większy.

Answer 2

Nie jest open-source, ale być może można użyć Google Maps API:

Reverse Geocoding

Answer 3

innym wątku zaleca mod_geoip poprzez MaxMind. Działa na poziomie Apache, zanim dotrze do PHP/.NET/Java. Maxmind geolocation apis: Apache vs PHP

Answer 4

Jeśli masz zarówno długość, jak i szerokość suwaka i aktualną lokalizację, możesz obliczyć promień i znaleźć punkty w tym okręgu. Jeśli przyjmiesz założoną granicę każdego zakresu kodu pocztowego, możesz przyspieszyć wyszukiwanie.

Jeśli możesz użyć SQL 2008 (standardowy lub ekspresowy), możesz użyć typów Spatial data.

Answer 5

Yahoo! Placemaker to bezpłatna usługa internetowa, która może to zrobić. Może wyszukiwać nazwy miejsc ("Nowy Jork", "Pałac Buckingham"), ale może również wyszukiwać szerokości i długości geograficzne za pomocą Geo microformat.

Aby skorzystać z usługi, należy przesłać żądanie POST, i zwraca XML:

Mały przykład wiersza polecenia (mam zasłonięte mój Yahoo!identyfikator aplikacji; musisz zarejestrować własną rękę):

$ 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 

Zwraca bardzo szczegółowy dokument XML, z których część jest:

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

zawiera również następujące dane:

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

Nie używałem zbyt dużo Placemaker, ale użyłem ich Geocoding API i jest bardzo szybki. Połącz to z lokalnym memcached i użytkownicy nie mają pojęcia, że ​​dane nie są lokalne.

Answer 6

powinieneś sprawdzić geonames. mają API, które zwraca XML i/lub JSON. również, możesz dl ich bazy danych.

Answer 7

Zobacz bazę danych geonames.org dla danych źródłowych.

Dla lekkiej bazy danych, sqlite jest dobrym wyborem.

geonames wykonuje również usługę internetową, ale jeśli chcesz zrobić to samemu bez połączenia z internetem (i brzmi tak, jakbyś to robił), będziesz potrzebować lokalnej bazy danych. Następnie wystarczy wykonać odpowiednie wyliczenia trygonometru, aby ustalić odległość między wielkimi okręgami (google that) między parą punktów lat/lng, a następnie uporządkować wyniki według odległości. Możesz także użyć obwiedni lub promienia, jeśli chcesz ograniczyć promień wyszukiwania przed wykonaniem obliczeń.

Jeśli twoja lokalna baza danych może być oparta na języku SQL (która jest sqllite3), to wszystko składa się na zapytanie SQL, które dodaje kilka wyliczeń trygresji, aby obliczyć kolumnę "odległości", a może także podobną klauzulę "gdzie" do ograniczyć wyszukiwanie w promieniu lub ramce ograniczającej. Po obliczeniu kolumny odległości w zapytaniu można łatwo zamówić według odległości i dodać dowolne inne kryteria. Jeśli znasz ruby ​​/ szyny i chcesz zobaczyć ładny przykład tego, jak to zrobić, spójrz na źródło wtyczek szyny GeoKit.

Answer 8

Użyj parametru kd-tree, aby przyspieszyć wyszukiwanie najbliższego sąsiada. Powinno być dostępnych wiele darmowych implementacji niezależnie od platformy.

Answer 9

Jak daleko od miejsca pochodzenia można się spodziewać najbliższe miasto? 50 mil? 200 mil? 500 mil? Jeśli dwa miasta są prawie równe, czy to ma znaczenie, jeśli twój algorytm wybierze dokładnie bliżej? Możesz użyć tych informacji, aby przyspieszyć wyszukiwanie.

Jeśli można racjonalnie założyć, że różnica odległości jest mała (około 250 mi jest prawdopodobnie wystarczająco blisko, aby można było uznać ją za "małą"), a obliczenie odległości może być nieco "rozmyte", wówczas można zoptymalizować Kontrola "brutalnej siły" poprzez ograniczenie przestrzeni poszukiwań do +/- 5 lat od źródła (~ 70 mil za lat, więc daje to 350 lub więcej mil na północ i południe) i +/- 5 długości (przypuszczając, że nie szukają miast na biegunach, to jest gdzieś od ~ 350 mil na równiku do ~ 100 mil w północnej Kanadzie). Dostosuj te zakresy do tego, co uważasz za odpowiednie dla miejsca na problem.

Podczas gdy funkcje trygonometryczne ułatwią dokładne wskazanie odległości, dla mniejszych odległości takich jak te pitagorejczyk jest na ogół wystarczająco blisko, aby uzyskać odpowiedź "najlepiej odgadnąć", przy czym x = 69.1 * (sourcelat - citylat) i y = 53,0 * (sourcelong - citylong).

Answer 10

To bardzo interesujące pytanie ze złożoną odpowiedzią.

Podajesz bazę danych miast z lat/lon, ale miasta nie są pojedynczymi punktami, co może mieć duże znaczenie w gęsto zaludnionych obszarach, gdzie znaczna część miasta A może być bliższa "centrum" miasta B niż do centrum miasta A. Weź duże miasto otoczone mniejszymi przedmieściami. Odległe części wielkiego miasta mogą być bliżej centrów przedmieść niż centrum wielkiego miasta. Przyciąganie do najbliższego centrum miasta oznacza mapę, która jest diagramem Voronoi punktów centrum miasta. Taka mapa nie wyglądałaby jak mapa miast.

Jeśli chcesz poznać miasto i stan dla danego wyrażenia lat/lon, musisz zapytać o poprawną mapę i zrobić punkt w testach wielokątów, aby dowiedzieć się, który to jest. Brzmi to kosztowo, ale jest kosztowne właściwie nieźle, jeśli używasz odpowiedniego indeksu przestrzennego i jesteś ostrożny w swoim kodowaniu. Prowadzę witrynę internetową, która sprzedaje dostęp API do tego i innych zapytań geograficznych, a nasz bazowy silnik (napisany w Javie) może zwrócić zawierające lub najbliższe miasto w USA ze średnim czasem zapytania wynoszącym 3e-4 sekundy (ponad 3 000 zapytań na sekundę).

Mimo, że je sprzedajemy, z przyjemnością wyjaśniam, jak to działa, ponieważ taniej byłoby kupić go od nas, niż zbudować samemu, nawet z instrukcjami. Oto one:

• Znajdź mapę, którą chcesz. W przypadku amerykańskich lokalizacji spis powszechny Stanów Zjednoczonych oferuje wyjątkowo dokładne mapy pod adresem: http://www.census.gov/geo/www/tiger/tgrshp2010/tgrshp2010.html. Nie znalazłem globalnych map, które są tak dobre jak amerykańskie mapy spisów, ale mogą istnieć.
• Znajdź lub zapisz analizator składni dla formatu plików kształtu ESRI. Nie mam do tego konkretnego odnośnika, ponieważ jest on bardzo zależny od języka, ale istnieje wiele parserów, zarówno bezpłatnych, jak i komercyjnych dostępnych w Internecie. Po prostu wyszukaj "shapefile parser" wraz z twoim językiem programowania.
• Załaduj mapę do pamięci. Mapa cyfrowa składa się z listy wielokątów reprezentowanych przez listę par lat/lon, zazwyczaj uporządkowanych w kierunku przeciwnym do ruchu wskazówek zegara. Większość map umożliwia wycinanie (np. Lesotho w RPA), które są wymienione tylko jako wielokąty, w których pary lat/lon są wymienione w kierunku zgodnym z ruchem wskazówek zegara. Ze względu na wydajność i zużycie pamięci, będziesz chciał używać surowych macierzy float (unikaj podwójnej precyzji, ponieważ marnuje to pamięć i używa natywnych macierzy, gdzie to możliwe, aby uniknąć boksowania).
• Następnie będziesz potrzebować kodu, aby odpowiedzieć, czy dany punkt zapytania znajduje się w danym wielokącie. Oto doskonała dyskusja na temat problemu punktu w wielokącie: How can I determine whether a 2D Point is within a Polygon?
• Z mojego doświadczenia wynika, że ​​technika brute force zasugerowana w innej odpowiedzi (sprawdzanie każdej jednostki) nie działa dobrze na mapach krajowych lub światowych. Zamiast tego, zdecydowanie sugeruję szybki indeks przestrzenny, który zwraca listę potencjalnych wielokątów dla danego wyrażenia lat/lon. Tutaj jest wiele opcji. Wiele osób sugerowałoby indeksy oparte na drzewach, ale preferuję indeksy siatki, ponieważ są one szybsze, a nowoczesne serwery mają zwykle dużo pamięci. Napisałem jedyny taki indeks, z którym współpracowałem. Wiem, że istnieją w bibliotekach GIS, ale uważam, że większość kodów GIS jest zbyt skomplikowana, powolna i trudna w użyciu. Tak więc, biorąc pod uwagę zapytanie lat/lon, otrzymujesz listę potencjalnych wielokątów z indeksu przestrzennego i używasz funkcji punkt w wielokącie, aby znaleźć, który z kandydatów zawiera punkt zapytania.
• Ważne jest również, aby obsługiwać przypadki, w których punkt zapytania nie jest zawarty w żadnym wielokącie. W takim przypadku prawdopodobnie będziesz chciał znaleźć najbliższy taki wielokąt do określonej maksymalnej odległości. Aby to zrobić, musisz się upewnić, że indeks przestrzenny może zwrócić listę pobliskich wielokątów, a nie tylko listę kandydatów zawierających wielokąty. Będziesz także potrzebował kodu do obliczenia odległości między punktem zapytania a segmentem linii lon/lon (jest to trudne, ponieważ lat/lon nie jest przestrzenią euklidesową). Nie znalazłem żadnej dobrej dyskusji na temat tego, jak to zrobić w Internecie, więc opracowałem własną metodę.Działa poprzez utworzenie zlinearyzowanej przestrzeni wokół punktu zapytania (która staje się (0, 0) w nowej przestrzeni), w której długość geograficzna jest ponownie skalowana tak, że stopień zmodyfikowanej długości geograficznej jest taki sam, jak stopień szerokości geograficznej (polega na pomnożeniu względnej długości geograficznej przez cosinus szerokości geograficznej). W tej zlinearyzowanej przestrzeni znajdujesz najbliższy punkt na segmencie linii, używając standardowych metod (patrz Shortest distance between a point and a line segment), a następnie przekształć ten punkt z powrotem na lat/lon i użyj formuły Haversine, aby obliczyć odległość między dwoma punktami (patrz Calculate distance between two latitude-longitude points? (Haversine formula)).

I to wszystko. Zbudowałem taki system przez około pół roku. Mój szacunek jest taki, że są w nim co najmniej trzy miesiące poważnego kodowania, i to jest ktoś obeznany z przedmiotami (więc uważaj, jeśli podejmujesz decyzję kupna lub budowy).