Какая структура данных подходит для запроса "всех точек на расстоянии d от точки p",

У меня есть 3D pointcloud, и я бы хотел эффективно запросить все точки на расстоянии d от произвольной точки p (которая не обязательно является частью сохраненного pointcloud)

Запрос будет выглядеть примерно так:

Pointcloud getAllPoints(Point p, float d);

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

спасибо!

согласно предложению новолактократов, я пытаюсь определить желаемые функции структуры:

SearchStructure Create(Set<Point> cloud) 
Set<Point> Query(SearchStructure S, Point p, float maxDistance)
SearchStructure Remove(Point p)
SearchStructure Insert(Point p)
SearchStructure Displace(Set<Point> displacement) //where each value describes an offsetVector to the currently present points

Обычно, после n запросов, точки смещаются и вводятся несколько (не много!) вставок и исключений. векторы смещения очень малы по сравнению с ограничивающим блоком всех точек

Ответ 1

То, что вы хотите, это структура, которая разлагает пространство, чтобы определенные регионы могли быть найдены эффективно. Правильно разложенное octree или kD-дерево должно позволить вам сделать это хорошо, так как вы только "откроете" раздел дерева, содержащий вашу точку p, чтобы искать точки поблизости. Это должно позволить вам установить довольно низкую асимптотическую оценку того, сколько лишних очков вам нужно сравнить с расстоянием до (зная, что ниже уровня разложения все точки достаточно близки). К сожалению, я не знаю литературы в этой области достаточно хорошо, чтобы дать более подробные указания. Моя встреча с этими вещами связана с алгоритмом моделирования n-Body Barnes-Hut.

Здесь другой вопрос, тесно связанный с этим. И еще. И третий, указав структуру данных (Hilbert R-Trees), о которой я раньше не слышал.

Ответ 2

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

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

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

Ответ 3

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

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

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

Ответ 4

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

Ответ 5

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

Ответ 6

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

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

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

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