30.1 Delaunay 三角剖分 ¶
Delaunay 三角剖分由一组外接圆构造而成。这些外接圆的选取原则是：参与三角剖分的点集中至少有三个点位于该外接圆的圆周上。点集中的任何点都不会落在任意外接圆的内部。
一般情况下，每个外接圆的圆周上只有三个点。然而在某些情况下，特别是对于规则网格，四个或更多的点可能位于同一个外接圆上。此时，Delaunay 三角剖分不是唯一的。
tri =delaunay(x, y)¶tetr =delaunay(x, y, z)¶tri =delaunay(x)¶tri =delaunay(…, options)¶计算二维或三维点集的 Delaunay 三角剖分。
对于二维点集，返回值 tri 是一组三角形，满足 Delaunay 外接圆准则，即 [x, y] 中的数据点没有落在定义三角形的外接圆内部。三角形集合 tri 是一个大小为 [n, 3] 的矩阵。每一行定义一个三角形，三列分别为三角形的三个顶点。
tri(i,j)的值是 x 和 y 中的索引，用于定位第 i 个三角形的第 j 个顶点。对于三维点集，返回值 tetr 是一组四面体，满足 Delaunay 外接圆准则，即 [x, y, z] 中的数据点没有落在定义四面体的外接球内部。四面体集合是一个大小为 [n, 4] 的矩阵。每一行定义一个四面体，四列分别为四面体的四个顶点。
tetr(i,j)的值是 x、y、z 中的索引，用于定位第 i 个四面体的第 j 个顶点。输入参数 x 也可以是一个具有两列或三列的矩阵，其中第一列包含 x 数据，第二列包含 y 数据，可选的第三列包含 z 数据。
可选的最后一个参数必须是字符串或字符串元胞数组，包含传递给底层 qhull 命令的选项。有关详细信息，请参阅 Qhull 库的文档 http://www.qhull.org/html/qh-quick.htm#options。 默认选项为
{"Qt", "Qbb", "Qc"}。 如果 Qhull 在二维输入时失败，则会使用选项{"Qt", "Qbb", "Qc", "Qz"}重新尝试三角剖分，但这可能会降低精度。如果 options 不存在或为
[]，则使用默认参数。否则，options 将替换默认参数列表。要将用户选项附加到默认选项之后，需要在 options 中重复默认参数。使用空字符串表示不传递任何参数。x = rand (1, 10); y = rand (1, 10); tri = delaunay (x, y); triplot (tri, x, y); hold on; plot (x, y, "r*"); axis ([0,1,0,1]);
另请参阅： delaunayn、convhull、voronoi、triplot、trimesh、tetramesh、trisurf。
对于三维输入，delaunay 返回一组满足 Delaunay 外接球准则的四面体。类似地，delaunayn 返回满足 Delaunay 外接球准则的 N 维单纯形。三角剖分的 N 维推广称为曲面细分（tessellation）。
T =delaunayn(pts)¶T =delaunayn(pts, options)¶计算 N 维点集的 Delaunay 三角剖分。
Delaunay 三角剖分是对一组点的凸包进行曲面细分，使得由 N 维单纯形定义的 N 维球不包含该点集中的任何其他点。
输入矩阵 pts 的大小为 [n, dim]，在 dim 维空间中包含 n 个点。返回矩阵 T 的大小为 [m, dim+1]。T 的每一行包含一组索引，指向原始点集 pts 中的点，描述了一个 dim 维的单纯形。例如，2 维单纯形是三角形，3 维单纯形是四面体。
可选的第二个参数必须是字符串或字符串元胞数组，包含传递给底层 qhull 命令的选项。有关详细信息，请参阅 Qhull 库的文档 http://www.qhull.org/html/qh-quick.htm#options。 默认选项取决于输入的维度：
- 二维和三维：options =
{"Qt", "Qbb", "Qc"} - 四维及以上：options =
{"Qt", "Qbb", "Qc", "Qx"}
如果 Qhull 在二维输入时失败，则会使用选项
{"Qt", "Qbb", "Qc", "Qz"}重新尝试三角剖分，但这可能会降低精度。如果 options 不存在或为
[]，则使用默认参数。否则，options 将替换默认参数列表。要将用户选项附加到默认选项之后，需要在 options 中重复默认参数。使用空字符串表示不传递任何参数。- 二维和三维：options =
以下是一个点集 Delaunay 三角剖分的示例：
rand ("state", 1);
x = rand (1, 10);
y = rand (1, 10);
T = delaunay (x, y);
X = [ x(T(:,1)); x(T(:,2)); x(T(:,3)); x(T(:,1)) ];
Y = [ y(T(:,1)); y(T(:,2)); y(T(:,3)); y(T(:,1)) ];
axis ([0, 1, 0, 1]);
plot (X, Y, "b", x, y, "r*");
其结果如图 图 30.1 所示。
图 30.1：随机点集的 Delaunay 三角剖分
