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

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

Определения

Неформальное определение

Пример диаграмы Вороного

Есть множество точек [math]P[/math] на плоскости. Для всех точек [math]q \notin P[/math] этой плоскости узнаем ближайшую к [math]q[/math] точку из [math]P[/math]. Таким образом получим разбиение плоскости на кусочки, в каждом из которых содержится одна точка [math]p_i[/math] из [math]P[/math] и все точки [math]q[/math], для которых [math]p_i[/math] — ближайшая среди точек из [math]P[/math].

Формальное определение

[math]P = \{ p_1, p_2, ..., p_n\}[/math] — множество точек на плоскости. Назовём их сайтами (site).

Определение:

Диаграмма Вороного (Voronoi diagram, [math]Vor(P)[/math]) для сайтов [math]P = \{ p_1, p_2, ..., p_n\}[/math] на плоскости — это разбиение плоскости на [math]n[/math] ячеек (ячейка Вороного, Voronoi cell, [math]\mathcal{V}(p_i)[/math]), по одной для каждого сайта, которые обладают свойством: [math]\rho(q, p_i) \lt \rho(q, p_j)[/math] для всех [math]p_j \in P, \ j \neq i[/math].

В зависимости от контекста будем называть диаграммой Вороного как разбиение на ячейки, так и составляющие эти ячейки вершины и рёбра.

Свойства

Возьмём две точки плоскости: [math]p[/math] и [math]q[/math]. Проведём серединный перпендикуляр к отрезку [math]pq[/math]; полученную полуплоскость, которая содержит в себе [math]p[/math], обозначим [math]h(p, q)[/math], другую — [math]h(q, p)[/math]. Заметим, что [math]r \in h(p, q)[/math] тогда и только тогда, когда [math]\rho(r, p) \lt \rho(r, q)[/math]. Отсюда вытекает следующее:

Утверждение:

[math]\mathcal{V}(p_i) = \cap_{1 \leqslant j \leqslant n, j \neq i} h(p_i, p_j)[/math]

Отсюда получаем, что что ячейка Вороного — это пересечение [math]n - 1[/math] полуплоскостей, и поэтому представляет собой (возможно, неограниченную) открытую выпуклую область с не более чем [math]n - 1[/math] вершинами и [math]n - 1[/math] рёбрами.

Теорема:

Пусть [math]P[/math] — множество из [math]n[/math] сайтов. Если они все лежат на одной прямой, то [math]Vor(P)[/math] представляет собой [math]n - 1[/math] параллельную прямую. Иначе [math]Vor(P)[/math] связная и все её рёбра — либо отрезки, либо лучи.

Доказательство:

[math]\triangleright[/math]

В случае, если все сайты лежат на одной прямой, каждая пара соседних сайтов порождает серединный перпендикуляр к отрезку, содержащему их, и, соответственно, к прямой, которая содержит все сайты. Так получаются [math]n - 1[/math] прямая, каждая из которых перпендикулярна прямой, содержащей сайты, а значит, эти прямые параллельны. Рассмотрим теперь случай, когда сайты не лежат на одной прямой. Покажем, что рёбра — это отрезки или лучи, от противного. Предположим, что есть ребро [math]e[/math], являющееся прямой. Пусть оно — граница ячеек [math]\mathcal{V}(p_i)[/math] и [math]\mathcal{V}(p_j)[/math]. Пусть точка [math]p_k \in P[/math] не лежит на прямой [math]p_i p_j[/math] (по условию такая точка существует). Тогда серединный перпендикуляр к [math]p_j p_k[/math] не параллелен [math]e[/math], и, значит, он его пересекает. Но тогда та часть [math]e[/math], что лежит в [math]h(p_k, p_j)[/math], не может быть границей [math]\mathcal{V}(p_j)[/math], потому что она ближе к [math]p_k[/math], чем к [math]p_j[/math]. Пришли к противоречию. Докажем теперь, что диаграмма связна. Предположим, что это не так. Тогда на её рёбрах найдутся две точки [math]s[/math] и [math]t[/math], между которыми нет пути по рёбрам диаграммы. Рассмотрим отрезок [math]st[/math]. Он пересекает некоторое количество ячеек диаграммы, и, раз пути по рёбрам нет, какая-то из них несвязная. Это возможно, только если какая-то ячейка представляет собой полосу, ограниченную двумя параллельными прямыми. Но в нашем случае в диаграмме не может быть прямых, пришли к противоречию.

