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

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?

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

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.

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.

• PostGIS (rozszerzenie GIS dla PostgreSQL) używa R-Drzew: http://postgis.net/docs/using_postgis_dbmanagement.html#idm2246 (typ GiST)
• SQL Server używa indeksów siatki: https://docs.microsoft.com/en-us/sql/relational-databases/spatial/spatial-indexes-overview?view=sql-server-2017
• Oracle używa R-Trees: https://docs.oracle.com/database/121/SPATL/creating-spatial-index.htm
• MySQL używa R-Trees: https://dev.mysql.com/doc/refman/8.0/en/optimizing-spatial-analysis.html

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.

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.