Документация

Графическое изображение 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 поддерживает вычисление топологии Voronoi для дискретных точек в N-D (N ≥ 2). Метод voronoiDiagram поддерживает вычисление топологии Voronoi для дискретных точек, 2D или 3-D.

Метод voronoiDiagram рекомендуется для 2D или 3-D вычислений топологии, когда это более устойчиво и дает лучшую производительность для больших наборов данных. Этот метод поддерживает инкрементную вставку и удаление точек и дополнительных запросов, таких как поиск точки ближайшего соседа.

Функция voronoin и метод voronoiDiagram представляют топологию Диаграммы Вороного с помощью матричного формата. Смотрите Матричный Формат Триангуляции для получения дальнейшей информации на этой структуре данных.

Учитывая набор точек, X, получают топологию Диаграммы Вороного можно следующим образом:

[V,R] = voronoin(X)

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')