[math]\triangleleft[/math]

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

Сайт (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]\Sigma[/math] — слабо пересекающееся между собой множество сайтов. Тогда [math]\forall s \in \Sigma[/math] ячейки Вороного [math]V(s, \Sigma)[/math] — односвязные множества.

Доказательство:

[math]\triangleright[/math]

Для начала докажем, что ячейки связны. Пусть это не так и у ячейки [math]V(s, \Sigma)[/math] несколько компонент связности. Рассмотрим [math]\varepsilon[/math] — одну из тех, которая не содержит в себе [math]s[/math]. Начнём идти по кратчайшему пути [math]P[/math] от любой точки [math]p \in \varepsilon[/math] до [math]s[/math]. Так как [math]p[/math] и [math]s[/math] лежат в разных компонентах связности, найдётся [math]s' \in \Sigma[/math], такой что путь [math]P[/math] проходит через [math]V(s', \Sigma)[/math]. Значит существует путь от [math]p[/math] до [math]s'[/math], который короче, чем [math]P[/math], следовательно и [math]\delta(p, s') \lt \delta(p, s) = |P|[/math]. Противоречие. Теперь допустим, что [math]V(s, \Sigma)[/math] содержит разрыв в виде другой ячейки [math]V(s', \Sigma)[/math]. Проведём прямую, которая соответствует кратчайшему расстоянию между [math]s[/math] и [math]s'[/math] и рассмотрим точку [math]p[/math], которая лежит на её продолжении за [math]s'[/math] и принадлежит [math]V(s, \Sigma)[/math]. Такая точка будет существовать, т.к. [math]V(s', \Sigma)[/math] лежит внутри [math]V(s, \Sigma)[/math]. Получаем, что кратчайший путь от [math]p[/math] до [math]s[/math] проходит через [math]s'[/math]. Опять противоречие.

[math]\triangleleft[/math]

