Najlepszy algorytm krytyczny wydajności dla rozwiązywania najbliższego sąsiada

Question

Mamy listę x, y par. Każda para reprezentuje punkt w przestrzeni 2D. Chcę znaleźć najbliższy punkt z tej listy, do określonego punktu xq, yq. Jaki jest najlepszy algorytm krytyczny pod względem wydajności dla tego problemu? Lisp punktów nie zmieni się; co oznacza, że ​​nie muszę wykonywać operacji wstawiania i usuwania. Chcę właśnie znaleźć najbliższy sąsiad docelowego xq, punkt yq w tym zbiorze.

Edytuj 1: Dziękujemy wszystkim! Stephan202 prawidłowo odgadł, chcę to zrobić wielokrotnie; jak funkcja. Lista niekoniecznie jest posortowana (W rzeczywistości nie rozumiem, jak można ją posortować - podobnie jak w przypadku tabeli z kluczem podstawowym z 2 kolumn ai y? Jeśli to pomoże, to ją posortuję).

Po raz pierwszy skonstruuję strukturę danych na podstawie tej listy, a następnie wykorzystam tę wygenerowaną strukturę danych w funkcji (jeśli ten proces sam w sobie jest istotny).

Dziękuję Jacob; Wygląda na to, że struktura danych KD-Tree jest dobrym kandydatem do bycia odpowiedzią (I czuję, że to jest.) Aktualizuję, gdy otrzymam odpowiednie wyniki).

Edycja 2: Zauważyłem, że ten problem nazywa się "najbliższy sąsiad"!

Edycja 3: Pierwszy tytuł brzmiał "W poszukiwaniu algorytmu (dla przestrzennego kwerendy i indeksowania przestrzennego) (najbliższy sąsiad)"; Wybrałem nowy tytuł: "Najlepszy algorytm wydajności - krytyczny dla rozwiązywania najbliższego sąsiada". Ponieważ nie chcę wykonywać operacji wstawiania i usuwania na moich początkowych danych i chcę, aby najbliższy od nich do nowego punktu (który nie zostanie wstawiony), wybrałem (obecnie) pracę na KD-Drzew. Dziękuje za wszystko!

Answer 1

Jak zauważył Stephan202, jeśli planujesz znaleźć najbliższe dopasowanie dla więcej niż jednego punktu, powinieneś użyć drzewa.

Polecam drzewo KD, którego implementację można łatwo znaleźć w kilku pakietach, takich jak OpenCV 2.0. Lub możesz sam je wdrożyć!

EDYCJA: Zadałem pytanie dotyczące implementacji drzewa kd here - może być przydatne.

EDIT: kd-drzewa były szeroko stosowane z powodzeniem do poszukiwań NN :) - Ponadto, jeśli jesteś gotów przyjąć przybliżone wyniki, można użyć Fast Library for Approximate Nearest Neigbor (FLANN). Implementacja FLANN jest obecna w OpenCV 2.0.

Jeśli nie chcesz przybliżonych odpowiedzi, możesz dostosować parametry FLANN, aby przeszukać całe drzewo.

Answer 2

Powtórz każdy punkt za pomocą wzoru odległości, aby znaleźć minimalną odległość od Q (xq, yq).

Jednak nie podano wystarczających informacji, aby uzyskać odpowiedź krytyczną dla wydajności.

Na przykład, jeśli Q jest BARDZO popularnym punktem, możesz obliczyć odległość do Q i zapisać ją z każdym punktem.

Drugi przykład, jeśli masz ogromną liczbę punktów, można zorganizować punkty na sekcje i zacząć punktów tylko w tej samej sekcji i sąsiednich sekcji do sekcji zawierającej Q.

Answer 3

Jeśli punkt zapytania (xq, yq) jest różny, a lista nie, musisz obliczyć Voronoi diagram listy punktów.To da ci zestaw wielokątów lub "komórek" (niektóre z nich są nieskończone); każdy wielokąt odpowiada punktowi z oryginalnej listy, zwanemu "witryną" tej komórki. Każdy punkt znajdujący się w całości w jednym wielokącie jest bliższy miejscu tego wielokąta niż w innych miejscach na oryginalnej liście. Każdy punkt na granicy między dwoma wielokątami leży równie daleko od każdego miejsca.

Gdy dotrzesz do tak daleko, potrzebujesz prostego sposobu na ustalenie, który wielokąt jest w twoim zasięgu. Jest to znane jako point location problem.

Naprawdę, naprawdę dobra książka dla tego rodzaju rzeczy jest Computational Geometry: Algorithms and Applications. Omawiają one zarówno obliczenia diagramu Voronoi, jak i metodę trapezoidalnej lokalizacji punktu w szczegółach.

Jeśli nie chcesz samodzielnie wykonywać kodu, a nie powinieneś, spróbuj uzyskać bibliotekę podobną do CGAL, która wykona większość pracy za Ciebie. Prawdopodobnie dotyczy to również odpowiedzi na drzewo KD, ale nie wiem dokładnie.

Answer 4

Potrzebujesz spatial index.

Jeśli rzucasz własną, możesz zrobić o wiele gorzej, niż wybrać algorytmy R-Tree lub Quad-tree.

Answer 5

Poszedłbym z quadtree. Jest to najprostsza struktura przestrzenna. W 2 wymiarach ogólnie polecam system quadtree zamiast kd-tree, ponieważ jest prostszy, szybszy. Jego wadą jest większe zużycie pamięci, jeśli liczba wymiarów jest wysoka, ale w przypadku 2 wymiarów różnica nie jest znacząca.

Istnieje dobra sztuczka optymalizacyjna, jeśli współrzędne są zmiennoprzecinkowe: W zapytaniu najpierw trzeba będzie znaleźć węzeł-liść, który zawiera punkt, do którego jest wysyłany najbliżej położony punkt. Aby to zrobić, będziesz musiał przejść do drzewa od korzenia do liścia - w każdej iteracji decydującej, który węzeł-dziecko ma nadepnąć. Przechowuj identyfikatory/adresy węzłów potomnych w 4-wymiarowej tablicy w strukturze węzła. Digitalizacja współrzędnych punktu w algorytmie zapytań. Wtedy będziesz w stanie znaleźć odpowiedni pod-węzeł, po prostu indeksując tablicę 2 odpowiednimi bitami cyfrowej współrzędnej punktu. Digitalizacja jest szybka: zaimplementuj ją za pomocą prostego static_cast.

Ale najpierw zaimplementuj quadtree bez optymalizacji, ponieważ łatwo jest popełnić błąd w bitach. Nawet bez tej optymalizacji nadal będzie to najszybsze rozwiązanie.