libqhull: user.c Source File

Go to the documentation of this file.
00001 /*<html><pre>  -<a                             href="qh-user.htm"
00002   >-------------------------------</a><a name="TOP">-</a>
00003 
00004    user.c
00005    user redefinable functions
00006 
00007    see user2.c for qh_fprintf, qh_malloc, qh_free
00008 
00009    see README.txt  see COPYING.txt for copyright information.
00010 
00011    see libqhull.h for data structures, macros, and user-callable functions.
00012 
00013    see user_eg.c, unix.c, and qhull_interface.cpp for examples.
00014 
00015    see user.h for user-definable constants
00016 
00017       use qh_NOmem in mem.h to turn off memory management
00018       use qh_NOmerge in user.h to turn off facet merging
00019       set qh_KEEPstatistics in user.h to 0 to turn off statistics
00020 
00021    This is unsupported software.  You're welcome to make changes,
00022    but you're on your own if something goes wrong.  Use 'Tc' to
00023    check frequently.  Usually qhull will report an error if
00024    a data structure becomes inconsistent.  If so, it also reports
00025    the last point added to the hull, e.g., 102.  You can then trace
00026    the execution of qhull with "T4P102".
00027 
00028    Please report any errors that you fix to qhull@qhull.org
00029 
00030    call_qhull is a template for calling qhull from within your application
00031 
00032    if you recompile and load this module, then user.o will not be loaded
00033    from qhull.a
00034 
00035    you can add additional quick allocation sizes in qh_user_memsizes
00036 
00037    if the other functions here are redefined to not use qh_print...,
00038    then io.o will not be loaded from qhull.a.  See user_eg.c for an
00039    example.  We recommend keeping io.o for the extra debugging
00040    information it supplies.
00041 */
00042 
00043 #include "qhull_a.h"
00044 
00045 #include <stdarg.h>
00046 
00047 /*-<a                             href="qh-user.htm#TOC"
00048   >-------------------------------</a><a name="call_qhull">-</a>
00049 
00050   qh_call_qhull( void )
00051     template for calling qhull from inside your program
00052     remove #if 0, #endif to compile
00053 
00054   returns:
00055     exit code(see qh_ERR... in libqhull.h)
00056     all memory freed
00057 
00058   notes:
00059     This can be called any number of times.
00060 
00061   see:
00062     qh_call_qhull_once()
00063 
00064 */
00065 #if 0
00066 {
00067   int dim;                  /* dimension of points */
00068   int numpoints;            /* number of points */
00069   coordT *points;           /* array of coordinates for each point */
00070   boolT ismalloc;           /* True if qhull should free points in qh_freeqhull() or reallocation */
00071   char flags[]= "qhull Tv"; /* option flags for qhull, see qh_opt.htm */
00072   FILE *outfile= stdout;    /* output from qh_produce_output()
00073                                use NULL to skip qh_produce_output() */
00074   FILE *errfile= stderr;    /* error messages from qhull code */
00075   int exitcode;             /* 0 if no error from qhull */
00076   facetT *facet;            /* set by FORALLfacets */
00077   int curlong, totlong;     /* memory remaining after qh_memfreeshort */
00078 
00079 #if qh_QHpointer  /* see user.h */
00080   if (qh_qh){
00081       printf ("QH6238: Qhull link error.  The global variable qh_qh was not initialized\n\
00082               to NULL by global.c.  Please compile this program with -Dqh_QHpointer_dllimport\n\
00083               as well as -Dqh_QHpointer, or use libqhullstatic, or use a different tool chain.\n\n");
00084       exit -1;
00085   }
00086 #endif
00087 
00088   /* initialize dim, numpoints, points[], ismalloc here */
00089   exitcode= qh_new_qhull(dim, numpoints, points, ismalloc,
00090                       flags, outfile, errfile);
00091   if (!exitcode) {                  /* if no error */
00092     /* 'qh facet_list' contains the convex hull */
00093     FORALLfacets {
00094        /* ... your code ... */
00095     }
00096   }
00097   qh_freeqhull(!qh_ALL);
00098   qh_memfreeshort(&curlong, &totlong);
00099   if (curlong || totlong)
00100     qh_fprintf(errfile, 7068, "qhull internal warning (main): did not free %d bytes of long memory(%d pieces)\n", totlong, curlong);
00101 }
00102 #endif
00103 
00104 /*-<a                             href="qh-user.htm#TOC"
00105   >-------------------------------</a><a name="new_qhull">-</a>
00106 
00107   qh_new_qhull( dim, numpoints, points, ismalloc, qhull_cmd, outfile, errfile )
00108     build new qhull data structure and return exitcode (0 if no errors)
00109 
00110   notes:
00111     do not modify points until finished with results.
00112       The qhull data structure contains pointers into the points array.
00113     do not call qhull functions before qh_new_qhull().
00114       The qhull data structure is not initialized until qh_new_qhull().
00115 
00116     outfile may be null
00117     qhull_cmd must start with "qhull "
00118     projects points to a new point array for Delaunay triangulations ('d' and 'v')
00119     transforms points into a new point array for halfspace intersection ('H')
00120 
00121 
00122   To allow multiple, concurrent calls to qhull()
00123     - set qh_QHpointer in user.h
00124     - use qh_save_qhull and qh_restore_qhull to swap the global data structure between calls.
00125     - use qh_freeqhull(qh_ALL) to free intermediate convex hulls
00126 
00127   see:
00128     user_eg.c for an example
00129 */
00130 int qh_new_qhull(int dim, int numpoints, coordT *points, boolT ismalloc,
00131                 char *qhull_cmd, FILE *outfile, FILE *errfile) {
00132   int exitcode, hulldim;
00133   boolT new_ismalloc;
00134   static boolT firstcall = True;
00135   coordT *new_points;
00136 
00137   if (firstcall) {
00138     qh_meminit(errfile);
00139     firstcall= False;
00140   }
00141   if (strncmp(qhull_cmd,"qhull ", (size_t)6)) {
00142     qh_fprintf(errfile, 6186, "qhull error (qh_new_qhull): start qhull_cmd argument with \"qhull \"\n");
00143     qh_exit(qh_ERRinput);
00144   }
00145   qh_initqhull_start(NULL, outfile, errfile);
00146   trace1((qh ferr, 1044, "qh_new_qhull: build new Qhull for %d %d-d points with %s\n", numpoints, dim, qhull_cmd));
00147   exitcode = setjmp(qh errexit);
00148   if (!exitcode)
00149   {
00150     qh NOerrexit = False;
00151     qh_initflags(qhull_cmd);
00152     if (qh DELAUNAY)
00153       qh PROJECTdelaunay= True;
00154     if (qh HALFspace) {
00155       /* points is an array of halfspaces,
00156          the last coordinate of each halfspace is its offset */
00157       hulldim= dim-1;
00158       qh_setfeasible(hulldim);
00159       new_points= qh_sethalfspace_all(dim, numpoints, points, qh feasible_point);
00160       new_ismalloc= True;
00161       if (ismalloc)
00162         qh_free(points);
00163     }else {
00164       hulldim= dim;
00165       new_points= points;
00166       new_ismalloc= ismalloc;
00167     }
00168     qh_init_B(new_points, numpoints, hulldim, new_ismalloc);
00169     qh_qhull();
00170     qh_check_output();
00171     if (outfile) {
00172       qh_produce_output();
00173     }else {
00174       qh_prepare_output();
00175     }
00176     if (qh VERIFYoutput && !qh STOPpoint && !qh STOPcone)
00177       qh_check_points();
00178   }
00179   qh NOerrexit = True;
00180   return exitcode;
00181 } /* new_qhull */
00182 
00183 /*-<a                             href="qh-user.htm#TOC"
00184   >-------------------------------</a><a name="errexit">-</a>
00185 
00186   qh_errexit( exitcode, facet, ridge )
00187     report and exit from an error
00188     report facet and ridge if non-NULL
00189     reports useful information such as last point processed
00190     set qh.FORCEoutput to print neighborhood of facet
00191 
00192   see:
00193     qh_errexit2() in libqhull.c for printing 2 facets
00194 
00195   design:
00196     check for error within error processing
00197     compute qh.hulltime
00198     print facet and ridge (if any)
00199     report commandString, options, qh.furthest_id
00200     print summary and statistics (including precision statistics)
00201     if qh_ERRsingular
00202       print help text for singular data set
00203     exit program via long jump (if defined) or exit()
00204 */
00205 void qh_errexit(int exitcode, facetT *facet, ridgeT *ridge) {
00206 
00207   if (qh ERREXITcalled) {
00208     qh_fprintf(qh ferr, 8126, "\nqhull error while processing previous error.  Exit program\n");
00209     qh_exit(qh_ERRqhull);
00210   }
00211   qh ERREXITcalled= True;
00212   if (!qh QHULLfinished)
00213     qh hulltime= qh_CPUclock - qh hulltime;
00214   qh_errprint("ERRONEOUS", facet, NULL, ridge, NULL);
00215   qh_fprintf(qh ferr, 8127, "\nWhile executing: %s | %s\n", qh rbox_command, qh qhull_command);
00216   qh_fprintf(qh ferr, 8128, "Options selected for Qhull %s:\n%s\n", qh_version, qh qhull_options);
00217   if (qh furthest_id >= 0) {
00218     qh_fprintf(qh ferr, 8129, "Last point added to hull was p%d.", qh furthest_id);
00219     if (zzval_(Ztotmerge))
00220       qh_fprintf(qh ferr, 8130, "  Last merge was #%d.", zzval_(Ztotmerge));
00221     if (qh QHULLfinished)
00222       qh_fprintf(qh ferr, 8131, "\nQhull has finished constructing the hull.");
00223     else if (qh POSTmerging)
00224       qh_fprintf(qh ferr, 8132, "\nQhull has started post-merging.");
00225     qh_fprintf(qh ferr, 8133, "\n");
00226   }
00227   if (qh FORCEoutput && (qh QHULLfinished || (!facet && !ridge)))
00228     qh_produce_output();
00229   else {
00230     if (exitcode != qh_ERRsingular && zzval_(Zsetplane) > qh hull_dim+1) {
00231       qh_fprintf(qh ferr, 8134, "\nAt error exit:\n");
00232       qh_printsummary(qh ferr);
00233       if (qh PRINTstatistics) {
00234         qh_collectstatistics();
00235         qh_printstatistics(qh ferr, "at error exit");
00236         qh_memstatistics(qh ferr);
00237       }
00238     }
00239     if (qh PRINTprecision)
00240       qh_printstats(qh ferr, qhstat precision, NULL);
00241   }
00242   if (!exitcode)
00243     exitcode= qh_ERRqhull;
00244   else if (exitcode == qh_ERRsingular)
00245     qh_printhelp_singular(qh ferr);
00246   else if (exitcode == qh_ERRprec && !qh PREmerge)
00247     qh_printhelp_degenerate(qh ferr);
00248   if (qh NOerrexit) {
00249     qh_fprintf(qh ferr, 6187, "qhull error while ending program.  Exit program\n");
00250     qh_exit(qh_ERRqhull);
00251   }
00252   qh ERREXITcalled= False;
00253   qh NOerrexit= True;
00254   longjmp(qh errexit, exitcode);
00255 } /* errexit */
00256 
00257 
00258 /*-<a                             href="qh-user.htm#TOC"
00259   >-------------------------------</a><a name="errprint">-</a>
00260 
00261   qh_errprint( fp, string, atfacet, otherfacet, atridge, atvertex )
00262     prints out the information of facets and ridges to fp
00263     also prints neighbors and geomview output
00264 
00265   notes:
00266     except for string, any parameter may be NULL
00267 */
00268 void qh_errprint(const char *string, facetT *atfacet, facetT *otherfacet, ridgeT *atridge, vertexT *atvertex) {
00269   int i;
00270 
00271   if (atfacet) {
00272     qh_fprintf(qh ferr, 8135, "%s FACET:\n", string);
00273     qh_printfacet(qh ferr, atfacet);
00274   }
00275   if (otherfacet) {
00276     qh_fprintf(qh ferr, 8136, "%s OTHER FACET:\n", string);
00277     qh_printfacet(qh ferr, otherfacet);
00278   }
00279   if (atridge) {
00280     qh_fprintf(qh ferr, 8137, "%s RIDGE:\n", string);
00281     qh_printridge(qh ferr, atridge);
00282     if (atridge->top && atridge->top != atfacet && atridge->top != otherfacet)
00283       qh_printfacet(qh ferr, atridge->top);
00284     if (atridge->bottom
00285         && atridge->bottom != atfacet && atridge->bottom != otherfacet)
00286       qh_printfacet(qh ferr, atridge->bottom);
00287     if (!atfacet)
00288       atfacet= atridge->top;
00289     if (!otherfacet)
00290       otherfacet= otherfacet_(atridge, atfacet);
00291   }
00292   if (atvertex) {
00293     qh_fprintf(qh ferr, 8138, "%s VERTEX:\n", string);
00294     qh_printvertex(qh ferr, atvertex);
00295   }
00296   if (qh fout && qh FORCEoutput && atfacet && !qh QHULLfinished && !qh IStracing) {
00297     qh_fprintf(qh ferr, 8139, "ERRONEOUS and NEIGHBORING FACETS to output\n");
00298     for (i=0; i < qh_PRINTEND; i++)  /* use fout for geomview output */
00299       qh_printneighborhood(qh fout, qh PRINTout[i], atfacet, otherfacet,
00300                             !qh_ALL);
00301   }
00302 } /* errprint */
00303 
00304 
00305 /*-<a                             href="qh-user.htm#TOC"
00306   >-------------------------------</a><a name="printfacetlist">-</a>
00307 
00308   qh_printfacetlist( fp, facetlist, facets, printall )
00309     print all fields for a facet list and/or set of facets to fp
00310     if !printall,
00311       only prints good facets
00312 
00313   notes:
00314     also prints all vertices
00315 */
00316 void qh_printfacetlist(facetT *facetlist, setT *facets, boolT printall) {
00317   facetT *facet, **facetp;
00318 
00319   qh_printbegin(qh ferr, qh_PRINTfacets, facetlist, facets, printall);
00320   FORALLfacet_(facetlist)
00321     qh_printafacet(qh ferr, qh_PRINTfacets, facet, printall);
00322   FOREACHfacet_(facets)
00323     qh_printafacet(qh ferr, qh_PRINTfacets, facet, printall);
00324   qh_printend(qh ferr, qh_PRINTfacets, facetlist, facets, printall);
00325 } /* printfacetlist */
00326 
00327 
00328 /*-<a                             href="qh-io.htm#TOC"
00329   >-------------------------------</a><a name="printhelp_degenerate">-</a>
00330 
00331   qh_printhelp_degenerate( fp )
00332     prints descriptive message for precision error
00333 
00334   notes:
00335     no message if qh_QUICKhelp
00336 */
00337 void qh_printhelp_degenerate(FILE *fp) {
00338 
00339   if (qh MERGEexact || qh PREmerge || qh JOGGLEmax < REALmax/2)
00340     qh_fprintf(fp, 9368, "\n\
00341 A Qhull error has occurred.  Qhull should have corrected the above\n\
00342 precision error.  Please send the input and all of the output to\n\
00343 qhull_bug@qhull.org\n");
00344   else if (!qh_QUICKhelp) {
00345     qh_fprintf(fp, 9369, "\n\
00346 Precision problems were detected during construction of the convex hull.\n\
00347 This occurs because convex hull algorithms assume that calculations are\n\
00348 exact, but floating-point arithmetic has roundoff errors.\n\
00349 \n\
00350 To correct for precision problems, do not use 'Q0'.  By default, Qhull\n\
00351 selects 'C-0' or 'Qx' and merges non-convex facets.  With option 'QJ',\n\
00352 Qhull joggles the input to prevent precision problems.  See \"Imprecision\n\
00353 in Qhull\" (qh-impre.htm).\n\
00354 \n\
00355 If you use 'Q0', the output may include\n\
00356 coplanar ridges, concave ridges, and flipped facets.  In 4-d and higher,\n\
00357 Qhull may produce a ridge with four neighbors or two facets with the same \n\
00358 vertices.  Qhull reports these events when they occur.  It stops when a\n\
00359 concave ridge, flipped facet, or duplicate facet occurs.\n");
00360 #if REALfloat
00361     qh_fprintf(fp, 9370, "\
00362 \n\
00363 Qhull is currently using single precision arithmetic.  The following\n\
00364 will probably remove the precision problems:\n\
00365   - recompile qhull for realT precision(#define REALfloat 0 in user.h).\n");
00366 #endif
00367     if (qh DELAUNAY && !qh SCALElast && qh MAXabs_coord > 1e4)
00368       qh_fprintf(fp, 9371, "\
00369 \n\
00370 When computing the Delaunay triangulation of coordinates > 1.0,\n\
00371   - use 'Qbb' to scale the last coordinate to [0,m] (max previous coordinate)\n");
00372     if (qh DELAUNAY && !qh ATinfinity)
00373       qh_fprintf(fp, 9372, "\
00374 When computing the Delaunay triangulation:\n\
00375   - use 'Qz' to add a point at-infinity.  This reduces precision problems.\n");
00376 
00377     qh_fprintf(fp, 9373, "\
00378 \n\
00379 If you need triangular output:\n\
00380   - use option 'Qt' to triangulate the output\n\
00381   - use option 'QJ' to joggle the input points and remove precision errors\n\
00382   - use option 'Ft'.  It triangulates non-simplicial facets with added points.\n\
00383 \n\
00384 If you must use 'Q0',\n\
00385 try one or more of the following options.  They can not guarantee an output.\n\
00386   - use 'QbB' to scale the input to a cube.\n\
00387   - use 'Po' to produce output and prevent partitioning for flipped facets\n\
00388   - use 'V0' to set min. distance to visible facet as 0 instead of roundoff\n\
00389   - use 'En' to specify a maximum roundoff error less than %2.2g.\n\
00390   - options 'Qf', 'Qbb', and 'QR0' may also help\n",
00391                qh DISTround);
00392     qh_fprintf(fp, 9374, "\
00393 \n\
00394 To guarantee simplicial output:\n\
00395   - use option 'Qt' to triangulate the output\n\
00396   - use option 'QJ' to joggle the input points and remove precision errors\n\
00397   - use option 'Ft' to triangulate the output by adding points\n\
00398   - use exact arithmetic (see \"Imprecision in Qhull\", qh-impre.htm)\n\
00399 ");
00400   }
00401 } /* printhelp_degenerate */
00402 
00403 
00404 /*-<a                             href="qh-globa.htm#TOC"
00405   >-------------------------------</a><a name="printhelp_narrowhull">-</a>
00406 
00407   qh_printhelp_narrowhull( minangle )
00408     Warn about a narrow hull
00409 
00410   notes:
00411     Alternatively, reduce qh_WARNnarrow in user.h
00412 
00413 */
00414 void qh_printhelp_narrowhull(FILE *fp, realT minangle) {
00415 
00416     qh_fprintf(fp, 9375, "qhull precision warning: \n\
00417 The initial hull is narrow (cosine of min. angle is %.16f).\n\
00418 Is the input lower dimensional (e.g., on a plane in 3-d)?  Qhull may\n\
00419 produce a wide facet.  Options 'QbB' (scale to unit box) or 'Qbb' (scale\n\
00420 last coordinate) may remove this warning.  Use 'Pp' to skip this warning.\n\
00421 See 'Limitations' in qh-impre.htm.\n",
00422           -minangle);   /* convert from angle between normals to angle between facets */
00423 } /* printhelp_narrowhull */
00424 
00425 /*-<a                             href="qh-io.htm#TOC"
00426   >-------------------------------</a><a name="printhelp_singular">-</a>
00427 
00428   qh_printhelp_singular( fp )
00429     prints descriptive message for singular input
00430 */
00431 void qh_printhelp_singular(FILE *fp) {
00432   facetT *facet;
00433   vertexT *vertex, **vertexp;
00434   realT min, max, *coord, dist;
00435   int i,k;
00436 
00437   qh_fprintf(fp, 9376, "\n\
00438 The input to qhull appears to be less than %d dimensional, or a\n\
00439 computation has overflowed.\n\n\
00440 Qhull could not construct a clearly convex simplex from points:\n",
00441            qh hull_dim);
00442   qh_printvertexlist(fp, "", qh facet_list, NULL, qh_ALL);
00443   if (!qh_QUICKhelp)
00444     qh_fprintf(fp, 9377, "\n\
00445 The center point is coplanar with a facet, or a vertex is coplanar\n\
00446 with a neighboring facet.  The maximum round off error for\n\
00447 computing distances is %2.2g.  The center point, facets and distances\n\
00448 to the center point are as follows:\n\n", qh DISTround);
00449   qh_printpointid(fp, "center point", qh hull_dim, qh interior_point, -1);
00450   qh_fprintf(fp, 9378, "\n");
00451   FORALLfacets {
00452     qh_fprintf(fp, 9379, "facet");
00453     FOREACHvertex_(facet->vertices)
00454       qh_fprintf(fp, 9380, " p%d", qh_pointid(vertex->point));
00455     zinc_(Zdistio);
00456     qh_distplane(qh interior_point, facet, &dist);
00457     qh_fprintf(fp, 9381, " distance= %4.2g\n", dist);
00458   }
00459   if (!qh_QUICKhelp) {
00460     if (qh HALFspace)
00461       qh_fprintf(fp, 9382, "\n\
00462 These points are the dual of the given halfspaces.  They indicate that\n\
00463 the intersection is degenerate.\n");
00464     qh_fprintf(fp, 9383,"\n\
00465 These points either have a maximum or minimum x-coordinate, or\n\
00466 they maximize the determinant for k coordinates.  Trial points\n\
00467 are first selected from points that maximize a coordinate.\n");
00468     if (qh hull_dim >= qh_INITIALmax)
00469       qh_fprintf(fp, 9384, "\n\
00470 Because of the high dimension, the min x-coordinate and max-coordinate\n\
00471 points are used if the determinant is non-zero.  Option 'Qs' will\n\
00472 do a better, though much slower, job.  Instead of 'Qs', you can change\n\
00473 the points by randomly rotating the input with 'QR0'.\n");
00474   }
00475   qh_fprintf(fp, 9385, "\nThe min and max coordinates for each dimension are:\n");
00476   for (k=0; k < qh hull_dim; k++) {
00477     min= REALmax;
00478     max= -REALmin;
00479     for (i=qh num_points, coord= qh first_point+k; i--; coord += qh hull_dim) {
00480       maximize_(max, *coord);
00481       minimize_(min, *coord);
00482     }
00483     qh_fprintf(fp, 9386, "  %d:  %8.4g  %8.4g  difference= %4.4g\n", k, min, max, max-min);
00484   }
00485   if (!qh_QUICKhelp) {
00486     qh_fprintf(fp, 9387, "\n\
00487 If the input should be full dimensional, you have several options that\n\
00488 may determine an initial simplex:\n\
00489   - use 'QJ'  to joggle the input and make it full dimensional\n\
00490   - use 'QbB' to scale the points to the unit cube\n\
00491   - use 'QR0' to randomly rotate the input for different maximum points\n\
00492   - use 'Qs'  to search all points for the initial simplex\n\
00493   - use 'En'  to specify a maximum roundoff error less than %2.2g.\n\
00494   - trace execution with 'T3' to see the determinant for each point.\n",
00495                      qh DISTround);
00496 #if REALfloat
00497     qh_fprintf(fp, 9388, "\
00498   - recompile qhull for realT precision(#define REALfloat 0 in libqhull.h).\n");
00499 #endif
00500     qh_fprintf(fp, 9389, "\n\
00501 If the input is lower dimensional:\n\
00502   - use 'QJ' to joggle the input and make it full dimensional\n\
00503   - use 'Qbk:0Bk:0' to delete coordinate k from the input.  You should\n\
00504     pick the coordinate with the least range.  The hull will have the\n\
00505     correct topology.\n\
00506   - determine the flat containing the points, rotate the points\n\
00507     into a coordinate plane, and delete the other coordinates.\n\
00508   - add one or more points to make the input full dimensional.\n\
00509 ");
00510     if (qh DELAUNAY && !qh ATinfinity)
00511       qh_fprintf(fp, 9390, "\n\n\
00512 This is a Delaunay triangulation and the input is co-circular or co-spherical:\n\
00513   - use 'Qz' to add a point \"at infinity\" (i.e., above the paraboloid)\n\
00514   - or use 'QJ' to joggle the input and avoid co-circular data\n");
00515   }
00516 } /* printhelp_singular */
00517 
00518 /*-<a                             href="qh-globa.htm#TOC"
00519   >-------------------------------</a><a name="user_memsizes">-</a>
00520 
00521   qh_user_memsizes()
00522     allocate up to 10 additional, quick allocation sizes
00523 
00524   notes:
00525     increase maximum number of allocations in qh_initqhull_mem()
00526 */
00527 void qh_user_memsizes(void) {
00528 
00529   /* qh_memsize(size); */
00530 } /* user_memsizes */
00531 
00532