Вычисление per-vertex (site) областей клеток Вороного непосредственно из триангуляции Делоне

Question

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

Philip

Answer 1

Вы можете использовать Формула шнурка , если знаете вершины ячейки Вороного против часовой стрелки.Это, однако, просто, так как триангуляция Делоне является двойственной диаграммы Вороного : вершина Вороного двойственна треугольнику Делоне, и вершина расположена в точке, равноудаленной от углов треугольника.

Итак, если вас интересует площадь ячейки Вороного точки p в наборе точек, то (i) рассмотрите все инцидентные треугольники Делоне T в направлении против часовой стрелки, (ii) вычислите локусы узлов Вороного,и (iii) подключиться к формуле шнурка.

Answer 2

Используя CGAL , здесь представлено решение для трехмерного случая:

https://lists -sop.inria.fr / sympa / arc / cgal-обсудить / 2011-01 / msg00117.html