Struktura danych najbliższego sąsiada dla przestrzeni konfiguracyjnej innej niż euklidesowa

Próbuję zaimplementować strukturę najbliższego sąsiada do użycia w narzędziu do planowania ruchu RRT. Aby zrobić coś lepszego niż liniowe wyszukiwanie najbliższego sąsiada z użyciem brutalnej siły, chciałbym zaimplementować coś w rodzaju drzewa kd. Wydaje się jednak, że klasyczna implementacja drzewa kd zakłada, że ​​każdy wymiar przestrzeni można podzielić na „lewy” i „prawy”. Pojęcie to nie wydaje się mieć zastosowania na przykład do przestrzeni innych niż euklidesowe, takich jak SO (2).

Pracuję z szeregowym ramieniem manipulatora z w pełni obrotowymi łącznikami, co oznacza, że ​​każdy wymiar przestrzeni konfiguracyjnej robota to SO (2), a zatem nie-euklidesowy. Czy można zmodyfikować algorytm drzewa KD, aby obsługiwał tego rodzaju podprzestrzenie? Jeśli nie, to czy istnieje inna struktura najbliższego sąsiada, która może obsługiwać te nie-euklidesowe podprzestrzenie, a jednocześnie jest łatwa do aktualizacji i wyszukiwania? Spojrzałem również na FLANN , ale z ich dokumentacji nie było dla mnie jasne, czy mogą one obsługiwać nie-euklidesowe podprzestrzenie.

Masz rację, że drzewa kd zwykle działają tylko w małych, euklidesowych przestrzeniach metrycznych. Ale jest dużo pracy dla ogólnych aplikacji najbliższych sąsiadów w przestrzeniach metrycznych (gdziekolwiek można zasadniczo zdefiniować funkcję odległości).

Klasyczna praca dotyczy drzewek kulowych , które następnie uogólniono na drzewa metryczne .

Istnieje kilka nowszych prac zwanych drzewami okładkowymi, które mają nawet kod GPL. Od ponad dwóch lat chciałem przyjrzeć się charakterystyce wydajności tych drzew i drzew KD.

Mam nadzieję, że pasuje do twojej aplikacji.

$sqrt(N)$próbki w wyszukiwaniu. Zostało to zaimplementowane w OMPL, patrz ompl::NearestNeighborsSqrtApprox< _T >Odwołanie do szablonu klasy .

Zmniejsza to złożoność do $O(sqrt(N))$.