355
правок
Изменения
→Вставка точки, лежащей внутри триангуляции
=== Вставка точки ===
==== Вставка точки, лежащей внутри триангуляции ====
Для начала локализуемся: поймём, в каком фейсе лежит точка (или на каком ребре). Вставляем Если точка лежит внутри фейса, добавляем три ребра, сам фейс превращаем в один из новых смежных с вставляемой точкой и добавялем ещё два фейса. Если же точка лежит на ребре, два смежных с ребром фейса превращаем в два новых, добавляем ещё два, а так же превращаем ребро, на которое вставляется точка, в ребро, которое заканчивается в этой точке, и вставляем три новых. Итого у нас появилось несколько новых рёбер. Они все хорошие ({{TODO|t=Доказать, почему}}), плохими могут оказаться только рёбра, противолежащие вставленной точке. Флипаем рёбра, пока триангуляция не станет хорошей.
Среднее число флипов — <tex>O(1)</tex> ({{TODO|t=Доказать, почему}}). Поэтому время вставки целиком зависит от времени локализации.
==== Вставка точки, лежащей снаружи триангуляции ====
Представим, что вне триангуляции — бесконечные треугольники, основания которых — рёбра выпуклой оболочки триангуляции, а противолежащая ребру вершина — это бесконечно удалённая точка. Тогда понятно, что вставка точки, не лежащей в триангуляции, сведётся к вставке точки внутрь триангуляции, если мы научимся обрабатывать бесконечные фейсы.
