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.

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

• 2-D и 3-D: options = {"Qbb"}
• 4-D и выше: 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. Обратите внимание, что на рисунке добавлена описанная окружность одного из треугольников, чтобы нагляднее показать связь между разбиением Делоне и диаграммой Вороного.

Рисунок 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-мерные параллелепипеды; в этом случае в зависимости от числа измерений вычисляется объём или гиперобъём.

Двумерные прямоугольники задаются как [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.

Рисунок 30.4: Демонстрация функции inpolygon для определения точек, находящихся внутри многоугольника