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

Здравствуйте! У меня возник вопрос касательно итеративного алгоритма триангуляции Делоне набора точек.

Кратко опишу алгоритм.

Вначале строится треугольник, покрывающий весь набор точек. После этого на каждом шаге, к полученной триангуляции добавляется новая точка p0. При этом вначале ищется треугольник T( в уже построенной на предыдущем шаге триангуляции), содержащий новую точку. Далее все вершины треугольника T, соединяются с вершинами T.Образуются новые 3 треугольника. После этого каждый полученный треугольник и смежный с ним проверяются на выполнение условия Делоне. На рис. это треугольники T1 и T2. Если оно не выполнено, то удаляется диагональ в четырехугольнике, который состоит из T1 и T2, и вставляется противоположная диагональ. После этого образуются треугольники T3 и T4.

Вопрос: нужно ли теперь проверять получившиеся треугольники(T3 и T4) на условие Делоне со смежными к ним трегольниками?Например, нужно ли проверять пару T3 и T5? Если да, то что будет, если пара T3 и T5 образуют невыпуклый четырехугольник?

Миниатюры

 

0

Да, нужно. Образуется "волна" - ведь смежные к смежным тоже нужно проверять и.т.д. Ну это недостаток такого подхода, хотя обычно волна затухает быстро.

0

Так а могут ли в таком процессе образовываться невыпуклые четырехугольники, когда проверяешь пару? Как на рисунке(T3 и T5)?

0

Сообщение от AlexBay Так а могут ли в таком процессе образовываться невыпуклые четырехугольники, когда проверяешь пару? Как на рисунке(T3 и T5)?

Может это и необязательно, но во всяком случае проще перед вычислением суммы углов (по Борису Николаевичу) проверить четырехугольник на выпуклость

1

Вот про то, могут ли образовываться такие углы или нет, я нигде ничего не нашел, поэтому и задался вопросом...Я в этом пока новичок!Во всяком случае спасибо!Буду пробовать=)

0