Znajdowanie na mapie użytkowników znajdujących się najbliżej

Znajdowanie na mapie użytkowników znajdujących się najbliżej
0

Jeśli było przepraszam i prosiłbym o podesłanie linka do tematu, szukałem w wyszukiwarce i znalazło 29172 tematów, a mi nie za bardzo chce się to przeglądać :)
Zaciekawiła mnie pewna kwestia:
Powiedzmy, że mamy wirtualną mapę, na niej przebywają użytkownicy jako punkty, chciałbym znaleźć userów najbliżej mnie, do głowy wpadł mi następujący algorytm:

  1. Z punktu (x,y), w którym się znajduję narysuj linię prostą (promień koła w zasięgu którego będą poszukiwani użytkownicy)
  2. Pobierz z tabeli lokalizacja lokalizację użytkownika
  3. Za pomocą równania okręgu sprawdź czy punkt należy do tego okręgu
  4. Powtarzaj, dopóki nie sprawdzisz całej tabeli lokalizacja

Trochę niewydajene ;)
Czy mój tok myślenia jest prawidłowy? Czy istnieją inne sposoby?
Znalazłem jeszcze coś takiego ale chyba to się akurat nie nada.

Patryk27
Moderator
  • Rejestracja:ponad 17 lat
  • Ostatnio:ponad rok
  • Lokalizacja:Wrocław
  • Postów:13042
0

W podstawowej wersji musisz przelecieć całą tabelę, licząc dla każdego użytkownika jego odległość od testowanego punktu - tyle że na dłuższą metę jest to średnio wydajne rozwiązanie.
Możesz je zoptymalizować dzieląc mapę na sektory (identyfikowane np. krotką (x,y)) - gdy użytkownik się przemieszcza, aktualizuj jego dane na temat sektora, w którym się obecnie znajduje, dzięki czemu podczas wykonywania zapytania będziesz mógł przygotować dodatkowy warunek WHERE odrzucający tych użytkowników, którzy z całą pewnością są za daleko.

PS pamiętaj, że możesz dodatkowo zoptymalizować algorytm liczenia odległości, pozbywając się pierwiastkowania na rzecz potęgi:
\sqrt{x<sup>2 + y</sup>2} &lt;= r -> x<sup>2 + y</sup>2 &lt;= r^2


0
  1. Jak mógłby wyglądać taki przykładowy warunek?
  2. Co to za wzór? Zawsze byłem słaby z matmy xD
Patryk27
Moderator
  • Rejestracja:ponad 17 lat
  • Ostatnio:ponad rok
  • Lokalizacja:Wrocław
  • Postów:13042
0

Ad 1: narysuj sobie na kartce siatkę złożoną z kwadratowych pól, każde oznacz odpowiednimi wartościami (x,y) (w zależności od położenia danego pola), a sam zrozumiesz.

Ad 2: przyjrzyj się postaci kanoniczej równania okręgu.


edytowany 1x, ostatnio: Patryk27
0

Dzięki, przyda się
Zaplusowałbym ale nie mam konta
Temat do zamknięcia, chyba, że ktoś chce coś dodać od siebie

0

Jeszcze jedno: MySQL [i chyba nie tylko] obsługuje typy spatial, czy one mogły by być jakoś pomocne w rozwiązaniu tego problemu?
EDIT:
@Patryk27 już chyba wiem o co Ci chodziło z sektorami, to bardziej efektywniejsze niż szukanie kołowe, bo zamiast pobierać całą bazę i szukać, który user jest blisko, można dać selecta, do tabeli, by wybrał wszystkich userów z danego sektora :)

Patryk27
Moderator
  • Rejestracja:ponad 17 lat
  • Ostatnio:ponad rok
  • Lokalizacja:Wrocław
  • Postów:13042
0

zamiast pobierać całą bazę i szukać, który user jest blisko, można dać selecta, do tabeli, by wybrał wszystkich userów z danego sektora
O to mi właśnie chodziło - tylko nie zapominaj o sektorach przyległych, ponieważ może się okazać, że kogoś pominiesz. A testowanie odległości i tak musisz wykorzystać, tyle że na mniejszej już liczbie użytkowników.


