Webstack
Bejelentkezés

Elfelejtetted a jelszavad?

Nem vagy még tag? Kattints ide és regisztrálj most!

Távolság szerinti keresés és rendezés MySQL segítségével

mySQL | tomizej  | 2012-10-15 11:22:14

Vannak weboldalak, ahol manapság már nagyon fontos lehet egy olyan funkció, amivel a felhasználó a saját pozíciójához viszonyítva tudja szűrni az információkat. Egy ilyen rendszer lehet pl. egy utazási iroda honlapja, ahol lehetőség van a szálláshelyhez közeli éttermek kereséséhez.
Ma már a weben A GPS-ek és az okos-telefonok elterjedésével némely web alkalmazásban is hangsúlyt kell fektetni a helység szerinti szűrésre, növelve ezzel a felhasználó élményt, valamint a relevanciát.

Felhasználási területek

A leggyakrabb esetek, ahol szükség lehet a helység alapú keresésre:

  • Közösségi oldalak: Ismerősök keresése a közelben
  • Térkép alapú alkalmazások: Hasznos helyek a közelben (POI)
  • Szabadidő: Programok a lakhelyed, vagy tartózkodási helyed közelében

A helység alapú web alkalmazások fejlesztése során alapvető probléma, hogy az adatbázisunkból úgy kell kinyernünk az információkat, hogy az az aktuális, vagy meghatározott pozícióhoz van viszonyítva. Ilyen például, ha szeretnénk megjeleníteni a felhasználóknak az ő pozíciójukhoz közeli éttermeket, szálláshelyeket.

Távolságok meghatározása koordináták segítségével

Adott egy probléma: Keressük a pozíciónkhoz közeli éttermeket 50km-es körzetben és távolság szerint rendezzük növekvő sorrendbe (távolodó sorrend).

Első körben szükségünk van az éttermek táblára. Minden étteremnek fontos, hogy meglegyenek a GPS koordinátái (szélességi kör, hosszúsági kör). Ha nincsenek pontos adataink a koordinátákról, bizonyos limitált keretek közt lekérdezhetjük ezeket a Google Geocoding API segítségével is ingyenesen.

Étterem
---------
id | name		| lat		| lng
1  | Laci pizzéria	| 21.1101010	| 19.12121211
2  | Mc Donalds    	| 19.1010101	| 31.12121212

Fontos, hogy ezeket már felvitelkor tároljuk el, mivel később trükkösebb megoldás kell, ha szeretnénk egyszerre több ezer rekord koordinátáit lekérdezni.

Google Geocoding API

A Google Geocoding API egy nagyon okos rendszer, aminek segítségével egy egyszerű HTTP kéréssel Földrajzi információkat nyerhetünk ki a megadott címről. Pl.: "3300 Eger Leányka út 12." kérésre megkaphatjuk a számunkra szükséges szélességi és hosszúsági kört. Intelligens feldolgozójának hibatűrése igen nagy, tehát irányítószám és akár betűhibák esetén is képes visszaadni a kellő információt. Gyakorlatilag ugyanaz történik, mikor a google maps keresőjébe írunk címeket.


A következő URL-re kell küldeni a HTTP kérést:

http://maps.googleapis.com/maps/api/geocode/output?parameters

Kötelező URL paraméterek:

  • address: Cím
  • sensor: Beállítható, hogy a kérelem, olyan eszközről jött-e amin van GPS szenzor.

Egy példa, hogyan tudunk XML formában információkat kinyerni:

http://maps.googleapis.com/maps/api/geocode/xml?address=3300+Eger+Liget+utca+3&sensor=true

Ha ezt az URL-t egy böngészőbe bemásoljuk, láthatjuk az XML kimenetet. Tehát egy PHP feldolgozóval Az XML válaszból kinyerhetjük a számunkra fontos információkat. (result->geometry->location-> lat, lng)

Ha utólag nincsenek tárolt koordináta adatok a lekéréséhez és sok rekordunk van, akkor kell egy feldolgozó folyamat. Egy egyszerű curl kéréssel ciklusban nem sokra megyünk, mivel limitálva vannak az egyszeri kérelmek száma. A GeoCoding API-val és a feldolgozással részletesebben egy másik cikkben foglalkozunk.

Távolság meghatározása 2 pont között (gömb felületen)

Hogy meghatározzuk a földön 2 koordináta közti távolságot, meg kell értenünk, mit is jelentek a szélesség és hosszúsági koordináták (latidue, longitude).

földrajzi koordináták

A földrajzi koordináták reprezentálnak egy földrajzi pozíciót.
A térképeken ezek vetülete látható a síkban, de a valóságban a megadott koordináták az ellipszoid felületén jelölnek pontokat.

