MongoDB i odległość pomiędzy dwoma punktami

Potrzebna pomoc
21

Underley, wytłumaczę Ci jak kretynowi, skoro poprzednie próby spaliły na niczym…

Jesteś w Warszawie, centrum. Szukasz stuffu w odległości 5km od siebie. Każdy przedmiot ma parę longitude, latitude, na podstawie której chcesz określić odległość.
Używasz swojej metryki taksówkowej albo pitagorejskiej (advanced mode), przyjmujesz że 1km = 0.01 stopnia (prawda na równiku), czyli szukasz stuffu w odległości do 0.05 stopnia od centrum. I oto co uzyskujesz:

(mapka niedokładnie odpowiada wymiarom elipsy, bo szkicowałem na szybko – tzn. powinienem elipsę zrobić większą / przy mniejszej skali. ale kształt/proporcja są jak najbardziej OK)

To jest mój zarzut wobec metryki kartezjańskiej i taksówkowej: że traktują oba wymiary równoważnie. Podczas kiedy (“u nas” na 52N) ten sam kąt “w lewo” to prawie dwa razy mniejsza odległość niż ten sam kąt “w górę”.

Czy teraz rozumiesz? Robisz błąd systematyczny rzędu 100%. Dość sporo, nawet jak na z zasady niedokładne aplikacje webowe, hm?
Nawet Ci zrobiłem grafikę, żeby pokazać dlaczego nie masz racji – wyświadcz mi przysługę i przeczytaj oraz obejrzyj wszystko dokładnie przed napisaniem kolejnego posta.

Sortowanie? Proszę bardzo. Nagle się okazuje, że (według Twojej metryki) Arkadia albo Galeria Mokotów są bliżej Centrum niż Most Poniatowskiego. (teraz przesadzam, ale wiadomo o co chodzi)

EDIT: w poziomie na elipsie zamiast “5km” powinno być “5.7km”.

22

Ok, to ja Ci dla odmiany jak chłop krowie na miedzy:

Nie interesuje mnie odległość. Interesuje mnie posortowanie po odległości. Nie muszę w tym celu korzystać z mądrych wzorów na wyliczanie odległości z sinusami i cosinusami. Ja tej odległości nie potrzebuję. Biorę odleglość po równoleżniku, dodaje do niej odległość po południku. I tak dla każdego punktu. Nie potrzebuję uwzględniać tego, że na równoleżniku przechodzącym przez Centrum jedna minuta kątowa jest dłuższa niż jedna minuta kątowa równoleżnika przechodzącego przez Arkadię. Ba, nawet w skali Hel-Warszawa-Ustrzyki jest to do pominięcia.

Przy 1000 punktach w bazie i 10 zapytaniach na godzinę można sobie pozwolić na dokładne liczenie - tylko po co, jeśli takim samym nakładem pracy mamy akceptowalny wynik. Przy milionie punktów i 10 zapytaniach na sekundę - warto już przemyśleć takie rzeczy.

I na koniec - wiem, że wątek zaczął się od czegoś innego. I co do tego, ze przy dużym rozrzucie po równoleżnikach takie uproszczenie wprowadza błąd masz rację - ale nie zmienia to faktu, że przy dużym rozrzucie po równoleżnikach w większości przypadków ten błąd i tak nie ma znaczenia, tyle że z innego powodu niż w przypadku małego rozrzutu.

23

Ale wtedy Twoje sortowanie promuje (wrzuca na wyższe miejsca jako bliższe) lokacje w osi północ-południe kosztem tych na osi wschód-zachód.
Miej wokół tego model biznesowy (niekoniecznie swój, wystarczy że któregoś ze swoich użytkowników), a za jaja Cię powieszą za sortowanie niezgodne z deklaracjami (“według odległości”).
Zanim zdążysz się wytłumaczyć (“używamy niedokładnego wzoru do liczenia odległości, północ jest bliżej niż zachód”), będziesz miał na głowie pół Digga/Wykopu (“niezależny sklep bez powodu pokarany pojawieniem się na drugiej stronie wyników wyszukiwania, pomimo bycia bliżej niż moloch należący do Grażyny Kulczyk”).

Znaczy, uważam że wynik z błędem 90% nie jest akceptowalny.
I prosi się o znysowanie programisty, który coś takiego napisał i przyjął.

24

