1 /*<html><pre> -<a href="qh-user.htm"
2 >-------------------------------</a><a name="TOP">-</a>
3
4 user.c
5 user redefinable functions
6
7 see user2.c for qh_fprintf, qh_malloc, qh_free
8
9 see README.txt see COPYING.txt for copyright information.
10
11 see libqhull.h for data structures, macros, and user-callable functions.
12
13 see user_eg.c, unix.c, and qhull_interface.cpp for examples.
14
15 see user.h for user-definable constants
16
17 use qh_NOmem in mem.h to turn off memory management
18 use qh_NOmerge in user.h to turn off facet merging
19 set qh_KEEPstatistics in user.h to 0 to turn off statistics
20
21 This is unsupported software. You're welcome to make changes,
22 but you're on your own if something goes wrong. Use 'Tc' to
23 check frequently. Usually qhull will report an error if
24 a data structure becomes inconsistent. If so, it also reports
25 the last point added to the hull, e.g., 102. You can then trace
26 the execution of qhull with "T4P102".
27
28 Please report any errors that you fix to qhull@qhull.org
29
30 call_qhull is a template for calling qhull from within your application
31
32 if you recompile and load this module, then user.o will not be loaded
33 from qhull.a
34
35 you can add additional quick allocation sizes in qh_user_memsizes
36
37 if the other functions here are redefined to not use qh_print...,
38 then io.o will not be loaded from qhull.a. See user_eg.c for an
39 example. We recommend keeping io.o for the extra debugging
40 information it supplies.
41 */
42
43 #include "qhull_a.h"
44
45 #include <stdarg.h>
46
47 /*-<a href="qh-user.htm#TOC"
48 >-------------------------------</a><a name="call_qhull">-</a>
49
50 qh_call_qhull( void )
51 template for calling qhull from inside your program
52 remove #if 0, #endif to compile
53
54 returns:
55 exit code(see qh_ERR... in libqhull.h)
56 all memory freed
57
58 notes:
59 This can be called any number of times.
60
61 see:
62 qh_call_qhull_once()
63
64 */
65 #if 0
66 {
67 int dim; /* dimension of points */
68 int numpoints; /* number of points */
69 coordT *points; /* array of coordinates for each point */
70 boolT ismalloc; /* True if qhull should free points in qh_freeqhull() or reallocation */
71 char flags[]= "qhull Tv"; /* option flags for qhull, see qh_opt.htm */
72 FILE *outfile= stdout; /* output from qh_produce_output()
73 use NULL to skip qh_produce_output() */
74 FILE *errfile= stderr; /* error messages from qhull code */
75 int exitcode; /* 0 if no error from qhull */
76 facetT *facet; /* set by FORALLfacets */
77 int curlong, totlong; /* memory remaining after qh_memfreeshort */
78
79 #if qh_QHpointer /* see user.h */
80 if (qh_qh){
81 printf ("QH6238: Qhull link error. The global variable qh_qh was not initialized\n\
82 to NULL by global.c. Please compile this program with -Dqh_QHpointer_dllimport\n\
83 as well as -Dqh_QHpointer, or use libqhullstatic, or use a different tool chain.\n\n");
84 exit -1;
85 }
86 #endif
87
88 /* initialize dim, numpoints, points[], ismalloc here */
89 exitcode= qh_new_qhull(dim, numpoints, points, ismalloc,
90 flags, outfile, errfile);
91 if (!exitcode) { /* if no error */
92 /* 'qh facet_list' contains the convex hull */
93 FORALLfacets {
94 /* ... your code ... */
95 }
96 }
97 qh_freeqhull(!qh_ALL);
98 qh_memfreeshort(&curlong, &totlong);
99 if (curlong || totlong)
100 qh_fprintf(errfile, 7068, "qhull internal warning (main): did not free %d bytes of long memory(%d pieces)\n", totlong, curlong);
101 }
102 #endif
103
104 /*-<a href="qh-user.htm#TOC"
105 >-------------------------------</a><a name="new_qhull">-</a>
106
107 qh_new_qhull( dim, numpoints, points, ismalloc, qhull_cmd, outfile, errfile )
108 build new qhull data structure and return exitcode (0 if no errors)
109
110 notes:
111 do not modify points until finished with results.
112 The qhull data structure contains pointers into the points array.
113 do not call qhull functions before qh_new_qhull().
114 The qhull data structure is not initialized until qh_new_qhull().
115
116 outfile may be null
117 qhull_cmd must start with "qhull "
118 projects points to a new point array for Delaunay triangulations ('d' and 'v')
119 transforms points into a new point array for halfspace intersection ('H')
120
121
122 To allow multiple, concurrent calls to qhull()
123 - set qh_QHpointer in user.h
124 - use qh_save_qhull and qh_restore_qhull to swap the global data structure between calls.
125 - use qh_freeqhull(qh_ALL) to free intermediate convex hulls
126
127 see:
128 user_eg.c for an example
129 */
qh_new_qhull(int dim,int numpoints,coordT * points,boolT ismalloc,char * qhull_cmd,FILE * outfile,FILE * errfile)130 int qh_new_qhull(int dim, int numpoints, coordT *points, boolT ismalloc,
131 char *qhull_cmd, FILE *outfile, FILE *errfile) {
132 int exitcode, hulldim;
133 boolT new_ismalloc;
134 static boolT firstcall = True;
135 coordT *new_points;
136
137 if (firstcall) {
138 qh_meminit(errfile);
139 firstcall= False;
140 }
141 if (strncmp(qhull_cmd,"qhull ", (size_t)6)) {
142 qh_fprintf(errfile, 6186, "qhull error (qh_new_qhull): start qhull_cmd argument with \"qhull \"\n");
143 qh_exit(qh_ERRinput);
144 }
145 qh_initqhull_start(NULL, outfile, errfile);
146 trace1((qh ferr, 1044, "qh_new_qhull: build new Qhull for %d %d-d points with %s\n", numpoints, dim, qhull_cmd));
147 exitcode = setjmp(qh errexit);
148 if (!exitcode)
149 {
150 qh NOerrexit = False;
151 qh_initflags(qhull_cmd);
152 if (qh DELAUNAY)
153 qh PROJECTdelaunay= True;
154 if (qh HALFspace) {
155 /* points is an array of halfspaces,
156 the last coordinate of each halfspace is its offset */
157 hulldim= dim-1;
158 qh_setfeasible(hulldim);
159 new_points= qh_sethalfspace_all(dim, numpoints, points, qh feasible_point);
160 new_ismalloc= True;
161 if (ismalloc)
162 qh_free(points);
163 }else {
164 hulldim= dim;
165 new_points= points;
166 new_ismalloc= ismalloc;
167 }
168 qh_init_B(new_points, numpoints, hulldim, new_ismalloc);
169 qh_qhull();
170 qh_check_output();
171 if (outfile) {
172 qh_produce_output();
173 }else {
174 qh_prepare_output();
175 }
176 if (qh VERIFYoutput && !qh STOPpoint && !qh STOPcone)
177 qh_check_points();
178 }
179 qh NOerrexit = True;
180 return exitcode;
181 } /* new_qhull */
182
183 /*-<a href="qh-user.htm#TOC"
184 >-------------------------------</a><a name="errexit">-</a>
185
186 qh_errexit( exitcode, facet, ridge )
187 report and exit from an error
188 report facet and ridge if non-NULL
189 reports useful information such as last point processed
190 set qh.FORCEoutput to print neighborhood of facet
191
192 see:
193 qh_errexit2() in libqhull.c for printing 2 facets
194
195 design:
196 check for error within error processing
197 compute qh.hulltime
198 print facet and ridge (if any)
199 report commandString, options, qh.furthest_id
200 print summary and statistics (including precision statistics)
201 if qh_ERRsingular
202 print help text for singular data set
203 exit program via long jump (if defined) or exit()
204 */
qh_errexit(int exitcode,facetT * facet,ridgeT * ridge)205 void qh_errexit(int exitcode, facetT *facet, ridgeT *ridge) {
206
207 if (qh ERREXITcalled) {
208 qh_fprintf(qh ferr, 8126, "\nqhull error while processing previous error. Exit program\n");
209 qh_exit(qh_ERRqhull);
210 }
211 qh ERREXITcalled= True;
212 if (!qh QHULLfinished)
213 qh hulltime= qh_CPUclock - qh hulltime;
214 qh_errprint("ERRONEOUS", facet, NULL, ridge, NULL);
215 qh_fprintf(qh ferr, 8127, "\nWhile executing: %s | %s\n", qh rbox_command, qh qhull_command);
216 qh_fprintf(qh ferr, 8128, "Options selected for Qhull %s:\n%s\n", qh_version, qh qhull_options);
217 if (qh furthest_id >= 0) {
218 qh_fprintf(qh ferr, 8129, "Last point added to hull was p%d.", qh furthest_id);
219 if (zzval_(Ztotmerge))
220 qh_fprintf(qh ferr, 8130, " Last merge was #%d.", zzval_(Ztotmerge));
221 if (qh QHULLfinished)
222 qh_fprintf(qh ferr, 8131, "\nQhull has finished constructing the hull.");
223 else if (qh POSTmerging)
224 qh_fprintf(qh ferr, 8132, "\nQhull has started post-merging.");
225 qh_fprintf(qh ferr, 8133, "\n");
226 }
227 if (qh FORCEoutput && (qh QHULLfinished || (!facet && !ridge)))
228 qh_produce_output();
229 else if (exitcode != qh_ERRinput) {
230 if (exitcode != qh_ERRsingular && zzval_(Zsetplane) > qh hull_dim+1) {
231 qh_fprintf(qh ferr, 8134, "\nAt error exit:\n");
232 qh_printsummary(qh ferr);
233 if (qh PRINTstatistics) {
234 qh_collectstatistics();
235 qh_printstatistics(qh ferr, "at error exit");
236 qh_memstatistics(qh ferr);
237 }
238 }
239 if (qh PRINTprecision)
240 qh_printstats(qh ferr, qhstat precision, NULL);
241 }
242 if (!exitcode)
243 exitcode= qh_ERRqhull;
244 else if (exitcode == qh_ERRsingular)
245 qh_printhelp_singular(qh ferr);
246 else if (exitcode == qh_ERRprec && !qh PREmerge)
247 qh_printhelp_degenerate(qh ferr);
248 if (qh NOerrexit) {
249 qh_fprintf(qh ferr, 6187, "qhull error while ending program. Exit program\n");
250 qh_exit(qh_ERRqhull);
251 }
252 qh ERREXITcalled= False;
253 qh NOerrexit= True;
254 longjmp(qh errexit, exitcode);
255 } /* errexit */
256
257
258 /*-<a href="qh-user.htm#TOC"
259 >-------------------------------</a><a name="errprint">-</a>
260
261 qh_errprint( fp, string, atfacet, otherfacet, atridge, atvertex )
262 prints out the information of facets and ridges to fp
263 also prints neighbors and geomview output
264
265 notes:
266 except for string, any parameter may be NULL
267 */
qh_errprint(const char * string,facetT * atfacet,facetT * otherfacet,ridgeT * atridge,vertexT * atvertex)268 void qh_errprint(const char *string, facetT *atfacet, facetT *otherfacet, ridgeT *atridge, vertexT *atvertex) {
269 int i;
270
271 if (atfacet) {
272 qh_fprintf(qh ferr, 8135, "%s FACET:\n", string);
273 qh_printfacet(qh ferr, atfacet);
274 }
275 if (otherfacet) {
276 qh_fprintf(qh ferr, 8136, "%s OTHER FACET:\n", string);
277 qh_printfacet(qh ferr, otherfacet);
278 }
279 if (atridge) {
280 qh_fprintf(qh ferr, 8137, "%s RIDGE:\n", string);
281 qh_printridge(qh ferr, atridge);
282 if (atridge->top && atridge->top != atfacet && atridge->top != otherfacet)
283 qh_printfacet(qh ferr, atridge->top);
284 if (atridge->bottom
285 && atridge->bottom != atfacet && atridge->bottom != otherfacet)
286 qh_printfacet(qh ferr, atridge->bottom);
287 if (!atfacet)
288 atfacet= atridge->top;
289 if (!otherfacet)
290 otherfacet= otherfacet_(atridge, atfacet);
291 }
292 if (atvertex) {
293 qh_fprintf(qh ferr, 8138, "%s VERTEX:\n", string);
294 qh_printvertex(qh ferr, atvertex);
295 }
296 if (qh fout && qh FORCEoutput && atfacet && !qh QHULLfinished && !qh IStracing) {
297 qh_fprintf(qh ferr, 8139, "ERRONEOUS and NEIGHBORING FACETS to output\n");
298 for (i=0; i < qh_PRINTEND; i++) /* use fout for geomview output */
299 qh_printneighborhood(qh fout, qh PRINTout[i], atfacet, otherfacet,
300 !qh_ALL);
301 }
302 } /* errprint */
303
304
305 /*-<a href="qh-user.htm#TOC"
306 >-------------------------------</a><a name="printfacetlist">-</a>
307
308 qh_printfacetlist( fp, facetlist, facets, printall )
309 print all fields for a facet list and/or set of facets to fp
310 if !printall,
311 only prints good facets
312
313 notes:
314 also prints all vertices
315 */
qh_printfacetlist(facetT * facetlist,setT * facets,boolT printall)316 void qh_printfacetlist(facetT *facetlist, setT *facets, boolT printall) {
317 facetT *facet, **facetp;
318
319 qh_printbegin(qh ferr, qh_PRINTfacets, facetlist, facets, printall);
320 FORALLfacet_(facetlist)
321 qh_printafacet(qh ferr, qh_PRINTfacets, facet, printall);
322 FOREACHfacet_(facets)
323 qh_printafacet(qh ferr, qh_PRINTfacets, facet, printall);
324 qh_printend(qh ferr, qh_PRINTfacets, facetlist, facets, printall);
325 } /* printfacetlist */
326
327
328 /*-<a href="qh-io.htm#TOC"
329 >-------------------------------</a><a name="printhelp_degenerate">-</a>
330
331 qh_printhelp_degenerate( fp )
332 prints descriptive message for precision error
333
334 notes:
335 no message if qh_QUICKhelp
336 */
qh_printhelp_degenerate(FILE * fp)337 void qh_printhelp_degenerate(FILE *fp) {
338
339 if (qh MERGEexact || qh PREmerge || qh JOGGLEmax < REALmax/2)
340 qh_fprintf(fp, 9368, "\n\
341 A Qhull error has occurred. Qhull should have corrected the above\n\
342 precision error. Please send the input and all of the output to\n\
343 qhull_bug@qhull.org\n");
344 else if (!qh_QUICKhelp) {
345 qh_fprintf(fp, 9369, "\n\
346 Precision problems were detected during construction of the convex hull.\n\
347 This occurs because convex hull algorithms assume that calculations are\n\
348 exact, but floating-point arithmetic has roundoff errors.\n\
349 \n\
350 To correct for precision problems, do not use 'Q0'. By default, Qhull\n\
351 selects 'C-0' or 'Qx' and merges non-convex facets. With option 'QJ',\n\
352 Qhull joggles the input to prevent precision problems. See \"Imprecision\n\
353 in Qhull\" (qh-impre.htm).\n\
354 \n\
355 If you use 'Q0', the output may include\n\
356 coplanar ridges, concave ridges, and flipped facets. In 4-d and higher,\n\
357 Qhull may produce a ridge with four neighbors or two facets with the same \n\
358 vertices. Qhull reports these events when they occur. It stops when a\n\
359 concave ridge, flipped facet, or duplicate facet occurs.\n");
360 #if REALfloat
361 qh_fprintf(fp, 9370, "\
362 \n\
363 Qhull is currently using single precision arithmetic. The following\n\
364 will probably remove the precision problems:\n\
365 - recompile qhull for realT precision(#define REALfloat 0 in user.h).\n");
366 #endif
367 if (qh DELAUNAY && !qh SCALElast && qh MAXabs_coord > 1e4)
368 qh_fprintf(fp, 9371, "\
369 \n\
370 When computing the Delaunay triangulation of coordinates > 1.0,\n\
371 - use 'Qbb' to scale the last coordinate to [0,m] (max previous coordinate)\n");
372 if (qh DELAUNAY && !qh ATinfinity)
373 qh_fprintf(fp, 9372, "\
374 When computing the Delaunay triangulation:\n\
375 - use 'Qz' to add a point at-infinity. This reduces precision problems.\n");
376
377 qh_fprintf(fp, 9373, "\
378 \n\
379 If you need triangular output:\n\
380 - use option 'Qt' to triangulate the output\n\
381 - use option 'QJ' to joggle the input points and remove precision errors\n\
382 - use option 'Ft'. It triangulates non-simplicial facets with added points.\n\
383 \n\
384 If you must use 'Q0',\n\
385 try one or more of the following options. They can not guarantee an output.\n\
386 - use 'QbB' to scale the input to a cube.\n\
387 - use 'Po' to produce output and prevent partitioning for flipped facets\n\
388 - use 'V0' to set min. distance to visible facet as 0 instead of roundoff\n\
389 - use 'En' to specify a maximum roundoff error less than %2.2g.\n\
390 - options 'Qf', 'Qbb', and 'QR0' may also help\n",
391 qh DISTround);
392 qh_fprintf(fp, 9374, "\
393 \n\
394 To guarantee simplicial output:\n\
395 - use option 'Qt' to triangulate the output\n\
396 - use option 'QJ' to joggle the input points and remove precision errors\n\
397 - use option 'Ft' to triangulate the output by adding points\n\
398 - use exact arithmetic (see \"Imprecision in Qhull\", qh-impre.htm)\n\
399 ");
400 }
401 } /* printhelp_degenerate */
402
403
404 /*-<a href="qh-globa.htm#TOC"
405 >-------------------------------</a><a name="printhelp_narrowhull">-</a>
406
407 qh_printhelp_narrowhull( minangle )
408 Warn about a narrow hull
409
410 notes:
411 Alternatively, reduce qh_WARNnarrow in user.h
412
413 */
qh_printhelp_narrowhull(FILE * fp,realT minangle)414 void qh_printhelp_narrowhull(FILE *fp, realT minangle) {
415
416 qh_fprintf(fp, 9375, "qhull precision warning: \n\
417 The initial hull is narrow (cosine of min. angle is %.16f).\n\
418 Is the input lower dimensional (e.g., on a plane in 3-d)? Qhull may\n\
419 produce a wide facet. Options 'QbB' (scale to unit box) or 'Qbb' (scale\n\
420 last coordinate) may remove this warning. Use 'Pp' to skip this warning.\n\
421 See 'Limitations' in qh-impre.htm.\n",
422 -minangle); /* convert from angle between normals to angle between facets */
423 } /* printhelp_narrowhull */
424
425 /*-<a href="qh-io.htm#TOC"
426 >-------------------------------</a><a name="printhelp_singular">-</a>
427
428 qh_printhelp_singular( fp )
429 prints descriptive message for singular input
430 */
qh_printhelp_singular(FILE * fp)431 void qh_printhelp_singular(FILE *fp) {
432 facetT *facet;
433 vertexT *vertex, **vertexp;
434 realT min, max, *coord, dist;
435 int i,k;
436
437 qh_fprintf(fp, 9376, "\n\
438 The input to qhull appears to be less than %d dimensional, or a\n\
439 computation has overflowed.\n\n\
440 Qhull could not construct a clearly convex simplex from points:\n",
441 qh hull_dim);
442 qh_printvertexlist(fp, "", qh facet_list, NULL, qh_ALL);
443 if (!qh_QUICKhelp)
444 qh_fprintf(fp, 9377, "\n\
445 The center point is coplanar with a facet, or a vertex is coplanar\n\
446 with a neighboring facet. The maximum round off error for\n\
447 computing distances is %2.2g. The center point, facets and distances\n\
448 to the center point are as follows:\n\n", qh DISTround);
449 qh_printpointid(fp, "center point", qh hull_dim, qh interior_point, -1);
450 qh_fprintf(fp, 9378, "\n");
451 FORALLfacets {
452 qh_fprintf(fp, 9379, "facet");
453 FOREACHvertex_(facet->vertices)
454 qh_fprintf(fp, 9380, " p%d", qh_pointid(vertex->point));
455 zinc_(Zdistio);
456 qh_distplane(qh interior_point, facet, &dist);
457 qh_fprintf(fp, 9381, " distance= %4.2g\n", dist);
458 }
459 if (!qh_QUICKhelp) {
460 if (qh HALFspace)
461 qh_fprintf(fp, 9382, "\n\
462 These points are the dual of the given halfspaces. They indicate that\n\
463 the intersection is degenerate.\n");
464 qh_fprintf(fp, 9383,"\n\
465 These points either have a maximum or minimum x-coordinate, or\n\
466 they maximize the determinant for k coordinates. Trial points\n\
467 are first selected from points that maximize a coordinate.\n");
468 if (qh hull_dim >= qh_INITIALmax)
469 qh_fprintf(fp, 9384, "\n\
470 Because of the high dimension, the min x-coordinate and max-coordinate\n\
471 points are used if the determinant is non-zero. Option 'Qs' will\n\
472 do a better, though much slower, job. Instead of 'Qs', you can change\n\
473 the points by randomly rotating the input with 'QR0'.\n");
474 }
475 qh_fprintf(fp, 9385, "\nThe min and max coordinates for each dimension are:\n");
476 for (k=0; k < qh hull_dim; k++) {
477 min= REALmax;
478 max= -REALmin;
479 for (i=qh num_points, coord= qh first_point+k; i--; coord += qh hull_dim) {
480 maximize_(max, *coord);
481 minimize_(min, *coord);
482 }
483 qh_fprintf(fp, 9386, " %d: %8.4g %8.4g difference= %4.4g\n", k, min, max, max-min);
484 }
485 if (!qh_QUICKhelp) {
486 qh_fprintf(fp, 9387, "\n\
487 If the input should be full dimensional, you have several options that\n\
488 may determine an initial simplex:\n\
489 - use 'QJ' to joggle the input and make it full dimensional\n\
490 - use 'QbB' to scale the points to the unit cube\n\
491 - use 'QR0' to randomly rotate the input for different maximum points\n\
492 - use 'Qs' to search all points for the initial simplex\n\
493 - use 'En' to specify a maximum roundoff error less than %2.2g.\n\
494 - trace execution with 'T3' to see the determinant for each point.\n",
495 qh DISTround);
496 #if REALfloat
497 qh_fprintf(fp, 9388, "\
498 - recompile qhull for realT precision(#define REALfloat 0 in libqhull.h).\n");
499 #endif
500 qh_fprintf(fp, 9389, "\n\
501 If the input is lower dimensional:\n\
502 - use 'QJ' to joggle the input and make it full dimensional\n\
503 - use 'Qbk:0Bk:0' to delete coordinate k from the input. You should\n\
504 pick the coordinate with the least range. The hull will have the\n\
505 correct topology.\n\
506 - determine the flat containing the points, rotate the points\n\
507 into a coordinate plane, and delete the other coordinates.\n\
508 - add one or more points to make the input full dimensional.\n\
509 ");
510 }
511 } /* printhelp_singular */
512
513 /*-<a href="qh-globa.htm#TOC"
514 >-------------------------------</a><a name="user_memsizes">-</a>
515
516 qh_user_memsizes()
517 allocate up to 10 additional, quick allocation sizes
518
519 notes:
520 increase maximum number of allocations in qh_initqhull_mem()
521 */
qh_user_memsizes(void)522 void qh_user_memsizes(void) {
523
524 /* qh_memsize(size); */
525 } /* user_memsizes */
526
527
528