Построение тетраэдров из множества случайных точек - тетраэдризация
У меня есть набор точек (1 миллион из них, возможно, больше в будущем, например, 10 или 100 миллионов) в трехмерном пространстве, которые образуют сферу (они заполняют сферу - они не только на поверхности), и я хотел бы построить тетраэдры, которые соединяют каждую сферу с ее первыми соседями... Пока я искал тетраэдризацию, все, что я нашел, это:
- алгоритмы для создания сетки, но они заполняют пустые места, насколько я понимаю, тогда как мои точки фиксированы.
- алгоритмы для просмотра поверхности, что совершенно неактуально
- алгоритмы просмотра 3D-изображений (в основном в области медицины): что ближе, но не совсем подходит.
Как я могу это сделать?
2014-08-09 Прежде всего, спасибо всем за ваши предложения! Я был - и все еще - в отпуске и просто проходил мимо, чтобы проверить, ответил ли кто-нибудь... Я не разочарован!!!!:-) Думаю, я сначала попробую CGAL, и посмотрю оттуда. У меня есть другие расчеты данных для того же набора точек в O(n2), которые, как я ожидаю, будут длиться около 1 недели, поэтому несколько часов не будут такими уж плохими. Минуты станут мечтой!
2 ответа
Похоже, вы ищете алгоритм триангуляции Делоне в 3-мерном пространстве.
Надеюсь, вы не против подождать некоторое время, потому что триангуляция Делоне в 100 миллионов точек займет довольно много времени.
У qhull есть n-мерная реализация Делоне, которую вы можете попробовать. Как и CGAL. Оба пакета будут вычислять триангуляцию Делоне по асимптотическому времени O(n log(n)), и CGAL может при соответствующем выборе геометрических ядер делать это численно устойчивым образом. (То есть он может автоматически переключаться на точную арифметику для тех вычислений, где неточная арифметика дает неопределенный результат.)
Я бы не советовал пытаться реализовать быструю триангуляцию Делоне самостоятельно, даже в двух измерениях. Страшные вещи могут произойти, когда вам нужно оценить предикаты по результатам арифметики.
Я использую tetgen для одного из моих проектов, чтобы сделать тетраэдризацию. Работает довольно хорошо и достаточно быстро