64
правки
Изменения
Нет описания правки
Если же <tex>S</tex> {{---}} это замкнутый отрезок <tex>t</tex>, то сначала вставляем конечные точки <tex>p'_t</tex> и <tex>p''_t</tex>, используя процедуру, описанную выше. Остаётся вставить открытый отрезок <tex>t^\circ</tex>. Так как <tex>p'_t</tex> и <tex>p''_t</tex> {{---}} соседи <tex>t^\circ</tex> в диаграмме <tex>V(\Sigma \cup \{p'_t, p''_t, t^\circ\})</tex>, <tex>t^\circ</tex> обязан конфликтовать с каким-нибудь ребром ячейки, соответствующей <tex>p'_t</tex> или <tex>p''_t</tex>. Таким образом, первый конфликт <tex>t^\circ</tex> с <tex>V_1(\Sigma \cup \{p'_t, p''_t\})</tex> можно найти, просматривая рёбра ячейки <tex>V(p'_t, \Sigma \cup \{p'_t, p''_t\})</tex> или <tex>V(p''_t, \Sigma \cup \{p'_t, p''_t\})</tex>, то есть, можно опустить шаг поиска ближайшего соседа. Остаётся найти всю область конфликтов, как и в случае с точкой.
===Случай сильно пересекающихся сайтов===
{|border="0" width="100%"
|Пусть <tex>p</tex> {{---}} точка, которая сильно пересекается с отрезком <tex>t_i</tex>, т.е. <tex>p \in t^\circ</tex>. Понятно, что <tex>t^\circ</tex> будет ближайшим соседом <tex>p</tex> в <tex>\Sigma</tex>. Пусть <tex>e'_i(p)</tex> и <tex>e''_i(p)</tex> {{---}} два ребра <tex>V(t^\circ, \Sigma)</tex>, которые пересекаются с нормалями к <tex>t</tex>, проведёнными из точки <tex>p</tex> (см. рисунок). Пусть <tex>v'_i(p)</tex> и <tex>v''_i(p)</tex> {{---}} точки пересечения нормалей с рёбрами <tex>e'_i(p)</tex> и <tex>e''_i(p)</tex> соответственно. Тогда алгоритм вставки точки <tex>p</tex> в диаграмму <tex>V(\Sigma)</tex> будет выглядеть следующим образом:
Начинаем с поиска ближайшего соседа <tex>N_\Sigma(p)</tex>. Если <tex>N_\Sigma(p) = p</tex>, то ничего не делаем. Если <tex>N_\Sigma(p)</tex> {{---}} точка, или отрезок, с которым <tex>p</tex> не пересекается, то запускается процедура вставки, которая была описана выше. Иначе <tex>N_\Sigma(p) = t_i^\circ</tex> {{---}} отрезок, пересекающийся с <tex>p</tex>. Сначала добавляем <tex>p</tex> в <tex>\Sigma</tex> и заменяем <tex>t_i^\circ</tex> двумя отрезками <tex>p'_ip</tex> и <tex>pp''_i</tex>, где <tex>p'_i</tex> и <tex>p''_i</tex> {{---}} конечные точки <tex>t_i</tex>. Затем ищем рёбра <tex>e'_i(p)</tex> и <tex>e''_i(p)</tex>, разбиваем их в точках <tex>v'_i(p)</tex> и <tex>v''_i(p)</tex> и добавляем отрезки <tex>v'_i(p)p</tex> и <tex>v''_i(p)p</tex> в диаграмму.
||[[Файл:strongly_intersect.png|300px|thumb|right]]
|}
Если же мы хотим вставить в диаграмму отрезок <tex>t</tex>, то вставляем сначала его крайние точки <tex>p'_t</tex> и <tex>p''_t</tex>. Затем, начиная с <tex>p'_t</tex>, ищем первый конфликт <tex>t^\circ</tex> с текущей диаграммой Вороного и ищем всю область конфликтов. Во время этого поиска, прежде чем тестировать ребро Вороного <tex>e</tex> существующей диаграммы на потенциальный конфликт, мы проверяем, не пересекается ли <tex>t^\circ</tex> с одним из сайтов, связанных с <tex>e</tex>. Если такой сайт <tex>S_i</tex> найден, то поиск останавливается. Если <tex>S_i</tex> {{---}} точка, <tex>p_i</tex>, то вставляем отрезки <tex>p'_tp_i</tex> и <tex>p_ip''_t</tex> рекурсивно. Если <tex>S_i</tex> {{---}} отрезок <tex>t^\circ_i</tex>, то сначала проверяем, не принадлежит ли один из <tex>t^\circ</tex>, <tex>t^\circ_i</tex> другому. Если так и есть, то прекращаем работу, иначе вычисляем точку пересечения <tex>p_+</tex> отрезков <tex>t^\circ</tex> и <tex>t^\circ_i</tex>, вставляем её в диаграмму, а затем рекурсивно вставляем отрезки <tex>p'_tp_+</tex> и <tex>p_+p''_t</tex>.
[[Категория: Вычислительная геометрия]]
