libqhull: qhalf.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    qhalf.c
00005      compute the intersection of halfspaces about a point
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 qhull
00047 
00048   notes:
00049     restricted version of libqhull.c
00050 
00051   see:
00052     concise prompt below
00053 */
00054 
00055 /* duplicated in qhalf.htm */
00056 char hidden_options[]=" d n v Qbb QbB Qf Qg Qm Qr QR Qv Qx Qz TR E V Fa FA FC FD FS Ft FV Gt Q0 Q1 Q2 Q3 Q4 Q5 Q6 Q7 Q8 Q9 ";
00057 
00058 char qh_prompta[]= "\n\
00059 qhalf- compute the intersection of halfspaces about a point\n\
00060     http://www.qhull.org  %s\n\
00061 \n\
00062 input (stdin):\n\
00063     optional interior point: dimension, 1, coordinates\n\
00064     first lines: dimension+1 and number of halfspaces\n\
00065     other lines: halfspace coefficients followed by offset\n\
00066     comments:    start with a non-numeric character\n\
00067 \n\
00068 options:\n\
00069     Hn,n - specify coordinates of interior point\n\
00070     Qt   - triangulated output\n\
00071     QJ   - joggled input instead of merged facets\n\
00072     Qc   - keep coplanar halfspaces\n\
00073     Qi   - keep other redundant halfspaces\n\
00074 \n\
00075 Qhull control options:\n\
00076     QJn  - randomly joggle input in range [-n,n]\n\
00077 %s%s%s%s";  /* split up qh_prompt for Visual C++ */
00078 char qh_promptb[]= "\
00079     Qbk:0Bk:0 - remove k-th coordinate from input\n\
00080     Qs   - search all halfspaces for the initial simplex\n\
00081     QGn  - print intersection if visible to halfspace n, -n for not\n\
00082     QVn  - print intersections for halfspace n, -n if not\n\
00083 \n\
00084 ";
00085 char qh_promptc[]= "\
00086 Trace options:\n\
00087     T4   - trace at level n, 4=all, 5=mem/gauss, -1= events\n\
00088     Tc   - check frequently during execution\n\
00089     Ts   - print statistics\n\
00090     Tv   - verify result: structure, convexity, and redundancy\n\
00091     Tz   - send all output to stdout\n\
00092     TFn  - report summary when n or more facets created\n\
00093     TI file - input data from file, no spaces or single quotes\n\
00094     TO file - output results to file, may be enclosed in single quotes\n\
00095     TPn  - turn on tracing when halfspace n added to intersection\n\
00096     TMn  - turn on tracing at merge n\n\
00097     TWn  - trace merge facets when width > n\n\
00098     TVn  - stop qhull after adding halfspace n, -n for before (see TCn)\n\
00099     TCn  - stop qhull after building cone for halfspace n (see TVn)\n\
00100 \n\
00101 Precision options:\n\
00102     Cn   - radius of centrum (roundoff added).  Merge facets if non-convex\n\
00103      An  - cosine of maximum angle.  Merge facets if cosine > n or non-convex\n\
00104            C-0 roundoff, A-0.99/C-0.01 pre-merge, A0.99/C0.01 post-merge\n\
00105     Rn   - randomly perturb computations by a factor of [1-n,1+n]\n\
00106     Un   - max distance below plane for a new, coplanar halfspace\n\
00107     Wn   - min facet width for outside halfspace (before roundoff)\n\
00108 \n\
00109 Output formats (may be combined; if none, produces a summary to stdout):\n\
00110     f    - facet dump\n\
00111     G    - Geomview output (dual convex hull)\n\
00112     i    - non-redundant halfspaces incident to each intersection\n\
00113     m    - Mathematica output (dual convex hull)\n\
00114     o    - OFF format (dual convex hull: dimension, points, and facets)\n\
00115     p    - vertex coordinates of dual convex hull (coplanars if 'Qc' or 'Qi')\n\
00116     s    - summary (stderr)\n\
00117 \n\
00118 ";
00119 char qh_promptd[]= "\
00120 More formats:\n\
00121     Fc   - count plus redundant halfspaces for each intersection\n\
00122          -   Qc (default) for coplanar and Qi for other redundant\n\
00123     Fd   - use cdd format for input (homogeneous with offset first)\n\
00124     FF   - facet dump without ridges\n\
00125     FI   - ID of each intersection\n\
00126     Fm   - merge count for each intersection (511 max)\n\
00127     FM   - Maple output (dual convex hull)\n\
00128     Fn   - count plus neighboring intersections for each intersection\n\
00129     FN   - count plus intersections for each non-redundant halfspace\n\
00130     FO   - options and precision constants\n\
00131     Fp   - dim, count, and intersection coordinates\n\
00132     FP   - nearest halfspace and distance for each redundant halfspace\n\
00133     FQ   - command used for qhalf\n\
00134     Fs   - summary: #int (8), dim, #halfspaces, #non-redundant, #intersections\n\
00135                       for output: #non-redundant, #intersections, #coplanar\n\
00136                                   halfspaces, #non-simplicial intersections\n\
00137                     #real (2), max outer plane, min vertex\n\
00138     Fv   - count plus non-redundant halfspaces for each intersection\n\
00139     Fx   - non-redundant halfspaces\n\
00140 \n\
00141 ";
00142 char qh_prompte[]= "\
00143 Geomview output (2-d, 3-d and 4-d; dual convex hull)\n\
00144     Ga   - all points (i.e., transformed halfspaces) as dots\n\
00145      Gp  -  coplanar points and vertices as radii\n\
00146      Gv  -  vertices (i.e., non-redundant halfspaces) as spheres\n\
00147     Gi   - inner planes (i.e., halfspace intersections) only\n\
00148      Gn  -  no planes\n\
00149      Go  -  outer planes only\n\
00150     Gc   - centrums\n\
00151     Gh   - hyperplane intersections\n\
00152     Gr   - ridges\n\
00153     GDn  - drop dimension n in 3-d and 4-d output\n\
00154 \n\
00155 Print options:\n\
00156     PAn  - keep n largest facets (i.e., intersections) by area\n\
00157     Pdk:n- drop facet if normal[k] <= n (default 0.0)\n\
00158     PDk:n- drop facet if normal[k] >= n\n\
00159     Pg   - print good facets (needs 'QGn' or 'QVn')\n\
00160     PFn  - keep facets whose area is at least n\n\
00161     PG   - print neighbors of good facets\n\
00162     PMn  - keep n facets with most merges\n\
00163     Po   - force output.  If error, output neighborhood of facet\n\
00164     Pp   - do not report precision problems\n\
00165 \n\
00166     .    - list of all options\n\
00167     -    - one line descriptions of all options\n\
00168 ";
00169 /* for opts, don't assign 'e' or 'E' to a flag (already used for exponent) */
00170 
00171 /*-<a                             href="../libqhull/qh-qhull.htm#TOC"
00172   >-------------------------------</a><a name="prompt2">-</a>
00173 
00174   qh_prompt2
00175     synopsis for qhull
00176 */
00177 char qh_prompt2[]= "\n\
00178 qhalf- halfspace intersection about a point.  Qhull %s\n\
00179     input (stdin): [dim, 1, interior point], dim+1, n, coefficients+offset\n\
00180     comments start with a non-numeric character\n\
00181 \n\
00182 options (qhalf.htm):\n\
00183     Hn,n - specify coordinates of interior point\n\
00184     Qt   - triangulated output\n\
00185     QJ   - joggled input instead of merged facets\n\
00186     Tv   - verify result: structure, convexity, and redundancy\n\
00187     .    - concise list of all options\n\
00188     -    - one-line description of all options\n\
00189 \n\
00190 output options (subset):\n\
00191     s    - summary of results (default)\n\
00192     Fp   - intersection coordinates\n\
00193     Fv   - non-redundant halfspaces incident to each intersection\n\
00194     Fx   - non-redundant halfspaces\n\
00195     o    - OFF file format (dual convex hull)\n\
00196     G    - Geomview output (dual convex hull)\n\
00197     m    - Mathematica output (dual convex hull)\n\
00198     QVn  - print intersections for halfspace n, -n if not\n\
00199     TO file - output results to file, may be enclosed in single quotes\n\
00200 \n\
00201 examples:\n\
00202     rbox d | qconvex FQ n | qhalf s H0,0,0 Fp\n\
00203     rbox c | qconvex FQ FV n | qhalf s i\n\
00204     rbox c | qconvex FQ FV n | qhalf s o\n\
00205 \n\
00206 ";
00207 /* for opts, don't assign 'e' or 'E' to a flag (already used for exponent) */
00208 
00209 /*-<a                             href="../libqhull/qh-qhull.htm#TOC"
00210   >-------------------------------</a><a name="prompt3">-</a>
00211 
00212   qh_prompt3
00213     concise prompt for qhull
00214 */
00215 char qh_prompt3[]= "\n\
00216 Qhull %s.\n\
00217 Except for 'F.' and 'PG', upper_case options take an argument.\n\
00218 \n\
00219  incidences     Geomview       mathematica    OFF_format     point_dual\n\
00220  summary        facet_dump\n\
00221 \n\
00222  Fc_redundant   Fd_cdd_in      FF_dump_xridge FIDs           Fmerges\n\
00223  Fneighbors     FN_intersect   FOptions       Fp_coordinates FP_nearest\n\
00224  FQhalf         Fsummary       Fv_halfspace   FMaple         Fx_non_redundant\n\
00225 \n\
00226  Gvertices      Gpoints        Gall_points    Gno_planes     Ginner\n\
00227  Gcentrums      Ghyperplanes   Gridges        Gouter         GDrop_dim\n\
00228 \n\
00229  PArea_keep     Pdrop d0:0D0   Pgood          PFacet_area_keep\n\
00230  PGood_neighbors PMerge_keep   Poutput_forced Pprecision_not\n\
00231 \n\
00232  Qbk:0Bk:0_drop Qcoplanar      QG_half_good   Qi_redundant   QJoggle\n\
00233  Qsearch_1st    Qtriangulate   QVertex_good\n\
00234 \n\
00235  T4_trace       Tcheck_often   Tstatistics    Tverify        Tz_stdout\n\
00236  TFacet_log     TInput_file    TPoint_trace   TMerge_trace   TOutput_file\n\
00237  TWide_trace    TVertex_stop   TCone_stop\n\
00238 \n\
00239  Angle_max      Centrum_size   Random_dist    Ucoplanar_max  Wide_outside\n\
00240 ";
00241 
00242 /*-<a                             href="../libqhull/qh-qhull.htm#TOC"
00243   >-------------------------------</a><a name="main">-</a>
00244 
00245   main( argc, argv )
00246     processes the command line, calls qhull() to do the work, and exits
00247 
00248   design:
00249     initializes data structures
00250     reads points
00251     finishes initialization
00252     computes convex hull and other structures
00253     checks the result
00254     writes the output
00255     frees memory
00256 */
00257 int main(int argc, char *argv[]) {
00258   int curlong, totlong; /* used !qh_NOmem */
00259   int exitcode, numpoints, dim;
00260   coordT *points;
00261   boolT ismalloc;
00262 
00263 #if __MWERKS__ && __POWERPC__
00264   char inBuf[BUFSIZ], outBuf[BUFSIZ], errBuf[BUFSIZ];
00265   SIOUXSettings.showstatusline= false;
00266   SIOUXSettings.tabspaces= 1;
00267   SIOUXSettings.rows= 40;
00268   if (setvbuf(stdin, inBuf, _IOFBF, sizeof(inBuf)) < 0   /* w/o, SIOUX I/O is slow*/
00269   || setvbuf(stdout, outBuf, _IOFBF, sizeof(outBuf)) < 0
00270   || (stdout != stderr && setvbuf(stderr, errBuf, _IOFBF, sizeof(errBuf)) < 0))
00271     fprintf(stderr, "qhull internal warning (main): could not change stdio to fully buffered.\n");
00272   argc= ccommand(&argv);
00273 #endif
00274 
00275   if ((argc == 1) && isatty( 0 /*stdin*/)) {
00276     fprintf(stdout, qh_prompt2, qh_version);
00277     exit(qh_ERRnone);
00278   }
00279   if (argc > 1 && *argv[1] == '-' && !*(argv[1]+1)) {
00280     fprintf(stdout, qh_prompta, qh_version,
00281         qh_promptb, qh_promptc, qh_promptd, qh_prompte);
00282     exit(qh_ERRnone);
00283   }
00284   if (argc >1 && *argv[1] == '.' && !*(argv[1]+1)) {
00285     fprintf(stdout, qh_prompt3, qh_version);
00286     exit(qh_ERRnone);
00287   }
00288   qh_init_A(stdin, stdout, stderr, argc, argv);  /* sets qh qhull_command */
00289   exitcode= setjmp(qh errexit); /* simple statement for CRAY J916 */
00290   if (!exitcode) {
00291     qh_option("Halfspace", NULL, NULL);
00292     qh HALFspace= True;    /* 'H'   */
00293     qh_checkflags(qh qhull_command, hidden_options);
00294     qh_initflags(qh qhull_command);
00295     if (qh SCALEinput) {
00296       fprintf(qh ferr, "\
00297 qhull error: options 'Qbk:n' and 'QBk:n' are not used with qhalf.\n\
00298              Use 'Qbk:0Bk:0 to drop dimension k.\n");
00299       qh_errexit(qh_ERRinput, NULL, NULL);
00300     }
00301     points= qh_readpoints(&numpoints, &dim, &ismalloc);
00302     if (dim >= 5) {
00303       qh_option("Qxact_merge", NULL, NULL);
00304       qh MERGEexact= True; /* 'Qx' always */
00305     }
00306     qh_init_B(points, numpoints, dim, ismalloc);
00307     qh_qhull();
00308     qh_check_output();
00309     qh_produce_output();
00310     if (qh VERIFYoutput && !qh FORCEoutput && !qh STOPpoint && !qh STOPcone)
00311       qh_check_points();
00312     exitcode= qh_ERRnone;
00313   }
00314   qh NOerrexit= True;  /* no more setjmp */
00315 #ifdef qh_NOmem
00316   qh_freeqhull( True);
00317 #else
00318   qh_freeqhull( False);
00319   qh_memfreeshort(&curlong, &totlong);
00320   if (curlong || totlong)
00321     fprintf(stderr, "qhull internal warning (main): did not free %d bytes of long memory(%d pieces)\n",
00322        totlong, curlong);
00323 #endif
00324   return exitcode;
00325 } /* main */
00326