30.2 Voronoi图 ¶

一组点 s 在 N 维空间中的 Voronoi 图或 Voronoi 镶嵌，是指将 N 维空间划分成多个区域，使得在每个区域 v(p)（其中 p 是 s 中的一个点）中，所有点到 p 的距离都比到 s 中任何其他点更近。Voronoi 图与一组点的 Delaunay 三角剖分相关，因为 Voronoi 镶嵌的顶点是 Delaunay 镶嵌的单纯形的外接圆的圆心。

voronoi (x, y) ¶

voronoi (x, y, options) ¶

voronoi (…, "linespec") ¶

voronoi (hax, …) ¶

h = voronoi (…) ¶

[vx, vy] = voronoi (…) ¶

绘制点集 (x, y) 的 Voronoi 图。

不绘制顶点在无穷远处的 Voronoi 面。

options 参数必须是字符串或字符串元胞数组，包含传递给底层 qhull 命令的选项。 有关详细信息，请参阅 Qhull 库的文档 http://www.qhull.org/html/qh-quick.htm#options。

如果给出了 "linespec"，则用于设置绘图的颜色和线条样式。

如果提供了坐标轴图形句柄 hax，则 Voronoi 图将绘制在指定的坐标轴上，而不是绘制在新图形中。

如果请求单个输出参数，则会绘制 Voronoi 图并返回该图的图形句柄 h。

[vx, vy] = voronoi (…) 返回 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 维 Voronoi 面。

输入矩阵 pts 的大小为 [n, dim]，包含 dim 维空间中的 n 个点。

C 包含 Voronoi 面的顶点。列表 F 包含每个面的 Voronoi 点的索引。

可选的第二个参数必须是字符串或字符串元胞数组， 包含传递给底层 qhull 命令的选项。有关详细信息， 请参阅 Qhull 库的文档 http://www.qhull.org/html/qh-quick.htm#options。

默认选项取决于输入的维度：

• 2 维和 3 维：options = {"Qbb"}
• 4 维及更高：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。注意，其中一个三角形的外接圆已被添加到该图中，以便更清晰地展示 Delaunay 镶嵌与 Voronoi 图之间的关系。

图 30.3：随机点集的 Delaunay 三角剖分（蓝线）和 Voronoi 图（红线）

关于 Voronoi 图的面的大小，以及点集中的哪些点位于多边形内，可以分别通过 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

顶点在无穷远处的 Voronoi 图的面具有无穷大的面积。适用于矩形的 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 行对应 a 的第 i 行，第 j 列对应 b 的第 j 行。

另请参阅： polyarea。

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

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

对于由顶点 (xv, yv) 定义的多边形，如果点 (x, y) 在多边形内部（或在边界上），则返回 true；否则返回 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 函数确定多边形内点的演示