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

Question

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

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

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 запросов точки смещаются, и делается несколько (не так много!) Вставок и удалений. векторы смещения очень малы по сравнению с ограничительной рамкой всех точек

Answer 1

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

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

Answer 2

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

void vtkAbstractPointLocator :: FindPointsWithinRadius (
двойной R, двойной х, двойной у, двойной z, vtkIdList * result
)

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

Answer 3

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

Answer 4

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

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

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

Answer 5

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

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

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

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

Answer 6

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