Jak mogę przeprowadzić efektywne wyszukiwanie zakresu + liczenie z danymi szerokości / długości geograficznej? - algorytm, struktury danych, geoprzestrzenna, szerokość geograficzna, geografia

Pracuję z dużą liczbą punktówreprezentowane przez pary długości / szerokości geograficznej (punkty niekoniecznie są unikalne, w zestawie może być kilka punktów, które znajdują się w tym samym miejscu). Punkty są przechowywane w bazie danych.

To, co muszę zrobić, to znaleźć sposóbwydajnie wykonuj wyszukiwanie, aby uzyskać liczbę punktów leżących w promieniu (np. 25 mil) dowolnego punktu. Liczba nie musi być w 100% dokładna - co ważniejsze, musi być szybka i rozsądnie zbliżona do prawidłowej liczby. Można to zrobić za pomocą SQL, używając zapytania z pewną trygonometrią w klauzuli WHERE do filtrowania punktów według ich odległości od punktu odniesienia. Niestety, to zapytanie jest bardzo, bardzo kosztowne i buforowanie prawdopodobnie nie zapewni dużej pomocy, ponieważ lokalizacje będą bardzo rozległe.

W końcu zamierzam zbudować coś w rodzajuw strukturze pamięci, która będzie w stanie wydajnie obsłużyć tego rodzaju operację - odsprzedając trochę dokładności i żywotności danych (może odbudowując je tylko raz dziennie) w zamian za szybkość. Robiłem pewne badania na drzewach kd, ale nie wiem jeszcze, jak dobrze można to zastosować do danych szerokości / długości geograficznej (w przeciwieństwie do danych x, y w płaszczyźnie 2d).

Jeśli ktoś ma jakieś pomysły lub rozwiązania, które powinienem rozważyć, naprawdę to doceniam - więc z góry dzięki.

Odpowiedzi:

9 dla odpowiedzi № 1

Nie sądzę, że powinieneś używać tego rozwiązania. Losowo myśląc o tym kilka dni temu, myślę, że mierząc odległość od określonego punktu, kwadraty siatki "lokalizacje będą oparte na okręgach, a nie na umundurowanej siatce. Im dalej od 0,0, tym mniej dokładne będzie to być!

To, co zrobiłem, to mieć 2 dodatkowe wartości na mojej klasie PostalCode. Ilekroć aktualizuję Long / Lat na PostalCode, obliczam odległość X, Y od Long 0, Lat 0.

public static class MathExtender
{
public static double GetDistanceBetweenPoints(double sourceLatitude, double sourceLongitude, double destLatitude, double destLongitude)
{
double theta = sourceLongitude - destLongitude;
double distance =
Math.Sin(DegToRad(sourceLatitude))
* Math.Sin(DegToRad(destLatitude))
+ Math.Cos(DegToRad(sourceLatitude))
* Math.Cos(DegToRad(destLatitude))
* Math.Cos(DegToRad(theta));
distance = Math.Acos(distance);
distance = RadToDeg(distance);
distance = distance * 60 * 1.1515;
return (distance);
}


public static double DegToRad(double degrees)
{
return (degrees * Math.PI / 180.0);
}

public static double RadToDeg(double radians)
{
return (radians / Math.PI * 180.0);
}
}

Następnie aktualizuję moją klasę tak:

private void CalculateGridReference()
{
GridReferenceX = MathExtender.GetDistanceBetweenPoints(0, 0, 0, Longitude);
GridReferenceY = MathExtender.GetDistanceBetweenPoints(0, 0, Latitude, 0);
}

Więc teraz mam odległość siatki x, y (w milach)od siatki odniesienia 0,0 dla każdego wiersza w moim DB. Jeśli chcę znaleźć wszystkie miejsca z 5 milami długości / lat, najpierw otrzymam odniesienie do siatki X, Y (powiedzmy 25,75), a następnie przeszukuję 20..30, 70..80 w bazie danych i dalej filtruj wyniki w pamięci za pomocą

