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