已知点集的matlab 三维凸包 用公式表达出来

用 qhull 计算三维点集的凸包

在计算几何领域，qhull 是个很强大的程序，它可以计算 2 维、3 维，以及4 维以上维度点集的凸包、Delaunay 网格、Voronoi 图，并且 Matlab 和 Octave 都基于它来提供计算几何功能，Mathematica 使用它实现 Delaunay 网格构造。不过，也正是因为它过于强大，所以我在它的源代码中逡巡了好久，也没有看懂。现在我能做到的，就是找个梯子先爬上这个黑箱子。

因为 qhull 是一个复杂的命令行工具箱，用户可以通过各种命令选项去调用适当的程序。比如，要对点集进行 Delaunay 网格化，可以直接使用 "qdelaunay" 命令来实现，也可以通过 "qhull d Qbb" 命令来实现。

在 qhull 工具箱中，要构建点集的凸包，可以调用 "qconvex" 命令来实现，而且 "qhull" 如果在未设定命令选项时，默认调用的程序就是 qconvex。对于我要解决的问题，即使用 qhull 构造三维点集的凸包而言，基本命令格式如下：

$ qconvex [选项] <input_file >output_file

qconvex 程序的行为由一组功能选项来控制，常用的如下：

Qt - 三角化输出，也就是输出由三角面片组合而成的凸包数据

QJ - 对于近似于平面的数据进行一些简化，譬如对于三维点集，

- 可以保证不会出现 4 点共面的情况

Tv - 从结构、凸性以及数据包含等方面对凸包构建结果进行校验

-- 输出 qconvex 所有选项信息

对于凸包构建结果的输出，qconvex 提供了一组输出控制选项，常用的如下：

s- 输出凸包构建结果概要 (default)

i - 输出凸包上每个面片的顶点

n- 输出凸包上每个面的方程系数

p- 输出要进行凸包求解的点集的坐标

Fx - 输出极点（凸包顶点）

FA - 输出凸包的面积和体积

o- 采用 OFF 格式输出凸包构建结果（维度, 顶点数, 面数, 边数）

G- 采用 Geomview 格式输出凸包构建结果（只支持 2 维至 4 维）

m- 采用 Mathematica 格式输出凸包构建结果（只支持 2 维与 3 维）

TO 文件名 - 将凸包构建结果输出到文件

我们来玩真格的。首先准备好一份存放三维数据点信息的文本文件，文件的第一行是点数，其余每行都是一个数据点的 x, y, z 坐标信息。对于下图所示的 venus 点云，其数据文件 venus.asc 格式为：

26218

3.554705 199.173300 8.394049

3.584999 199.553600 10.168500

3.648500 200.610500 9.662390

3.667395 198.429900 10.576820

3.740701 198.771200 12.616080

3.796498 200.566700 7.518420

3.798301 197.899800 9.092709

3.814104 197.907700 12.370720

3.839600 200.038700 12.814610

... ... ... ... ... ...

现在使用 qconvex 对 venus.asc 文件所包含的点集构建凸包，采用 OFF (Object File Format) 格式输出：

$ qconvex o <venus.asc TO result.off

qconvex 输出的 off 格式文件自上而下由三部分构成：

文件头信息，即文件的第一行是数据的维度，第二行的内容是凸包顶点数、面片数和边数；

点表，存放凸包顶点的坐标信息；

面表，按逆时针次序记录面片顶点在点表中的序号（从 0 开始）。

在 off 文件的面表区域，第一列数字用来表示每个面片所含的顶点的个数。

在 linux 下，可以使用 geomview 来显示 OFF 格式文件，但前提是将 qconvex 输出的 off 文件的第一行内容替换为 "OFF"。下面是一份 geomview 所能接受的 OFF 文件格式，显示结果如下图所示。

# 文件头 （本行文本是注释，实际中应当去掉）

OFF

26218 4870 7305

# 点表 （本行文本是注释，实际中应当去掉）

3.584999 199.5536 10.1685

3.740701 198.7712 12.61608

3.796498 200.5667 7.51842

... ... ... ... ... ...

# 面表 （本行文本是注释，实际中应当去掉）

3 9864 9563 9674

3 9563 9864 9833

3 6318 1422 452

这个问题是可以做的，首先要确定的是两类点有两个凸包，需要分别求解。这个是二维点集生成平面图形的问题，解决你给的这个问题的方法有很多。我给个思路，在凸包（Convex Hull）的生成过程中，采用的是从某一个基点（比如最左下角的点），将所有其他点与该点连线的斜率均计算出来，按照一定的顺序（比如斜率从小到大的顺序）将各个点连接起来，这个是原始的凸包算法，这个算法中只考虑了斜率，没考虑两个点距离。因此，你这个问题需要把两点间距离考虑进来，把距离d和斜率k综合考虑。具体实现过程你可以自己完成了，顺便多说一句，最好把d设置成一个可变化的量，比如当寻找到的下一个点是个错误的点，那么就把d变化为原来的1.2倍再尝试。

---