qhull 求取包络 QT

下面是使用qhull库求取二维数据包络的Qt代码示例：

#include <QCoreApplication>
#include <QDebug>
#include <qhull/qhull.h>

#define DIM 2   // 二维数据
#define MAX_POINTS 1000   // 最大点数

int main(int argc, char *argv[])
{
    QCoreApplication a(argc, argv);

    int i, j, numpoints;
    coordT points[MAX_POINTS][DIM];
    facetT *facet;
    vertexT *vertex, **vertexp;
    setT *vertices;
    boolT ismalloc = False;
    char flags[250];

    // 读取点数据
    qDebug() << "Please input the number of points:";
    scanf("%d", &numpoints);
    for (i = 0; i < numpoints; i++) {
        qDebug() << QString("Please input the coordinate of point %1:").arg(i+1);
        for (j = 0; j < DIM; j++) {
            scanf("%lf", &points[i][j]);
        }
    }

    // 设置qhull选项
    sprintf(flags, "qhull d Qt");

    // 调用qhull库求取凸包
    qh_init_A(stdin, stdout, stderr, 0, NULL);
    qh_initflags(flags);
    qh_init_B(points[0], numpoints, DIM, ismalloc);
    qh_qhull();
    qh_check_output();

    // 输出凸包顶点
    vertices = qh_vertexintersect_new(NULL, qh_facet_list, False);
    qDebug() << "Convex Hull Vertices:";
    FORALLvertices {
        qDebug() << QString("(%1, %2)").arg(vertex->point[0]).arg(vertex->point[1]);
    }

    // 输出包络
    qDebug() << "Convex Hull Facets:";
    FORALLfacets {
        if (!facet->upperdelaunay) {
            qDebug() << "Facet:";
            vertexp = facet->vertices;
            do {
                vertex = *vertexp;
                qDebug() << QString("(%1, %2)").arg(vertex->point[0]).arg(vertex->point[1]);
            } while ((vertexp = (vertexT**)qh_settnext(facet->vertices, vertexp)) != facet->vertices);
        }
    }

    qh_freeqhull(!qh_ALL);
    qh_memfreeshort(&ismalloc);

    return a.exec();
}

其中，需要注意的是：

- 二维数据点的坐标存储在`points`数组中；
- 设置qhull选项时，`d`表示求凸包，`Qt`表示输出凸包顶点；
- 调用qh_qhull函数求取凸包；
- 通过`qh_vertexintersect_new`和`FORALLvertices`宏可以遍历凸包的所有顶点；
- 通过`FORALLfacets`宏可以遍历凸包的所有面，使用`facet->upperdelaunay`属性可以判断面是否为上凸壳三角剖分的一部分；
- 使用`qh_freeqhull`函数释放qhull库分配的内存。