Построение трехмерной диаграммы Вороного из трехмерной мозаики Делоне

Я пытаюсь преобразовать трехмерную мозаику Делоне (созданную с помощью TetGen) в диаграмму Вороного. Я знаю, что TetGen может создавать диаграммы Вороного, но мне нужно выполнить преобразование самостоятельно из-за необычных граничных условий.

Я совершенно озадачен этой двойственностью. У меня два из четырех:

  1. Каждой вершине Делоне соответствует одна ячейка Вороного (центр ячейки находится в вершине).
  2. Каждому тетраэдру Делоне соответствует одна вершина Вороного (центр тетраэдра находится в вершине).

Я знаю, что каждая грань Делоне соответствует одному ребру Вороного, и у меня есть вершины граней, но как мне получить из нее ребро Вороного?

Также каждому ребру Делоне соответствует одна грань Вороного, но опять же — как найти грань, соответствующую ребру?


3d voronoi delaunay tetgen
person zmbq    schedule 31.01.2015    source источник

Ответы (1)


arrow_upward
2
arrow_downward

Рассмотрим ребро в триангуляции Делоне. Предположим пока, что он не находится на выпуклой оболочке входных точек. Рассмотрим один тетраэдр, инцидентный этому ребру. Вы получаете первую точку двойного лица. Затем выберите один из двух треугольников в тетраэдре, инцидентный ребру. Пересеките его, и вы окажетесь внутри другого тетраэдра, который дает вам вторую точку грани. Если вы продолжите поворачивать край вот так (в том же направлении), вы вернетесь в первый тетраэдр и получите описание лица. Если ребро находится на выпуклой оболочке, вам нужно будет добавить лучи вместо сегментов при описании грани.

Обратите внимание, что если у вас есть более 3 косферических точек, некоторые тетраэдры будут соответствовать одной и той же двойной вершине Вороного.

person sloriot    schedule 01.02.2015