Расчет диаграммы Вороного для самолетов в 3D

Question

Существует ли код / ​​библиотека, которая может рассчитать диаграмму Вороного для плоскостей (параллелограммов) в 3D?Я проверил Qhull, и кажется, что он может работать только с точками, в его примерах Voro ++ работает с сферами разного размера, но я ничего не мог найти для полигонов.

На этом изображении (образцы плоскостей в 3d) параллелограммы являются трехмерными, поскольку имеют толщину, но в этом случае толщина будет равна нулю.!

Answer 1

Клетки Вороного не являются параллелограммами. Вы смущены здесь изображением, которое вы разместили. Границы ячейки Вороного являются частями гиперплоскостей, разделяющих отдельные средства.

Посетите этот сайт, где обсуждаются и визуализируются трехмерные диаграммы вороной:

http://www.wblut.com/2009/04/28/ooh-ooh-ooh-3d-voronoi/

Чтобы вычислить клетки вороной, обычным способом является сначала построение триангуляции Делоне. Есть несколько алгоритмов, чтобы сделать это в 2D, в то время как в 3D это становится значительно более сложным. Но вы все равно должны быть в состоянии найти что-то. qhull может быть правильный путь.

Если у вас есть триангуляция Делоне, вычислите центр каждого тетраэдра. Это углы многоугольников, которые вам нужно нарисовать. Для любого ребра в триангуляции Делоне нарисуйте многоугольник, соединяющий соседние центры. Это должна быть гиперплоскость. Теперь все, что вам нужно сделать, это также нарисовать Гиперплоскости для ребер, которые являются частью выпуклой оболочки. Для этого вам нужно продолжить гиперплоскости, которые у вас уже должны быть, изнутри до бесконечности снаружи.

Я настоятельно рекомендую сначала начать с 2d. Если у вас есть рабочий код для 2D, посмотрите, как сделать то же самое в 3D. Это уже довольно сложно в 2D, если вы хотите, чтобы это было быстро.

Это рисунок из Википедии, отображающий диаграммы Делоне и Вороного:

Черные линии - триангуляция Делоне. Коричневые линии ортогональны этому и образуют диаграмму Вороного. Триангуляция Делоне может использоваться для различных интересных визуализаций: вычисления выпуклой оболочки, диаграмм вороного и альфа-форм: http://www.cgal.org/Manual/latest/doc_html/cgal_manual/Alpha_shapes_3/Chapter_main.html

Answer 2

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

Некоторое время назад была также японская газета, которая утверждала, что использует другой подход для разрешения этих ситуаций, начиная с триангуляции Делоне.и выработка клеток вороной из этого, но это тоже было ошибочным.Должно быть, приятно быть исследователем, придумывая широкие линейки алгоритмов и позволяя научным сотрудникам беспокоиться о деталях ...