Диаграмма Вороного

Эта статья находится в разработке!

Обозначения и определения

Сайт (site) — общее название для точки [math]p[/math] или замкнутого отрезка [math]t[/math].

[math]t^\circ[/math] — внутренняя часть отрезка. Внутренность точки — пустое множество.

Два замкнутых пересекающихся сайта слабо пересекаются (weakly intersect), если точка их пересечения не принадлежит их внутренностям, то есть они касаются концами.

Два сайта сильно пересекаются (strongly intersect), если точка их пересечения принадлежит внутренности хотя бы одного из данных сайтов.

Расстояние от точки [math]x \in \mathbb{E}^2[/math] до замкнутого сайта [math]S_i[/math]: [math]\delta(x, S_i) = \min{\{||x - y|| : y \in S_i\}}[/math].

Пусть [math]H_{ij} = \{x \in \mathbb{E}^2 : \delta(x, S_i) \le \delta(x, S_j)\}[/math]. Ячейка Вороного (Voronoi cell) [math]V(S_i, \Sigma)[/math] — множество точек, которые находятся ближе к [math]S_i[/math], чем к любому другому сайту, то есть [math]V(S_i, \Sigma) = \cap_{i \ne j}H_{ij}[/math]. Ячейки Вороного односвязны.

Ребро Вороного (Voronoi edge) — связное множество точек, принадлежащих пересечению ровно двух ячеек Вороного.

Вершина Вороного (Voronoi vertex) — точка, которая принадлежит хотя бы трём ячейкам Вороного.

Диаграмма Вороного (Voronoi diagram) [math]V(\Sigma)[/math] множества сайтов [math]\Sigma[/math] — разбиение плоскости на вершины, рёбра и ячейки Вороного.

1-каркас (1-skeleton) [math]V_1(\Sigma)[/math] — набор вершин и рёбер Вороного.

В процессе работы алгоритма множество сайтов, которые подаются на вход, может измениться. Чтобы различать начальное и конечное множество сайтов, будем обозначать входное множество через [math]\Sigma_I[/math], а множество сайтов, которые присутствуют на результирующей диаграмме Вороного, через [math]\Sigma[/math]. [math]\Sigma_I[/math] всегда состоит из замкнутых сайтов, а [math]\Sigma[/math] — из точек и открытых отрезков.

Пусть сайты [math]S_i[/math] и [math]S_j[/math] слабо пересекаются. Тогда битангентная окружность Вороного (bitangent Voronoi circle) [math]C_{ij}[/math] — окружность, касающаяся одновременно [math]S_i[/math] и [math]S_j[/math]. При рассмотрении трёх сайтов [math]S_i[/math], [math]S_j[/math] и [math]S_k[/math], окружность, касающаяся всех трёх сайтов, называется тритангентной окружностью Вороного (tritangent Voronoi circle). Точки, принадлежащие рёбрам Вороного, являются центрами битангентных окружностей, а вершины — тритангентных.

Рассмотрим [math]S \notin \Sigma_I[/math]. Будем говорить, что [math]S[/math] конфликтует с окружностью Вороного [math]C[/math], если [math]S[/math] пересекается с кругом, ограниченным [math]C[/math]. Также [math]S[/math] конфликтует с ребром [math]e \in V(S, \Sigma)[/math], если он пересекается с кругом, ограниченным одной из окружностей Вороного с центром в точке, принадлежащей [math]e[/math]. Область конфликтов (conflict region) [math]R_\Sigma(S)[/math] — множество точек 1-каркаса [math]V_1(\Sigma)[/math], соответствующих окружностям Вороного, которые конфликтуют с [math]S[/math].

Алгоритм

Рассмотрим сначала алгоритм для слабо пересекающихся сайтов, а потом обобщим его для случая сильно пересекающихся сайтов.

Случай слабо пересекающихся сайтов

Пусть мы уже построили диаграмму Вороного для некоторого множества [math]\Sigma[/math]. Рассмотрим процедуру вставки нового сайта [math]S[/math].

Алгоритм состоит из четырёх шагов:

1. Найти первый конфликт сайта [math]S[/math] с каркасом [math]V_1(\Sigma)[/math].

2. Найти всю область конфликтов сайта [math]S[/math] c каркасом [math]V_1(\Sigma)[/math].

3. Построить диаграмму Вороного для [math]\Sigma \cup \{S\} [/math].

4. Обновить локализационную структуру.

Пусть сайт [math]S[/math] — это точка [math]p[/math].

Теорема: Пусть [math]\Sigma[/math] — множество слабо пересекающихся сайтов, [math]p[/math] — точка, [math]p \notin \Sigma[/math]. Тогда [math]R_\Sigma(p)[/math] — связная кривая, содержащая более одной точки. Доказательство: [math]\triangleright[/math] Пусть [math]C = V(p, \Sigma \cup \{p\})[/math], [math]R_\Sigma(p) = \varepsilon[/math]. Заметим, что [math]\varepsilon = V_1(\Sigma) \cap C[/math]. Если бы область конфликтов [math]\varepsilon[/math] была пустой, то было бы верно [math]C \subset V(q, \Sigma \cup \{p\})[/math] для некоторого [math]q \in \Sigma[/math] и [math]V(q, \Sigma \cup p)[/math] не было бы односвязным. Пусть [math]\varepsilon_1, \varepsilon_2, ... , \varepsilon_k[/math] — связные компоненты [math]\varepsilon[/math] для некоторого [math]k[/math]. Предположим, что [math]k \ge 2[/math]. Тогда cуществует путь [math]P \subseteq C \setminus \varepsilon[/math], соединяющий две точки [math]x[/math] и [math]y[/math] на границе [math]C[/math] и отделяющий [math]\varepsilon_1[/math] от [math]\varepsilon_2[/math](см. рисунок). [math]P \cap \varepsilon = \varnothing \Rightarrow P \cap V_1(\Sigma) = \varnothing \Rightarrow P \subseteq intV(s, \Sigma)[/math] для некоторого [math]s \in \Sigma[/math]. [math]x, y \in P \Rightarrow[/math] все достаточно малые окрестности [math]U(x)[/math], [math]U(y)[/math] полностью содержатся в [math]V(s, \Sigma)[/math]. Значит, точки пересечения этих окрестностей с дополнением [math]C[/math] лежат в [math]V(s, \Sigma \cup p)[/math] и могут быть соединены путём [math]L \subseteq V(s, \Sigma \cup \{p\}) \subseteq V(s, \Sigma)[/math]. Следовательно, цикл [math]P \circ L[/math] полностью содержится в [math]V(s, \Sigma)[/math] и содержит [math]\varepsilon_1[/math] или [math]\varepsilon_2[/math] в своей внутренней части. Это противоречит тому, что [math]V(s, \Sigma)[/math] — односвязное множество, следовательно [math]k = 1[/math]. [math]\triangleleft[/math]

Таким образом, для нахождения области конфликтов, можно найти одно конфликтующее ребро, а затем, при помощи DFS, найти все остальные.

Первый шаг алгоритма начинается с поиска ближайшего соседа [math]N_\Sigma(p)[/math] точки p среди сайтов [math]\Sigma[/math] (если есть несколько ближайших, то подойдёт любой из них). Либо [math]N_\Sigma(p)[/math] и [math]p[/math] — это одна и та же точка, и ничего делать не нужно, либо [math]p[/math] конфликтует хотя бы с одним ребром, принадлежащим границе ячейки [math]V(N_\Sigma(p))[/math]. Тогда первый шаг завершается рассмотрением границы [math]V(N_\Sigma(p))[/math] и возвращением одного из рёбер, конфликтующих с [math]p[/math]. Как было сказано раньше, второй шаг — DFS по рёбрам [math]V_1(\Sigma)[/math] с целью найти все рёбра, конфликтующие с точкой [math]p[/math]. После того, как мы узнали [math]R_\Sigma(p)[/math], третий шаг будет заключаться в создании новой ячейки Вороного, имеющей границу [math]R_\Sigma(p)[/math].