Мы поможем в написании ваших работ!
ЗНАЕТЕ ЛИ ВЫ?
|
Дуальность разбиений Вороного и Делоне
10.4 Дуальность разбиений Вороного и Делоне
Мы рассмотрели разбиения Вороного и Делоне по отдельности. Однако тот факт, что оба разбиения однозначно определяются системой {А}, говорит, что они сами однозначно определяют друг друга. Другими словами, если мы получили разбиение Вороного, то тем самым имеем полную информацию о разбиении Делоне, и наоборот. Как методом пустого шара, Делоне, так и с помощью плоскостей Вороного мы выявляем одну и ту же систему точек { D}. Действительно, согласно первому следствию теоремы 1, каждая вершина d в мозаике Вороного расположена на одинаковом расстоянии от четырех точек системы. Но это означает, что данная четверка лежит на сфере с центром в выбранной вершине d. Эта сфера является тем пустым шаром Делоне, который определяет соответствующий симплекс Делоне. Можно рассуждать в обратном порядке. Точка d из системы { D}, определенная с помощью пустого шара, лежит, по построению, на одинаковом расстоянии от своей четверки точек из {А}, но такая точка является общей для всех плоскостей Вороного данной четверки точек, а поэтому является общей вершиной их многогранников Вороного.
Рис. 10.5.Разбиение Вороного—Делоне для двумерной системы точек. Сплошными линиями нарисована мозаика Вороного, пунктирными — мозаика Делоне.
10.5 Алгоритм построения тетраэдризации Делоне
Реализованный в данной работе алгоритм строит тетраэдеризацию Делоне в пространстве (алгоритм триангуляции Делоне на плоскости можно получить путём относительно несложной адаптации данного, поэтому далее речь пойдёт только о 3D случае). Алгоритм относится к итерационным алгоритмам построения триангуляции (сначала строится первый тетраэдр, а затем к структуре по одной добавляются точки, которые образуют с уже полученной структурой новые тетраэдры). На каждом шаге алгоритма локализация следующей точки происходит методом «вкатывания шара».
Алгоритм Вороного работает на уже построенном разбиении Делоне, используя дуальность этих разбиений. Алгоритм основан на том свойстве, что вершины ячеек Вороного совпадают с центрами сфер, описанных вокруг каждого из тетраэдров Делоне. После нахождения центров описанных сфер, строится выпуклую оболочку, которая и будет ячейкой Вороного. Выпуклая оболочка строится методом «заворачивания подарка».
|
