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

График 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 функция поддерживает расчет топологии Вороного для дискретных точек в N-D (N ≥ 2). The voronoiDiagram метод поддерживает расчет топологии Вороного для дискретных точек 2-D или 3-D.

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

voronoin функции и voronoiDiagram метод представляет топологию диаграммы Вороного с использованием матричного формата. Для получения дополнительной информации об этой структуре данных см. Формат Triangulation Matrix.

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

[V,R] = voronoin(X)

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