3D триангуляция Делоне: найти тетраэдр, заключающий в себе точку запроса

Question

Предположим, я построил трехмерную триангуляцию Делоне из N точек. Теперь у меня есть точка запроса, и мне нужно найти тетраэдр триангуляции, который охватывает точку запроса. Как это сделать максимально быстро? Мне известны общие методы ottree и kdtree, но я надеялся, что существует быстрый метод, который использует тот факт, что тетраэдры не произвольные, а скорее результат трехмерного делоне.

Я могу использовать VTK или CGAL или другую библиотеку C ++, и код должен быть на C ++.

Answer 1

Подсказка:

В методе Грина и Сибсона для 2D Делоне они осуществляют поиск ближайшего соседа, начиная с центра облака и следуя по краям триангуляции к цели. Для равномерных распределений точек это приводит к стоимости √N операций за поиск.

Я полагаю, что этот принцип может быть обобщен на тетраэдризации и будет соответствовать стоимости ³√N. Не так хорошо, как журнал N, но все равно привлекательно. Если точки запроса не являются случайными, но остаются локализованными, запуск с предыдущей точки может еще больше сократить время запроса.

Answer 2

В этом примере показано, как использовать функцию locate() для трехмерной триангуляции CGAL. Если вам нужно ускорить локацию, а не строительство, вы можете установить параметр LP из Delaunay_triangulation_3 в CGAL::Fast_location.