Földrajzi hosszúság:
(λ): egy pont meridián síkjának a kezdő meridián síkjával bezárt, (megállapodás szerint keleti irányban pozitív, nyugati irányban negatív) szöge. A pont meridián síkja az a sík, ami tartalmazza a két pólust és a pontot.
A hosszúsági kör vagy délkör, vagy földrajzi meridián az ideális gömbnek tekintett Föld felszínén a két földrajzi póluson áthaladó tetszőleges főkör egyik vagy másik, pólustól pólusig tartó félköre.
A keleti és nyugati hosszúsági félkörökből összesen: 360 db van. Az Egyenlítőn az egymástól 1°-ra lévő hosszúsági körök közötti távolság 111km. Ez a 45°-nál 78,848 km-re csökken, a sarkokon pedig nulla.

Földrajzi szélesség:
(φ): A P pont szélességét úgy kapjuk, hogy összekötjük a Föld középpontjával, és az így kapott egyenes és az Egyenlítő síkja által bezárt szög adja a szélességet. Megállapodás alapján északi irányba pozitív, déli irányba negatív az érték előjele. A szélességi körök távolsága azonos (kb. 111 km). Az északi és déli szélességi körökből 90-90 db van, az Egyenlítővel együtt összesen: 181db.

Távolság kiszámolása

2 pont közti távolságot egy gömb felületen a Haversine formulával tudunk kiszámolni.

harvesine formula

d = 2 pont közti távolság
R = A gömb sugara. Föld esetében: 6371 km.
lat1, lng2 = Az első pont koordinátái
lat2, lng2 = A második pont koordinátái

MySQL Implementáció

Távolság 2 koordináta közt:

6371 * acos( cos( radians( start.lat ) ) * 
		cos( radians( lat ) ) * 
		cos( radians( lng ) - radians( start.lng) ) 
		+ 
		sin( radians( start.lat) ) * 
		sin( radians( lat ) ) 
           )

Keressük a pozíciónkhoz közeli éttermeket 50km-es körzetben és távolság szerint rendezzük csökkenőben (távolodó sorrend):

SELECT * , 
	( 6371 * acos( cos( radians( start.lat ) ) * 
		cos( radians( lat ) ) * 
		cos( radians( lng ) - radians( start.lon ) ) 
		+ 
		sin( radians( start.lat ) ) * 
		sin( radians( lat ) ) 
                ) 
         ) AS dist
FROM etterem dest
HAVING dist <80
ORDER BY dist

start.lat helyére behelyettesítendő a kezdő pozíció szélességi koordinátája!
start.lng helyére behelyettesítendő a kezdő pozíció hosszúsági koordinátája!

eredmény

Sok tízezer rekord esetében ez a módszer lassú lehet. A fenti queryvel az a probléma, hogy a tábla összes rekordján végigmegy, és kiszámolja a távolságot, majd az egész eredményhalmazon rendez. 100ezer rekord felett már másodpercekig is futhat egyetlen lekérdezés, ami már egy nagyobb látogatottságú sitenál komoly problémát jelent. Itt megjegyezném, hogy 10-20, vagy pár száz rekordnál nem igazán van jelentősége az optimalizálásnak, futási időben csak ezred másodpercek töredékeivel lehetnek eltérések.

Optimalizálás

Ha eddig még nem tettük volna meg először indexeljük a lat és az lng mezőt! Erre a 2 mezőre fogunk WHERE feltételt írni, indexelés nélkül megsokszoroznánk a futási időt.

A teszt tábla amin a lekérdezéseket végeztük egy 2 503 471 rekordos tábla, benne Afrika, USA, Kína összes települése koordinátákkal.

explain1


Az előző esetben az egész tábla tartalmát végigvizsgáltuk. Azonban ha ismét felvetjük a problémát, hogy nekünk mire is van szükségünk:
"Keressük a pozíciónkhoz közeli éttermeket 50km-es körzetben..."
Tehát bennünket csak azok az éttermek érdekelnek, amik 50kmes körzetben jelen vannak. Le kell szűkítenünk a vizsgálandó eredményhalmazt, hogy csak az 50kmes körzeten belüli éttermek legyenek benne. Ehhez meghatározunk egy négyzetet, melynek középpontja a kiindulási pontunk. A keresendő halmazunk gyakorlatilag ezen négyzetnek a beírható köre.

távolság szerinti keresés

Kiszámoljuk a négyzet 4 csúcsának koordinátáját.

1˚ szélességi kör a földön ~= 111.04 Km
1˚ hosszásgi kör a földön ~= cos(latitude) * 111.04 Km

lng1 = start.long – dist / ABS(COS(RADIANS(start.lat)) * 111.04)
lng2 = start.long + dist / ABS(COS(RADIANS(start.lat)) * 111.04)

lat1 = start.lat – dist / (111.04)
lat2 = start.lat + dist / (111.04)

A négyzet koordinátákat kiszámolhatjuk PHP-vel is, és úgy helyettesítjük be a Querybe, vagy MySql Session változót is használhatunk.

SET @lng1 = .....;
SET @lng2 = .....;

