Jak efektywnie wyszukiwać wszystkie punkty orientacyjne w zasięgu określonego punktu orientacyjnego?

14

Próbuję rozpocząć od projektu wyszukiwania geograficznego, który znajdzie wszystkie punkty orientacyjne w odległości 10 km / mil (nieistotne dla tej historii) określonego punktu orientacyjnego.

Załóżmy na przykład, że mam bazę danych zawierającą 1 000 000 punktów orientacyjnych. Aby znaleźć wszystkie punkty orientacyjne w odległości 10 mil od punktu orientacyjnego o określonych współrzędnych, musiałbym obliczyć odległość między punktem orientacyjnym z mojego wyszukiwania a 1 000 000 punktów orientacyjnych.

Czy jest na to lepszy sposób?

Alternatywą, o której myślałem, jest kategoryzowanie punktów orientacyjnych, takich jak kraj, region, miasto, dzielnica, biznes, historia itp. W taki sposób, aby biznes mógł być częścią dzielnicy lub miasta. Miasto jest częścią regionu, kraju itp. Może to zawęzić listę obliczeń, ale nadal wygląda na to, że wiele pracy trzeba zrobić, aby wyszukiwanie było szybkie i dokładne.

Czy interfejs API Map Google może pomóc?

Dario Granich
źródło
5
Prawdopodobnie możesz wyeliminować wiele z nich po prostu wykonując szybkie obliczenie odległości na Manhattanie, a następnie wykonując drugi filtr, aby wykluczyć punkty orientacyjne, które są w promieniu 10 km kwadratowych, ale znajdują się poza promieniem 10 km.
Neil,
3
Jakiej technologii baz danych używasz? Odpowiedź nie jest niezależna od bazy danych.
jpmc26,
1
@ Nee W drugim przejeździe możesz uwzględnić dowolny punkt orientacyjny, w którym x i y przypadają na 7 km od początku bez obliczania rzeczywistej odległości.
JimmyJames,

Odpowiedzi:

10

Od SQL Server 2008 istnieje typ danych geograficznych, który przechowuje lokalizacje (pary lat / lon) i ułatwia pisanie zapytań związanych z lokalizacją.

Istnieje istniejąca odpowiedź StackOverflow, która omawia to dogłębnie.

Podstawowe zapytanie, aby znaleźć najbliższe 7 pozycji :

USE AdventureWorks2012  
GO  
DECLARE @g geography = 'POINT(-121.626 47.8315)';  
SELECT TOP(7) SpatialLocation.ToString(), City FROM Person.Address  
WHERE SpatialLocation.STDistance(@g) IS NOT NULL  
ORDER BY SpatialLocation.STDistance(@g);  

Podstawowe zapytanie pozwalające znaleźć wszystko w odległości 100 m (druga odpowiedź na pytanie)

-- Get the center point
DECLARE @g geography
SELECT @g = geo FROM yourTable WHERE PointId = something

-- Get the results, radius 100m
SELECT * FROM yourTable WHERE @g.STDistance(geo) <= 100
Flater
źródło
11
@KonradRudolph: Tak jest w przypadku każdej kolumny SQL, która jest używana do tworzenia zapytań w tabeli z ogromną liczbą wierszy. Masz rację, ale ten komentarz będzie miał zastosowanie do praktycznie każdego zapytania SQL, które zostanie opublikowane jako odpowiedź.
Flater
2
Gdzie przeczytałeś „MS SQL Server” w pytaniu?
Doc Brown,
3
@Później zgadzam się, że normalnie byłoby to oczywiste i zbędne, ale sformułowania OP wydają się sugerować, że nie są świadomi takich mechanizmów.
Konrad Rudolph
2
@ jpmc26: Jesteś zbulwersowany, że wymieniłem prawidłową opcję i nie zawierałem innej opcji? Co? Jeśli uważasz, że warto dodać PostGIS, dodaj odpowiedź samodzielnie (co zrobiłeś) i nie uciekaj się do krytykowania innych za to, że nie masz takiego samego pomysłu jak ty.
Flater,
3
Twoja odpowiedź wydaje mi się w zasadzie tylko wielkością sprzedaży MS SQL. Wasze komentarze sugerują, że zmieniają bazy danych na coś, co kosztowałoby 10 tysięcy dolarów bez faktycznego pytania o to, jaka jest ich sytuacja. Nie opisuje nawet, w jaki sposób OP może faktycznie zaimplementować swoje zapytanie, ani dyskutować o tym, że wykonanie tego i zapewnienie indeksu przestrzennego nie jest tak proste w MS SQL jak w innych DB. Nie omawia też żadnych podstawowych pojęć. To zła odpowiedź, niezależnie od tego, czy jest „ważna”. Dlatego mi to przeszkadza.
jpmc26,
29

