418
правок
Изменения
Нет описания правки
Инициализация графа для тетраэдра тривиальна: для каждой точки определяем, какие грани видны из неё. Далее на каждом шаге после добавления точки <tex>p_r</tex> удалим из графа соответствующие удаляемым из выпуклой оболочки граням вершины и инцидентные им рёбра: просто удаляем все достижимые из <tex>p_r</tex> вершины. Также удалим вершину, соответствующую <tex>p_r</tex>. Далее добавляем новые грани выпуклой оболочки. Необходимо найти их конфликты. Сами грани представляют из себя треугольники, если, конечно, они не были смержены с уже имеющимися гранями. Во втором случае новая грань находится в конфликте с теми же точками, что и старая грань, т.к. смерженные грани копланарны.
[[Файл:3dconvexhullconflictlist.png|200px|thumb|left]]Перейдём к первому случаю. Пусть мы добавили точку <tex>p_r</tex> и рассматриваем грань <tex>f</tex>. <tex>e</tex> — ребро, принадлежащее horizon, <tex>f_1, f_2</tex> — грани, пересечение которых образовывало <tex>e</tex> в старой оболочке. Пусть <tex>p_t</tex> — ещё не добавленная точка, из которой видно <tex>f</tex>, тогда из неё видно и ребро <tex>e</tex>, причём как в новой, так и в старой выпуклой оболочке (так как новая включает в себя старую). Но это возможно, только если из <tex>p_t</tex> видно <tex>f_1</tex> или <tex>f_2</tex>. Значит, точки, с которыми у <tex>f</tex> есть конфликт — это только какие-то из точек, у которых есть конфликт у <tex>f_1</tex> и <tex>f_2</tex>.
