Niepoważnik programisty

Jakiś czas temu przyszło mi się zmierzyć z zagadnieniem prezentowania obiektów znajdujących się w pewnej odległości od zadanego punktu. Jako dane wejściowe miałem do dyspozycji współrzędne geograficzne, a moim zadaniem było oprogramowanie prostego interface`u opartego o mapę. Pogooglałem, poczytałem, popytałem i doszedłem do pewnego rozwiązania, którym dziś (zachęcony wpisem znalzionym na DZone) chcę się podzielić.

Obliczanie odległości

Ponieważ obliczam odległość nie na płaskiej powierzchni, ale na sferze, zwykłe twierdznie Pitagorasa nie wystarczy ;) Ponieważ wzór na odległość pomiędzy punktami na kuli ziemskiej (polecam zapoznać się z artykułem na Wikipedii oraz stronie Movable Type) nie należy do najkrótszych, postanowiłem ułatwić sobie życie poprzez napisanie funkcji w PGPLSQLu (w projekcie korzystamy z bazy danych PostgreSQL):

CREATE OR REPLACE FUNCTION distance(_lat1 numeric, _lon1 numeric, _lat2 numeric, _lon2 numeric, _unit character)
  RETURNS numeric AS
$BODY$
DECLARE
	dist	decimal;
	miles	decimal;
	unit	character;
BEGIN
	dist	= sin(radians(_lat1)) * sin(radians(_lat2)) + cos(radians(_lat1)) * cos(radians(_lat2)) * cos(radians(_lon1 - _lon2));
	dist	= acos(dist);
	dist	= degrees(dist);
	miles	= dist * 60 * 1.1515;
	unit	= upper(_unit);
 
	IF ( unit = 'K') then
		RETURN miles * 1.609344;
	elsif ( unit = 'N') then
		RETURN miles * 1.8684;
	else
		RETURN miles;
	end IF;
END;
$BODY$
  LANGUAGE 'plpgsql' VOLATILE;
ALTER FUNCTION distance(numeric, numeric, numeric, numeric, character) OWNER TO test_pg;

Funkcja wylicza wynik w różnych jednostkach, w zależności od podanego parametru :) I wszystko byłoby pięknie i cacy, gdyby nie fakt, że w standardowym zapytaniu ($1 i $2 to szerokość i wysokość punktu centralnego):

SELECT * FROM TABLE WHERE distance(lat,lng,$1,$2,'K') < 10

wartość odległości obliczana jest dla każdego wiersza. Przy 100 rekordach nic się nie dzieje, podobnie przy 1000 czy 10000. Jednak przy 100000 czy 1000000 wpisów pojawia się spory problem (je testowałem na bazie zawierającej ponad 1.2 mln rekordów i musiałem ubijać proces :P). Okazuje się jednak, że problem można całkiem prosto rozwiązać! Wystarczy wstępnie zawęzić obszar przeszukiwania!

Wstępne zawężanie obszaru

Załóżmy, że chcemy znaleźć osoby mieszkające w promieniu 10km od centrum Warszawy. Interesuje Nas taki obszar:

Mapa Warszawy z zaznaczonym obszarem znajdującym się 10km od centrum miasta

Rozwiązanie polega na ograniczeniu wybieranych rekordów do tych, które mają wysokość pomiędzy “skrajnymi” wysokościami okręgu oraz szerokość pomiędzy “skrajnymi” szrokościami okręgu, czyli znajdujących się w prostokątnym obszarze jak na rysunku:

Mapa Warszawy z zaznaczonym obszarem wyznaczonym przez skrajne wartości długości i szerokości

Mapa Warszawy z zaznaczonym obszarem wyznaczonym przez “skrajne” wartości długości i szerokościWyznaczenie takiego obszaru to trywialne zadanie:

SELECT count(*) FROM TABLE WHERE (lat BETWEEN $1 AND $2) AND (lng BETWEEN $3 AND $4)

Do zapytania przekazujemy 4 parametry- 2x wysokość oraz 2x szerokość, które będą ograniczały wstępnie wyniki. Otrzymane wyniki musimy jeszcze dodatkowo zawęzić, aby pozbyć się obiektów “na rogach”, co obrazuje poniższy rysunek:

Warszawa z nałożonymi obszarami- zawężonym i docelowym

Zatem wynikowe zapytanie wygląda następująco:

SELECT * FROM TABLE
WHERE (lat BETWEEN $1 AND $2) AND (lng BETWEEN $3 AND $4) AND
distance(lat,lng,($5)::numeric,($6)::numeric,($7)::character)<=$8

Parametrów jest w sumie 8, ale dzięki temu otrzymujemy wydajny sposób na pobranie obiektów oddalonych od podanego punktu o zadaną odległość w wybranej jednostce ;)

Mam nadzieję, że komuś się przyda :)