Użyj bazy danych z obsługą zapytań GIS (systemy informacji geograficznej) . Większość baz danych obsługuje to wprost lub ma rozszerzenia, ale szczegóły będą specyficzne dla bazy danych (w ich odpowiedzi Flater pokazuje składnię dla serwera SQL).

Jeśli potrzebujesz zaimplementować takie zapytania w swojej aplikacji, możesz zaimplementować strukturę danych, która umożliwia zapytania przestrzenne, np . Drzewo kd . To jest jak drzewo wyszukiwania binarnego, z tym wyjątkiem, że każdy poziom drzewa dzieli się na inny wymiar współrzędnych. Pozwala to ograniczyć wyszukiwanie do mniejszego zestawu możliwych kandydatów. Skutecznie przekładasz swoje wyszukiwanie „promień 10 km” na granice dla każdego wymiaru współrzędnych i zacieśniasz granice, gdy wracasz do drzewa.

amon
źródło
5
Istnieje również
wymiana stosu
8
PostGIS to najlepsza darmowa opcja. Obsługuje znacznie, znacznie więcej niż bardzo podstawowe typy i funkcje GIS programu SQL Server. Ale to podstawowa funkcjonalność.
jpmc26,
@amon Uważam komentarz jpmc26 za dobry dodatek i nie tyle krytykujący twój przykład. „Jeśli chcesz zacząć od zera, nie musisz płacić za licencjonowaną bazę danych - ten darmowy program typu open source również dobrze sobie z tym poradzi”.
mgarciaisaia
11

Tak, jest lepszy sposób. Musisz użyć indeksu przestrzennego . Indeksy te organizują metadane dotyczące geometrii, aby bardzo szybko odfiltrować odległe geometrie, oszczędzając wiele cykli procesora, unikając opisywanych obliczeń. Nie powinieneś zawracać sobie głowy ich implementacją, ponieważ wszystkie główne relacyjne bazy danych zapewniają typ geometrii przestrzennej i odpowiednie indeksy.

To, co chcesz sprawdzić, to zapytania „w odległości” (zapytania dotyczące geometrii w pewnej odległości od innej geometrii). Są to bardzo standardowe i bardzo rozwiązane problemy i są możliwe we wszystkich powyższych bazach danych (i są wbudowane w kilka):

  • PostGIS: ST_DWithin
  • SQL Server: STDistance(Nie jest jasne, że użycie indeksu w wersji geograficznej 3D tej funkcji jest obsługiwane)
  • Oracle: SDO_WITHIN_DISTANCE(To nie mówi wprost, że spowoduje użycie indeksu. Chciałbym dokładnie sprawdzić plan zapytań. Może być konieczne zastosowanie an, SDO_FILTERaby uzyskać indeks).
  • MySQL: Wciąż to rozgryzam.

Obejście dotyczące wyzwalania użycia indeksu

W najgorszym przypadku, gdy masz problemy z użyciem przez system indeksu przestrzennego do tych zapytań, możesz dodać dodatkowy filtr. Można by utworzyć obwiednię kwadratowy o bokach długości 2 * (wyszukiwanie na odległość) na środku u punktu wyszukiwanie i porównywanie geometrii tabeli ograniczającej pola przeciwko że przed sprawdzeniem faktycznej odległości. I tak właśnie robi PostGIS ST_DWithinpowyżej.


Odległość w GIS