Ale w skali Polski błąd wynosi około 10% w przypadku bardzo skrajnym. Równie dobrze ktoś się może czepić, że do jego ośrodka wczasowego w Bieszczadach jest bliżej licząc odleglość “drogową” niż na Pomorze, które jest w wynikach pozycję wyżej. Nawet w wypadku miasta da się wymyślić taki naciągany przykład, że wcale nie jest bliżej, choć geograficznie jest bliżej.

25

10%? Kurde, a prosilem zebys przeczytal mojego posta…

26

Tak czytałem, i wiem jaki błąd w założeniach robisz. “Flat mode” nie polega na liczeniu na stopniach jakby były jednostkaim długości. Flat polega na przeliczeniu odległości kątowej na na długość “liniową” i użyciu jej do obliczeń. Wprowadza to pewien błąd zależny od tego na jak dużym zakresie szerokości geograficznych operujemy (bo wtedy przelicznik powinien się zmieniać). Ale ten błąd jest dla wycinka mapy obejmującego obszar Polski ciut powyżej 10% przy metryce taksówkowej, a przy wzorze Pitagorasa zdaje się w okolicy 3% (jak zdążyłeś zauważyć mało pamiętam z matmy). Dla uproszczenia pewnych rzeczy (np. znalezienie 10 najbliższych sąsiadów ze zbioru 1000) jest to ok. A używania do tego wzorów ze strony którą podałeś uważam za wytaczanie armaty na wróbla - sorry, to aplikacje webowe a nie geodezja.

27

[quote=Tomash][quote=SimonG]A to święte oburzenie, bo sądzisz, że to co napisałeś jest super poprawne, a to co napisał Hubert jest z gruntu złe?
Tak reasumując: obaj błądzicie i obaj macie rację.[/quote]
Napisz mi gdzie błądzę albo przeproś i przestań siać FUD jeśli nie wiesz.[/quote]
Ojej, to już nie można się nie zgodzić? Od razu tylko, że sieję FUD albo że mam przepraszać.

To może skoro już chcesz wykładu, a ja mam chwilkę… Całe książki na ten temat napisano, ale po kolei.

  1. Kiedyś się zorientowano, że Ziemia płaska nie jest. Potem się zorientowano, że nie jest też super okrągła, jest bardziej elipsoidą, która ma jakieś dwa promienie. No i fajnie, tylko pytanie jakie. Na to pytanie odpowiadano różnie, przez co jest wiele standardów określających m.in. te promienie i punkt zerowy. Przez to ten sam punkt na Ziemi ma różne współrzędne, zależnie od wspomnianego standardu. Dlatego też nie ma sensu mówić o punkcie o współrzędnych (10,20). Żeby to był jednoznacznie zdefiniowany punkt musisz dołożyć jeszcze standard, który opisuje tę elipsoidę, na której punkt ma te współrzędne. Najpowszechniej używanym standardem jest WGS84 (używany np. przez GPS), ale nie wyklucza to używania innego.

  2. Oczywiście miałeś rację pisząc, że trzeba użyć tego drogiego obliczeniowo wzoru na obliczenie odległości między punktami. Wtedy (mając współrzędne punktów z tego samego standardu, np. WGS84) można sobie ładnie obliczyć odległości. Znać by też trzeba jaki jest ten standard, tak żeby wziąć odpowiednie promienie elipsoidy.

  3. Hubert też miał rację pisząc o takiej normalnej odległości, ino to ma to pewne ograniczenia. Te wszystkie punkty muszą być na tyle blisko siebie, żeby Ziemia koło nich mogła być uznana za płaską (tak co by błąd obliczeń byłby pomijalnie mały). Jak mam pewien punkt i wyciągam z bazy wszystkie punkty w promieniu 300m i mam znaleźć np. najbliższy… to spokojnie mogę liczyć to normalnie (bład jest naprawdę minimalny). Przecież nikt normalny nie będzie liczył kątów z tego dużego wzoru jak chce po prostu zmierzyć długość ogrodzenia dookoła swojej działki. Chyba, że mówimy o działce wielkości Alaski.
    Takie płaskie mapy normalnie się stosuje (np. odwzorowanie Gaussa-Krugera) ale mają takie ograniczenie, że mają środek. Im bliżej środka, tym odległości są dokładniejsze, im dalej tym gorzej.

  4. To co robisz drogi Tomashu w Postgresie to takie wymyślanie koła na nowo. Jest np. PostGis, taki dodatek przestrzenny do Postgresa, on to wszystko robi. A nawet o wiele więcej. Do Oracla też jest dodatek, który załatwia to wszystko (i tam też przy określaniu geometrii trzeba podać system z jakiego są wzięte współrzędne).

