qhull 一维包络 C语言

qhull是一个用于计算凸包的C库，也可以用于计算一维包络。以下是一个简单的示例程序，可以通过qhull库计算一维点集的上下包络：

#include <stdio.h>
#include <stdlib.h>
#include <qhull/qhull_a.h>

#define DIM 1

int main(int argc, char **argv)
{
    int i, j;
    int exitcode;
    char flags[] = "qhull QJ Pp";
    facetT *facet;
    vertexT *vertex, **vertexp;
    int curlong, totlong;
    int numpoints = argc - 1;

    coordT *points = malloc(numpoints * DIM * sizeof(coordT));
    if (!points) {
        fprintf(stderr, "Error: Out of memory.\n");
        exit(EXIT_FAILURE);
    }

    for (i = 1; i < argc; i++) {
        points[i - 1] = atof(argv[i]);
    }

    qh_initflags(flags);
    exitcode = qh_new_qhull(DIM, numpoints, points, False, NULL, NULL, stderr);
    if (!exitcode) {
        FORALLfacets {
            if (facet->upperdelaunay) {
                printf("Upper Envelope:\n");
            } else if (facet->lowerdelaunay) {
                printf("Lower Envelope:\n");
            } else {
                continue;
            }

            printf("  Facet %d: ", facet->id);
            FORALLvertex_(facet->vertices) {
                printf("%g ", vertex->point[0]);
            }
            printf("\n");
        }
        qh_freeqhull(!qh_ALL);
        qh_memfreeshort(&curlong, &totlong);
    } else {
        fprintf(stderr, "Error: qhull failed with exit code %d\n", exitcode);
        exit(EXIT_FAILURE);
    }

    free(points);
    return 0;
}

代码中，我们使用`qh_new_qhull`函数计算包络。计算结果是一组凸包面，其中的上包络和下包络可以通过`facet->upperdelaunay`和`facet->lowerdelaunay`属性进行区分。我们可以遍历所有的面，找到上包络和下包络，并打印出它们的点集。