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

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.

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:
->

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

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.

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

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 :)

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.

Jeszcze raz dzięki ;)
W sumie nie trzeba sprawdzać odległości, bo jak mam np sektor 3x3 (czyli ma powierzchnię 9 j²) 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

Rozpatruj przypadki pesymistyczne:

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.

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?

Trzeba brać pod uwagę przyległe sektory, w zależności od ich wymiarów oraz sprawdzanego promienia:

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.

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

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

Ok, jeszcze raz wielkie dzięki ;)

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?

 
<?
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

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

Czyli ten wzór nie jest do tego?

Pozwolę Ci samemu sobie odpowiedzieć na to pytanie.

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

    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)

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

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) 

 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)