edytowany 1x, ostatnio: Patryk27
0

Jeszcze raz dzięki ;)
W sumie nie trzeba sprawdzać odległości, bo jak mam np sektor 3x3 (czyli ma powierzchnię 9 j2) to osoby z tego sektora można uznać za będące stosunkowo blisko bo ten kwadrat jest stosunkowo mały i prawdopodobieństwo, że dwa punkty A i B są blisko siebie jest duże

Patryk27
Moderator
  • Rejestracja:ponad 17 lat
  • Ostatnio:ponad rok
  • Lokalizacja:Wrocław
  • Postów:13042
0

Rozpatruj przypadki pesymistyczne:
407cc4847e.png
Szukając sąsiadów punktu czerwonego i biorąc pod uwagę tylko jeden sektor (w którym on sam się znajduje), nie zostanie wzięty pod uwagę żaden z niebieskich punktów, który także może być sąsiadem (przy czym zwiększenie wymiarów sektora nie ma wpływu na to zjawisko).
Chyba że specyfika Twojego projektu zezwala na coś takiego, wtedy ok.


edytowany 1x, ostatnio: Patryk27
0

No tak
Można również zrobić tak, wziąć sąsiednie sektory (tak aby utworzyło krzyż jak na obrazku) i stworzyć z nich jeden wirtualny sektor, wtedy zarówno dla czerwonego punktu jak i zielonych sąsiadami byłyby punkty z sąsiednich sektorów, a dla niebieskich z sąsiedniego sektora, byłyby to sektor oznaczony kolorem czerwonym.
Co sądzisz o takim rozwiązaniu?
user image

Patryk27
Moderator
  • Rejestracja:ponad 17 lat
  • Ostatnio:ponad rok
  • Lokalizacja:Wrocław
  • Postów:13042
0

Trzeba brać pod uwagę przyległe sektory, w zależności od ich wymiarów oraz sprawdzanego promienia:
3711a09f19.png
W tym wypadku punkt czerwony znajduje się w sektorze ciemnopomarańczowym, zatem do sprawdzenia mamy na pałę sektory ograniczone kolorem jasnopomarańczowym - tutaj akurat wyszedł kwadrat, lecz w miarę powiększania się promienia, otrzymamy koło sektorów.


edytowany 1x, ostatnio: Patryk27
0

Hmm, a jeśli te niebieskie punkty obok pomarańczowego kwadratu miały sąsiadów, to dla nich sektor poszukiwań zazębiałby się z tym sektorem dla zielonych

Patryk27
Moderator
  • Rejestracja:ponad 17 lat
  • Ostatnio:ponad rok
  • Lokalizacja:Wrocław
  • Postów:13042
0

Nie interesują Cię sąsiedzi punktów obok - tylko Twoi (testowanego punktu) sąsiedzi.


0

Ok, jeszcze raz wielkie dzięki ;)

0

Chciałem skorzystać ze sposobu kolegi z początku, napisałem w PHP ale nie działa, może ktoś mi powiedzieć, gdzie jest błąd?

Kopiuj
 
<?
function czy_blisko($X1,$Y1,$X2,$Y2,$R){
	return (pow($X2 - $X1,2) + pow($Y2 - $Y1,2) == pow($R,2));
}
var_dump(czy_blisko(3,3,5,1,10));
?>

Zwraca mi to false a te punkt X2 jest w zasięgu koła X1

Patryk27
Moderator
  • Rejestracja:ponad 17 lat
  • Ostatnio:ponad rok
  • Lokalizacja:Wrocław
  • Postów:13042
0

Twoja funkcja czy_blisko sprawdza czy punkt znajduje się na okręgu, a nie wewnątrz koła. Spójrz na operator.


0

Czyli ten wzór nie jest do tego?

Patryk27
Moderator
  • Rejestracja:ponad 17 lat
  • Ostatnio:ponad rok
  • Lokalizacja:Wrocław
  • Postów:13042
1

Pozwolę Ci samemu sobie odpowiedzieć na to pytanie.


edytowany 1x, ostatnio: Patryk27
0

TABELA UŻYTKOWNICY(id,nick,email)
TABELA LOKALIZACJE(id,user_id,x,y)

