GoldenLine
Zaloguj się

konto usunięte

Temat: GMaps, funkcja kołowa, dużo matematyki ;)

Mam punkt A(x,y)
(w praktyce A będzie jakimś miejscem na mapie google, a jego koordynaty to powiedzmy 53.0 i 18.0)

Punkt A będzie dla mnie środkiem wykresu (punktem 0,0).

Mam (dajmy na to, że) losowe punkty od B do Z na mapie google. Zadaję teraz promień r (niech to bedzie 10km) i szukam wszystkich punktów od B do Z, które leżą w odległości mniejszej lub równej od punktu A.

Wszystkie punkty (od A do Z) mam w bazie Mysql w tablicy skladajacej sie z id_markera, dlugosc, szerokosc.

Duzo wygodniej byloby mi zatem matematycznie policzyc ktore markery beda w odleglosci r od A, niz wrzucac wszystko na serwery google'a i odpytywać, czy przypadkiem któres z 10mln markerow, ktore mam nie są w odleglosci 10km od A.

[wroc]

jesli dobrze mysle, najsensowniej byloby sprawdzac odleglosci od A do kazdego punktu po kolei (z wzoru na odleglosc dwoch punktow na ukladzie kartezjanskim) i odkladac tylko te o odleglosc=<r... Ale co jesli bede miec cala mase tych markerów? pare minut odpowiedzi z serwera!Grzegorz Kaszuba edytował(a) ten post dnia 31.07.09 o godzinie 21:08
Link do wypowiedziLink

konto usunięte

Temat: GMaps, funkcja kołowa, dużo matematyki ;)

Grzegorz Kaszuba:
Mam punkt A(x,y)
(w praktyce A będzie jakimś miejscem na mapie google, a jego koordynaty to powiedzmy 53.0 i 18.0)

Punkt A będzie dla mnie środkiem wykresu (punktem 0,0).

Mam (dajmy na to, że) losowe punkty od B do Z na mapie google. Zadaję teraz promień r (niech to bedzie 10km) i szukam wszystkich punktów od B do Z, które leżą w odległości mniejszej lub równej od punktu A.

Wszystkie punkty (od A do Z) mam w bazie Mysql w tablicy skladajacej sie z id_markera, dlugosc, szerokosc.

Duzo wygodniej byloby mi zatem matematycznie policzyc ktore markery beda w odleglosci r od A, niz wrzucac wszystko na serwery google'a i odpytywać, czy przypadkiem któres z 10mln markerow, ktore mam nie są w odleglosci 10km od A.

[wroc]

jesli dobrze mysle, najsensowniej byloby sprawdzac odleglosci od A do kazdego punktu po kolei (z wzoru na odleglosc dwoch punktow na ukladzie kartezjanskim) i odkladac tylko te o odleglosc=<r...
> Ale co jesli bede miec cala mase tych markerów? pare minut
odpowiedzi z serwera!

nie wiem czy Cię dobrze zrozumiałem, ale być może to Ci pomoże...

http://code.google.com/intl/pl/apis/maps/articles/phps...

http://aravindtrue.wordpress.com/2009/06/30/calculate-...Piotr Lewandowski edytował(a) ten post dnia 31.07.09 o godzinie 21:11
Link do wypowiedziLink

konto usunięte

Temat: GMaps, funkcja kołowa, dużo matematyki ;)

SQL

W selectcie
ROUND(DEGREES(ACOS(SIN(RADIANS(TWOJA_LATITUDE))
* SIN(RADIANS(latitude))
+ COS(RADIANS(TWOJA_LATITUDE))
* COS(RADIANS(latitude))
* COS(RADIANS(TWOJA_LONGITUDE - longitude))))) * 69.09 AS distance

order by distance

Tak wyszukasz elementy najblizej tego punktu.

TWOJE_* <- podajesz swoj punktMarcin Bachleda edytował(a) ten post dnia 31.07.09 o godzinie 21:23
Link do wypowiedziLink

konto usunięte

Temat: GMaps, funkcja kołowa, dużo matematyki ;)

troche mi zajmie ogarniecie tego zeby dzialalo, ale z gory dziekuje chlopaki! :)
Link do wypowiedziLink

konto usunięte

Temat: GMaps, funkcja kołowa, dużo matematyki ;)

To co ja podalem, wkladasz w selecta w sqlu :)

Raz dwa powinno pojsc :)
Link do wypowiedziLink
Wojciech Sznapka

Wojciech Sznapka CTO @ STS Zakłady
Bukmacherskie

Temat: GMaps, funkcja kołowa, dużo matematyki ;)

jakbys używał doctrine ORM to tam jest behavior do takich geo zabaw :-)
Link do wypowiedziLink

konto usunięte

Temat: GMaps, funkcja kołowa, dużo matematyki ;)

Marcin Bachleda:
To co ja podalem, wkladasz w selecta w sqlu :)

