libqhull: qconvex.c Source File

Go to the documentation of this file.
00001 /*<html><pre>  -<a                             href="../libqhull/qh-qhull.htm"
00002   >-------------------------------</a><a name="TOP">-</a>
00003 
00004    qconvex.c
00005       compute convex hulls using qhull
00006 
00007    see unix.c for full interface
00008 
00009    Copyright (c) 1993-2011, The Geometry Center
00010 */
00011 
00012 #include <stdio.h>
00013 #include <stdlib.h>
00014 #include <string.h>
00015 #include <ctype.h>
00016 #include <math.h>
00017 #include "libqhull.h"
00018 #include "mem.h"
00019 #include "qset.h"
00020 
00021 #if __MWERKS__ && __POWERPC__
00022 #include <SIOUX.h>
00023 #include <Files.h>
00024 #include <console.h>
00025 #include <Desk.h>
00026 
00027 #elif __cplusplus
00028 extern "C" {
00029   int isatty(int);
00030 }
00031 
00032 #elif _MSC_VER
00033 #include <io.h>
00034 #define isatty _isatty
00035 int _isatty(int);
00036 
00037 #else
00038 int isatty(int);  /* returns 1 if stdin is a tty
00039                    if "Undefined symbol" this can be deleted along with call in main() */
00040 #endif
00041 
00042 /*-<a                             href="../libqhull/qh-qhull.htm#TOC"
00043   >-------------------------------</a><a name="prompt">-</a>
00044 
00045   qh_prompt
00046     long prompt for qconvex
00047 
00048   notes:
00049     restricted version of libqhull.c
00050 
00051   see:
00052     concise prompt below
00053 */
00054 
00055 /* duplicated in qconvex.htm */
00056 char hidden_options[]=" d v H Qbb Qf Qg Qm Qr Qu Qv Qx Qz TR E V Fp Gt Q0 Q1 Q2 Q3 Q4 Q5 Q6 Q7 Q8 Q9 ";
00057 
00058 char qh_prompta[]= "\n\
00059 qconvex- compute the convex hull\n\
00060     http://www.qhull.org  %s\n\
00061 \n\
00062 input (stdin):\n\
00063     first lines: dimension and number of points (or vice-versa).\n\
00064     other lines: point coordinates, best if one point per line\n\
00065     comments:    start with a non-numeric character\n\
00066 \n\
00067 options:\n\
00068     Qt   - triangulated output\n\
00069     QJ   - joggled input instead of merged facets\n\
00070     Qc   - keep coplanar points with nearest facet\n\
00071     Qi   - keep interior points with nearest facet\n\
00072 \n\
00073 Qhull control options:\n\
00074     Qbk:n   - scale coord k so that low bound is n\n\
00075       QBk:n - scale coord k so that upper bound is n (QBk is %2.2g)\n\
00076     QbB  - scale input to unit cube centered at the origin\n\
00077     Qbk:0Bk:0 - remove k-th coordinate from input\n\
00078     QJn  - randomly joggle input in range [-n,n]\n\
00079     QRn  - random rotation (n=seed, n=0 time, n=-1 time/no rotate)\n\
00080 %s%s%s%s";  /* split up qh_prompt for Visual C++ */
00081 char qh_promptb[]= "\
00082     Qs   - search all points for the initial simplex\n\
00083     QGn  - good facet if visible from point n, -n for not visible\n\
00084     QVn  - good facet if it includes point n, -n if not\n\
00085 \n\
00086 ";
00087 char qh_promptc[]= "\
00088 Trace options:\n\
00089     T4   - trace at level n, 4=all, 5=mem/gauss, -1= events\n\
00090     Tc   - check frequently during execution\n\
00091     Ts   - print statistics\n\
00092     Tv   - verify result: structure, convexity, and point inclusion\n\
00093     Tz   - send all output to stdout\n\
00094     TFn  - report summary when n or more facets created\n\
00095     TI file - input data from file, no spaces or single quotes\n\
00096     TO file - output results to file, may be enclosed in single quotes\n\
00097     TPn  - turn on tracing when point n added to hull\n\
00098      TMn - turn on tracing at merge n\n\
00099      TWn - trace merge facets when width > n\n\
00100     TVn  - stop qhull after adding point n, -n for before (see TCn)\n\
00101      TCn - stop qhull after building cone for point n (see TVn)\n\
00102 \n\
00103 Precision options:\n\
00104     Cn   - radius of centrum (roundoff added).  Merge facets if non-convex\n\
00105      An  - cosine of maximum angle.  Merge facets if cosine > n or non-convex\n\
00106            C-0 roundoff, A-0.99/C-0.01 pre-merge, A0.99/C0.01 post-merge\n\
00107     Rn   - randomly perturb computations by a factor of [1-n,1+n]\n\
00108     Un   - max distance below plane for a new, coplanar point\n\
00109     Wn   - min facet width for outside point (before roundoff)\n\
00110 \n\
00111 Output formats (may be combined; if none, produces a summary to stdout):\n\
00112     f    - facet dump\n\
00113     G    - Geomview output (see below)\n\
00114     i    - vertices incident to each facet\n\
00115     m    - Mathematica output (2-d and 3-d)\n\
00116     n    - normals with offsets\n\
00117     o    - OFF file format (dim, points and facets; Voronoi regions)\n\
00118     p    - point coordinates \n\
00119     s    - summary (stderr)\n\
00120 \n\
00121 ";
00122 char qh_promptd[]= "\
00123 More formats:\n\
00124     Fa   - area for each facet\n\
00125     FA   - compute total area and volume for option 's'\n\
00126     Fc   - count plus coplanar points for each facet\n\
00127            use 'Qc' (default) for coplanar and 'Qi' for interior\n\
00128     FC   - centrum for each facet\n\
00129     Fd   - use cdd format for input (homogeneous with offset first)\n\
00130     FD   - use cdd format for numeric output (offset first)\n\
00131     FF   - facet dump without ridges\n\
00132     Fi   - inner plane for each facet\n\
00133     FI   - ID for each facet\n\
00134     Fm   - merge count for each facet (511 max)\n\
00135     Fn   - count plus neighboring facets for each facet\n\
00136     FN   - count plus neighboring facets for each point\n\
00137     Fo   - outer plane (or max_outside) for each facet\n\
00138     FO   - options and precision constants\n\
00139     FP   - nearest vertex for each coplanar point\n\
00140     FQ   - command used for qconvex\n\
00141     Fs   - summary: #int (8), dimension, #points, tot vertices, tot facets,\n\
00142                       for output: #vertices, #facets,\n\
00143                                   #coplanar points, #non-simplicial facets\n\
00144                     #real (2), max outer plane, min vertex\n\
00145     FS   - sizes:   #int (0) \n\
00146                     #real (2) tot area, tot volume\n\
00147     Ft   - triangulation with centrums for non-simplicial facets (OFF format)\n\
00148     Fv   - count plus vertices for each facet\n\
00149     FV   - average of vertices (a feasible point for 'H')\n\
00150     Fx   - extreme points (in order for 2-d)\n\
00151 \n\
00152 ";
00153 char qh_prompte[]= "\
00154 Geomview output (2-d, 3-d, and 4-d)\n\
00155     Ga   - all points as dots\n\
00156      Gp  -  coplanar points and vertices as radii\n\
00157      Gv  -  vertices as spheres\n\
00158     Gi   - inner planes only\n\
00159      Gn  -  no planes\n\
00160      Go  -  outer planes only\n\
00161     Gc   - centrums\n\
00162     Gh   - hyperplane intersections\n\
00163     Gr   - ridges\n\
00164     GDn  - drop dimension n in 3-d and 4-d output\n\
00165 \n\
00166 Print options:\n\
00167     PAn  - keep n largest facets by area\n\
00168     Pdk:n - drop facet if normal[k] <= n (default 0.0)\n\
00169     PDk:n - drop facet if normal[k] >= n\n\
00170     Pg   - print good facets (needs 'QGn' or 'QVn')\n\
00171     PFn  - keep facets whose area is at least n\n\
00172     PG   - print neighbors of good facets\n\
00173     PMn  - keep n facets with most merges\n\
00174     Po   - force output.  If error, output neighborhood of facet\n\
00175     Pp   - do not report precision problems\n\
00176 \n\
00177     .    - list of all options\n\
00178     -    - one line descriptions of all options\n\
00179 ";
00180 /* for opts, don't assign 'e' or 'E' to a flag (already used for exponent) */
00181 
00182 /*-<a                             href="../libqhull/qh-qhull.htm#TOC"
00183   >-------------------------------</a><a name="prompt2">-</a>
00184 
00185   qh_prompt2
00186     synopsis for qhull
00187 */
00188 char qh_prompt2[]= "\n\
00189 qconvex- compute the convex hull.  Qhull %s\n\
00190     input (stdin): dimension, number of points, point coordinates\n\
00191     comments start with a non-numeric character\n\
00192 \n\
00193 options (qconvex.htm):\n\
00194     Qt   - triangulated output\n\
00195     QJ   - joggled input instead of merged facets\n\
00196     Tv   - verify result: structure, convexity, and point inclusion\n\
00197     .    - concise list of all options\n\
00198     -    - one-line description of all options\n\
00199 \n\
00200 output options (subset):\n\
00201     s    - summary of results (default)\n\
00202     i    - vertices incident to each facet\n\
00203     n    - normals with offsets\n\
00204     p    - vertex coordinates (includes coplanar points if 'Qc')\n\
00205     Fx   - extreme points (convex hull vertices)\n\
00206     FA   - report total area and volume\n\
00207     FS   - compute total area and volume\n\
00208     o    - OFF format (dim, n, points, facets)\n\
00209     G    - Geomview output (2-d, 3-d, and 4-d)\n\
00210     m    - Mathematica output (2-d and 3-d)\n\
00211     QVn  - print facets that include point n, -n if not\n\
00212     TO file- output results to file, may be enclosed in single quotes\n\
00213 \n\
00214 examples:\n\
00215     rbox c D2 | qconvex s n                    rbox c D2 | qconvex i\n\
00216     rbox c D2 | qconvex o                      rbox 1000 s | qconvex s Tv FA\n\
00217     rbox c d D2 | qconvex s Qc Fx              rbox y 1000 W0 | qconvex s n\n\
00218     rbox y 1000 W0 | qconvex s QJ              rbox d G1 D12 | qconvex QR0 FA Pp\n\
00219     rbox c D7 | qconvex FA TF1000\n\
00220 \n\
00221 ";
00222 /* for opts, don't assign 'e' or 'E' to a flag (already used for exponent) */
00223 
00224 /*-<a                             href="../libqhull/qh-qhull.htm#TOC"
00225   >-------------------------------</a><a name="prompt3">-</a>
00226 
00227   qh_prompt3
00228     concise prompt for qhull
00229 */
00230 char qh_prompt3[]= "\n\
00231 Qhull %s.\n\
00232 Except for 'F.' and 'PG', upper-case options take an argument.\n\
00233 \n\
00234  incidences     mathematica    normals        OFF_format     points\n\
00235  summary        facet_dump\n\
00236 \n\
00237  Farea          FArea_total    Fcoplanars     FCentrums      Fd_cdd_in\n\
00238  FD_cdd_out     FFacet_xridge  Finner         FIDs           Fmerges\n\
00239  Fneighbors     FNeigh_vertex  Fouter         FOptions       FPoint_near\n\
00240  FQhull         Fsummary       FSize          Fvertices      FVertex_ave\n\
00241  Fxtremes       FMaple\n\
00242 \n\
00243  Gvertices      Gpoints        Gall_points    Gno_planes     Ginner\n\
00244  Gcentrums      Ghyperplanes   Gridges        Gouter         GDrop_dim\n\
00245 \n\
00246  PArea_keep     Pdrop d0:0D0   PFacet_area_keep Pgood        PGood_neighbors\n\
00247  PMerge_keep    Poutput_forced Pprecision_not\n\
00248 \n\
00249  QbBound 0:0.5  QbB_scale_box  Qcoplanar      QGood_point    Qinterior\n\
00250  QJoggle        Qrandom        QRotate        Qsearch_1st    Qtriangulate\n\
00251  QVertex_good\n\
00252 \n\
00253  T4_trace       Tcheck_often   Tstatistics    Tverify        Tz_stdout\n\
00254  TFacet_log     TInput_file    TPoint_trace   TMerge_trace   TOutput_file\n\
00255  TWide_trace    TVertex_stop   TCone_stop\n\
00256 \n\
00257  Angle_max      Centrum_size   Random_dist    Ucoplanar_max  Wide_outside\n\
00258 ";
00259 
00260 /*-<a                             href="../libqhull/qh-qhull.htm"
00261   >-------------------------------</a><a name="main">-</a>
00262 
00263   main( argc, argv )
00264     processes the command line, calls qhull() to do the work, and exits
00265 
00266   design:
00267     initializes data structures
00268     reads points
00269     finishes initialization
00270     computes convex hull and other structures
00271     checks the result
00272     writes the output
00273     frees memory
00274 */
00275 int main(int argc, char *argv[]) {
00276   int curlong, totlong; /* used !qh_NOmem */
00277   int exitcode, numpoints, dim;
00278   coordT *points;
00279   boolT ismalloc;
00280 
00281 #if __MWERKS__ && __POWERPC__
00282   char inBuf[BUFSIZ], outBuf[BUFSIZ], errBuf[BUFSIZ];
00283   SIOUXSettings.showstatusline= false;
00284   SIOUXSettings.tabspaces= 1;
00285   SIOUXSettings.rows= 40;
00286   if (setvbuf(stdin, inBuf, _IOFBF, sizeof(inBuf)) < 0   /* w/o, SIOUX I/O is slow*/
00287   || setvbuf(stdout, outBuf, _IOFBF, sizeof(outBuf)) < 0
00288   || (stdout != stderr && setvbuf(stderr, errBuf, _IOFBF, sizeof(errBuf)) < 0))
00289     fprintf(stderr, "qhull internal warning (main): could not change stdio to fully buffered.\n");
00290   argc= ccommand(&argv);
00291 #endif
00292 
00293   if ((argc == 1) && isatty( 0 /*stdin*/)) {
00294     fprintf(stdout, qh_prompt2, qh_version);
00295     exit(qh_ERRnone);
00296   }
00297   if (argc > 1 && *argv[1] == '-' && !*(argv[1]+1)) {
00298     fprintf(stdout, qh_prompta, qh_version, qh_DEFAULTbox,
00299                 qh_promptb, qh_promptc, qh_promptd, qh_prompte);
00300     exit(qh_ERRnone);
00301   }
00302   if (argc >1 && *argv[1] == '.' && !*(argv[1]+1)) {
00303     fprintf(stdout, qh_prompt3, qh_version);
00304     exit(qh_ERRnone);
00305   }
00306   qh_init_A(stdin, stdout, stderr, argc, argv);  /* sets qh qhull_command */
00307   exitcode= setjmp(qh errexit); /* simple statement for CRAY J916 */
00308   if (!exitcode) {
00309     qh_checkflags(qh qhull_command, hidden_options);
00310     qh_initflags(qh qhull_command);
00311     points= qh_readpoints(&numpoints, &dim, &ismalloc);
00312     if (dim >= 5) {
00313       qh_option("Qxact_merge", NULL, NULL);
00314       qh MERGEexact= True; /* 'Qx' always */
00315     }
00316     qh_init_B(points, numpoints, dim, ismalloc);
00317     qh_qhull();
00318     qh_check_output();
00319     qh_produce_output();
00320     if (qh VERIFYoutput && !qh FORCEoutput && !qh STOPpoint && !qh STOPcone)
00321       qh_check_points();
00322     exitcode= qh_ERRnone;
00323   }
00324   qh NOerrexit= True;  /* no more setjmp */
00325 #ifdef qh_NOmem
00326   qh_freeqhull( True);
00327 #else
00328   qh_freeqhull( False);
00329   qh_memfreeshort(&curlong, &totlong);
00330   if (curlong || totlong)
00331     fprintf(stderr, "qhull internal warning (main): did not free %d bytes of long memory(%d pieces)\n",
00332        totlong, curlong);
00333 #endif
00334   return exitcode;
00335 } /* main */
00336