28

Podoba mi się Twój upór. Jeszcze 18 godzin temu nie miałeś pojęcia co to formuła Haversine’a, jeszcze 9 godzin temu twierdziłeś, że istnieje równoważność (względem sortowania) pomiędzy polem powierchni prostokąta a jego obwodem. Pomimo wyprowadzenia z błędu i podania informacji na tacy idziesz w zaparte. Powinieneś trenować sztuki walki – tam taki upór (niezmienny pomimo okoliczności) jest świetną cechą.

W programowaniu (czy ogólnie inżynierii) taki upór, niestety, prowadzi do ignorancji, a w konsekwencji do niekompetencji.

Enyłej.

“ciut” i “zdaje się”? Policzmy.

Polska leży pomiędzy szerokościami 49N a 54N. Czyli zakładam, że do przeliczenia jednego stopnia długości geogr. na kilometry użyjesz średniej, czyli równoleżnika 51.5N. Na tym równoleżniku jeden stopień długości to 70km (z dokładnością do 1km).
A teraz skrajności. Na równoleżniku 49N jeden stopień długości to 65km, a 54N - 73km. Uśrednijmy dla symetrycznej niedokładności, czyli 1 stopień to 69km plus/minus 4km. Błąd 6% w każdą stronę.

6% to sporo, ale jest do przełknięcia, póki zakładasz, że Twój serwis będzie operował wyłącznie w Polsce.
Możesz wtedy hardkodować 1° longitude = 69km i zdrowia.

Gorzej się robi, kiedy masz klienta z Niemiec i chciałby on serwis operujący we wszystich krajach niemieckojęzycznych – wtedy masz rozpiętość od 46N (południowa Szwajcaria) do 55N (północne Niemcy) – tu już robisz błąd 11%.

A kiedy serwis ma być anglojęzyczny i/lub międzynarodowy… mówiąc krótko – jesteś w dupie. No chyba że dla każdej lokacji zapiszesz “odpowiedni dla niej” przelicznik szerokości do liczenia odległości w jakimś (wąskim) zakresie. Co jest hackiem na hacku. Nie lepiej od razu zrobić porządnie i mieć spokój?

Czyli póki pracujesz dla Allegro to jest jeszcze akceptowalne, ale z eBaya już by Cię wywalili :wink:

TL;DR wszystko można uprościć w imię “wystarczającej dokładności”, ale zbyt chamskie uproszczenia prowadzą do strzału w stopę prędzej czy później

29

No i cały czas udowadniasz, że “wy wiecie swoje, a my mamy racje” - Twój tekst o uporze równie dobrze jak do mnie pasuje do Ciebie.

Nie trzeba takiego przelicznika zapisywać. Wystarczy go obliczyć. Raz na całą operację wyszukiwania/sortowania - dla punktu centralnego. Obliczenie jest proste. Zajrzyj do źródeł geokita, którego zjechałeś za nienadadający się do niczego tryb flat.

Podobnie w drugą stronę. Trzeba mieć rozsądek i umieć wybrać odpowiednie rozwiązanie do odpowiednich celów. Jak za bardzo skomplikujesz - też wtopisz. Na tym też polega inżynieria - na odpowiednim doborze środków. Wyjątkowo dobrze wiem co mówię - ostatnie pół roku spędziłem sprzątając po podejściu “zróbmy to maksymalnie szczegółowo i z rozmachem”. To tak jak już zeszliśmy na tematy filozoficzne.

Można prosić moderatora o przeniesienie tego do jakiegoś innego wątku? Ktoś będzie szukał informacji o MongoDB i włos mu się na głowie zjeży. Tytuł wątku może wybrać Tomash - niech ma to ostatnie słowo, o które cały dzień dzielnie walczy. :wink:

30

Jest różnica pomiędzy “nie wiem jak to można zrobić dokładnie, więc wybieram niedokładne rozwiązanie jako jedyne mi znane” a “wiem jak to można zrobić na różne sposoby, świadomie i po rozważeniu wybieram prostsze rozwiązanie”. Ty jeszcze parę godzin temu byłeś w tym pierwszym punkcie, więc nie ściemniaj mi tu o świadomym wyborze :stuck_out_tongue: