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

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

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

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