Qt - 三角化输出，也就是输出由三角面片组合而成的凸包数据
QJ - 对于近似于平面的数据进行一些简化，譬如对于三维点集，
- 可以保证不会出现 4 点共面的情况
Tv - 从结构、凸性以及数据包含等方面对凸包构建结果进行校验
- - 输出 qconvex 所有选项信息
用 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 程序的行为由一组功能选项来控制，常用的如下：
对于凸包构建结果的输出，qconvex 提供了一组输出控制选项，常用的如下：
s - 输出凸包构建结果概要 (default)
i - 输出凸包上每个面片的顶点
n - 输出凸包上每个面的方程系数
p - 输出要进行凸包求解的点集的坐标
Fx - 输出极点（凸包顶点）
FA - 输出凸包的面积和体积
o - 采用 OFF 格式输出凸包构建结果（维度, 顶点数, 面数, 边数）
G - 采用 Geomview 格式输出凸包构建结果（只支持 2 维至 4 维）
m - 采用 Mathematica 格式输出凸包构建结果（只支持 2 维与 3 维）
TO 文件名 - 将凸包构建结果输出到文件
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
... ... ... ... ... ...
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
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
2009年12月07日 01:29
博主您好，感谢您对‘用 qhull 计算三维点集的凸包’资源的分享。
本人想用matlab的qhull工具箱求凸包的凸顶点。
想请教你，matlab中如何来求一个数集的凸顶点呢？
在matlab的help 里找到了qhull工具箱所包含的几个函数：
convhull Functions MATLAB
convhulln Functions MATLAB
delaunay Functions MATLAB
delaunay3 Functions MATLAB
delaunayn Functions MATLAB
dsearchn Functions MATLAB
griddata Functions MATLAB
griddata3 Functions MATLAB
griddatan Functions MATLAB
tsearchn Functions MATLAB
voronoi Functions MATLAB
voronoin Functions MATLAB
感觉就是前两个函数，convhull、convhulln！
2009年12月07日 02:52
抱歉的很，我不会用 matlab :)
2009年12月07日 05:11
仔细看了下函数的说明，可能是用这个函数求解凸顶点，
[V,C] = voronoin(X)
其中V即是X的顶点，（英语很差，这是我对如下语句的理解）
the voronoin function returns two outputs: V is an m-by-n matrixof m points in n-space. Each row of V representsa Voronoi vertex.
C is a cell array of vectors. Each vectorin the cell array C represents a Voronoi cell.
The vector contains indices of the points in V that are the vertices
of the Voronoi cell. Each Voronoi cell may have a different number of points.
但是在matlab中运行该语句时出现提示信息:Not enough points to do tessellation.
难得是我的向量X维数太高吗？X是5行，108列人脸数据，同一个人脸的5幅pca降维后的数据。
请您指导下，谢谢！
另外，由于没有找到其他联系您的方式，就直接在此处留言请教了，我的问题影响您主页的整洁，联系上您后，可以考虑删除我的留言！我的Email：xinqing2002@gmail.com