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

У меня есть набор треугольников, и я хочу найти ближайший треугольник к произвольной точке пространства.

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

Моя проблема в том, что структуры, которые я изучал (rtree, kdtree), используют ограничивающие рамки для сужения поиска, но во многих случаях ближайшие ограничивающие рамки не обязательно соответствуют ближайшим треугольникам.

Вот один из таких случаев:

пример bbox

Обратите внимание, что синяя точка находится ближе всего к большому ограничивающему прямоугольнику, но ближе к маленькому зеленому треугольнику. Это заставляет меня чувствовать, что структуры данных, основанные на ограничивающих прямоугольниках, приведут к неверным результатам поиска... если только я не упустил что-то очевидное?

В целом, я ищу легковесное решение на С++ (так что никаких CGAL или других чудовищных пакетов) или просто точку в направлении правильного алгоритма, который мне следует изучить.

Спасибо!


c++ search kdtree
person Tyson    schedule 14.11.2015    source источник
comment
Подойдет любая структура данных/алгоритм пространственного разбиения: я предлагаю начать с фиксированных трехмерных сеток или октодеревьев. По сути, вы делите свое пространство на куски/ячейки, и чтобы найти треугольники, ближайшие к точке, вы просто выполняете вычисления расстояния со всеми треугольниками, которые находятся в том же куске/ячейке, что и точка. Это работает для чего угодно, не только для треугольников — могут быть оптимизированные структуры и алгоритмы для треугольников, но я о них не знаю.   -  person Vittorio Romeo    schedule 14.11.2015
comment
вы можете использовать ограничивающие рамки, чтобы сузить поиск до небольшого количества треугольников, а затем использовать грубую силу   -  person 463035818_is_not_a_number    schedule 14.11.2015
comment
@ tobi303 какие-нибудь рекомендации по эвристике, которая поможет сузить поиск? Как мне избежать проблемного случая в моем исходном сообщении?   -  person Tyson    schedule 14.11.2015

Ответы (2)


arrow_upward
2
arrow_downward

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

  • Найдите ближайшую ограничивающую рамку (скажем, в вашем примере она большая)
  • Пусть r — расстояние между точкой и ближайшей ограничивающей рамкой, а b — размер ограничивающей рамки. Найдите все ограничивающие прямоугольники, которые находятся ближе, чем (r+b) от точки.
  • Используйте грубую силу, чтобы найти ближайший треугольник среди оставшихся ограничивающих прямоугольников.
person 463035818_is_not_a_number    schedule 14.11.2015
comment
А, мне нравится идея с (r+b) ближайшим поиском. На данный момент я не могу вспомнить ни одного случая, когда это потерпит неудачу. Спасибо! - person Tyson; 14.11.2015
comment
@Tyson На самом деле (r + b) это слишком много, я думаю (r + 0,5 * sqrt (2) * b) достаточно, но я не уверен на 100%. - person 463035818_is_not_a_number; 14.11.2015

arrow_upward
0
arrow_downward

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

По сути, у вас будет что-то похожее на дерево k-d, где вместо разделения по оси вы можете разделить по произвольной плоскости (обычно на основе одного из существующих ребер в сцене).

Недостатком является то, что дерево, вероятно, будет строиться медленнее.

person Adam    schedule 14.11.2015