Majd a queryben ezekre a változókra hivatkozunk.

A lekérdezést az alábbi módon egészíthetjük ki:

SELECT * , 
	( 6371 * acos( cos( radians( start.lat ) ) * 
		cos( radians( lat ) ) * 
		cos( radians( lng ) - radians( start.lng ) ) 
		+ 
		sin( radians( start.lat ) ) * 
		sin( radians( lat ) ) 
                ) 
         ) AS dist
FROM etterem dest
HAVING dist <80
ORDER BY dist

WHERE dest.lng between lng1 and lng2 and dest.lat between lat1 and lat2

explain2

Látható, hogy jóval kevesebb rekordon hajtódott végre a távolság meghatározás. A 2 503 471 rekord helyett csak 504 darabon kellett művelete végezni.

futási idő

A sebesség is magáért beszél. Egy több mint 2 millió rekordos táblán végrehajtottuk a műveletet 1 tizedmásodperc alatt.

Tárolt eljárás

Az egyik leghasználhatóbb és leggyorsabb megoldása a problémára, ha írunk egy tárolt eljárást, ami kiszámolja a határoló keret (négyzet) koordinátáit, majd a távolságokat is, a kezdő pozíciótól viszonyítva.

DELIMITER $$
CREATE PROCEDURE geodistance (IN mylng double, IN mylat DOUBLE, IN dist int)
BEGIN

	declare lng1 float; 
	declare lng2 float;
	declare lat1 float; 
	declare lat2 float;

	-- Kiszámoljuk a határoló négyzet koordinátáit:
	set lng1 = mylng-dist/abs(cos(radians(mylat)) * 111.04);
	set lng2 = mylng+dist/abs(cos(radians(mylat)) * 111.04);
	set lat1 = mylng-(dist/111.04); 
	set lat2 = mylng+(dist/111.04);
	SELECT * , 
		( 6371 * acos( cos( radians( mylat ) ) * 
			cos( radians( lat ) ) * 
			cos( radians( lng ) - radians( mylng ) ) 
			+ 
			sin( radians( mylat ) ) * 
			sin( radians( lat ) ) 
					) 
			 ) AS distance
	FROM etterem dest

	WHERE dest.lng between lng1 and lng2 and dest.lat between lat1 and lat2
	HAVING distance < dist
	ORDER BY distance;
END $$
DELIMITER ;

A közeli éttermeket így egyetlen hívással lekérdezhetjük, távolodó sorrendbe rendezve.

CALL geodistance(42.121212, 12.12121212, 50);

 

Szerző: tomizej

címkék
Címkék: tutorial, mySQL, php,

Hozzászólások

badboy
2013-07-19 06:50:28

Nálam valamiért nem működik ez az eljárás.Csak lefut de nem produkál eredményt.

badboy
2013-07-20 12:26:32

Kicsit átbogarásztam a kódot és javítottam.Íme egy működő megoldás:

<?php


$lng1 = round($ay-20/abs(cos(deg2rad($ax)) * 111.198),4);
$lng2 = round($ay+20/abs(cos(deg2rad($ax)) * 111.198),4);
$lat1 = round($ax-(20/111.198),4);
$lat2 = round($ax+(20/111.198),4);

 

//az sql lekérés pedig a következő

$sql2="SELECT nev,lat,lng FROM koordinatak WHERE (20 >(sqrt((".$ax."-lat)*(".$ax."-lat)+(".$ay."-lng)*(".$ay."-lng))*111.198)) AND lat between $lat1 AND $lat2 AND lng between $lng1 AND $lng2";

?>

Futási ideje a magyar GPS adatbázison : Processing time: 0.00683594 seconds

Magyar GPS Adatbázis->http://data.hu/get/6753441/koordinatak_1.sql

tomizej
2013-09-23 04:51:03

Le kellene pedig futnia. A kódot egyenesen a mySQL Workbenche konzolból másoltam ki :) Futtatás után. Nézd meg kérlek, hogy nem írtad e el a táblanevet. Próbáld ki, hogy maga a SELECt lefut-e egyáltalán a tábládra.

badboy
2014-05-15 12:04:22

két paramétert meg kellett cserélni aszthiszem a between feltételben hogy működjön de már régen próbáltam de bitztos én írtam vagyis cseréltem fel valamit.

Hunsziszi
2017-09-06 01:42:33

Tök jó hogy megtaláltam a cikket, pont erre volt szükség. Kellet némi idő mire megtaláltam a hibát a tárolt elrjárásban, de leírom ha már megvan :)

set lat1 = mylng-(dist/111.04);
set lat2 = mylng+(dist/111.04);

HELYETT

set lat1 = mylat-(dist/111.04);
set lat2 = mylat+(dist/111.04);

Így már működni fog.

 

 

 

 

Hozzászóláshoz be kell jelentkezni!

Keress minket Facebookon
Ajánlások