3622
правки
Изменения
м
→Инкрементальный алгоритм
[[Файл:voronoi-incremental.png|200px|thumb|right]]Храним диаграмму в РСДС. Пусть у нас уже есть диаграмма для точек <tex>p_1, p_2, ..., p_i</tex>. Добавим новый сайт <tex>p_{i+1}</tex>. Сначала найдём сайт <tex>p_j</tex>, в ячейку которого попадает <tex>p_{i+1}</tex>. После этого строим новую ячейку: сначала проведём серединный перпендикуляр для <tex>p_{i+1}p_j</tex>, он пересечёт границу ячейки <tex>\mathcal{V}(p_j)</tex> с ячейкой <tex>\mathcal{V}(p_k)</tex>; на следующем шаге будем строить серединный перпендикуляр для <tex>p_{i+1} p_k</tex> и так далее.
[[Файл:voronoi-update-dcel.png|400px|thumb|left]]В процессе построения перпендикуляров необходимо обновлять РСДС. Каждый раз, когда новое ребро <tex>e</tex>, порождаемое <tex>p_{i+1}</tex> и <tex>p_j</tex>, пересекает существовавшее ранее ребро <tex>e'</tex>, создаются создаётся новая вершина <tex>v</tex> и начинается новое ребро <tex>e+1</tex>.
* для ребра <tex>e</tex> в РСДС конец в вершине <tex>v</tex>, следующее ребро — <tex>e'</tex>, инцидентные грани — слева <tex>\mathcal{V}(i+1)</tex>, справа — <tex>\mathcal{V}(j)</tex>;
