Диаграмма Вороного набора точек X разлагает пространство вокруг каждой точки X(i) в область влияния R{i}. Это разложение имеет свойство, что произвольная точка P в пределах области R{i} ближе к точке i чем любая другая точка. Область влияния называется Воронойской областью и набор всех Воронойских областей - диаграмма Вороного.
Диаграмма Вороного является N-D геометрической конструкцией, но большинство практических применений находятся в 2-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-D и 3-D диаграммы Вороного.
MATLAB® обеспечивает функции для построения графика диаграммы Вороного в 2-D и вычисления топологии диаграммы Вороного в N-D. На практике расчета Вороного не практичны в размерностях, выходящих за пределы 6-D, для умеренных и больших наборов данных из-за экспоненциального роста необходимой памяти.
voronoi функция построения графика строит графики диаграммы Вороного для набора точек в 2-D пространстве. В MATLAB существует два способа вычисления топологии диаграммы Вороного набора точек:
Использование функции voronoin
Использование delaunayTriangulation метод, voronoiDiagram.
voronoin функция поддерживает расчет топологии Вороного для дискретных точек в N-D (N ≥ 2). The voronoiDiagram метод поддерживает расчет топологии Вороного для дискретных точек 2-D или 3-D.
The voronoiDiagram Метод рекомендуется для 2-D или 3-D топологии расчетов так как он является более устойчивым и дает лучшую эффективность для больших наборов данных. Этот метод поддерживает инкрементальную вставку и удаление точек и дополнительных запросов, таких как поиск по ближайшей соседней точке.
voronoin функции и voronoiDiagram метод представляет топологию диаграммы Вороного с использованием матричного формата. Для получения дополнительной информации об этой структуре данных см. Формат Triangulation Matrix.
Учитывая набор точек, 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 область Вороного является выпуклым многогранником, синтаксис создания диаграммы Вороного аналогичен. Однако геометрия Вороной области сложнее. Следующий пример иллюстрирует создание 3-D диаграммы Вороного и графическое изображение одной области.
Создайте выборку из 25 точек в трехмерном пространстве и вычислите топологию диаграммы Вороного для этого набора точек.
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')