1
/*<html><pre> -<a href="../libqhull/qh-qhull.htm"
2
>-------------------------------</a><a name="TOP">-</a>
5
compute Voronoi diagrams and furthest-point Voronoi
8
see unix.c for full interface
10
Copyright (c) 1993-2012, The Geometry Center
22
#if __MWERKS__ && __POWERPC__
35
#define isatty _isatty
39
int isatty(int); /* returns 1 if stdin is a tty
40
if "Undefined symbol" this can be deleted along with call in main() */
43
/*-<a href="../libqhull/qh-qhull.htm#TOC"
44
>-------------------------------</a><a name="prompt">-</a>
50
restricted version of libqhull.c
56
/* duplicated in qvoron_f.htm and qvoronoi.htm
57
QJ and Qt are deprecated, but allowed for backwards compatibility
59
char hidden_options[]=" d n m v H U Qb QB Qc Qf Qg Qi Qm Qr QR Qv Qx TR E V Fa FA FC Fp FS Ft FV Pv Gt Q0 Q1 Q2 Q3 Q4 Q5 Q6 Q7 Q8 Q9 ";
61
char qh_prompta[]= "\n\
62
qvoronoi- compute the Voronoi diagram\n\
63
http://www.qhull.org %s\n\
66
first lines: dimension and number of points (or vice-versa).\n\
67
other lines: point coordinates, best if one point per line\n\
68
comments: start with a non-numeric character\n\
71
Qu - compute furthest-site Voronoi diagram\n\
73
Qhull control options:\n\
74
Qz - add point-at-infinity to Voronoi diagram\n\
75
%s%s%s%s"; /* split up qh_prompt for Visual C++ */
77
Qs - search all points for the initial simplex\n\
78
QGn - Voronoi vertices if visible from point n, -n if not\n\
79
QVn - Voronoi vertices for input point n, -n if not\n\
84
T4 - trace at level n, 4=all, 5=mem/gauss, -1= events\n\
85
Tc - check frequently during execution\n\
87
Tv - verify result: structure, convexity, and in-circle test\n\
88
Tz - send all output to stdout\n\
89
TFn - report summary when n or more facets created\n\
90
TI file - input data from file, no spaces or single quotes\n\
91
TO file - output results to file, may be enclosed in single quotes\n\
92
TPn - turn on tracing when point n added to hull\n\
93
TMn - turn on tracing at merge n\n\
94
TWn - trace merge facets when width > n\n\
95
TVn - stop qhull after adding point n, -n for before (see TCn)\n\
96
TCn - stop qhull after building cone for point n (see TVn)\n\
99
Cn - radius of centrum (roundoff added). Merge facets if non-convex\n\
100
An - cosine of maximum angle. Merge facets if cosine > n or non-convex\n\
101
C-0 roundoff, A-0.99/C-0.01 pre-merge, A0.99/C0.01 post-merge\n\
102
Rn - randomly perturb computations by a factor of [1-n,1+n]\n\
103
Wn - min facet width for non-coincident point (before roundoff)\n\
105
Output formats (may be combined; if none, produces a summary to stdout):\n\
106
s - summary to stderr\n\
107
p - Voronoi vertices\n\
108
o - OFF format (dim, Voronoi vertices, and Voronoi regions)\n\
109
i - Delaunay regions (use 'Pp' to avoid warning)\n\
113
char qh_promptd[]= "\
115
Fc - count plus coincident points (by Voronoi vertex)\n\
116
Fd - use cdd format for input (homogeneous with offset first)\n\
117
FD - use cdd format for output (offset first)\n\
118
FF - facet dump without ridges\n\
119
Fi - separating hyperplanes for bounded Voronoi regions\n\
120
FI - ID for each Voronoi vertex\n\
121
Fm - merge count for each Voronoi vertex (511 max)\n\
122
Fn - count plus neighboring Voronoi vertices for each Voronoi vertex\n\
123
FN - count and Voronoi vertices for each Voronoi region\n\
124
Fo - separating hyperplanes for unbounded Voronoi regions\n\
125
FO - options and precision constants\n\
126
FP - nearest point and distance for each coincident point\n\
127
FQ - command used for qvoronoi\n\
128
Fs - summary: #int (8), dimension, #points, tot vertices, tot facets,\n\
129
for output: #Voronoi regions, #Voronoi vertices,\n\
130
#coincident points, #non-simplicial regions\n\
131
#real (2), max outer plane and min vertex\n\
132
Fv - Voronoi diagram as Voronoi vertices between adjacent input sites\n\
133
Fx - extreme points of Delaunay triangulation (on convex hull)\n\
136
char qh_prompte[]= "\
137
Geomview options (2-d only)\n\
138
Ga - all points as dots\n\
139
Gp - coplanar points and vertices as radii\n\
140
Gv - vertices as spheres\n\
141
Gi - inner planes only\n\
143
Go - outer planes only\n\
145
Gh - hyperplane intersections\n\
147
GDn - drop dimension n in 3-d and 4-d output\n\
150
PAn - keep n largest Voronoi vertices by 'area'\n\
151
Pdk:n - drop facet if normal[k] <= n (default 0.0)\n\
152
PDk:n - drop facet if normal[k] >= n\n\
153
Pg - print good Voronoi vertices (needs 'QGn' or 'QVn')\n\
154
PFn - keep Voronoi vertices whose 'area' is at least n\n\
155
PG - print neighbors of good Voronoi vertices\n\
156
PMn - keep n Voronoi vertices with most merges\n\
157
Po - force output. If error, output neighborhood of facet\n\
158
Pp - do not report precision problems\n\
160
. - list of all options\n\
161
- - one line descriptions of all options\n\
163
/* for opts, don't assign 'e' or 'E' to a flag (already used for exponent) */
165
/*-<a href="../libqhull/qh-qhull.htm#TOC"
166
>-------------------------------</a><a name="prompt2">-</a>
171
char qh_prompt2[]= "\n\
172
qvoronoi- compute the Voronoi diagram. Qhull %s\n\
173
input (stdin): dimension, number of points, point coordinates\n\
174
comments start with a non-numeric character\n\
176
options (qvoronoi.htm):\n\
177
Qu - compute furthest-site Voronoi diagram\n\
178
Tv - verify result: structure, convexity, and in-circle test\n\
179
. - concise list of all options\n\
180
- - one-line description of all options\n\
182
output options (subset):\n\
183
s - summary of results (default)\n\
184
p - Voronoi vertices\n\
185
o - OFF file format (dim, Voronoi vertices, and Voronoi regions)\n\
186
FN - count and Voronoi vertices for each Voronoi region\n\
187
Fv - Voronoi diagram as Voronoi vertices between adjacent input sites\n\
188
Fi - separating hyperplanes for bounded regions, 'Fo' for unbounded\n\
189
G - Geomview output (2-d only)\n\
190
QVn - Voronoi vertices for input point n, -n if not\n\
191
TO file- output results to file, may be enclosed in single quotes\n\
194
rbox c P0 D2 | qvoronoi s o rbox c P0 D2 | qvoronoi Fi\n\
195
rbox c P0 D2 | qvoronoi Fo rbox c P0 D2 | qvoronoi Fv\n\
196
rbox c P0 D2 | qvoronoi s Qu Fv rbox c P0 D2 | qvoronoi Qu Fo\n\
197
rbox c G1 d D2 | qvoronoi s p rbox c P0 D2 | qvoronoi s Fv QV0\n\
200
/* for opts, don't assign 'e' or 'E' to a flag (already used for exponent) */
202
/*-<a href="../libqhull/qh-qhull.htm#TOC"
203
>-------------------------------</a><a name="prompt3">-</a>
206
concise prompt for qhull
208
char qh_prompt3[]= "\n\
210
Except for 'F.' and 'PG', upper-case options take an argument.\n\
212
OFF_format p_vertices i_delaunay summary facet_dump\n\
214
Fcoincident Fd_cdd_in FD_cdd_out FF-dump-xridge Fi_bounded\n\
215
Fxtremes Fmerges Fneighbors FNeigh_region FOptions\n\
216
Fo_unbounded FPoint_near FQvoronoi Fsummary Fvoronoi\n\
219
Gvertices Gpoints Gall_points Gno_planes Ginner\n\
220
Gcentrums Ghyperplanes Gridges Gouter GDrop_dim\n\
222
PArea_keep Pdrop d0:0D0 Pgood PFacet_area_keep\n\
223
PGood_neighbors PMerge_keep Poutput_forced Pprecision_not\n\
225
QG_vertex_good Qsearch_1st Qupper_voronoi QV_point_good Qzinfinite\n\
226
T4_trace Tcheck_often Tstatistics Tverify Tz_stdout\n\
227
TFacet_log TInput_file TPoint_trace TMerge_trace TOutput_file\n\
228
TWide_trace TVertex_stop TCone_stop\n\
230
Angle_max Centrum_size Random_dist Wide_outside\n\
233
/*-<a href="../libqhull/qh-qhull.htm#TOC"
234
>-------------------------------</a><a name="main">-</a>
237
processes the command line, calls qhull() to do the work, and exits
240
initializes data structures
242
finishes initialization
243
computes convex hull and other structures
248
int main(int argc, char *argv[]) {
249
int curlong, totlong; /* used !qh_NOmem */
250
int exitcode, numpoints, dim;
254
#if __MWERKS__ && __POWERPC__
255
char inBuf[BUFSIZ], outBuf[BUFSIZ], errBuf[BUFSIZ];
256
SIOUXSettings.showstatusline= false;
257
SIOUXSettings.tabspaces= 1;
258
SIOUXSettings.rows= 40;
259
if (setvbuf(stdin, inBuf, _IOFBF, sizeof(inBuf)) < 0 /* w/o, SIOUX I/O is slow*/
260
|| setvbuf(stdout, outBuf, _IOFBF, sizeof(outBuf)) < 0
261
|| (stdout != stderr && setvbuf(stderr, errBuf, _IOFBF, sizeof(errBuf)) < 0))
262
fprintf(stderr, "qhull internal warning (main): could not change stdio to fully buffered.\n");
263
argc= ccommand(&argv);
266
if ((argc == 1) && isatty( 0 /*stdin*/)) {
267
fprintf(stdout, qh_prompt2, qh_version);
270
if (argc > 1 && *argv[1] == '-' && !*(argv[1]+1)) {
271
fprintf(stdout, qh_prompta, qh_version,
272
qh_promptb, qh_promptc, qh_promptd, qh_prompte);
275
if (argc >1 && *argv[1] == '.' && !*(argv[1]+1)) {
276
fprintf(stdout, qh_prompt3, qh_version);
279
qh_init_A(stdin, stdout, stderr, argc, argv); /* sets qh qhull_command */
280
exitcode= setjmp(qh errexit); /* simple statement for CRAY J916 */
282
qh_option("voronoi _bbound-last _coplanar-keep", NULL, NULL);
283
qh DELAUNAY= True; /* 'v' */
285
qh SCALElast= True; /* 'Qbb' */
286
qh_checkflags(qh qhull_command, hidden_options);
287
qh_initflags(qh qhull_command);
288
points= qh_readpoints(&numpoints, &dim, &ismalloc);
290
qh_option("_merge-exact", NULL, NULL);
291
qh MERGEexact= True; /* 'Qx' always */
293
qh_init_B(points, numpoints, dim, ismalloc);
297
if (qh VERIFYoutput && !qh FORCEoutput && !qh STOPpoint && !qh STOPcone)
299
exitcode= qh_ERRnone;
301
qh NOerrexit= True; /* no more setjmp */
305
qh_freeqhull( False);
306
qh_memfreeshort(&curlong, &totlong);
307
if (curlong || totlong)
308
fprintf(stderr, "qhull internal warning (main): did not free %d bytes of long memory(%d pieces)\n",
added
removed
src/qvoronoi/qvoronoi.c
