Określanie punktów w ramach algorytmu o określonym promieniu

Question

Nie jestem pewien, jaką matematyczną koncepcją jest wspieranie mojego pytania. ^^

Załóżmy, że mamy PointA jako odniesienie. Problem polega na znalezieniu punktów wokół Punktu A w danym promieniu (Używanie współrzędnych). Moim podejściem byłoby obliczenie odległości każdego punktu (pitagorejskiego), a następnie porównanie z danym promieniem. Jestem pewien, że to by było wciągające pod względem złożoności.

Jakie algorytmy możesz zasugerować? Przykładowy kod wskazujący rzeczy byłby bardzo doceniany. Dzięki.

Answer 1

Jeśli twoje punkty nie są indeksowane, jest to właściwie optymalny algorytm. Jest n punktów, a zajmie to O ( n) czas przeszukać wszystkie z nich, pod nieobecność jakiegokolwiek innego indeksu.

Jedna mikrooptymalizacja polega na pominięciu operacji sqrt i porównaniu sumy kwadratów delt współrzędnych z kwadratem o pożądanym promieniu.

JEŚLI zamierzasz wykonywać wiele zapytań przeciwko temu samemu zestawowi danych, istnieją różne schematy indeksowania, których możesz użyć, aby zająć trochę czasu na obliczenie (O (n log n)), ale dokonaj wyszukiwania szybciej (O (m + log n), gdzie m to liczba znalezionych punktów.)

kd-trees to prawdopodobnie miejsce, od którego można zacząć.

Answer 2

Zacznę od utworzenia pudełka po okręgu i najpierw sprawdzenia, czy coś nie mieści się w pudełku. Wtedy prawdopodobnie unikasz obliczania sqrts i kwadratów przez cały czas. Wybierz jedną krawędź okna (znaczy jeden po lewej stronie) i obliczyć jego wartość x:

xMin = xOrigin - radius 

Wtedy wszystko, co satifies

xTest < xMin 

mogą być ignorowane. Powtórz to samo dla wszystkich czterech stron. W momencie, gdy test się nie powiedzie, przestań pracować nad tym punktem. Nie rób niepotrzebnych obliczeń.

To wskazuje, że punkt jest blisko, ale niekoniecznie w promieniu. Następny oblicz:

abs(sqr(xOrigin - xTest) - sqr(yOrigin - yTest)) 

jeśli jest to mniej niż promień * promień (który wstępnie oblicz uniknąć stosując pierwiastki kwadratowe), wtedy masz punkt w obrębie promienia.

To najlepsza rzecz, jaką mogę sobie wyobrazić, najpierw przygotowując dane.

Answer 3

Twoja jedyna złożoność to obliczanie odległości. Wystarczy przesiać i uprościć obliczenia, a Ty jesteś optymalny.

Jeśli 'Środek' oznacza (x, y), a następnie na każdy punkt B (x1, y1) rozważyć:

1/Jeżeli B znajduje się w swoim wymaganej odległości d od punktu B, to wówczas następuje zarówno x-x1 < d, jak i . Najpierw sprawdź te warunki, aby odfiltrować wykluczenia "o niskim poziomie wiszącej owoców".

2/Zamiast obliczać odległość, obliczyć kwadrat odległości i porównać go z kwadratem maksymalnej dozwolonej odległości (co należy wyraźnie obliczyć i podać, zamiast przeliczać za każdym razem).Oznacza to, że nie trzeba obliczać pierwiastka kwadratowego dla każdego punktu.

Są to dość niewielkie optymalizacje, ale zakładając, że punkty są nieposortowane i losowe, jest to najlepsze, co otrzymasz.

Answer 4

Najlepsza odpowiedź zależy od liczby wymiarów. Zakładam, że pracujesz w przestrzeni 2D lub 3D.

Prostym podejściem byłoby stworzenie jednolitej siatki wielkości komórki, na przykład r. Następnie odrzuć wszystkie punkty do odpowiednich komórek.

Każdy punkt zapytania przecina tylko kilka komórek, na przykład 9. Należy wtedy sprawdzić tylko przecinające się komórki.

Bardziej efektywnym podejściem byłoby skonstruowanie drzewa czwórkowego lub drzewa KD (istnieje wiele innych opcji, ale w przypadku 2D możliwe byłoby wykonanie drzewa cztero lub KD).

Sprawdzanie przecięcia prostokąt-koło jest konieczne w przypadku struktur hierarchicznych, ale zostało to opisane w algorytmie najbliższego sąsiada KD (wystarczy tylko nieznacznie go zmodyfikować).

Jeśli naprawdę zależy Ci na wydajności, możesz skonstruować wiele siatek (przesuniętych lub obróconych) i zawsze wybierać ten z komórką najbardziej wycentrowaną w punkcie, aby wyszukiwanie było ograniczone do najmniejszej liczby komórek.