Podczas gdy indeksy przestrzenne są fantastyczne i absolutnie właściwe rozwiązanie problemu, obliczanie odległości może być logicznie skomplikowane. W szczególności musisz się martwić o to, w jakim rzucie (w zasadzie wszystkie parametry układu współrzędnych) są przechowywane twoje dane. Większość rzutów 2D (inne niż układy współrzędnych kątowych, takie jak różne rzuty szerokości / długości) znacznie zniekształcają długość. Na przykład projekcja Web Mercator (ta używana przez Google, Bing i każdego innego głównego dostawcę map bazowych) rozszerza obszary i odległości w miarę zbliżania się do równika . Mogę się mylić, ponieważ nie jestem formalnie wykształcony w GIS, ale najlepsze, co widziałem dla projekcji 2D, to niektóre z tych, które obiecują prawidłowe odległości odpojedynczy, stały punkt na całym świecie. (Nie, nie jest praktyczne użycie innej projekcji dla każdego zapytania; to uczyniłoby twoje indeksy bezużytecznymi).

Najważniejsze jest to, że musisz upewnić się, że matematyka jest dokładna. Najprostszym sposobem na to z punktu widzenia rozwoju jest użycie rzutów kątowych (często określanych jako „geograficzne”) i funkcji, które wspierają wykonywanie matematyki przy użyciu modelu sferoidalnego, ale te obliczenia są nieco droższe niż odpowiedniki 2D a niektóre bazy danych mogą nie obsługiwać ich indeksowania. Jeśli jednak możesz uzyskać akceptowalną wydajność przy ich użyciu, prawdopodobnie jest to właściwy sposób. Inną powszechną opcją są prognozy regionalne (takie jak strefy UTM), które zbliżają zarówno odległości, jak i obszary, bardzo blisko do poprawienia, jeśli dane są ograniczone do określonej części świata. To, co będzie najlepsze dla Twojej aplikacji, będzie zależeć od Twoich konkretnych wymagań,

Dotyczy to nawet jeśli nie korzystasz z wbudowanych indeksów przestrzennych. Twoje dane mają pewną projekcję, niezależnie od tego, jakiej technologii lub techniki obecnie używasz lub używasz w przyszłości, i już teraz wpływa ona na wszelkie zapytania i obliczenia, które wykonujesz.

jpmc26
źródło
3

Zgodziłbym się, że jeśli to możliwe, użycie konkretnego wsparcia w bazie danych byłoby najbardziej rozsądnym sposobem na zrobienie tego.

Gdybym jednak musiał to zrobić w bazie danych bez konkretnego wsparcia, zacznę od zapytania o kwadrat, który otacza kółko, np. (Y> (y1 - rad)) AND (y <(y1 + rad)) AND (x> ( x1 - rad)) ORAZ (x <(x1 + rad)). Zakładając, że twoje punkty mają mniej więcej równe zapytanie o rozkład dla kwadratu, otrzymasz twoje prawdziwe dopasowania plus około 30% dodatkowych fałszywych dopasowań. Następnie możesz wyeliminować fałszywe dopasowania.

Peter Green
źródło
Ale bez odpowiedniego indeksu przestrzennego takie zapytanie skanuje w najgorszym przypadku całą bazę danych, w najlepszym wypadku wszystkie elementy w ramach danej szerokości geograficznej LUB zakresu długości geograficznej, w zależności od indeksu, tj. „Pasma” zamiast kwadratu. Jeśli nie chcesz zabijać wydajności, skorzystaj z bazy danych obsługującej indeksy przestrzenne!
jcaron
@jcaron Uważam, że to zapytanie można zoptymalizować za pomocą zwykłego indeksu B-drzewa na xi y. (Być może połączone, może osobne.
Wyprofilowałbym
@ jpmc26 Nie, nie może. Przemyśl to, zobaczysz.
jcaron
@jcaron Być może byłoby lepiej, gdybyś nie był tajemniczy w czymś, co najwyraźniej nie jest proste. B-drzewa mogą być używane do BETWEENzapytań. Nie rozumiem, dlaczego w najgorszym przypadku nie można mieć 2 indeksów, a następnie filtrowane wyniki z każdego indeksu łączą się. (Jest to coś, co RDBMS robią wewnętrznie, gdy uznają, że warto używać wielu indeksów.) Jeśli indeks łączony działa, powinien całkowicie odfiltrować jeden wymiar na pierwszym poziomie, a następnie stosunkowo szybko zawęzić na drugim poziomie.
jpmc26,
2
@ jcaron faktycznie możesz użyć indeksu do czegoś takiego, y between -68 and -69 and x between 10 and 11ale oczywiście indeks przestrzenny wykona lepszą robotę do tego zadania
Juan Carlos Oropeza