Вычисление расстояния от точки до триангуляции в 3D с помощью Matlab

Question

У меня есть трехмерное облако точек, которое я преобразовал в триангуляцию Делоне, используя функцию Матлаба DelaunayTri. Теперь у меня есть контрольная точка в 3D и я хочу вычислить в Matlab наименьшее расстояние между этой точкой и триангуляцией.

До сих пор я думал об использовании функции-члена nearNeighbor(...) класса DelaunayTri в Matlab, чтобы найти точку в триангуляции, ближайшую к моей контрольной точке, и затем вычислить расстояние между ними. Это что-то, но это не то, что я действительно хочу.

Самая близкая точка триангуляции к моей контрольной точке, в общем, не вершина триангуляции, а где-то на поверхности треугольника. Как я могу найти эту точку?

Спасибо!!!

Answer 1

Я написал инструмент point2trimesh для этой проблемы. Это своего рода решение "грубой силы", которое работает и для невыпуклых поверхностей.

Answer 2

Я написал коды для этих вещей, но их нет в Файлообменнике. Я могу быть убежден выдать их по прямой почте, хотя.

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

Итак, чтобы найти ближайшую точку на выпуклой триангуляции:

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

2. Вычислить ограничивающую окружность для каждого треугольного фасета поверхности. Это позволяет вам знать, когда прекратить проверку фасетов.

3. Получите расстояния до каждой точки на поверхности. Сортируйте каждый фасет по расстоянию до ближайшей точки этого фасета. Начните с поиска ближайшего аспекта в этом списке.

4. Вычислите расстояние до, по-видимому, ближайшего фасета, найденного на шаге 3. Простое решение можно найти с помощью программирования наименьшего расстояния (LDP), которое можно преобразовать в ограниченный линейный метод наименьших квадратов. У Лоусона и Хансона есть алгоритм для этого.

Повторяйте шаг 4 до тех пор, пока текущее наилучшее найденное расстояние не станет меньше расстояния, сравнивая его с любым из окружностей, начиная с шага 2. Эта петля будет действительно очень короткой, по крайней мере, для выпуклой оболочки. Для более общего невыпуклого корпуса из альфа-формы это может занять больше времени.

Вы также можете немного уменьшить пространство поиска, исключив из поиска фасеты, которые указывают ОТСУТСТВУЮТ от рассматриваемой точки. Используйте эти грани нормалей для этого теста.