Предположим, я построил трехмерную триангуляцию Делоне из N точек. Теперь у меня есть точка запроса, и мне нужно найти тетраэдр триангуляции, который окружает точку запроса. Как это сделать максимально быстро? Я знаю об общих методах octtree и kdtree, но я надеялся, что есть быстрый метод, который использует тот факт, что тетраэдры не произвольны, а являются результатом трехмерного Делоне.
Я могу использовать VTK или CGAL или другую библиотеку C++, и код должен быть на C++.
Этот пример показывает, как использовать locate() для трехмерной триангуляции CGAL. Если вам нужно ускорить локацию, а не собственно построение, можно поставить параметр LP из Delaunay_triangulation_3 до CGAL::Fast_location.
Подсказка:
В методе Грина и Сибсона для 2D Делоне они реализуют поиск ближайшего соседа, начиная с центра облака и следуя по краям триангуляции к цели. Для равномерного распределения точек это приводит к стоимости √N операций на поиск.
Я считаю, что этот принцип можно обобщить на тетраэдризации и он будет соответствовать стоимости ³√N. Не так хорошо, как log N, но в любом случае привлекательно. Если точки запроса не являются случайными, а остаются локализованными, запуск с предыдущей точки может еще больше сократить время запроса.
