30.2 Диаграммы Вороного ¶

Диаграмма Вороного или Воронинское разбиение множества точек s в N-мерном пространстве представляет собой разбиение N-мерного пространства таким образом, что все точки в v(p), это части разбиения, где p — член множества s, находятся ближе к p, чем к любой другой точке в s. Диаграмма Вороного связана с треугольной сеткой Делоне множества точек, так как вершины Воронинского разбиения являются центрами описанных окружностей простых многоугольников треугольной сетки Делоне.

: voronoi (x, y) ¶

: voronoi (x, y, options) ¶

: voronoi (…, "linespec") ¶

: voronoi (hax, …) ¶

: h = voronoi (…) ¶

: [vx, vy] = voronoi (…) ¶

Постройте диаграмму Вороного для точек (x, y).

Грани Вороного с точками в бесконечности не отображаются.

Аргумент options, который должен быть строкой или массивом строк, содержит параметры, передаваемые в базовую команду qhull. Подробности см. в документации библиотеки Qhull http://www.qhull.org/html/qh-quick.htm#options.

Если "linespec" задано, оно используется для установки цвета и стиля линии графика.

Если предоставлен дескриптор графического объекта осей hax, диаграмма Вороного будет построена на указанных осях, а не в новой фигуре.

Если запрошен единственный выходной аргумент, диаграмма Вороного будет построена, и в качестве результата будет возвращён дескриптор графического объекта h графика.

[vx, vy] = voronoi (…) возвращает вершины Вороного, а не строит диаграмму.

x = rand (10, 1);
y = rand (size (x));
h = convhull (x, y);
[vx, vy] = voronoi (x, y);
plot (vx, vy, "-b", x, y, "o", x(h), y(h), "-g");
legend ("", "points", "hull");

См. также: voronoin, delaunay, convhull.

: [C, F] = voronoin (pts) ¶

: [C, F] = voronoin (pts, options) ¶

Вычисление N-мерных граней Вороного.

Входная матрица pts размера [n, dim] содержит n точек в пространстве размерности dim.

C содержит точки граней Вороного. Список F содержит для каждой грани индексы точек Вороного.

Необязательный второй аргумент, который должен быть строкой или массивом строк, содержит параметры, передаваемые в базовую команду qhull. Подробности см. в документации библиотеки Qhull http://www.qhull.org/html/qh-quick.htm#options.

Значения параметров по умолчанию зависят от размерности входных данных:

• 2D и 3D: options = {"Qbb"}
• 4D и выше: options = {"Qbb", "Qx"}

Если options отсутствует или [] используются значения по умолчанию. В противном случае options заменяет список аргументов по умолчанию. Для добавления пользовательских параметров к значениям по умолчанию необходимо повторить параметры по умолчанию в options. Для передачи без аргументов используйте пустую строку.

См. также: voronoi, convhulln, delaunayn.

Пример использования voronoi

rand ("state",9);
x = rand (10,1);
y = rand (10,1);
tri = delaunay (x, y);
[vx, vy] = voronoi (x, y, tri);
triplot (tri, x, y, "b");
hold on;
plot (vx, vy, "r");

Результат можно увидеть на рисунке 30.3. Обратите внимание, что для большей наглядности отношения между треугольной сеткой Делоне и диаграммой Вороного в эту фигуру добавлена окружность одной из треугольников.

Дополнительную информацию о размерах граней диаграммы Вороного и о том, какие точки из набора точек находятся в многоугольнике, можно получить с помощью функций polyarea и inpolygon соответственно.

: a = polyarea (x, y) ¶

: a = polyarea (x, y, dim) ¶

Определение площади многоугольника методом треугольников.

Переменные x и y определяют пары вершин и должны иметь одинаковую форму. Они могут быть векторами или массивами. Если они являются массивами, то столбцы x и y обрабатываются отдельно, и возвращается площадь для каждого.

Если необязательный аргумент dim задан, то polyarea работает по этому измерению массивов x и y.

Пример использования polyarea может быть

rand ("state", 2);
x = rand (10, 1);
y = rand (10, 1);
[c, f] = voronoin ([x, y]);
af = zeros (size (f));
for i = 1 : length (f)
  af(i) = polyarea (c (f {i, :}, 1), c (f {i, :}, 2));
endfor

Грани диаграммы Вороного с вершиной в бесконечности имеют бесконечную площадь. Упрощенная версия polyarea для прямоугольников доступна с помощью функции rectint

: area = rectint (a, b) ¶

Вычисление площади или объёма пересечения прямоугольников или N-мерных прямоугольных параллелепипедов.

Вычисление площади пересечения прямоугольников в a и прямоугольников в b. Поддерживаются N-мерные прямоугольные параллелепипеды, в этом случае вычисляется объём или гиперобъём в зависимости от количества измерений.

2-мерные прямоугольники определяются как [xpos ypos width height] где xpos и ypos — координаты левого нижнего угла. Поддерживаются и более высокие размерности, где координаты минимального значения каждого измерения следуют за длиной прямоугольного параллелепипеда в этом измерении, например [xpos ypos zpos kpos … width height depth k_length …].

Каждая строка a и b определяет прямоугольник, и если обе задают несколько прямоугольников, то выход area является матрицей, где i-я строка соответствует i-й строке a, а j-й столбец соответствует j-й строке b.

См. также: polyarea.

: in = inpolygon (x, y, xv, yv) ¶

: [in, on] = inpolygon (x, y, xv, yv) ¶

Для многоугольника, определённого вершинами (xv, yv), возвращает true, если точки (x, y) находятся внутри (или на границе) многоугольника; в противном случае возвращает false.

Входные переменные x и y должны иметь одинаковую размерность.

Необязательный выходной on возвращает true, если точки находятся точно на границе многоугольника, и false в противном случае.

См. также: delaunay.

Пример использования inpolygon может быть

randn ("state", 2);
x = randn (100, 1);
y = randn (100, 1);
vx = cos (pi * [-1 : 0.1: 1]);
vy = sin (pi * [-1 : 0.1 : 1]);
in = inpolygon (x, y, vx, vy);
plot (vx, vy, x(in), y(in), "r+", x(!in), y(!in), "bo");
axis ([-2, 2, -2, 2]);

Результат можно увидеть на рисунке 30.4.