[MySQL][SQL][PHP] Znajdowanie najblizszych obiektow wedug wspolrzednych Opcje

[Bojakki]

Mam taka sytuacje. Mam w bazie powiedzmy 4 obiekty, ktore sa punktami na mapie o 2 wspolrzednych (liczone wg rownoleznikow i poludnikow):

id wsp1 wsp2
1 54 18
2 50 19
3 33 44
4 51 25

I teraz chce zrobic tak by znalezc obiekt ktory jest najblizszy obiektowi nr 1, czyli robie operacje:

[PHP] pobierz, plaintext 
 $sz1 = 54;     
   $wy1 = 18;
   $sz2 = 50; 
   $wy2 = 19;
 
   $km = rad2deg(acos(sin(deg2rad($sz1)) * sin(deg2rad($sz2)) +  cos(deg2rad($sz1)) * cos(deg2rad($sz2)) * cos(deg2rad($wy1-$wy2))))  * 111.18957696;
   print 'Ortodroma: '. $km. 'km <br />';
[PHP] pobierz, plaintext 

To dla obiektu nr 2 odleglosc 450km
I teraz mam pytanie. Jak mozna zrobic to w miare wydajnie by operacja sparwdzila 1500 obiektow, ustawila wyniki wedlugug odleglosci i wybrala ten o najmniejszej odleglosci od punktu a. Liczenie nie musi byc z Ortodroma, bo nie potrzebuje sprawdzic jaka dokladnie odlegosc jest, ale to ktory obiekt jest najblizej

[wookieb]

Poczytaj o algorytmie zamiatania płaszczyzny.
Ale wydaje mi się, że w twoim przypadku najlepszym rozwiązaniem byłoby stworzenie tabeli obległości pomiędzy każdym z punktów (albo chociaż z ich częścią). Odpowiednio założyć indexy i masz bardzo szybko wynik.

[Kshyhoo]

Ja stawiam na algorytm Dijkstra. Sprawdź tu.

[Bojakki]

Chlopaki, przemyslalem sprawe i tzreba to zrobic tak, ze:
- wyciagam z bazy tabele z id i wspolrzednymi i dla kazdej z osobna obliczam odleglosc, wrzucajac jendoczesnie id i obliczona odleglosc w tymczasowa tablice
- sortuje tablice
- wybieram punkt o najmniejszej odleglosci i wpisuje w rekord wzgledem ktorego byla obliczana odleglosc.


W ten sposob dla kazdego rekordu odleglosc liczona by byla tylko raz. Co jakies 2-3 meisiace by sie to aktualizowalo i tyle.

Tylko teraz mam prosbe o pomoc w napisaniu skrypciku:

Mamtak

[PHP] pobierz, plaintext 
$sz1 = '52'; $wy1 = '43';
$query = mysql_query("SELECT id, sz, wy FROM obiekty WHERE id>0 ") or die(mysql_error());
while($row = mysql_fetch_row($query))
{
$odleglosc = rad2deg(acos(sin(deg2rad($sz1)) * sin(deg2rad($row['sz']) +  cos(deg2rad($sz1)) * cos(deg2rad($row['sz'])) * cos(deg2rad($wy1-$row['wy']))))  * 111.18957696;
}
[PHP] pobierz, plaintext 

Jak teraz wyniki z petli wrzucac do tablicy w php?
tablica ma 2 kolumny: id i odleglosc wyliczona z powyzszego wzoru

[altruista2]

[PHP] pobierz, plaintext 
$odleglosc = rad2deg(acos(sin(deg2rad($sz1)) * sin(deg2rad($row['sz']) + cos(deg2rad($sz1)) * cos(deg2rad($row['sz'])) * cos(deg2rad($wy1-$row['wy'])))) * 111.18957696;
[PHP] pobierz, plaintext 

uśmiałem się, ktoś tu chyba spał na matematyce

[PHP] pobierz, plaintext 
// $x1, $y1, $x2, $y2 - wspolrzedne punktow 1,2
 
$odleglosc = sqrt(($x2-$x1)*($x2-$x1) + ($y2-$y1)*($y2-$y1));
[PHP] pobierz, plaintext 

A wyliczanie najbliższego najbliższego punktu można zrobić po prostu w samym tylko zapytaniu SQL...

Ten post edytował altruista2 17.02.2010, 18:56:53

[Bojakki]

Ktos chyba spal na geografii i nie wie ze ziemia jest kula.

[altruista2]

To co za problem zapisywać współrzędne geograficzne jako X,Y?

Wtedy całe zapytanie wygląda tak:

[PHP] pobierz, plaintext 
$x = 435; // Szerokość naszego punktu (płaskie)
$y = 813; // Wysokość naszego punktu  (płaskie)
 
$sql = "SELECT ID, x, y, (sqrt((x-$x)*(x-$x) + (y-$y)*(y-$y))) as Odleglosc FROM obiekty ORDER BY Odleglosc ASC LIMIT 1";
[PHP] pobierz, plaintext 

Prawda że proste?

Jest tylko problem kuli ale wtedy wykonujemy to samo zapytanie, tylko odejmujemy od $x, $y granicę płaszycny i wykonujemy drugie zapytanie.

A jeśli chcesz się trzymać tego :

[PHP] pobierz, plaintext 
rad2deg(acos(sin(deg2rad($sz1)) * sin(deg2rad($row['sz']) + cos(deg2rad($sz1)) * cos(deg2rad($row['sz'])) * cos(deg2rad($wy1-$row['wy'])))) * 111.18957696;
[PHP] pobierz, plaintext 

To wpisz to do mojego zapytania zamiast:

[SQL] pobierz, plaintext 
(sqrt((x-$x)*(x-$x) + (y-$y)*(y-$y)))
[SQL] pobierz, plaintext 

Tutaj masz funkcje matematyczne w MySQL:
http://dev.mysql.com/doc/refman/5.0/en/mat...-functions.html
Być możę będziesz wtedy musiał w bazie również trzymać szerokości w radianach aby to szybciej działało

Ten post edytował altruista2 17.02.2010, 19:17:17

[l3l0]

Może warto zainteresować się tym:
http://dev.mysql.com/doc/refman/5.0/en/spa...extensions.html