Raz dwa powinno pojsc :)

tylko, ze mam jeszcze pusta baze markerow i nie chce mi sie teraz jej wypelniac, a powyzsze jest mała czescia czegos wiekszego ;) jak skoncze podstawy tego wiekszego, doloze wyszukiwanie w promieniu x km i powinno chodzic ;) na pewno sie pochwale :)
Link do wypowiedziLink

konto usunięte

Temat: GMaps, funkcja kołowa, dużo matematyki ;)

Wojciech Sznapka:
jakbys używał doctrine ORM to tam jest behavior do takich geo zabaw :-)

Ja jeszcze za duży leszcz na to jestem, dopiero wącham MVC, wplatanie do Zenda ORM wydaje mi się być wyższą szkołą jazdy, jeśli to jest to, co rozumiem (warstwa do obiektowego obsługiwania relacyjnych db???)
Link do wypowiedziLink
Wojciech Sznapka

Wojciech Sznapka CTO @ STS Zakłady
Bukmacherskie

Temat: GMaps, funkcja kołowa, dużo matematyki ;)

Grzegorz Kaszuba:
Wojciech Sznapka:
jakbys używał doctrine ORM to tam jest behavior do takich geo zabaw :-)

Ja jeszcze za duży leszcz na to jestem, dopiero wącham MVC, wplatanie do Zenda ORM wydaje mi się być wyższą szkołą jazdy, jeśli to jest to, co rozumiem (warstwa do obiektowego obsługiwania relacyjnych db???)

dokładnie to, nie bój się tego, to jest raczej fajne, a w necie znajdziesz sporo pomocy :-)
Link do wypowiedziLink
Stanisław P.

Stanisław P. Software designer

Temat: GMaps, funkcja kołowa, dużo matematyki ;)

Ile masz tych punktów w założeniach? 1000? milion? Jeśli powyżej kilkudziesięciu tysięcy, to proponuję mapę podzielić na sektory wcześniej i przy wkładaniu dodać w jakim regionie leży.
Potem najpierw sprawdzasz które regiony wogóle są w zasięgu tego koła i dopiero wtedy z tych zbiorów szukasz wyników. Baza nie jest do dużej ilości operacji matematycznych przystosowana... lepiej to zoptymalizować (tak samo jak k-drzewka w 3d)
Link do wypowiedziLink

konto usunięte

Temat: GMaps, funkcja kołowa, dużo matematyki ;)

Sphinx moze zaindeksowac atrybuty (punkty) i pozniej je bardzo wydajnie przeliczac z uzyciem geolokalizacji, sprawdzone empirycznie na 3 milionach rekordow.
Link do wypowiedziLink

konto usunięte

Temat: GMaps, funkcja kołowa, dużo matematyki ;)

Stanisław Pitucha:
Ile masz tych punktów w założeniach? 1000? milion? Jeśli powyżej kilkudziesięciu tysięcy, to proponuję mapę podzielić na sektory wcześniej i przy wkładaniu dodać w jakim regionie leży.

Niegłupi pomysł, tylko nie wiem jak wyciągnąć taką informację z google i na ile ona będzie pomocna. mogę wyciągnąć z tego co wiem tiles'y na których konkretnie leży marker, ale chyba nic więcej.

a markerów nie spodziewam się w ekstremalnej wersji więcej niż 100 tysięcy, w dodatku sa podzielone na dwie tablice (tablica z markerami firm i tablica z markerami userów - tych będzie z pewnością więcej, a szukanie raczej będzie, jakby to nazwać... jeden do wielu? znaczy jeden user - wiele firm wkoło :) )
Link do wypowiedziLink

konto usunięte

Temat: GMaps, funkcja kołowa, dużo matematyki ;)

a tam mi wpadło do głowy: gdybym przy zapisywaniu poszczegolnych markerów firm zapisywał też ich odległość od jakiegoś tam orientacyjnego punktu w Polsce (np. Łódź), plus ćwiartka od tego punktu (1,2,3,4) to już mogę sobie zawężać wyszukiwania, hm?
Link do wypowiedziLink
Stanisław P.

Stanisław P. Software designer

Temat: GMaps, funkcja kołowa, dużo matematyki ;)

Grzegorz Kaszuba:

Niegłupi pomysł, tylko nie wiem jak wyciągnąć taką informację z google i na ile ona będzie pomocna. mogę wyciągnąć z tego co wiem tiles'y na których konkretnie leży marker, ale chyba nic więcej.

Skoro masz już współrzędne, to nie trzeba nic więcej.

index_x = floor((punkt_x-min_x)*ile_regionów/(max_x-min_x))
index_y = floor((punkt_y-min_y)*ile_regionów/(max_y-min_y))