Kopiuj
    select nick from UŻYTKOWNICY on  UŻYTKOWNICY.id = LOKALIZACJE.user_id where pow(a - (SELECT x FROM LOKALIZACJE WHERE user_id = 3),2)  + pow(b - (SELECT y FROM LOKALIZACJE WHERE user_id = 3),2) <= pow(7,2)
0

Poprawione (zapomniałem o inner join i brak zmiennych a i b, zamiast nich powinno być x i y)

Kopiuj
SELECT `nick` FROM `uzytkownicy` INNER JOIN `uzytkownicy` ON `uzytkownicy`.`id` = `lokalizacje`.`user_id` WHERE pow(x - (SELECT x FROM LOKALIZACJE WHERE user_id = 3),2)  + pow(y - (SELECT y FROM LOKALIZACJE WHERE user_id = 3),2) <= pow(7,2) 
0
Kopiuj
 SELECT `nick` FROM `uzytkownicy` INNER JOIN `lokalizacje` ON `uzytkownicy`.`id` = `lokalizacje`.`user_id` WHERE pow(x - (SELECT x FROM LOKALIZACJE WHERE user_id = 3),2)  + pow(y - (SELECT y FROM LOKALIZACJE WHERE user_id = 3),2) <= pow(7,2) 
Kliknij, aby dodać treść...

Pomoc 1.18.8

Typografia

Edytor obsługuje składnie Markdown, w której pojedynczy akcent *kursywa* oraz _kursywa_ to pochylenie. Z kolei podwójny akcent **pogrubienie** oraz __pogrubienie__ to pogrubienie. Dodanie znaczników ~~strike~~ to przekreślenie.

Możesz dodać formatowanie komendami , , oraz .

Ponieważ dekoracja podkreślenia jest przeznaczona na linki, markdown nie zawiera specjalnej składni dla podkreślenia. Dlatego by dodać podkreślenie, użyj <u>underline</u>.

Komendy formatujące reagują na skróty klawiszowe: Ctrl+B, Ctrl+I, Ctrl+U oraz Ctrl+S.

Linki

By dodać link w edytorze użyj komendy lub użyj składni [title](link). URL umieszczony w linku lub nawet URL umieszczony bezpośrednio w tekście będzie aktywny i klikalny.

Jeżeli chcesz, możesz samodzielnie dodać link: <a href="link">title</a>.

Wewnętrzne odnośniki

Możesz umieścić odnośnik do wewnętrznej podstrony, używając następującej składni: [[Delphi/Kompendium]] lub [[Delphi/Kompendium|kliknij, aby przejść do kompendium]]. Odnośniki mogą prowadzić do Forum 4programmers.net lub np. do Kompendium.

Wspomnienia użytkowników

By wspomnieć użytkownika forum, wpisz w formularzu znak @. Zobaczysz okienko samouzupełniające nazwy użytkowników. Samouzupełnienie dobierze odpowiedni format wspomnienia, zależnie od tego czy w nazwie użytkownika znajduje się spacja.

Znaczniki HTML

Dozwolone jest używanie niektórych znaczników HTML: <a>, <b>, <i>, <kbd>, <del>, <strong>, <dfn>, <pre>, <blockquote>, <hr/>, <sub>, <sup> oraz <img/>.

Skróty klawiszowe

Dodaj kombinację klawiszy komendą notacji klawiszy lub skrótem klawiszowym Alt+K.

Reprezentuj kombinacje klawiszowe używając taga <kbd>. Oddziel od siebie klawisze znakiem plus, np <kbd>Alt+Tab</kbd>.

Indeks górny oraz dolny

Przykład: wpisując H<sub>2</sub>O i m<sup>2</sup> otrzymasz: H2O i m2.

Składnia Tex

By precyzyjnie wyrazić działanie matematyczne, użyj składni Tex.

<tex>arcctg(x) = argtan(\frac{1}{x}) = arcsin(\frac{1}{\sqrt{1+x^2}})</tex>

Kod źródłowy

Krótkie fragmenty kodu

