Введение ограничения в триангуляцию Делоне с ограничениями

Одним из шагов при вставке ограничения в триангуляцию Делоне с ограничениями является повторная триангуляция оставшейся полости путем удаления треугольников, пересекаемых ограничением.

На следующем изображении ограничение u (A-F) вставляется в триангуляцию и пересекает треугольники, выделенные синим цветом. Таким образом, синяя область подвергается ретриангуляции. Треугольники синего цвета должны быть удалены из триангуляции

Это означает, что треугольники, выделенные синим цветом, будут удалены из триангуляции, и будут добавлены новые треугольники, чтобы заполнить дыру, оставшуюся после удаления этих треугольников. Только эти новые треугольники будут иметь ребро AF (которое является ограничением u) Треугольники зеленого цвета — это новые треугольники после вставки ограничения u.

Предполагая, что триангуляция была делоне перед вставкой ограничения u (за исключением других ребер с ограничениями) и что треугольники зеленого цвета сами по себе делоне (ни одна вершина зеленого многоугольника не находится внутри круга любого другого зеленого треугольника), нужно ли переворачивать ребра быть проверены/выполнены на ребрах, соединяющих зеленые треугольники с красными треугольниками? Или есть какая-то приличия, которая гарантирует, что не произойдет переворота края?

Другими словами, возможно ли, что вершина вне полости стала внутри одной из окружностей новых треугольников? (Обратите внимание, что такая вершина ранее не находилась внутри какой-либо другой окружности, потому что ранее она была Делоне).

Или, говоря простым языком, нужно ли проверять/выполнять переворот ребер на ребрах резонатора после его ретриангуляции?

Справочный документ, использованный для CDT: https://infoscience.epfl.ch/record/100269/files/Kallmann_and_al_Geometric_Modeling_03

Обратите внимание, что изображения были сделаны вручную с использованием GeoGebra, а не фактического кода триангуляции, а это означает, что треугольники на изображении могут выглядеть не так, как дело. Кроме того, на рисунках показана только часть триангуляции для наглядного примера.


person MathiasDG    schedule 30.06.2016    source источник
comment
Комментарии к вашей заметке о GeoGebra. Используя ipe и CGAL-Ipelets (doc.cgal.org/latest/CGAL_ipelets/index.html#title3) позволит вам создавать изображения CDT.   -  person sloriot    schedule 30.06.2016


Ответы (2)


Я так не думаю. Переворот края зависит только от отсортированных точек по часовой или против часовой стрелки.

person Gigamegs    schedule 30.06.2016

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

Я не читал об этом ни в одной статье и не видел ни в одном коде, поэтому я подозреваю, что все еще могу ошибаться.

person MathiasDG    schedule 02.07.2016