Optymalizacja algorytmu

Mam taki problem do rozwiązania:
Mam dwie grupy 10 000 punktów na osi XY.
Każda grupa podzielona jest na mniejsze grupy ale to jest mniej ważne.
Zadanie polega na tym aby dla każdego punktu z grupy pierwszej znaleźć liczbę punktów odległych o np. 10 (obliczane pitagorasem).

Problem w tym, że ja to robię aktualnie w pętli. Dla każdego punktu z grupy A sprawdzam odległość do każdego punktu z grupy B i jeśli odległość jest poniżej 10 to znaczy, że taki punkt spełnia kryteria.

Aktualnie robię tak, że iteruję 10 000 x 10 000 co trochę czasu zajmuje. Nie mam pomysłu jak to przyśpieszyć. Ma ktoś jakieś pomysły?

Można np.: https://en.wikipedia.org/wiki/DBSCAN
Można też posortować punkty a potem wybierać.

Najlepiej R-drzewem https://en.wikipedia.org/wiki/R-tree Gotową implementację masz w Boost.Geometry

Rozwiązanie naiwne to posortowanie punktów wg (x, y) a potem dla każdego skanowanie tylko tych punktów które:

abs(x0 - x1) <= 10
abs(y0 - y1) <= 10

gdzie (x0, y0) to punkt sprawdzany.
Złożoność to O(k*log n) gdzie k to średnia liczba punktów leżących w odległości a <= 10.
log n wynika z wyszukiwania binarnego (o ile takie będzie zastosowane), może być wersja niedokładna (czyli szukamy punktu wstawienia) jeśli dopuszczalne są punkty wejściowe których nie ma wśród przeszukiwanych wartości.

Kolejnym podejściem które warto rozważyć jest spatial hashing, znacznie prostszy w implemntacji od drzewa czwórkowego(r-drzewo), i przy równomiernym rozkładzie punktów na płaszczyźnie pozwala bardzo zawęzić obszar przeszukiwań dla każdego punktu.

https://conkerjo.wordpress.com/2009/06/13/spatial-hashing-implementation-for-fast-2d-collisions/

kd-tree tez sie moze nadac do tego problemu. Latwiej zaimplementowac niz R-tree.

Niestety nie jestem dobry w algorytmach oraz języku angielskim.

Zrobiłem tak. Biorąc punkt z grupy A generuje wszystkie możliwe punkty dla tego punktu i następnie sprawdzam czy ten punkt znajduję się w grupie B (słownik). Działa to znacznie szybciej i było proste w implementacji.

anonimowy napisał(a):

Każda grupa podzielona jest na mniejsze grupy ale to jest mniej ważne.

Logika podpowiada, że podstawowym kryterium grupowania punktów powinny być współrzędne. Wtedy wystarczy jakieś proste drzewo, sprawdzenie bounding boxa i błyskawicznie eliminujesz gro punktów, które trzeba sprawdzić.

To, że jest podzielona na mniejsze grupy to mogłem pominąć bo to mogę identyfikować już na podstawie wygenerowanych współrzędnych.

Chodzi mi o to, że problemem nie jest algorytm tylko zła struktura danych.

To tak jakbyś chciał wyszukiwać miejscowości według nazwy a pogrupowałbyś je według liczby mieszkańców. Nonsens.

Tylko, że tu nie zachodzi grupowanie współrzędnych. Muszę znaleźć dla każdej współrzędnej współrzędne sąsiednie.