MathExtensder.GetDistanceBetweenPoints(candidate.Lat, candidate.Long, search.Lat, search.Long) < TheRadiusOfInterest

Część DB jest ultraszybka, a część w pamięci działa na mniejszym zestawie, aby była bardzo dokładna.

---

4 dla odpowiedzi nr 2

Posługiwać się R-Trees.

W Oracle, używając Oracle Spatial, możesz utworzyć indeks:

CREATE INDEX ix_spatial ON spatial_table (locations) INDEXTYPE IS MDSYS.SPATIAL_INDEX;

to stworzy R-Tree dla ciebie i przeszukaj go.

Możesz użyć dowolnego Earth Model lubisz: WGS84, PZ-90 itp.

---

3 dla odpowiedzi nr 3

Użyj drzewa wyszukiwania dla danych przestrzennych, np. za drzewo quadowe. Więcej takich struktur danych jest wymienionych w "Zobacz także".

---

2 dla odpowiedzi № 4

Możesz znaleźć doskonałe wyjaśnienie sugestii Bombe w artykule Jana Philipa Matuscheka "Znajdowanie punktów w odległości od szerokości / długości geograficznej przy użyciu ograniczania współrzędnych".

---

1 dla odpowiedzi nr 5

Czy mógłbyś podać próbkę swojego kosztownego zapytania?

Jeśli wykonujesz odpowiednie obliczenia wielkogabarytowew oparciu o wzięcie sine () i cosinus () punktu odniesienia i innych punktów danych, można by dokonać bardzo dużej optymalizacji poprzez faktyczne przechowywanie tych wartości sin / cos w bazie danych oprócz wartości lat / long.

Alternatywnie, po prostu użyj swojej bazy danych, aby wyodrębnić prostokąt o długościach pasma / długości, które pasują, a dopiero potem odfiltruj te, które znajdują się poza prawdziwym promieniem koła.

Ale należy pamiętać, że jeden stopień długości geograficznejjest nieco krótszą odległością na dużych szerokościach geograficznych niż na równiku. Jednak powinno być łatwo znaleźć odpowiedni współczynnik proporcji dla tego prostokąta. Miałbyś również błędy, gdybyś potrzebował rozważyć obszary bardzo blisko biegunów, ponieważ dobór prostokątny nie poradziłby sobie z okręgiem pokrywającym się z biegunem.

---

1 dla odpowiedzi № 6

Ten UDF (SQL Server) dostanie odległość między dwoma punktami lat / lon:

CREATE FUNCTION [dbo].[zipDistance] (
@Lat1 decimal(11, 6),
@Lon1 decimal(11, 6),
@Lat2 decimal(11, 6),
@Lon2 decimal(11, 6)
)
RETURNS
decimal(11, 6) AS
BEGIN

IF @Lat1 = @Lat2 AND @Lon1 = @Lon2
RETURN 0 /* same lat/long points, 0 distance = */

DECLARE @x decimal(18,13)
SET @x = 0.0

/* degrees -> radians */
SET @Lat1 = @Lat1 * PI() / 180
SET @Lon1 = @Lon1 * PI() / 180
SET @Lat2 = @Lat2 * PI() / 180
SET @Lon2 = @Lon2 * PI() / 180

/* accurate to +/- 30 feet */
SET @x = Sin(@Lat1) * Sin(@Lat2) + Cos(@Lat1) * Cos(@Lat2) * Cos(@Lon2 - @Lon1)
IF 1 = @x
RETURN 0

DECLARE @EarthRad decimal(5,1)
SET @EarthRad = 3963.1

RETURN @EarthRadius * (-1 * ATAN(@x / SQRT(1 - @x * @x)) + PI() / 2)

END

Oczywiście możesz użyć tego w oddzielnym zapytaniu, na przykład:

SELECT * FROM table WHERE [dbo].[zipDistance] < 25.0

---