Алгоритм поиска k соседей в определенном диапазоне?

Question

Предположим, что облако точек имеет 50 000 точек в пространстве x-y-z 3D. Для каждой точки этого облака, какие алгоритмы или строгие данные должны быть реализованы, чтобы найти k соседей данной точки, которые находятся на расстоянии [R, r]? Наивный способ состоит в том, чтобы пройти каждый из 49 999 пунктов для каждой из 50 000 точек и выполнить метрическое тестирование. Но этот подход займет много времени. Точно так же, как есть kd tree, чтобы найти ближайшего соседа за небольшую паузу, так есть ли реализация DS/algo в реальном времени там, чтобы предварительно обработать облака точек, чтобы достичь цели в кратчайшие сроки?

Answer 1

Ваша проблема связана с темой Nearest Neighbor Search, или, точнее, k-Nearest Neighbor Search. Ответ на ваш вопрос зависит от структуры данных, которую вы используете для хранения баллов. Если вы используете R-trees или такие варианты, как R*-trees, и вы выполняете несколько поисков в своей базе данных, вы, вероятно, найдете значительное улучшение производительности в двух или трехмерном пространстве по сравнению с наивным линейным поиском. В более высоких измерениях схемы разбиения пространства имеют тенденцию к ухудшению линейного поиска.

Answer 2

Если вы используете обычную евклидову метрику, вы можете пройти через список три раза и извлечь те точки, которые внутри R в каждом измерении, по существу извлекая охватывающий куб. Поиск в результирующем списке все равно будет O (n^2), но на гораздо меньшем n.

Answer 3

Существуют эффективные алгоритмы (в среднем, для случайных данных), см. Nearest neighbor search.

Ваш подход не эффективен, но прост.

Прочтите, проверьте требования и вернитесь, чтобы мы могли помочь.

Answer 4

Как уже упоминалось, для поиска NN вы можете использовать какой-либо древовидный алгоритм, например k-d-tree. Существуют версии, доступные для всех языков программирования.

Если ваше описание [R,r] предлагает полый шар, вы должны сравнить одноразовое тестирование (в пределах интервала) по сравнению с двумя этапами (тест-для-внешний и удаление образцов, которые проходят тест-для-внутреннего).

Вы также не указали требования к производительности (время или частоту кадров?) И ваше предполагаемое приложение (допустимый подход?).