Изменения

Если же мы хотим вставить в диаграмму отрезок <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>.

[[Категория: Вычислительная геометрия]]