1 /*<html><pre> -<a href="../libqhull/qh-qhull.htm"
2 >-------------------------------</a><a name="TOP">-</a>
3
4 qconvex.c
5 compute convex hulls using qhull
6
7 see unix.c for full interface
8
9 Copyright (c) 1993-2015, The Geometry Center
10 */
11
12 #include "libqhull/libqhull.h"
13
14 #include <stdio.h>
15 #include <stdlib.h>
16 #include <string.h>
17 #include <ctype.h>
18 #include <math.h>
19
20 #if __cplusplus
21 extern "C" {
22 int isatty(int);
23 }
24
25 #elif _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/qh-qhull.htm#TOC"
36 >-------------------------------</a><a name="prompt">-</a>
37
38 qh_prompt
39 long prompt for qconvex
40
41 notes:
42 restricted version of libqhull.c
43
44 see:
45 concise prompt below
46 */
47
48 /* duplicated in qconvex.htm */
49 char hidden_options[]=" d v H Qbb Qf Qg Qm Qr Qu Qv Qx Qz TR E V Fp Gt Q0 Q1 Q2 Q3 Q4 Q5 Q6 Q7 Q8 Q9 ";
50
51 char qh_prompta[]= "\n\
52 qconvex- compute the convex hull\n\
53 http://www.qhull.org %s\n\
54 \n\
55 input (stdin):\n\
56 first lines: dimension and number of points (or vice-versa).\n\
57 other lines: point coordinates, best if one point per line\n\
58 comments: start with a non-numeric character\n\
59 \n\
60 options:\n\
61 Qt - triangulated output\n\
62 QJ - joggled input instead of merged facets\n\
63 Qc - keep coplanar points with nearest facet\n\
64 Qi - keep interior points with nearest facet\n\
65 \n\
66 Qhull control options:\n\
67 Qbk:n - scale coord k so that low bound is n\n\
68 QBk:n - scale coord k so that upper bound is n (QBk is %2.2g)\n\
69 QbB - scale input to unit cube centered at the origin\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 %s%s%s%s"; /* split up qh_prompt for Visual C++ */
74 char qh_promptb[]= "\
75 Qs - search all points for the initial simplex\n\
76 QGn - good facet if visible from point n, -n for not visible\n\
77 QVn - good facet if it includes point n, -n if not\n\
78 \n\
79 ";
80 char qh_promptc[]= "\
81 Trace options:\n\
82 T4 - trace at level n, 4=all, 5=mem/gauss, -1= events\n\
83 Tc - check frequently during execution\n\
84 Ts - print statistics\n\
85 Tv - verify result: structure, convexity, and point inclusion\n\
86 Tz - send all output to stdout\n\
87 TFn - report summary when n or more facets created\n\
88 TI file - input data from file, no spaces or single quotes\n\
89 TO file - output results to file, may be enclosed in single quotes\n\
90 TPn - turn on tracing when point n added to hull\n\
91 TMn - turn on tracing at merge n\n\
92 TWn - trace merge facets when width > n\n\
93 TVn - stop qhull after adding point n, -n for before (see TCn)\n\
94 TCn - stop qhull after building cone for point n (see TVn)\n\
95 \n\
96 Precision options:\n\
97 Cn - radius of centrum (roundoff added). Merge facets if non-convex\n\
98 An - cosine of maximum angle. Merge facets if cosine > n or non-convex\n\
99 C-0 roundoff, A-0.99/C-0.01 pre-merge, A0.99/C0.01 post-merge\n\
100 Rn - randomly perturb computations by a factor of [1-n,1+n]\n\
101 Un - max distance below plane for a new, coplanar point\n\
102 Wn - min facet width for outside point (before roundoff)\n\
103 \n\
104 Output formats (may be combined; if none, produces a summary to stdout):\n\
105 f - facet dump\n\
106 G - Geomview output (see below)\n\
107 i - vertices incident to each facet\n\
108 m - Mathematica output (2-d and 3-d)\n\
109 n - normals with offsets\n\
110 o - OFF file format (dim, points and facets; Voronoi regions)\n\
111 p - point coordinates \n\
112 s - summary (stderr)\n\
113 \n\
114 ";
115 char qh_promptd[]= "\
116 More formats:\n\
117 Fa - area for each facet\n\
118 FA - compute total area and volume for option 's'\n\
119 Fc - count plus coplanar points for each facet\n\
120 use 'Qc' (default) for coplanar and 'Qi' for interior\n\
121 FC - centrum for each facet\n\
122 Fd - use cdd format for input (homogeneous with offset first)\n\
123 FD - use cdd format for numeric output (offset first)\n\
124 FF - facet dump without ridges\n\
125 Fi - inner plane for each facet\n\
126 FI - ID for each facet\n\
127 Fm - merge count for each facet (511 max)\n\
128 Fn - count plus neighboring facets for each facet\n\
129 FN - count plus neighboring facets for each point\n\
130 Fo - outer plane (or max_outside) for each facet\n\
131 FO - options and precision constants\n\
132 FP - nearest vertex for each coplanar point\n\
133 FQ - command used for qconvex\n\
134 Fs - summary: #int (8), dimension, #points, tot vertices, tot facets,\n\
135 for output: #vertices, #facets,\n\
136 #coplanar points, #non-simplicial facets\n\
137 #real (2), max outer plane, min vertex\n\
138 FS - sizes: #int (0) \n\
139 #real (2) tot area, tot volume\n\
140 Ft - triangulation with centrums for non-simplicial facets (OFF format)\n\
141 Fv - count plus vertices for each facet\n\
142 FV - average of vertices (a feasible point for 'H')\n\
143 Fx - extreme points (in order for 2-d)\n\
144 \n\
145 ";
146 char qh_prompte[]= "\
147 Geomview output (2-d, 3-d, and 4-d)\n\
148 Ga - all points as dots\n\
149 Gp - coplanar points and vertices as radii\n\
150 Gv - vertices as spheres\n\
151 Gi - inner planes only\n\
152 Gn - no planes\n\
153 Go - outer planes only\n\
154 Gc - centrums\n\
155 Gh - hyperplane intersections\n\
156 Gr - ridges\n\
157 GDn - drop dimension n in 3-d and 4-d output\n\
158 \n\
159 Print options:\n\
160 PAn - keep n largest facets by area\n\
161 Pdk:n - drop facet if normal[k] <= n (default 0.0)\n\
162 PDk:n - drop facet if normal[k] >= n\n\
163 Pg - print good facets (needs 'QGn' or 'QVn')\n\
164 PFn - keep facets whose area is at least n\n\
165 PG - print neighbors of good facets\n\
166 PMn - keep n facets with most merges\n\
167 Po - force output. If error, output neighborhood of facet\n\
168 Pp - do not report precision problems\n\
169 \n\
170 . - list of all options\n\
171 - - one line descriptions of all options\n\
172 -V - version\n\
173 ";
174 /* for opts, don't assign 'e' or 'E' to a flag (already used for exponent) */
175
176 /*-<a href="../libqhull/qh-qhull.htm#TOC"
177 >-------------------------------</a><a name="prompt2">-</a>
178
179 qh_prompt2
180 synopsis for qhull
181 */
182 char qh_prompt2[]= "\n\
183 qconvex- compute the convex hull. Qhull %s\n\
184 input (stdin): dimension, number of points, point coordinates\n\
185 comments start with a non-numeric character\n\
186 \n\
187 options (qconvex.htm):\n\
188 Qt - triangulated output\n\
189 QJ - joggled input instead of merged facets\n\
190 Tv - verify result: structure, convexity, and point inclusion\n\
191 . - concise list of all options\n\
192 - - one-line description of all options\n\
193 -V - version\n\
194 \n\
195 output options (subset):\n\
196 s - summary of results (default)\n\
197 i - vertices incident to each facet\n\
198 n - normals with offsets\n\
199 p - vertex coordinates (includes coplanar points if 'Qc')\n\
200 Fx - extreme points (convex hull vertices)\n\
201 FA - report total area and volume\n\
202 FS - compute total area and volume\n\
203 o - OFF format (dim, n, points, facets)\n\
204 G - Geomview output (2-d, 3-d, and 4-d)\n\
205 m - Mathematica output (2-d and 3-d)\n\
206 QVn - print facets that include point n, -n if not\n\
207 TO file- output results to file, may be enclosed in single quotes\n\
208 \n\
209 examples:\n\
210 rbox c D2 | qconvex s n rbox c D2 | qconvex i\n\
211 rbox c D2 | qconvex o rbox 1000 s | qconvex s Tv FA\n\
212 rbox c d D2 | qconvex s Qc Fx rbox y 1000 W0 | qconvex s n\n\
213 rbox y 1000 W0 | qconvex s QJ rbox d G1 D12 | qconvex QR0 FA Pp\n\
214 rbox c D7 | qconvex FA TF1000\n\
215 \n\
216 ";
217 /* for opts, don't assign 'e' or 'E' to a flag (already used for exponent) */
218
219 /*-<a href="../libqhull/qh-qhull.htm#TOC"
220 >-------------------------------</a><a name="prompt3">-</a>
221
222 qh_prompt3
223 concise prompt for qhull
224 */
225 char qh_prompt3[]= "\n\
226 Qhull %s.\n\
227 Except for 'F.' and 'PG', upper-case options take an argument.\n\
228 \n\
229 incidences mathematica normals OFF_format points\n\
230 summary facet_dump\n\
231 \n\
232 Farea FArea_total Fcoplanars FCentrums Fd_cdd_in\n\
233 FD_cdd_out FFacet_xridge Finner FIDs Fmerges\n\
234 Fneighbors FNeigh_vertex Fouter FOptions FPoint_near\n\
235 FQhull Fsummary FSize Fvertices FVertex_ave\n\
236 Fxtremes FMaple\n\
237 \n\
238 Gvertices Gpoints Gall_points Gno_planes Ginner\n\
239 Gcentrums Ghyperplanes Gridges Gouter GDrop_dim\n\
240 \n\
241 PArea_keep Pdrop d0:0D0 PFacet_area_keep Pgood PGood_neighbors\n\
242 PMerge_keep Poutput_forced Pprecision_not\n\
243 \n\
244 QbBound 0:0.5 QbB_scale_box Qcoplanar QGood_point Qinterior\n\
245 QJoggle Qrandom QRotate Qsearch_1st Qtriangulate\n\
246 QVertex_good\n\
247 \n\
248 T4_trace Tcheck_often Tstatistics Tverify Tz_stdout\n\
249 TFacet_log TInput_file TPoint_trace TMerge_trace TOutput_file\n\
250 TWide_trace TVertex_stop TCone_stop\n\
251 \n\
252 Angle_max Centrum_size Random_dist Ucoplanar_max Wide_outside\n\
253 ";
254
255 /*-<a href="../libqhull/qh-qhull.htm"
256 >-------------------------------</a><a name="main">-</a>
257
258 main( argc, argv )
259 processes the command line, calls qhull() to do the work, and exits
260
261 design:
262 initializes data structures
263 reads points
264 finishes initialization
265 computes convex hull and other structures
266 checks the result
267 writes the output
268 frees memory
269 */
main(int argc,char * argv[])270 int main(int argc, char *argv[]) {
271 int curlong, totlong; /* used !qh_NOmem */
272 int exitcode, numpoints, dim;
273 coordT *points;
274 boolT ismalloc;
275
276 QHULL_LIB_CHECK /* Check for compatible library */
277
278 if ((argc == 1) && isatty( 0 /*stdin*/)) {
279 fprintf(stdout, qh_prompt2, qh_version);
280 exit(qh_ERRnone);
281 }
282 if (argc > 1 && *argv[1] == '-' && !*(argv[1]+1)) {
283 fprintf(stdout, qh_prompta, qh_version, qh_DEFAULTbox,
284 qh_promptb, qh_promptc, qh_promptd, qh_prompte);
285 exit(qh_ERRnone);
286 }
287 if (argc > 1 && *argv[1] == '.' && !*(argv[1]+1)) {
288 fprintf(stdout, qh_prompt3, qh_version);
289 exit(qh_ERRnone);
290 }
291 if (argc > 1 && *argv[1] == '-' && *(argv[1]+1)=='V') {
292 fprintf(stdout, "%s\n", qh_version2);
293 exit(qh_ERRnone);
294 }
295 qh_init_A(stdin, stdout, stderr, argc, argv); /* sets qh qhull_command */
296 exitcode= setjmp(qh errexit); /* simple statement for CRAY J916 */
297 if (!exitcode) {
298 qh NOerrexit = False;
299 qh_checkflags(qh qhull_command, hidden_options);
300 qh_initflags(qh qhull_command);
301 points= qh_readpoints(&numpoints, &dim, &ismalloc);
302 if (dim >= 5) {
303 qh_option("Qxact_merge", NULL, NULL);
304 qh MERGEexact= True; /* 'Qx' always */
305 }
306 qh_init_B(points, numpoints, dim, ismalloc);
307 qh_qhull();
308 qh_check_output();
309 qh_produce_output();
310 if (qh VERIFYoutput && !qh FORCEoutput && !qh STOPpoint && !qh STOPcone)
311 qh_check_points();
312 exitcode= qh_ERRnone;
313 }
314 qh NOerrexit= True; /* no more setjmp */
315 #ifdef qh_NOmem
316 qh_freeqhull(qh_ALL);
317 #else
318 qh_freeqhull(!qh_ALL);
319 qh_memfreeshort(&curlong, &totlong);
320 if (curlong || totlong)
321 qh_fprintf_stderr(6263, "qhull internal warning (main): did not free %d bytes of long memory(%d pieces)\n",
322 totlong, curlong);
323 #endif
324 return exitcode;
325 } /* main */
326
327