какая структура данных является соответствующей для запросов “всех точек на расстоянии d от точки p”

Я не понимаю ваш API, вы можете округлить все точки в PointCloud, которые лежат внутри произвольной сферы, но вы также говорите, что облака точек сохраняются? В этом случае разве вы не должны получить список PointCloud, который находится внутри данной сферы, иначе какой смысл (простите за каламбур) с сохранением PointCloud?

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

Я думаю, вам следует реализовать отбраковку ограничивающего прямоугольника с последующим более детальным поиском по сферам в качестве первой реализации. Возможно, это не такое узкое место, как вы думаете, и, возможно, вам придется учитывать гораздо более серьезные узкие места. Это'

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

Ну, это зависит от того, какие еще варианты использования вам нужны для структуры данных.

Вы можете получить список расстояний от точки p до других точек, упорядоченный по расстоянию, и сопоставить эти списки к точкам с помощью хэш-карты.

map:
p1 -> [{p2, d12}, {p4, d14}, {p3, d13}]
p2 -> ...
...

Вы можете найти точку на карте и перебирать список, пока расстояние не станет больше требуемого.

Вам нужна структура, которая разбивает пространство на части, чтобы можно было эффективно находить определенные области. Правильно разложенное октодерево или kD-дерево должно позволить вам сделать это хорошо, так как вы только «открываете» раздел дерева, содержащий вашу точку p искать точки поблизости. Это должно позволить вам установить довольно низкую асимптотическую границу того, сколько дополнительных точек вам нужно для сравнения расстояния (зная, что ниже некоторого уровня разложения все точки достаточно близки). К сожалению, я недостаточно хорошо знаю литературу в этой области, чтобы давать более подробные указания. Я столкнулся с этими вещами из алгоритма моделирования Барнс-Хат n-Body.

Вот еще один вопрос , тесно связанный с этим. И еще . И третий , упоминающий структуру данных (R-деревья Гильберта), о которой я раньше не слышал.

VTK может помочь:

void vtkAbstractPointLocator :: FindPointsWithinRadius (
двойной R, двойной х, двойной y, двойной z, vtkIdList * результат
)

Подклассы vtkAbstractPointLocator содержат различные структуры данных для ускорения поиска: обычные сегменты, kd-деревья и октодеревья.

Взгляните на Шаблон для задачи ближайшего соседа (Ларри Эндрюс из DDJ) . Это единственное 2D-изображение, имеющее сложность повторного вызова O (log n), но оно также может быть адаптировано для 3D.