1 /*<html><pre> -<a href="../libqhull_r/qh-qhull_r.htm"
2 >-------------------------------</a><a name="TOP">-</a>
3
4 qhalf_r.c
5 compute the intersection of halfspaces about a point
6
7 see unix_r.c for full interface
8
9 Copyright (c) 1993-2019, The Geometry Center
10 */
11
12 #include "libqhull_r/libqhull_r.h"
13
14 #include <stdio.h>
15 #include <stdlib.h>
16 #include <string.h>
17 #include <ctype.h>
18 #include <math.h>
19
20 #ifdef __cplusplus
21 extern "C" {
22 int isatty(int);
23 }
24
25 #elif defined(_MSC_VER)
26 #include <io.h>
27 #define isatty _isatty
28 /* int _isatty(int); */
29
30 #else
31 int isatty(int); /* returns 1 if stdin is a tty
32 if "Undefined symbol" this can be deleted along with call in main() */
33 #endif
34
35 /*-<a href="../libqhull_r/qh-qhull_r.htm#TOC"
36 >-------------------------------</a><a name="prompt">-</a>
37
38 qh_prompt
39 long prompt for qhull
40
41 notes:
42 restricted version of libqhull_r.c
43 same text as unix_r.c
44 see concise prompt below
45 limit maximum literal to 1800 characters
46 */
47
48 /* duplicated in qhalf.htm */
49 char hidden_options[]=" d n v Qbb QbB Qf Qg Qm 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 Q10 Q11 Q15 ";
50
51 char qh_prompta[]= "\n\
52 qhalf -- compute the intersection of halfspaces about a point\n\
53 http://www.qhull.org %s\n\
54 \n\
55 input (stdin):\n\
56 optional interior point: dimension, 1, coordinates\n\
57 first lines: dimension+1 and number of halfspaces\n\
58 other lines: halfspace coefficients followed by offset\n\
59 comments: start with a non-numeric character\n\
60 \n\
61 options:\n\
62 Hn,n - specify coordinates of interior point\n\
63 Qc - keep coplanar halfspaces\n\
64 Qi - keep other redundant halfspaces\n\
65 QJ - joggled input instead of merged facets\n\
66 Qt - triangulated output\n\
67 \n\
68 Qhull control options:\n\
69 Qa - allow input with fewer or more points than coordinates\n\
70 Qbk:0Bk:0 - remove k-th coordinate from input\n\
71 QJn - randomly joggle input in range [-n,n]\n\
72 QRn - random rotation (n=seed, n=0 time, n=-1 time/no rotate)\n\
73 Qs - search all halfspaces for the initial simplex\n\
74 \n\
75 %s%s%s%s"; /* split up qh_prompt for Visual C++ */
76 char qh_promptb[]= "\
77 Qhull extra options:\n\
78 QGn - print intersection if visible to halfspace n, -n for not\n\
79 QVn - print intersections for halfspace n, -n if not\n\
80 Qw - allow option warnings\n\
81 Q12 - allow wide facets and wide dupridge\n\
82 Q14 - merge pinched vertices that create a dupridge\n\
83 \n\
84 T options:\n\
85 TFn - report summary when n or more facets created\n\
86 TI file - input file, may be enclosed in single quotes\n\
87 TO file - output file, may be enclosed in single quotes\n\
88 Ts - statistics\n\
89 Tv - verify result: structure, convexity, and in-circle test\n\
90 Tz - send all output to stdout\n\
91 \n\
92 ";
93 char qh_promptc[]= "\
94 Trace options:\n\
95 T4 - trace at level n, 4=all, 5=mem/gauss, -1= events\n\
96 Ta - annotate output with message codes\n\
97 TAn - stop qhull after adding n vertices\n\
98 TCn - stop qhull after building cone for point n\n\
99 TVn - stop qhull after adding point n, -n for before\n\
100 Tc - check frequently during execution\n\
101 Tf - flush each qh_fprintf for debugging segfaults\n\
102 TPn - turn on tracing when point n added to hull\n\
103 TMn - turn on tracing at merge n\n\
104 TWn - trace merge facets when width > n\n\
105 \n\
106 Precision options:\n\
107 Cn - radius of centrum (roundoff added). Merge facets if non-convex\n\
108 An - cosine of maximum angle. Merge facets if cosine > n or non-convex\n\
109 C-0 roundoff, A-0.99/C-0.01 pre-merge, A0.99/C0.01 post-merge\n\
110 Rn - randomly perturb computations by a factor of [1-n,1+n]\n\
111 Un - max distance below plane for a new, coplanar halfspace\n\
112 Wn - min facet width for outside halfspace (before roundoff)\n\
113 \n\
114 Output formats (may be combined; if none, produces a summary to stdout):\n\
115 f - facet dump\n\
116 G - Geomview output (dual convex hull)\n\
117 i - non-redundant halfspaces incident to each intersection\n\
118 m - Mathematica output (dual convex hull)\n\
119 o - OFF format (dual convex hull: dimension, points, and facets)\n\
120 p - vertex coordinates of dual convex hull (coplanars if 'Qc' or 'Qi')\n\
121 s - summary (stderr)\n\
122 \n\
123 ";
124 char qh_promptd[]= "\
125 More formats:\n\
126 Fc - count plus redundant halfspaces for each intersection\n\
127 - Qc (default) for coplanar and Qi for other redundant\n\
128 Fd - use cdd format for input (homogeneous with offset first)\n\
129 FF - facet dump without ridges\n\
130 FI - ID of each intersection\n\
131 Fm - merge count for each intersection (511 max)\n\
132 FM - Maple output (dual 2-d or 3-d convex hull)\n\
133 Fn - count plus neighboring intersections for each intersection\n\
134 FN - count plus intersections for each non-redundant halfspace\n\
135 FO - options and precision constants\n\
136 Fp - dim, count, and intersection coordinates\n\
137 FP - nearest halfspace and distance for each redundant halfspace\n\
138 FQ - command used for qhalf\n\
139 Fs - summary: #int (8), dim, #halfspaces, #non-redundant, #intersections\n\
140 output: #non-redundant, #intersections, #coplanar\n\
141 halfspaces, #non-simplicial intersections\n\
142 #real (2), max outer plane, min vertex\n\
143 Fv - count plus non-redundant halfspaces for each intersection\n\
144 Fx - non-redundant halfspaces\n\
145 \n\
146 ";
147 char qh_prompte[]= "\
148 Geomview output (2-d, 3-d and 4-d; dual convex hull)\n\
149 Ga - all points (i.e., transformed halfspaces) as dots\n\
150 Gp - coplanar points and vertices as radii\n\
151 Gv - vertices (i.e., non-redundant halfspaces) as spheres\n\
152 Gc - centrums\n\
153 GDn - drop dimension n in 3-d and 4-d output\n\
154 Gh - hyperplane intersections\n\
155 Gi - inner planes (i.e., halfspace intersections) only\n\
156 Gn - no planes\n\
157 Go - outer planes only\n\
158 Gr - ridges\n\
159 \n\
160 Print options:\n\
161 PAn - keep n largest facets (i.e., intersections) by area\n\
162 Pdk:n- drop facet if normal[k] <= n (default 0.0)\n\
163 PDk:n- drop facet if normal[k] >= n\n\
164 PFn - keep facets whose area is at least n\n\
165 Pg - print good facets (needs 'QGn' or 'QVn')\n\
166 PG - print neighbors of good facets\n\
167 PMn - keep n facets with most merges\n\
168 Po - force output. If error, output neighborhood of facet\n\
169 Pp - do not report precision problems\n\
170 \n\
171 . - list of all options\n\
172 - - one line descriptions of all options\n\
173 -? - help with examples\n\
174 -V - version\n\
175 ";
176 /* for opts, don't assign 'e' or 'E' to a flag (already used for exponent) */
177
178 /*-<a href="../libqhull_r/qh-qhull_r.htm#TOC"
179 >-------------------------------</a><a name="prompt2">-</a>
180
181 qh_prompt2
182 synopsis for qhull
183 */
184 char qh_prompt2[]= "\n\
185 qhalf -- halfspace intersection about a point. Qhull %s\n\
186 input (stdin): [dimension, 1, interior point]\n\
187 dimension+1, number of halfspaces, coefficients+offset\n\
188 comments start with a non-numeric character\n\
189 \n\
190 options (qhalf.htm):\n\
191 Hn,n - specify coordinates of interior point\n\
192 Qt - triangulated output\n\
193 QJ - joggled input instead of merged facets\n\
194 Tv - verify result: structure, convexity, and redundancy\n\
195 . - concise list of all options\n\
196 - - one-line description of each option\n\
197 -? - this message\n\
198 -V - version\n\
199 \n\
200 output options (subset):\n\
201 s - summary of results (default)\n\
202 Fp - intersection coordinates\n\
203 Fv - non-redundant halfspaces incident to each intersection\n\
204 Fx - non-redundant halfspaces\n\
205 G - Geomview output (dual convex hull)\n\
206 m - Mathematica output (dual convex hull)\n\
207 o - OFF file format (dual convex hull)\n\
208 QVn - print intersections for halfspace n, -n if not\n\
209 TI file - input file, may be enclosed in single quotes\n\
210 TO file - output file, may be enclosed in single quotes\n\
211 \n\
212 examples:\n\
213 rbox d | qconvex FQ n | qhalf s H0,0,0 Fp\n\
214 rbox c | qconvex FQ FV n | qhalf s i\n\
215 rbox c | qconvex FQ FV n | qhalf s o\n\
216 \n\
217 ";
218 /* for opts, don't assign 'e' or 'E' to a flag (already used for exponent) */
219
220 /*-<a href="../libqhull_r/qh-qhull_r.htm#TOC"
221 >-------------------------------</a><a name="prompt3">-</a>
222
223 qh_prompt3
224 concise prompt for qhull
225 */
226 char qh_prompt3[]= "\n\
227 Qhull %s\n\
228 Except for 'F.' and 'PG', upper_case options take an argument.\n\
229 \n\
230 facet-dump Geomview H0,0-interior incidences mathematica\n\
231 off-format point-dual summary\n\
232 \n\
233 Fc-redundant Fd-cdd-in FF-dump-xridge FIDs Fmerges\n\
234 FMaple Fneighbors FN-intersect FOptions Fp-coordinates\n\
235 FP-nearest FQhalf Fsummary Fv-halfspace Fx-non-redundant\n\
236 \n\
237 Gall-points Gcentrums GDrop-dim Ghyperplanes Ginner\n\
238 Gno-planes Gouter Gpoints Gridges Gvertices\n\
239 \n\
240 PArea-keep Pdrop-d0:0D0 PFacet-area-keep Pgood PGood-neighbors\n\
241 PMerge-keep Poutput-forced Pprecision-not\n\
242 \n\
243 Qallow-short Qbk:0Bk:0-drop Qcoplanar QG-half-good Qi-redundant\n\
244 QJoggle QRotate Qsearch-all Qtriangulate QVertex-good\n\
245 Qwarn-allow Q12-allow-wide Q14-merge-pinched\n\
246 \n\
247 TFacet-log TInput-file TOutput-file Tstatistics Tverify\n\
248 Tz-stdout\n\
249 \n\
250 T4-trace Tannotate TAdd-stop Tcheck-often TCone-stop\n\
251 Tflush TMerge-trace TPoint-trace TVertex-stop TWide-trace\n\
252 \n\
253 Angle-max Centrum-size Random-dist Ucoplanar-max Wide-outside\n\
254 ";
255
256 /*-<a href="../libqhull_r/qh-qhull_r.htm#TOC"
257 >-------------------------------</a><a name="main">-</a>
258
259 main( argc, argv )
260 processes the command line, calls qhull() to do the work, and exits
261
262 design:
263 initializes data structures
264 reads points
265 finishes initialization
266 computes convex hull and other structures
267 checks the result
268 writes the output
269 frees memory
270 */
main(int argc,char * argv[])271 int main(int argc, char *argv[]) {
272 int curlong, totlong; /* used !qh_NOmem */
273 int exitcode, numpoints, dim;
274 coordT *points;
275 boolT ismalloc;
276 qhT qh_qh;
277 qhT *qh= &qh_qh;
278
279 QHULL_LIB_CHECK /* Check for compatible library */
280
281 if ((argc == 1) && isatty( 0 /*stdin*/)) {
282 fprintf(stdout, qh_prompt2, qh_version);
283 exit(qh_ERRnone);
284 }
285 if (argc > 1 && *argv[1] == '-' && (*(argv[1] + 1) == '?' || *(argv[1] + 1) == '-')) { /* -? or --help */
286 fprintf(stdout, qh_prompt2, qh_version);
287 exit(qh_ERRnone);
288 }
289 if (argc > 1 && *argv[1] == '-' && !*(argv[1]+1)) {
290 fprintf(stdout, qh_prompta, qh_version,
291 qh_promptb, qh_promptc, qh_promptd, qh_prompte);
292 exit(qh_ERRnone);
293 }
294 if (argc > 1 && *argv[1] == '.' && !*(argv[1]+1)) {
295 fprintf(stdout, qh_prompt3, qh_version);
296 exit(qh_ERRnone);
297 }
298 if (argc > 1 && *argv[1] == '-' && *(argv[1]+1)=='V') {
299 fprintf(stdout, "%s\n", qh_version2);
300 exit(qh_ERRnone);
301 }
302 qh_init_A(qh, stdin, stdout, stderr, argc, argv); /* sets qh->qhull_command */
303 exitcode= setjmp(qh->errexit); /* simple statement for CRAY J916 */
304 if (!exitcode) {
305 qh->NOerrexit = False;
306 qh_option(qh, "Halfspace", NULL, NULL);
307 qh->HALFspace= True; /* 'H' */
308 qh_checkflags(qh, qh->qhull_command, hidden_options);
309 qh_initflags(qh, qh->qhull_command);
310 if (qh->SCALEinput) {
311 fprintf(qh->ferr, "\
312 qhull error: options 'Qbk:n' and 'QBk:n' are not used with qhalf.\n\
313 Use 'Qbk:0Bk:0 to drop dimension k.\n");
314 qh_errexit(qh, qh_ERRinput, NULL, NULL);
315 }
316 points= qh_readpoints(qh, &numpoints, &dim, &ismalloc);
317 qh_init_B(qh, points, numpoints, dim, ismalloc);
318 qh_qhull(qh);
319 qh_check_output(qh);
320 qh_produce_output(qh);
321 if (qh->VERIFYoutput && !qh->FORCEoutput && !qh->STOPpoint && !qh->STOPcone)
322 qh_check_points(qh);
323 exitcode= qh_ERRnone;
324 }
325 qh->NOerrexit= True; /* no more setjmp */
326 #ifdef qh_NOmem
327 qh_freeqhull(qh, qh_ALL);
328 #else
329 qh_freeqhull(qh, !qh_ALL);
330 qh_memfreeshort(qh, &curlong, &totlong);
331 if (curlong || totlong)
332 qh_fprintf_stderr(7079, "qhull internal warning (main): did not free %d bytes of long memory(%d pieces)\n",
333 totlong, curlong);
334 #endif
335 return exitcode;
336 } /* main */
337
338