Всем привет.
В статье Скворцова про алгоритмы триангуляции предлагается два способа перестроек (при попадании новой точки внутрь триангуляции) при НЕвыполнении условия Делоне:
1) "удаляй и строй". Т.е. никаких перестроек не производится, а вместо этого из триангуляции удаляются все треугольники (близлежащие к новой точке) НЕудовлетворяющие условию Делоне, и на образовавшемся месте строятся новые путем соединения ребрами новой точки и всех точек, ставших "границей" после удаления треугольников.

2) производятся перестройки методом флипа спаренных треугольников.

Вопрос чисто практический. Какой из этих способов более эффективен?

PS: и если 2) лучше, то как производить перестройку? Может ли одна и таже пара треугольников "флипаться" более одного раза?

A>В статье Скворцова

A>Вопрос чисто практический. Какой из этих способов более эффективен?
Там вроде внизу было написано сравнение же?

Здравствуйте, W0nder, Вы писали:

A>>В статье Скворцова

A>>Вопрос чисто практический. Какой из этих способов более эффективен?
W>Там вроде внизу было написано сравнение же?
ДА. это хорошо.
Но в статье прямо сказано, что наибольший вклад в скорость вностит процедура "поиска треугольника", а не способ перестройки при невыполнении условия Делоне.
Т.е. мне нужны практические советы какой способ лучше и как реализовывается 2)... (Там получается могут быть и зацикливания флипов до бесконечности?)

Здравствуйте, piAnd, Вы писали:


A>Т.е. мне нужны практические советы какой способ лучше и как реализовывается 2)...
Имхо лучше флипать

A>(Там получается могут быть и зацикливания флипов до бесконечности?)
С какого пива?!

1) Из опыта практической реализации могу сказать,
что "удаляй и строй" реализуется сложнее (гораздо больше кода),
однако там можно немного сэкономить на скорости работы.
В целом рекомендую использовать метод флиппинга, т.к. его проще отладить.

2) Одна и таже пара флипаться не может дважды — это доказывается строго математически.

Скворцов.

Здравствуйте, W0nder, Вы писали:

W>Здравствуйте, piAnd, Вы писали:

W>Имхо лучше флипать
А можно чуть подробнее почему ИМХО лучше?

A>>(Там получается могут быть и зацикливания флипов до бесконечности?)
W>С какого пива?!
Не пинайте, но мне кажется может быть и такая ситуация:




На последнем рис.6 получается мы снова перестраиваем пару, с которой начинали...

А>2) Одна и таже пара флипаться не может дважды — это доказывается строго математически.
А>Скворцов.
Так то в математике, а реально могут же быть погрешности?! Или я гоню?

Чаднов.

Здравствуйте, piAnd, Вы писали:

Количество перестроений в худшем случае после вставки
треугольника и вправду может быть велико.
Но оно конечно, и меньше N (общего числа точек в триангуляции),
а в среднем равно 2,5 — 3,0 в зависимости от вида
распределения исходных данных.

Доказательство зацикливания и конечности тривиально.
Вводим параметр Ss = "сумма минимальных углов всех треугольников" или
Sr "сумма радиусов описанных окружностей всех треугольников".
После перестроения по условию Делоне Ss всегда возрастает,
а Sr всегда уменьшается (это легко доказывается и следует из
определения условия Делоне).
Т.к. эти параметры монотонно изменяются, следовательно, одна и та же
комбинация треугольников никогда не повторится, т.е.
возможность зацикливания исключена.
А т.к. количество всех возможных триангуляций на N точках конечно
(зависит по экспоненте от N), то и перестроения когда-то закончатся.

Здравствуйте, AlexSkvortsov, Вы писали:

AS>Доказательство зацикливания и конечности тривиально.
AS>Вводим параметр Ss = "сумма минимальных углов всех треугольников" или
AS>Sr "сумма радиусов описанных окружностей всех треугольников".
AS>После перестроения по условию Делоне Ss всегда возрастает,
AS>а Sr всегда уменьшается (это легко доказывается и следует из
AS>определения условия Делоне).
AS>Т.к. эти параметры монотонно изменяются, следовательно, одна и та же
AS>комбинация треугольников никогда не повторится, т.е.
AS>возможность зацикливания исключена.
Кажется понятно!
То есть по ходу перестановок Sr уменьшается И НЕ МОЖЕТ ДАЖЕ ЛОКАЛЬНО ВОЗРАСТИ?

AS>А т.к. количество всех возможных триангуляций на N точках конечно
AS>(зависит по экспоненте от N), то и перестроения когда-то закончатся.
Спасибо!!!