I zapisujesz index_x, index_y. Jak szukasz, musisz tylko sprawdzić, czy okrąg i region się pokrywają. (szybciej: sprawdzić, czy środek regionu jest w okręgu i dodać wszystkich sąsiadów)

Masz złożoność średnio {srqt(punkty)+log(indeksy)} (chyba, może mnie ktoś poprawi) zamiast {punkty}, czyli jeśli masz tylko Polskę oznakowaną, to po podzieleniu na np. 50 kawałków w każdym kierunku masz do analizy (amortyzowane) 1/2500 danych. Zamiast skanować 100.000 rekordów skanujesz tylko <50, które dostajesz z indeksów. Win ;)
Link do wypowiedziLink
Łukasz Ważny

Łukasz Ważny winning doesn't
really matter as
long as you win

Temat: GMaps, funkcja kołowa, dużo matematyki ;)

Możesz sprawdzić:

http://dev.mysql.com/doc/refman/5.0/en/spatial-extensi...

może Cie zainspiruje do czegoś ;)
Link do wypowiedziLink
Piotr T.

Piotr T. Head of IT, Fintech

Temat: GMaps, funkcja kołowa, dużo matematyki ;)

Na ile znam optymalizację SQL, do Marcina zapytania można dodać jeszcze ograniczenie prostokątem w rodzaju:
latMin < TWOJA_LAT < latMax AND
lngMin < TWOJA_LNG < lngMax AND

potem:
> ROUND(DEGREES(ACOS(SIN(RADIANS(TWOJA_LATITUDE))
* SIN(RADIANS(latitude))
+ COS(RADIANS(TWOJA_LATITUDE))
* COS(RADIANS(latitude))
* COS(RADIANS(TWOJA_LONGITUDE - longitude))))) * 69.09 AS distance < PROMIEN_MAX

SQL nie powinien obliczać skomplikowanych wyrażeń kiedy poprzednie części koniunkcji okazały się fałszywe.

> Łukasz Ważny:
W MySQL te "spatial extensions" są raczej w planach, niż implementacji. Bardzo fajne, działające funkcje ma PostgreSQL, np. wybieranie obiektów zawartych w wielokącie, kole, odległości, itd.

Swoją drogą, Marcin, skąd ten wzór? :)
Link do wypowiedziLink
Karol Nowacki

Karol Nowacki Programista PHP,
Perl, C,
administrator
systemów *NIX

Temat: GMaps, funkcja kołowa, dużo matematyki ;)

funkcja kołowa? nie łatwiej obliczyć wektor A->B i wybrać rekordy tylko a długością wektora < 10km?

select (...) where sqrt(pow(:TWOJA_LATITUDE-latitude,2)+pow(:TWOJA_LONGITUDE - longitude,2)) < :PROMIEN_MAX
Link do wypowiedziLink

konto usunięte

Temat: GMaps, funkcja kołowa, dużo matematyki ;)

Piotr T.:
Swoją drogą, Marcin, skąd ten wzór? :)

Ciekawe pytanie, kilka lat temu robilem jakies obliczenia i znalazlem troche teorii do geolokalizacji, do dzisiaj mam kilka snippetow z rozwiazanymi pewnymi problemami ;)
Link do wypowiedziLink
Piotr T.

Piotr T. Head of IT, Fintech

Temat: GMaps, funkcja kołowa, dużo matematyki ;)

Karol Nowacki:
funkcja kołowa? nie łatwiej obliczyć wektor A->B i wybrać rekordy tylko a długością wektora < 10km?
> 
select (...) where sqrt(pow(:TWOJA_LATITUDE-latitude,2)+pow(:TWOJA_LONGITUDE - longitude,2)) < :PROMIEN_MAX

gdyby nasza Ziemia była płaska, to byłoby łatwiej z wieloma rzeczami... :) Łatwo sprawdzić, bo "kwadrat" o boku X stopni w okolicy Polski jest zdecydowanie prostokątny :))
Link do wypowiedziLink
Karol Nowacki

Karol Nowacki Programista PHP,
Perl, C,
administrator
systemów *NIX

Temat: GMaps, funkcja kołowa, dużo matematyki ;)

Piotr T.:
gdyby nasza Ziemia była płaska, to byłoby łatwiej z wieloma rzeczami... :)
racja, chowam głowę w worek... zamiast sqrt(x^2+y^2) powinno byc R*sqrt(x^2 + (cos(x)*y)^2) gdzie R to średni promień Ziemi, x to różnica szerokości, a y różnica długości geograficznej...

ale tak na marginesie dokładając tylko R w poprzedniej mojej propozycji do dla poszukiwanych punktów w odległości 20km w naszym kraju to "tylko" ok. 25metrówKarol Nowacki edytował(a) ten post dnia 05.08.09 o godzinie 00:52
Link do wypowiedziLink
« Wróć do tematów
Odpowiedz

Podobne tematy





Wyślij zaproszenie do
Anuluj