1
/*<html><pre> -<a href="qh-qhull.htm"
2
>-------------------------------</a><a name="TOP">-</a>
5
compute the intersection of halfspaces about a point
7
see unix.c for full interface
9
copyright (c) 1993-2002, The Geometry Center
21
#if __MWERKS__ && __POWERPC__
34
#define isatty _isatty
37
int isatty (int); /* returns 1 if stdin is a tty
38
if "Undefined symbol" this can be deleted along with call in main() */
41
/*-<a href="qh-qhull.htm#TOC"
42
>-------------------------------</a><a name="prompt">-</a>
48
restricted version of qhull.c
54
/* duplicated in qhalf.htm */
55
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 ";
57
char qh_prompta[]= "\n\
58
qhalf- compute the intersection of halfspaces about a point\n\
59
http://www.geom.umn.edu/software/qhull %s\n\
62
optional interior point: dimension, 1, coordinates\n\
63
first lines: dimension+1 and number of halfspaces\n\
64
other lines: halfspace coefficients followed by offset\n\
65
comments: start with a non-numeric character\n\
68
Hn,n - specify coordinates of interior point\n\
69
Qt - triangulated output\n\
70
QJ - joggled input instead of merged facets\n\
71
Qc - keep coplanar halfspaces\n\
72
Qi - keep other redundant halfspaces\n\
74
Qhull control options:\n\
75
QJn - randomly joggle input in range [-n,n]\n\
76
%s%s%s%s"; /* split up qh_prompt for Visual C++ */
78
Qbk:0Bk:0 - remove k-th coordinate from input\n\
79
Qs - search all halfspaces for the initial simplex\n\
80
QGn - print intersection if visible to halfspace n, -n for not\n\
81
QVn - print intersections for halfspace n, -n if not\n\
86
T4 - trace at level n, 4=all, 5=mem/gauss, -1= events\n\
87
Tc - check frequently during execution\n\
88
Ts - print statistics\n\
89
Tv - verify result: structure, convexity, and redundancy\n\
90
Tz - send all output to stdout\n\
91
TFn - report summary when n or more facets created\n\
92
TI file - input data from file, no spaces or single quotes\n\
93
TO file - output results to file, may be enclosed in single quotes\n\
94
TPn - turn on tracing when halfspace n added to intersection\n\
95
TMn - turn on tracing at merge n\n\
96
TWn - trace merge facets when width > n\n\
97
TVn - stop qhull after adding halfspace n, -n for before (see TCn)\n\
98
TCn - stop qhull after building cone for halfspace n (see TVn)\n\
100
Precision options:\n\
101
Cn - radius of centrum (roundoff added). Merge facets if non-convex\n\
102
An - cosine of maximum angle. Merge facets if cosine > n or non-convex\n\
103
C-0 roundoff, A-0.99/C-0.01 pre-merge, A0.99/C0.01 post-merge\n\
104
Rn - randomly perturb computations by a factor of [1-n,1+n]\n\
105
Un - max distance below plane for a new, coplanar halfspace\n\
106
Wn - min facet width for outside halfspace (before roundoff)\n\
108
Output formats (may be combined; if none, produces a summary to stdout):\n\
110
G - Geomview output (dual convex hull)\n\
111
i - non-redundant halfspaces incident to each intersection\n\
112
m - Mathematica output (dual convex hull)\n\
113
o - OFF format (dual convex hull: dimension, points, and facets)\n\
114
p - vertex coordinates of dual convex hull (coplanars if 'Qc' or 'Qi')\n\
115
s - summary (stderr)\n\
118
char qh_promptd[]= "\
120
Fc - count plus redundant halfspaces for each intersection\n\
121
- Qc (default) for coplanar and Qi for other redundant\n\
122
Fd - use cdd format for input (homogeneous with offset first)\n\
123
FF - facet dump without ridges\n\
124
FI - ID of each intersection\n\
125
Fm - merge count for each intersection (511 max)\n\
126
Fn - count plus neighboring intersections for each intersection\n\
127
FN - count plus intersections for each non-redundant halfspace\n\
128
FO - options and precision constants\n\
129
Fp - dim, count, and intersection coordinates\n\
130
FP - nearest halfspace and distance for each redundant halfspace\n\
131
FQ - command used for qhalf\n\
132
Fs - summary: #int (8), dim, #halfspaces, #non-redundant, #intersections\n\
133
for output: #non-redundant, #intersections, #coplanar\n\
134
halfspaces, #non-simplicial intersections\n\
135
#real (2), max outer plane, min vertex\n\
136
Fv - count plus non-redundant halfspaces for each intersection\n\
137
Fx - non-redundant halfspaces\n\
140
char qh_prompte[]= "\
141
Geomview output (2-d, 3-d and 4-d; dual convex hull)\n\
142
Ga - all points (i.e., transformed halfspaces) as dots\n\
143
Gp - coplanar points and vertices as radii\n\
144
Gv - vertices (i.e., non-redundant halfspaces) as spheres\n\
145
Gi - inner planes (i.e., halfspace intersections) only\n\
147
Go - outer planes only\n\
149
Gh - hyperplane intersections\n\
151
GDn - drop dimension n in 3-d and 4-d output\n\
154
PAn - keep n largest facets (i.e., intersections) by area\n\
155
Pdk:n- drop facet if normal[k] <= n (default 0.0)\n\
156
PDk:n- drop facet if normal[k] >= n\n\
157
Pg - print good facets (needs 'QGn' or 'QVn')\n\
158
PFn - keep facets whose area is at least n\n\
159
PG - print neighbors of good facets\n\
160
PMn - keep n facets with most merges\n\
161
Po - force output. If error, output neighborhood of facet\n\
162
Pp - do not report precision problems\n\
164
. - list of all options\n\
165
- - one line descriptions of all options\n\
167
/* for opts, don't assign 'e' or 'E' to a flag (already used for exponent) */
169
/*-<a href="qh-qhull.htm#TOC"
170
>-------------------------------</a><a name="prompt2">-</a>
175
char qh_prompt2[]= "\n\
176
qhalf- halfspace intersection about a point. Qhull %s\n\
177
input (stdin): [dim, 1, interior point], dim+1, n, coefficients+offset\n\
178
comments start with a non-numeric character\n\
180
options (qhalf.htm):\n\
181
Hn,n - specify coordinates of interior point\n\
182
Qt - triangulated output\n\
183
QJ - joggled input instead of merged facets\n\
184
Tv - verify result: structure, convexity, and redundancy\n\
185
. - concise list of all options\n\
186
- - one-line description of all options\n\
188
output options (subset):\n\
189
s - summary of results (default)\n\
190
Fp - intersection coordinates\n\
191
Fv - non-redundant halfspaces incident to each intersection\n\
192
Fx - non-redundant halfspaces\n\
193
o - OFF file format (dual convex hull)\n\
194
G - Geomview output (dual convex hull)\n\
195
m - Mathematica output (dual convex hull)\n\
196
QVn - print intersections for halfspace n, -n if not\n\
197
TO file - output results to file, may be enclosed in single quotes\n\
200
rbox d | qconvex FQ n | qhalf s H0,0,0 Fp\n\
201
rbox c | qconvex FQ FV n | qhalf s i\n\
202
rbox c | qconvex FQ FV n | qhalf s o\n\
205
/* for opts, don't assign 'e' or 'E' to a flag (already used for exponent) */
207
/*-<a href="qh-qhull.htm#TOC"
208
>-------------------------------</a><a name="prompt3">-</a>
211
concise prompt for qhull
213
char qh_prompt3[]= "\n\
215
Except for 'F.' and 'PG', upper_case options take an argument.\n\
217
incidences Geomview mathematica OFF_format point_dual\n\
218
summary facet_dump\n\
220
Fc_redundant Fd_cdd_in FF_dump_xridge FIDs Fmerges\n\
221
Fneighbors FN_intersect FOptions Fp_coordinates FP_nearest\n\
222
FQhalf Fsummary Fv_halfspace Fx_non_redundant\n\
224
Gvertices Gpoints Gall_points Gno_planes Ginner\n\
225
Gcentrums Ghyperplanes Gridges Gouter GDrop_dim\n\
227
PArea_keep Pdrop d0:0D0 Pgood PFacet_area_keep\n\
228
PGood_neighbors PMerge_keep Poutput_forced Pprecision_not\n\
230
Qbk:0Bk:0_drop Qcoplanar QG_half_good Qi_redundant QJoggle\n\
231
Qsearch_1st Qtriangulate QVertex_good\n\
233
T4_trace Tcheck_often Tstatistics Tverify Tz_stdout\n\
234
TFacet_log TInput_file TPoint_trace TMerge_trace TOutput_file\n\
235
TWide_trace TVertex_stop TCone_stop\n\
237
Angle_max Centrum_size Random_dist Ucoplanar_max Wide_outside\n\
240
/*-<a href="qh-qhull.htm#TOC"
241
>-------------------------------</a><a name="main">-</a>
244
processes the command line, calls qhull() to do the work, and exits
247
initializes data structures
249
finishes initialization
250
computes convex hull and other structures
255
int main(int argc, char *argv[]) {
256
int curlong, totlong; /* used !qh_NOmem */
257
int exitcode, numpoints, dim;
261
#if __MWERKS__ && __POWERPC__
262
char inBuf[BUFSIZ], outBuf[BUFSIZ], errBuf[BUFSIZ];
263
SIOUXSettings.showstatusline= false;
264
SIOUXSettings.tabspaces= 1;
265
SIOUXSettings.rows= 40;
266
if (setvbuf (stdin, inBuf, _IOFBF, sizeof(inBuf)) < 0 /* w/o, SIOUX I/O is slow*/
267
|| setvbuf (stdout, outBuf, _IOFBF, sizeof(outBuf)) < 0
268
|| (stdout != stderr && setvbuf (stderr, errBuf, _IOFBF, sizeof(errBuf)) < 0))
269
fprintf (stderr, "qhull internal warning (main): could not change stdio to fully buffered.\n");
270
argc= ccommand(&argv);
273
if ((argc == 1) && isatty( 0 /*stdin*/)) {
274
fprintf(stdout, qh_prompt2, qh_VERSION);
277
if (argc > 1 && *argv[1] == '-' && !*(argv[1]+1)) {
278
fprintf(stdout, qh_prompta, qh_VERSION,
279
qh_promptb, qh_promptc, qh_promptd, qh_prompte);
282
if (argc >1 && *argv[1] == '.' && !*(argv[1]+1)) {
283
fprintf(stdout, qh_prompt3, qh_VERSION);
286
qh_init_A (stdin, stdout, stderr, argc, argv); /* sets qh qhull_command */
287
exitcode= setjmp (qh errexit); /* simple statement for CRAY J916 */
289
qh_option ("Halfspace", NULL, NULL);
290
qh HALFspace= True; /* 'H' */
291
qh_checkflags (qh qhull_command, hidden_options);
292
qh_initflags (qh qhull_command);
295
qhull error: options 'Qbk:n' and 'QBk:n' are not used with qhalf.\n\
296
Use 'Qbk:0Bk:0 to drop dimension k.\n");
297
qh_errexit(qh_ERRinput, NULL, NULL);
299
points= qh_readpoints (&numpoints, &dim, &ismalloc);
301
qh_option ("Qxact_merge", NULL, NULL);
302
qh MERGEexact= True; /* 'Qx' always */
304
qh_init_B (points, numpoints, dim, ismalloc);
308
if (qh VERIFYoutput && !qh FORCEoutput && !qh STOPpoint && !qh STOPcone)
310
exitcode= qh_ERRnone;
312
qh NOerrexit= True; /* no more setjmp */
316
qh_freeqhull( False);
317
qh_memfreeshort (&curlong, &totlong);
318
if (curlong || totlong)
319
fprintf (stderr, "qhull internal warning (main): did not free %d bytes of long memory (%d pieces)\n",