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

Графическое изображение 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 сопоставила с точкой 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')