Алгоритмы построения триангуляции Делоне

      Помимо оптимальной и жадной триангуляции, также широко известна триангуляция Делоне, обладающая рядом важных практических свойств.
      Говорят, что триангуляция удовлетворяет условию Делоне, если внутрь окружности, описанной вокруг любого построенного треугольника, не попадает ни одна из заданных точек триангуляции.
      Триангуляция является триангуляцией Делоне, если она является выпуклой и удовлетворяет условию Делоне (рис. 12).

Рис. 12. Триангуляция Делоне

 

      Говорят, что пара соседних треугольников триангуляции удовлетворяет условию Делоне, если этому условию удовлетворяет триангуляция, составленная только из этих двух треугольников.
      Говорят, что треугольник удовлетворяет условию Делоне, если этому условию удовлетворяет триангуляция, составленная только из этого треугольника и трёх его соседей (если они существуют).
      Триангуляция Делоне определяется как граф, двойственный диаграмме Вороного - одной из базовых структур вычислительной геометрии.
      Для заданной точки Р_i Î {P₁, ... Р_n } на плоскости многоугольником ячейкой) Вороного называется геометрическое место точек на плоскости, которые находятся к Р_i ближе, чем к любой другой задан­ной точке P_i, j ≠ i.
      Совокупность многоугольников Вороного образует разбиение плоскости, представляющее векторную сеть.
      Диаграммой Вороного заданного множества точек {Р₁, ... P_n) на­зывается совокупность всех многоугольников Вороного этих точек (рис. 13, а).
      Диаграммы Вороного также иногда называют разбиением Тиссена и ячейками Дирихле.
      Одним из главных свойств диаграммы Вороного является её двойственность триангуляции Делоне (рис. 14). А именно, соеди­нив отрезками тс исходные точки, чьи многоугольники Вороного соприкасаются хотя бы углами, мы получим триангуляцию Делоне (рис. 13, б).

 

Рис. 13. Диаграммы Вороного: а – пример диаграммы; б – двойственная диаграмме триангуляция Делоне

Рис. 14. Граф, двойственный диаграмме Вороного

Рис. 15. Перестроение треугольников, не удовлетворяющих условию Делоне

      Многие алгоритмы построения триангуляции Делоне исполь­зуют следующую теорему: триангуляцию Делоне можно получить из любой другой триангуляции по той же системе точек, последова­тельно перестраивая нары соседних треугольников ΔАВС и ΔBCD, не удовлетворяющих условию Делоне, в пары треугольников ΔABD и ΔACD (рис. 15). Такая операция перестроения также часто называ­ется флипом.
      Исходя из данной теоремы, как вы считаете, можно ли построить триангуляцию Делоне по некоторой триангуляции путем последова­тельного улучшения её до выполнения условия Делоне?
      При проверке условия Делоне для пары соседних треугольников можно использовать непосредственно определение условия Делоне, а также другие способы, основанные на следующих теоремах.
      - триангуляция Делоне обладает максимальной суммой мини­мальных углов всех своих треугольников среди всех возможных три­ангуляции;
    - триангуляция Делоне обладает минимальной суммой радиусов окружностей, описанных около треугольников, среди всех возмож­ных триангуляции.
      В данных теоремах фигурирует некая суммарная характеристика всей триангуляции (сумма минимальных углов или сумма радиусов), оптимизируя которую в нарах смежных треугольников, можно полу­чить триангуляцию Делоне.
      На практике обычно используют несколько способов проверки ус­ловия Делоне для заданной пары треугольников:

1. Проверка через уравнение описанной окружности.
2. Проверка с заранее вычисленной описанной окружностью.
3. Проверка суммы противолежащих углов.

      Рассмотрим подробнее каждый из них.
      1. Проверка через уравнение описанной окружности. Уравнение окружности, проходящей через точки (х₁,у₁), (х₂,у₂), (х₃,у₃) можно записать в виде:

     Как вы считаете, можно ли заменить данную формулу следующей: (x²+y²) · a – x · b + y · c –d = 0, где

     Тогда условие Делоне для любого заданного треугольника Δ((х₁,у₁), (х₂,у₂), (х₃,у₃)) будет выполняться тогда и только тогда, когда для любого узла (х₀,у₀) триангуляции верно ((x₀²+y₀²) × a – x₀ × b + y₀ × c – d) × sgn a≥ 0, т.е. когда (х₀,у₀) не попадает внутрь окружности, описанной вокруг треугольника Δ((х₁,у₁), (х₂,у₂), (х₃,у₃)).

     Для упрощения вычислений можно заметить, что если тройка точек (х₁,у₁), (х₂,у₂), (х₃,у₃) является правой (т.е. обход их в треугольнике выполняется по часовой стрелке), то всегда sgn a = –1, и наоборот, если тройка эта левая, то sgn а = 1.
     2. Проверка с заранее вычисленной описанной окружностью.
     Вычисляем для каждого построенного треугольника центр и радиус описанной вокруг него окружности, после чего проверка условия Делоне будет сводиться к вычислению расстояния до центра этой окружности и сравнению результата с радиусом. Таким образом, центр (х₀,у₀) и радиус г окружности, описанной вокруг треугольника Δ((х₁,у₁), (х₂,у₂), (х₃,у₃)), можно найти как:

где a, b, с, dопределены выше в (*).
     Тогда условие Делоне для треугольника Δ((х₁,у₁), (х₂,у₂), (х₃,у₃)) будет выполняться только тогда, когда для любой другой точки (х₀,у₀) триангуляции выполняется соотношение (х₀ – х_c)² + (у₀ – у_c)² ?r². Как вы считаете, какой знак должен связывать части данного соотношения?
      3. Проверка суммы противолежащих углов.
       Доказано, что условие Делоне для данного треугольника Δ((х₁,у₁), (х₂,у₂), (х₃,у₃)) будет выполняться только тогда, когда для любой другой точки (х₀,у₀) триангуляции α + β ≤ π (рис. 16).

 

Рис. 16. Проверка суммы противолежащих углов

     Это условие эквивалентно sin(α + β) ≥ 0, т.е.

Sin α . cos β + cos α . sin β ≥ 0. (**)

Значение синусов и косинусов углов можно вычислить через скалярные и векторные произведения соответствующих векторов:

     Подставьте эти значения в формулу (**) и сократите знаменатели дробей, какую формулу вы получили для проверки условия?

     Исходя из вышеизложенного, вам предлагается реализовать алго­ритм построения триангуляции Делоне. Правильность построенной конструкции предлагается доказать с помощью проверки условия Делоне одним из выбранных вами способов.