Диаграмма Вороного дискретного набора точек X анализирует пробел вокруг каждой точки X (i) в область влияния R {i}. Это разложение имеет свойство, что произвольная точка P в области R {i} ближе, чтобы указать i, чем какая-либо другая точка. Область влияния называется областью Voronoi, и набором всех областей Voronoi является Диаграмма Вороного.
Диаграмма Вороного является геометрическим построением N-D, но наиболее практические применения находятся на 2D и 3-D пробеле. Свойства Диаграммы Вороного лучше всего поняты с помощью примера.
Этот пример показывает Диаграмму Вороного и Триангуляцию Делоне на том же 2D графике.
Используйте 2D функцию 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
Из графика вы видите, что область Voronoi, сопоставленная с точкой X9, задана перпендикулярными биссектрисами ребер Delaunay, присоединенных к X9. Кроме того, вершины ребер Voronoi расположены в центрах описанной окружности треугольников Delaunay. Можно проиллюстрировать эти ассоциации путем графического вывода центра описанной окружности треугольника {|X9 |, | X4 |, | X8 |}.
Чтобы найти индекс этого треугольника, запросите триангуляцию. Треугольник содержит местоположение (-1, 0).
tidx = pointLocation(dt,-1,0);
Теперь, найдите центр описанной окружности этого треугольника и постройте его в зеленом.
cc = circumcenter(dt,tidx); hold on plot(cc(1),cc(2),'*g'); hold off
Триангуляция Делоне и Диаграмма Вороного являются геометрическими поединками друг друга. Можно вычислить Диаграмму Вороного из Триангуляции Делоне и наоборот.
Заметьте, что области Voronoi, сопоставленные с точками на выпуклой оболочке, неограниченны (например, область Voronoi, сопоставленная с X13). Ребра в этой области "заканчиваются" в бесконечности. Ребра Voronoi, которые делят пополам ребра Delaunay (X13, X12) и (X13, X14) расширяют к бесконечности. В то время как Диаграмма Вороного обеспечивает разложение ближайшего соседа пробела вокруг каждой точки в наборе, это непосредственно не поддерживает запросы ближайшего соседа. Однако геометрические конструкции, используемые, чтобы вычислить Диаграмму Вороного, также используются, чтобы выполнить поисковые запросы ближайшего соседа.
Этот пример показывает, как вычислить 2D и 3-D Диаграмму Вороного.
MATLAB® обеспечивает функции, чтобы построить Диаграмму Вороного в 2D и вычислить топологию Диаграммы Вороного в N-D. На практике вычисление Voronoi не практично в размерностях вне 6-D для умеренного к большим наборам данных, из-за экспоненциального роста в необходимой памяти.
Функция построения графика voronoi строит Диаграмму Вороного для набора точек на 2D пробеле. В MATLAB существует два способа вычислить топологию Диаграммы Вороного набора точки:
Используя функцию MATLAB voronoin
Используя метод delaunayTriangulation, voronoiDiagram.
Функция voronoin поддерживает вычисление топологии Voronoi для дискретных точек в N-D (N ≥ 2). Метод voronoiDiagram поддерживает вычисление топологии Voronoi для дискретных точек, 2D или 3-D.
Метод voronoiDiagram рекомендуется для 2D или 3-D вычислений топологии, когда это более устойчиво и дает лучшую производительность для больших наборов данных. Этот метод поддерживает инкрементную вставку и удаление точек и дополнительных запросов, таких как поиск точки ближайшего соседа.
Функция voronoin и метод voronoiDiagram представляют топологию Диаграммы Вороного с помощью матричного формата. Смотрите Матричный Формат Триангуляции для получения дальнейшей информации на этой структуре данных.
Учитывая набор точек, X, получают топологию Диаграммы Вороного можно следующим образом:
Используя функцию voronoin
[V,R] = voronoin(X)
Используя метод voronoiDiagram
dt = delaunayTriangulation(X);
[V,R] = voronoiDiagram(dt)
V является матрицей, представляющей координаты вершин Voronoi (вершины являются конечными точками ребер Voronoi). Условно первая вершина в V является бесконечной вершиной. R является векторной длиной массива ячеек size(X,1), представляя область Voronoi, сопоставленную с каждой точкой. Следовательно, областью Voronoi, сопоставленной с точкой 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} дает индексы вершин Voronoi, сопоставленных с сайтом точки X9.
R{9}ans = 1×5
5 7 17 12 9
Индексы вершин Voronoi являются индексами относительно массива V.
Точно так же R{4} дает индексы вершин Voronoi, сопоставленных с сайтом точки X4.
R{4}ans = 1×5
5 9 11 8 6
В 3-D область Voronoi является выпуклым многогранником, синтаксис для создания Диаграммы Вороного подобен. Однако геометрия области Voronoi является более комплексной. Следующий пример иллюстрирует создание 3-D Диаграммы Вороного и графический вывод одной области.
Создайте выборку 25 точек на 3-D пробеле и вычислите топологию Диаграммы Вороного для этого набора точки.
X = -3 + 6.*gallery('uniformdata',[25 3],0);
dt = delaunayTriangulation(X);Вычислите топологию Диаграммы Вороного.
[V,R] = voronoiDiagram(dt);
Найдите точку самой близкой к источнику и постройте область Voronoi, сопоставленную с этой точкой.
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')