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.