Znajdź najbliższy punkt z wektorem punktów

Question

mam wektor wskaźników do bardzo prostego Point klasy:

class Point{ 
public: 
    float x; 
    float y; 
    float z; 
}; 

Jak mogę znaleźć najbliższy obiekt do punktu referent przy użyciu STL?
Czy muszę najpierw najpierw uporządkować wektor, czy jest bardziej efektywny sposób?

Answer 1

Sortowanie zajmuje O(n*log(N)), więc nie jest zbyt wydajne. Możesz to zrobić w O(n), wykonując tylko iterację elementów i zapamiętując najlepsze dopasowanie.

Za pomocą for_each z <algorithm> można zdefiniować funkcję, która śledzi najbliższe elementy i kończy się w O(n).

Lub, prawdopodobnie, możesz nawet użyć min_element, również z <algorithm>.

Answer 2

Nie można przejść szybciej niż liniowe porównanie, jeśli wiadomo tylko, że istnieją punkty w wektorze. Jednak jeśli masz dodatkową wiedzę, wiele można poprawić. Na przykład, jeśli wiesz, że wszystkie punkty są uporządkowane i leżą na tej samej linii, istnieje rozwiązanie logarytmiczne.

Istnieją również lepsze struktury danych do rozwiązania problemu, na przykład k-d tree. To nie jest część STL - będziesz musiał ją zaimplementować samodzielnie, ale jest to struktura danych, której używasz do rozwiązania problemu, który masz.

Answer 3

Podstawowe pytanie brzmi: jak często będziesz wykonywać kwerendy przeciwko pojedynczemu zestawowi punktów.

Jeśli masz zamiar znaleźć jeden punkt w zestawie jeden raz, to znaczy, że @ Lucian ma rację: równie dobrze możesz pozostawić punkty nie posortowane i wykonać liniowe wyszukiwanie, aby znaleźć właściwy punkt.

Jeśli wykonasz stosunkowo dużą liczbę zapytań przeciwko temu samemu zestawowi punktów, warto uporządkować dane punktów, aby poprawić szybkość zapytań. @izomorphius wspomniał już o drzewie k-d, a to zdecydowanie dobra sugestia. Inną możliwością (wprawdzie bardzo podobną) jest drzewo oktowe. Pomiędzy tymi dwoma znajdujemy drzewo oktawowe, które jest nieco łatwiejsze do zrozumienia. Teoretycznie drzewo k-d powinno być nieco bardziej wydajne (średnio), ale nigdy nie widziałem dużej różnicy - choć być może przy różnych danych różnica byłaby znacząca.

Należy jednak zauważyć, że budowanie czegoś takiego jak drzewo k-d lub drzewo-oktawa nie jest wolne, więc nie trzeba wykonywać zbyt wielu zapytań dotyczących zestawu punktów, aby uzasadnić jego budowę. Jedno zapytanie wyraźnie tego nie usprawiedliwia, a dwa prawdopodobnie też nie będą - ale wbrew temu, co sugeruje Luchian, O (N log N) (tylko na przykład) nie jest bardzo powolny. Z grubsza rzecz biorąc, log (N) to liczba cyfr w liczbie N, więc O (N log N) nie jest tak naprawdę dużo wolniejsza niż O (N). To z kolei oznacza, że ​​nie potrzebujesz szczególnie dużej liczby zapytań, aby usprawnić organizowanie danych, aby przyspieszyć każdą z nich.

Answer 4

można spróbować użyć QuadTree http://en.wikipedia.org/wiki/Quadtree

lub coś podobnego.