Структура данных ближайшего соседа для неевклидового пространства конфигурации

15

Я пытаюсь реализовать структуру ближайшего соседа для использования в планировщике движения RRT. Чтобы сделать лучше, чем линейный поиск ближайших соседей, я хотел бы реализовать что-то вроде kd-дерева. Тем не менее, кажется, что классическая реализация дерева kd предполагает, что каждое измерение пространства может быть разделено на «левое» и «правое». Это понятие, кажется, не относится к неевклидовым пространствам, таким как, например, SO (2).

Я работаю с рычагом последовательного манипулятора с полностью вращающимися звеньями, что означает, что каждое измерение пространства конфигурации робота является SO (2) и, следовательно, неевклидовым. Можно ли изменить алгоритм дерева kd для обработки таких подпространств? Если нет, есть ли другая структура ближайшего соседа, которая может обрабатывать эти неевклидовы подпространства, в то же время проста для обновления и запроса? Я также взглянул на FLANN , но из их документации мне не было ясно, могут ли они обрабатывать неевклидовы подпространства.

giogadi
источник
Кстати, примерные ближайшие соседи тоже хороши (даже предпочтительнее, если ускорение значительно)
giogadi
1
Несмотря на то, что вы приняли отличный ответ, обычно рекомендуется подождать несколько дней, прежде чем принимать ответ, чтобы не препятствовать дальнейшим ответам, которые могут предоставить другие варианты.
Марк Бут
Спасибо Марк, я был на самом деле не уверен, как долго ждать, прежде чем принять ответ.
Джогади

Ответы:

6

Вы правы, что kd-деревья обычно работают только в небольших евклидовых метрических пространствах. Но есть много работы для общих приложений ближайших соседей в метрических пространствах (где угодно вы можете определить функцию расстояния по существу).

Классическая работа посвящена деревьям шаров , которые затем были обобщены до метрических деревьев .

Существует более новая работа, называемая деревьями покрытия, в которой даже есть код под GPL. Я хотел изучить характеристики производительности между этими деревьями и деревьями kd уже более двух лет.

Надеюсь, это подходит для вашего приложения.

Крис Мэнсли
источник
Извините, что отказался; просто следуя совету другого комментатора, чтобы дать этот вопрос еще несколько дней, чтобы "тушить". Я действительно нашел ваш ответ полезным, хотя!
Джогади
Booo. Просто шучу. Я просто счастлив, что вы нашли это полезным.
Крис Мэнсли