Диаграмма Вороного дискретного набора точек X анализирует пробел вокруг каждой точки Xi) в область влияния Ri}. Это разложение имеет свойство что произвольная точка P в области Ri} ближе, чтобы указать i чем какая-либо другая точка. Область влияния называется областью Voronoi, и набором всех областей Voronoi является Диаграмма Вороного.
Диаграмма Вороного является геометрическим построением N-D, но наиболее практические применения находятся в 2D и трехмерном пространстве. Свойства Диаграммы Вороного лучше всего изучены с помощью примера.
Этот пример показывает Диаграмму Вороного и Триангуляцию Делоне на том же 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 существует два способа вычислить топологию Диаграммы Вороного набора точки:
Используя функцию 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 сопоставила с точкой Xi) Ri.
Задайте и постройте диаграмму Вороного для набора точек
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 точек в трехмерном пространстве и вычислите топологию Диаграммы Вороного для этого набора точки.
rng('default')
X = -3 + 6.*rand([25 3]);
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')