Теорема: Пусть [math]\Sigma[/math] — множество слабо пересекающихся сайтов, [math]s[/math] — сайт, [math]s \notin \Sigma[/math]. Тогда [math]R_\Sigma(s)[/math] — связное непустое множество. Доказательство: [math]\triangleright[/math] Пусть [math]C = V(s, \Sigma \cup \{s\})[/math], [math]R_\Sigma(s) = \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 s)[/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(q, \Sigma)[/math] для некоторого [math]q \in \Sigma[/math]. [math]x, y \in P \Rightarrow[/math] все достаточно малые окрестности [math]U(x)[/math], [math]U(y)[/math] полностью содержатся в [math]V(q, \Sigma)[/math]. Значит, точки пересечения этих окрестностей с дополнением [math]C[/math] лежат в [math]V(q, \Sigma \cup s)[/math] и могут быть соединены путём [math]L \subseteq V(q, \Sigma \cup \{s\}) \subseteq V(q, \Sigma)[/math]. Следовательно, цикл [math]P \circ L[/math] полностью содержится в [math]V(q, \Sigma)[/math] и содержит [math]\varepsilon_1[/math] или [math]\varepsilon_2[/math] в своей внутренней части. Это противоречит тому, что [math]V(q, \Sigma)[/math] — односвязное множество, следовательно [math]k = 1[/math]. [math]\triangleleft[/math]

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

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

Первый шаг алгоритма начинается с поиска ближайшего соседа [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]V(S, \Sigma \cup \{S\})[/math] (а как это сделать, я не очень понимаю).

Если же [math]S[/math] — это замкнутый отрезок [math]t[/math], то сначала вставляем конечные точки [math]p'_t[/math] и [math]p''_t[/math], используя процедуру, описанную выше. Остаётся вставить открытый отрезок [math]t^\circ[/math]. Так как [math]p'_t[/math] и [math]p''_t[/math] — соседи [math]t^\circ[/math] в диаграмме [math]V(\Sigma \cup \{p'_t, p''_t, t^\circ\})[/math], [math]t^\circ[/math] обязан конфликтовать с каким-нибудь ребром ячейки, соответствующей [math]p'_t[/math] или [math]p''_t[/math]. Таким образом, первый конфликт [math]t^\circ[/math] с [math]V_1(\Sigma \cup \{p'_t, p''_t\})[/math] можно найти, просматривая рёбра ячейки [math]V(p'_t, \Sigma \cup \{p'_t, p''_t\})[/math] или [math]V(p''_t, \Sigma \cup \{p'_t, p''_t\})[/math], то есть, можно опустить шаг поиска ближайшего соседа. Остаётся найти всю область конфликтов, как и в случае с точкой.

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

Пусть [math]p[/math] — точка, которая сильно пересекается с отрезком [math]t_i[/math], т.е. [math]p \in t^\circ[/math]. Понятно, что [math]t^\circ[/math] будет ближайшим соседом [math]p[/math] в [math]\Sigma[/math]. Пусть [math]e'_i(p)[/math] и [math]e''_i(p)[/math] — два ребра [math]V(t^\circ, \Sigma)[/math], которые пересекаются с нормалями к [math]t[/math], проведёнными из точки [math]p[/math] (см. рисунок). Пусть [math]v'_i(p)[/math] и [math]v''_i(p)[/math] — точки пересечения нормалей с рёбрами [math]e'_i(p)[/math] и [math]e''_i(p)[/math] соответственно. Тогда алгоритм вставки точки [math]p[/math] в диаграмму [math]V(\Sigma)[/math] будет выглядеть следующим образом: Начинаем с поиска ближайшего соседа [math]N_\Sigma(p)[/math]. Если [math]N_\Sigma(p) = p[/math], то ничего не делаем. Если [math]N_\Sigma(p)[/math] — точка, или отрезок, с которым [math]p[/math] не пересекается, то запускается процедура вставки, которая была описана выше. Иначе [math]N_\Sigma(p) = t_i^\circ[/math] — отрезок, пересекающийся с [math]p[/math]. Сначала добавляем [math]p[/math] в [math]\Sigma[/math] и заменяем [math]t_i^\circ[/math] двумя отрезками [math]p'_ip[/math] и [math]pp''_i[/math], где [math]p'_i[/math] и [math]p''_i[/math] — конечные точки [math]t_i[/math]. Затем ищем рёбра [math]e'_i(p)[/math] и [math]e''_i(p)[/math], разбиваем их в точках [math]v'_i(p)[/math] и [math]v''_i(p)[/math] и добавляем отрезки [math]v'_i(p)p[/math] и [math]v''_i(p)p[/math] в диаграмму.

Если же мы хотим вставить в диаграмму отрезок [math]t[/math], то вставляем сначала его крайние точки [math]p'_t[/math] и [math]p''_t[/math]. Затем, начиная с [math]p'_t[/math], ищем первый конфликт [math]t^\circ[/math] с текущей диаграммой Вороного и ищем всю область конфликтов. Во время этого поиска, прежде чем тестировать ребро Вороного [math]e[/math] существующей диаграммы на потенциальный конфликт, мы проверяем, не пересекается ли [math]t^\circ[/math] с одним из сайтов, связанных с [math]e[/math]. Если такой сайт [math]S_i[/math] найден, то поиск останавливается. Если [math]S_i[/math] — точка, [math]p_i[/math], то вставляем отрезки [math]p'_tp_i[/math] и [math]p_ip''_t[/math] рекурсивно. Если [math]S_i[/math] — отрезок [math]t^\circ_i[/math], то сначала проверяем, не принадлежит ли один из [math]t^\circ[/math], [math]t^\circ_i[/math] другому. Если так и есть, то прекращаем работу, иначе вычисляем точку пересечения [math]p_+[/math] отрезков [math]t^\circ[/math] и [math]t^\circ_i[/math], вставляем её в диаграмму, а затем рекурсивно вставляем отрезки [math]p'_tp_+[/math] и [math]p_+p''_t[/math].

Время работы данного алгоритма составляет [math]O((n + m)\log^2m)[/math], где [math]n[/math] — количество элементов во входном множестве [math]\Sigma_I[/math], а [math]m[/math] — количество пар сильно пересекающихся сайтов.

Ссылки

• Menalaos I. Karavelas A robust and efficient implementation for the segment Voronoi diagram.
• Rolf Klein Randomized incremental construction of abstract Voronoi diagrams.