Вычисление per-vertex (site) областей клеток Вороного непосредственно из триангуляции Делоне
Я хочу вычислить области ячеек Вороного, которые относятся к триангуляции Делоне для набора точек без явного преобразования триангуляции Делоне в граф Вороного. Так как меня интересуют только области ячеек Вороного, я хотел избежать затрат на явное построение структуры данных Вороного. Это возможно? Есть ли какая-либо связь между триангуляцией / кругами Делоне и областями двойных клеток Вороного? Спасибо,
Филипп
2 ответа
Вы можете использовать формулу Шнеласа, как только узнаете вершины ячейки Вороного против часовой стрелки. Это, однако, просто, поскольку триангуляция Делоне является двойственной к диаграмме Вороного: вершина Вороного двойственна треугольнику Делоне, и вершина находится в точке, равноудаленной от углов треугольника.
Поэтому, если вас интересует область ячейки Вороного точки p в наборе точек, то (i) рассмотрите все инцидентные треугольники Делоне T в направлении против часовой стрелки, (ii) вычислите локусы узлов Вороного и (iii) подключить в формулу шнурка.
Используя CGAL, здесь предоставляется решение для трехмерного случая:
https://lists-sop.inria.fr/sympa/arc/cgal-discuss/2011-01/msg00117.html