Wszelkie jednolinijkowe instrukcje języka programowania powinny być zawarte pomiędzy obróconymi apostrofami: `kod instrukcji` lub ``console.log(`string`);``.

Kod wielolinijkowy

Dodaj fragment kodu komendą . Fragmenty kodu zajmujące całą lub więcej linijek powinny być umieszczone w wielolinijkowym fragmencie kodu. Znaczniki ``` lub ~~~ umożliwiają kolorowanie różnych języków programowania. Możemy nadać nazwę języka programowania używając auto-uzupełnienia, kod został pokolorowany używając konkretnych ustawień kolorowania składni:

```javascript
document.write('Hello World');
```

Możesz zaznaczyć również już wklejony kod w edytorze, i użyć komendy  by zamienić go w kod. Użyj kombinacji Ctrl+`, by dodać fragment kodu bez oznaczników języka.

Tabelki

Dodaj przykładową tabelkę używając komendy . Przykładowa tabelka składa się z dwóch kolumn, nagłówka i jednego wiersza.

Wygeneruj tabelkę na podstawie szablonu. Oddziel komórki separatorem ; lub |, a następnie zaznacz szablonu.

nazwisko;dziedzina;odkrycie
Pitagoras;mathematics;Pythagorean Theorem
Albert Einstein;physics;General Relativity
Marie Curie, Pierre Curie;chemistry;Radium, Polonium

Użyj komendy by zamienić zaznaczony szablon na tabelkę Markdown.

Lista uporządkowana i nieuporządkowana

Możliwe jest tworzenie listy numerowanych oraz wypunktowanych. Wystarczy, że pierwszym znakiem linii będzie * lub - dla listy nieuporządkowanej oraz 1. dla listy uporządkowanej.

Użyj komendy by dodać listę uporządkowaną.

1. Lista numerowana
2. Lista numerowana

Użyj komendy by dodać listę nieuporządkowaną.

* Lista wypunktowana
* Lista wypunktowana
** Lista wypunktowana (drugi poziom)

Składnia Markdown

Edytor obsługuje składnię Markdown, która składa się ze znaków specjalnych. Dostępne komendy, jak formatowanie , dodanie tabelki lub fragmentu kodu są w pewnym sensie świadome otaczającej jej składni, i postarają się unikać uszkodzenia jej.

Dla przykładu, używając tylko dostępnych komend, nie możemy dodać formatowania pogrubienia do kodu wielolinijkowego, albo dodać listy do tabelki - mogłoby to doprowadzić do uszkodzenia składni.

W pewnych odosobnionych przypadkach brak nowej linii przed elementami markdown również mógłby uszkodzić składnie, dlatego edytor dodaje brakujące nowe linie. Dla przykładu, dodanie formatowania pochylenia zaraz po tabelce, mogłoby zostać błędne zinterpretowane, więc edytor doda oddzielającą nową linię pomiędzy tabelką, a pochyleniem.

Skróty klawiszowe

Skróty formatujące, kiedy w edytorze znajduje się pojedynczy kursor, wstawiają sformatowany tekst przykładowy. Jeśli w edytorze znajduje się zaznaczenie (słowo, linijka, paragraf), wtedy zaznaczenie zostaje sformatowane.

  • Ctrl+B - dodaj pogrubienie lub pogrub zaznaczenie
  • Ctrl+I - dodaj pochylenie lub pochyl zaznaczenie
  • Ctrl+U - dodaj podkreślenie lub podkreśl zaznaczenie
  • Ctrl+S - dodaj przekreślenie lub przekreśl zaznaczenie

Notacja Klawiszy

  • Alt+K - dodaj notację klawiszy

Fragment kodu bez oznacznika

  • Alt+C - dodaj pusty fragment kodu

Skróty operujące na kodzie i linijkach:

  • Alt+L - zaznaczenie całej linii
  • Alt+, Alt+ - przeniesienie linijki w której znajduje się kursor w górę/dół.
  • Tab/⌘+] - dodaj wcięcie (wcięcie w prawo)
  • Shit+Tab/⌘+[ - usunięcie wcięcia (wycięcie w lewo)

Dodawanie postów:

  • Ctrl+Enter - dodaj post
  • ⌘+Enter - dodaj post (MacOS)