Диаграмма Вороного дискретного набора точек X разлагает пространство вокруг каждой точки X(i) в область влияния R{i}. Эта декомпозиция имеет свойство, которое является произвольной точкой P в пределах региона R{i} ближе к точке i чем любой другой момент. Область влияния называется областью Вороного, а совокупность всех областей Вороного - диаграммой Вороного.
Диаграмма Вороного является N-D геометрической конструкцией, но большинство практических применений находятся в 2-D и 3-D пространстве. Свойства диаграммы Вороного лучше всего понять на примере.
В этом примере показана диаграмма Вороного и триангуляция Делоне на одном и том же графике 2-D.
Используйте 2-D voronoi функция для построения диаграммы воронки для набора точек.
figure() X = [-1.5 3.2; 1.8 3.3; -3.7 1.5; -1.5 1.3; ... 0.8 1.2; 3.3 1.5; -4.0 -1.0;-2.3 -0.7; ... 0 -0.5; 2.0 -1.5; 3.7 -0.8; -3.5 -2.9; ... -0.9 -3.9; 2.0 -3.5; 3.5 -2.25]; voronoi(X(:,1),X(:,2)) % Assign labels to the points. nump = size(X,1); plabels = arrayfun(@(n) {sprintf('X%d', n)}, (1:nump)'); hold on Hpl = text(X(:,1), X(:,2), plabels, 'FontWeight', ... 'bold', 'HorizontalAlignment','center', ... 'BackgroundColor', 'none'); % Add a query point, P, at (0, -1.5). P = [0 -1]; plot(P(1),P(2), '*r'); text(P(1), P(2), 'P', 'FontWeight', 'bold', ... 'HorizontalAlignment','center', ... 'BackgroundColor', 'none'); hold off
Обратите внимание, что P ближе к X9 чем в любой другой момент в X, что верно для любой точки P в пределах области, ограничивающей X9.
Диаграмма Вороного набора точек X тесно связан с триангуляцией Делоне X. Чтобы увидеть эту связь, создайте триангуляцию Делоне набора точек X и наложить график триангуляции на диаграмму Вороного.
dt = delaunayTriangulation(X); hold on triplot(dt,'-r'); hold off
На графике видно, что область Вороного связана с точкой X9 определяется перпендикулярными биссекторами кромок Делоне, присоединенных к X9. Также вершины рёбер Вороного расположены в циркумцентрах треугольников Делоне. Эти связи можно проиллюстрировать, построив график циркумцентра треугольника {| X9 |, | X4 |, | X8 |}.
Чтобы найти индекс этого треугольника, запросите триангуляцию. Треугольник содержит расположение (-1, 0).
tidx = pointLocation(dt,-1,0);
Теперь найдите циркумцентр этого треугольника и постройте его зеленым цветом.
cc = circumcenter(dt,tidx); hold on plot(cc(1),cc(2),'*g'); hold off
Триангуляция Делоне и диаграмма Вороного являются геометрическими дуалами друг друга. Можно вычислить диаграмму Вороного из триангуляции Делоне и наоборот.
Обратите внимание, что Вороныйские районы, связанные с точками на выпуклом корпусе, являются неограниченными (например, Воронойский район, связанный с X13). Края в этой области «заканчиваются» на бесконечности. Края Вороного, которые Делоне пополам (X13, X12) и (X13, X14) простираются до бесконечности. Хотя диаграмма Вороного обеспечивает разложение ближайшего соседа пространства вокруг каждой точки в наборе, она не поддерживает непосредственно запросы ближайшего соседа. Однако геометрические конструкции, используемые для вычисления диаграммы Вороного, также используются для выполнения поиска ближайшего соседа.
Этот пример показывает, как вычислить 2-ю и 3D диаграмму Voronoi.
MATLAB ® предоставляет функции для построения диаграммы Вороного в 2-D и вычисления топологии диаграммы Вороного в N-D. На практике вычисление Вороного нецелесообразно в измерениях, выходящих за рамки 6-D для наборов данных от умеренных до больших, из-за экспоненциального роста требуемой памяти.
voronoi функция графика строит график Вороного для набора точек в 2-D пространстве. В MATLAB существует два способа вычисления топологии диаграммы Вороного набора точек:
Использование функции voronoin
Использование delaunayTriangulation способ, voronoiDiagram.
voronoin функция поддерживает вычисление топологии Вороного для дискретных точек в N-D (N ≥ 2). voronoiDiagram способ поддерживает вычисление топологии Вороного для дискретных точек 2-D или 3-D.
voronoiDiagram метод рекомендуется для 2-D или 3-D вычислений топологии, поскольку он является более надежным и обеспечивает лучшую производительность для больших наборов данных. Этот метод поддерживает инкрементную вставку и удаление точек и дополнительных запросов, таких как поиск ближайшей соседней точки.
voronoin функции и voronoiDiagram способ представляет топологию диаграммы Вороного с использованием матричного формата. Дополнительные сведения об этой структуре данных см. в разделе Формат матрицы триангуляции.
Учитывая набор точек, X, получить топологию диаграммы Вороного следующим образом:
Использование voronoin функция
[V,R] = voronoin(X)
Использование voronoiDiagram метод
dt = delaunayTriangulation(X);
[V,R] = voronoiDiagram(dt)
V - матрица, представляющая координаты вершин Вороного (вершины являются конечными точками рёбер Вороного). По соглашению первая вершина в V - бесконечная вершина. R - длина массива векторных ячеек size(X,1), представляющий область Вороного, связанную с каждой точкой. Отсюда и связанный с пунктом Вороной район X(iявляется R{i}.
Определение и построение графика воронки для набора точек
X = [-1.5 3.2; 1.8 3.3; -3.7 1.5; -1.5 1.3; 0.8 1.2; ... 3.3 1.5; -4.0 -1.0; -2.3 -0.7; 0 -0.5; 2.0 -1.5; ... 3.7 -0.8; -3.5 -2.9; -0.9 -3.9; 2.0 -3.5; 3.5 -2.25]; [VX,VY] = voronoi(X(:,1),X(:,2)); h = plot(VX,VY,'-b',X(:,1),X(:,2),'.r'); xlim([-4,4]) ylim([-4,4]) % Assign labels to the points X. nump = size(X,1); plabels = arrayfun(@(n) {sprintf('X%d', n)}, (1:nump)'); hold on Hpl = text(X(:,1), X(:,2)+0.2, plabels, 'color', 'r', ... 'FontWeight', 'bold', 'HorizontalAlignment',... 'center', 'BackgroundColor', 'none'); % Compute the Voronoi diagram. dt = delaunayTriangulation(X); [V,R] = voronoiDiagram(dt); % Assign labels to the Voronoi vertices V. % By convention the first vertex is at infinity. numv = size(V,1); vlabels = arrayfun(@(n) {sprintf('V%d', n)}, (2:numv)'); hold on Hpl = text(V(2:end,1), V(2:end,2)+.2, vlabels, ... 'FontWeight', 'bold', 'HorizontalAlignment',... 'center', 'BackgroundColor', 'none'); hold off
R{9} дает индексы вершин Вороного, связанных с площадкой точки X9.
R{9}ans = 1×5
5 7 17 12 9
Индексы вершин Вороного являются индексами относительно V массив.
Аналогично, R{4} дает индексы вершин Вороного, связанных с площадкой точки X4.
R{4}ans = 1×5
5 9 11 8 6
В 3-D область Вороного является выпуклым многогранником, синтаксис создания диаграммы Вороного аналогичен. Однако геометрия Вороного района более сложна. Следующий пример иллюстрирует создание 3D диаграммы Voronoi и нанесение единственного региона.
Создайте выборку из 25 точек в 3-D пространстве и вычислите топологию диаграммы Вороного для этого набора точек.
rng('default')
X = -3 + 6.*rand([25 3]);
dt = delaunayTriangulation(X);Вычислите топологию диаграммы Вороного.
[V,R] = voronoiDiagram(dt);
Найдите точку, ближайшую к началу координат, и постройте график области Вороного, связанной с этой точкой.
tid = nearestNeighbor(dt,0,0,0);
XR10 = V(R{tid},:);
K = convhull(XR10);
defaultFaceColor = [0.6875 0.8750 0.8984];
trisurf(K, XR10(:,1) ,XR10(:,2) ,XR10(:,3) , ...
'FaceColor', defaultFaceColor, 'FaceAlpha',0.8)
title('3-D Voronoi Region')