1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
|
<!DOCTYPE HTML PUBLIC "-//IETF//DTD HTML//EN">
<html>
<head>
<title>qhalf -- halfspace intersection about a point</title>
</head>
<body>
<!-- Navigation links -->
<p><a name="TOP"><b>Up</b></a><b>:</b> <a href="http://www.qhull.org">Home page</a> for Qhull<br>
<b>Up:</b> <a href="index.htm#TOC">Qhull manual</a>: Table of Contents<br>
<b>To:</b> <a href="qh-quick.htm#programs">Programs</a>
• <a href="qh-quick.htm#options">Options</a>
• <a href="qh-opto.htm#output">Output</a>
• <a href="qh-optf.htm#format">Formats</a>
• <a href="qh-optg.htm#geomview">Geomview</a>
• <a href="qh-optp.htm#print">Print</a>
• <a href="qh-optq.htm#qhull">Qhull</a>
• <a href="qh-optc.htm#prec">Precision</a>
• <a href="qh-optt.htm#trace">Trace</a>
• <a href="../src/libqhull_r/index.htm">Functions</a><br>
<b>To:</b> <a href="#synopsis">sy</a>nopsis
• <a href="#input">in</a>put • <a href="#outputs">ou</a>tputs
• <a href="#controls">co</a>ntrols • <a href="#graphics">gr</a>aphics
• <a href="#notes">no</a>tes • <a href="#conventions">co</a>nventions
• <a href="#options">op</a>tions
<hr>
<!-- Main text of document -->
<h1><a
href="http://www.geom.uiuc.edu/graphics/pix/Special_Topics/Computational_Geometry/half.html"><img
src="qh--half.gif" alt="[halfspace]" align="middle" width="100"
height="100"></a>qhalf -- halfspace intersection about a point</h1>
<p>The intersection of a set of halfspaces is a polytope. The
polytope may be unbounded. See Preparata & Shamos [<a
href="index.htm#pre-sha85">'85</a>] for a discussion. In low
dimensions, halfspace intersection may be used for linear
programming.
<blockquote>
<dl compact>
<dt><p><b>Example:</b> rbox c | qconvex <a href="qh-optf.htm#FQ">FQ</a> <a href="qh-optf.htm#FV">FV</a>
<a href="qh-opto.htm#n">n</a> | qhalf <a
href="qh-optf.htm#Fp">Fp</a></dt>
<dd>Print the intersection of the facets of a cube. <tt>rbox c</tt>
generates the vertices of a cube. <tt>qconvex FV n</tt> returns of average
of the cube's vertices (in this case, the origin) and the halfspaces
that define the cube. <tt>qhalf Fp</tt> computes the intersection of
the halfspaces about the origin. The intersection is the vertices
of the original cube.</dd>
<dt><p><b>Example:</b> rbox c d G0.55 | qconvex <a href="qh-optf.htm#FQ">FQ</a> <a href="qh-optf.htm#FV">FV</a>
<a href="qh-opto.htm#n">n</a> | qhalf <a
href="qh-optf.htm#Fp">Fp</a></dt>
<dd>Print the intersection of the facets of a cube and a diamond. There
are 24 facets and 14 intersection points. Four facets define each diamond
vertex. Six facets define each cube vertex.
</dd>
<dt><p><b>Example:</b> rbox c d G0.55 | qconvex <a href="qh-optf.htm#FQ">FQ</a> <a href="qh-optf.htm#FV">FV</a>
<a href="qh-opto.htm#n">n</a> | qhalf <a
href="qh-optf.htm#Fp">Fp</a>
<a href="qh-optq.htm#Qt">Qt</a></dt>
<dd>Same as above except triangulate before computing
the intersection points. Three facets define each intersection
point. There are two duplicates of the diamond and four duplicates of the cube.
</dd>
<dt><p><b>Example:</b> rbox 10 s t10 | qconvex <a href="qh-optf.htm#FQ">FQ</a> <a href="qh-optf.htm#FV">FV</a>
<a href="qh-opto.htm#n">n</a> | qhalf <a
href="qh-optf.htm#Fp">Fp</a> <a
href="qh-optf.htm#Fn">Fn</a></dt>
<dd>Print the intersection of the facets of the convex hull of 10 cospherical points.
Include the intersection points and the neighboring intersections.
As in the previous examples, the intersection points are nearly the same as the
original input points.
</dd>
</dl>
</blockquote>
<p>In Qhull, a <i>halfspace</i> is defined by the points on or below a hyperplane.
The distance of each point to the hyperplane is less than or equal to zero.
<p>Qhull computes a halfspace intersection by the geometric
duality between points and halfspaces.
See <a href="qh-eg.htm#half">halfspace examples</a>,
<a href="#notes">qhalf notes</a>, and
option 'p' of <a href="#outputs">qhalf outputs</a>. </p>
<p>Qhalf's <a href="#outputs">outputs</a> are the intersection
points (<a href="qh-optf.htm#Fp">Fp</a>) and
the neighboring intersection points (<a href="qh-optf.htm#Fn">Fn</a>).
For random inputs, halfspace
intersections are usually defined by more than <i>d</i> halfspaces. See the sphere example.
<p>You can try triangulated output ('<a href="qh-optq.htm#Qt">Qt</a>') and joggled input ('<a href="qh-optq.htm#QJn">QJ</a>').
It demonstrates that triangulated output is more accurate than joggled input.
<p>If you use '<a href="qh-optq.htm#Qt">Qt</a>' (triangulated output), all
halfspace intersections are simplicial (e.g., three halfspaces per
intersection in 3-d). In 3-d, if more than three halfspaces intersect
at the same point, triangulated output will produce
duplicate intersections, one for each additional halfspace. See the third example, or
add 'Qt' to the sphere example.</p>
<p>If you use '<a href="qh-optq.htm#QJn">QJ</a>' (joggled input), all halfspace
intersections are simplicial. This may lead to nearly identical
intersections. For example, either replace 'Qt' with 'QJ' above, or add
'QJ' to the sphere example.
See <a
href="qh-impre.htm#joggle">Merged facets or joggled input</a>. </p>
<p>The 'qhalf' program is equivalent to
'<a href=qhull.htm#outputs>qhull H</a>' in 2-d to 4-d, and
'<a href=qhull.htm#outputs>qhull H</a> <a href=qh-optq.htm#Qx>Qx</a>'
in 5-d and higher. It disables the following Qhull
<a href=qh-quick.htm#options>options</a>: <i>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,etc</i>.
<p><b>Copyright © 1995-2015 C.B. Barber</b></p>
<hr>
<h3><a href="#TOP">»</a><a name="synopsis">qhalf synopsis</a></h3>
<pre>
qhalf- halfspace intersection about a point.
input (stdin): [dim, 1, interior point]
dim+1, n
halfspace coefficients + offset
comments start with a non-numeric character
options (qhalf.htm):
Hn,n - specify coordinates of interior point
Qt - triangulated output
QJ - joggle input instead of merging facets
Tv - verify result: structure, convexity, and redundancy
. - concise list of all options
- - one-line description of all options
output options (subset):
s - summary of results (default)
Fp - intersection coordinates
Fv - non-redundant halfspaces incident to each intersection
Fx - non-redundant halfspaces
o - OFF file format (dual convex hull)
G - Geomview output (dual convex hull)
m - Mathematica output (dual convex hull)
QVn - print intersections for halfspace n, -n if not
TO file - output results to file, may be enclosed in single quotes
examples:
rbox d | qconvex n | qhalf s H0,0,0 Fp
rbox c | qconvex FV n | qhalf s i
rbox c | qconvex FV n | qhalf s o
</pre>
<h3><a href="#TOP">»</a><a name="input">qhalf input</a></h3>
<blockquote>
<p>The input data on <tt>stdin</tt> consists of:</p>
<ul>
<li>[optional] interior point
<ul>
<li>dimension
<li>1
<li>coordinates of interior point
</ul>
<li>dimension + 1
<li>number of halfspaces</li>
<li>halfspace coefficients followed by offset</li>
</ul>
<p>Use I/O redirection (e.g., qhalf < data.txt), a pipe (e.g., rbox c | qconvex FV n | qhalf),
or the '<a href=qh-optt.htm#TI>TI</a>' option (e.g., qhalf TI data.txt).
<p>Qhull needs an interior point to compute the halfspace
intersection. An interior point is clearly inside all of the halfspaces.
A point is <i>inside</i> a halfspace if its distance to the corresponding hyperplane is negative.
<p>The interior point may be listed at the beginning of the input (as shown above).
If not, option
'Hn,n' defines the interior point as
[n,n,0,...] where <em>0</em> is the default coordinate (e.g.,
'H0' is the origin). Use linear programming if you do not know
the interior point (see <a href="#notes">halfspace notes</a>),</p>
<p>The input to qhalf is a set of halfspaces that are defined by their hyperplanes.
Each halfspace is defined by
<em>d</em> coefficients followed by a signed offset. This defines
a linear inequality. The coefficients define a vector that is
normal to the halfspace.
The vector may have any length. If it
has length one, the offset is the distance from the origin to the
halfspace's boundary. Points in the halfspace have a negative distance to the hyperplane.
The distance from the interior point to each
halfspace is likewise negative.</p>
<p>The halfspace format is the same as Qhull's output options '<a
href="qh-opto.htm#n">n</a>', '<a href="qh-optf.htm#Fo">Fo</a>',
and '<a href="qh-optf.htm#Fi">Fi</a>'. Use option '<a
href="qh-optf.htm#Fd">Fd</a>' to use cdd format for the
halfspaces.</p>
<p>For example, here is the input for computing the intersection
of halfplanes that form a cube.</p>
<blockquote>
<p>rbox c | qconvex FQ FV n TO data </p>
<pre>
RBOX c | QCONVEX FQ FV n
3 1
0 0 0
4
6
0 0 -1 -0.5
0 -1 0 -0.5
1 0 0 -0.5
-1 0 0 -0.5
0 1 0 -0.5
0 0 1 -0.5
</pre>
<p>qhalf s Fp < data </p>
<pre>
Halfspace intersection by the convex hull of 6 points in 3-d:
Number of halfspaces: 6
Number of non-redundant halfspaces: 6
Number of intersection points: 8
Statistics for: RBOX c | QCONVEX FQ FV n | QHALF s Fp
Number of points processed: 6
Number of hyperplanes created: 11
Number of distance tests for qhull: 11
Number of merged facets: 1
Number of distance tests for merging: 45
CPU seconds to compute hull (after input): 0
3
3
8
-0.5 0.5 0.5
0.5 0.5 0.5
-0.5 0.5 -0.5
0.5 0.5 -0.5
0.5 -0.5 0.5
-0.5 -0.5 0.5
-0.5 -0.5 -0.5
0.5 -0.5 -0.5
</pre>
</blockquote>
</blockquote>
<h3><a href="#TOP">»</a><a name="outputs">qhalf outputs</a></h3>
<blockquote>
<p>The following options control the output for halfspace
intersection.</p>
<blockquote>
<dl compact>
<dt> </dt>
<dd><b>Intersections</b></dd>
<dt><a href="qh-optf.htm#FN">FN</a></dt>
<dd>list intersection points for each non-redundant
halfspace. The first line
is the number of non-redundant halfspaces. Each remaining
lines starts with the number of intersection points. For the cube
example, each halfspace has four intersection points.</dd>
<dt><a href="qh-optf.htm#Fn">Fn</a></dt>
<dd>list neighboring intersections for each intersection point. The first line
is the number of intersection points. Each remaining line
starts with the number of neighboring intersections. For the cube
example, each intersection point has three neighboring intersections.
<p>
In 3-d, a non-simplicial intersection has more than three neighboring
intersections. For random data (e.g., the sphere example), non-simplicial intersections are the norm.
Option '<a href="qh-optq.htm#Qt">Qt</a>' produces three
neighboring intersections per intersection by duplicating the intersection
points. Option <a href="qh-optq.htm#QJn">QJ</a>' produces three
neighboring intersections per intersection by joggling the hyperplanes and
hence their intersections.
</dd>
<dt><a href="qh-optf.htm#Fp">Fp</a></dt>
<dd>print intersection coordinates. The first line is the dimension and the
second line is the number of intersection points. The following lines are the
coordinates of each intersection.</dd>
<dt><a href="qh-optf.htm#FI">FI</a></dt>
<dd>list intersection IDs. The first line is the number of
intersections. The IDs follow, one per line.</dd>
<dt> </dt>
<dt> </dt>
<dd><b>Halfspaces</b></dd>
<dt><a href="qh-optf.htm#Fx">Fx</a></dt>
<dd>list non-redundant halfspaces. The first line is the number of
non-redundant halfspaces. The other lines list one halfspace per line.
A halfspace is <i>non-redundant</i> if it
defines a facet of the intersection. Redundant halfspaces are ignored. For
the cube example, all of the halfspaces are non-redundant.
</dd>
<dt><a href="qh-optf.htm#Fv">Fv</a></dt>
<dd>list non-redundant halfspaces incident to each intersection point.
The first line is the number of
non-redundant halfspaces. Each remaining line starts with the number
of non-redundant halfspaces. For the
cube example, each intersection is incident to three halfspaces.</dd>
<dt><a href="qh-opto.htm#i">i</a></dt>
<dd>list non-redundant halfspaces incident to each intersection point. The first
line is the number of intersection points. Each remaining line
lists the incident, non-redundant halfspaces. For the
cube example, each intersection is incident to three halfspaces.
</dd>
<dt><a href="qh-optf.htm#Fc">Fc</a></dt>
<dd>list coplanar halfspaces for each intersection point. The first line is
the number of intersection points. Each remaining line starts with
the number of coplanar halfspaces. A coplanar halfspace is listed for
one intersection point even though it is coplanar to multiple intersection
points.</dd>
<dt><a href="qh-optq.htm#Qc">Qi</a> <a href="qh-optf.htm#Fc">Fc</a></dt>
<dd>list redundant halfspaces for each intersection point. The first line is
the number of intersection points. Each remaining line starts with
the number of redundant halfspaces. Use options '<a href="qh-optq.htm#Qc">Qc</a> Qi Fc' to list
coplanar and redundant halfspaces.</dd>
<dt> </dt>
<dt> </dt>
<dd><b>General</b></dd>
<dt><a href="qh-opto.htm#s">s</a></dt>
<dd>print summary for the halfspace intersection. Use '<a
href="qh-optf.htm#Fs">Fs</a>' if you need numeric data.</dd>
<dt><a href="qh-opto.htm#o">o</a></dt>
<dd>print vertices and facets of the dual convex hull. The
first line is the dimension. The second line is the number of
vertices, facets, and ridges. The vertex
coordinates are next, followed by the facets, one per line.</dd>
<dt><a href="qh-opto.htm#p">p</a></dt>
<dd>print vertex coordinates of the dual convex hull. Each vertex corresponds
to a non-redundant halfspace. Its coordinates are the negative of the hyperplane's coefficients
divided by the offset plus the inner product of the coefficients and
the interior point (-c/(b+a.p).
Options 'p <a href="qh-optq.htm#Qc">Qc</a>' includes coplanar halfspaces.
Options 'p <a href="qh-optq.htm#Qi">Qi</a>' includes redundant halfspaces.</dd>
<dt><a href="qh-opto.htm#m">m</a></dt>
<dd>Mathematica output for the dual convex hull in 2-d or 3-d.</dd>
<dt><a href="qh-optf.htm#FM">FM</a></dt>
<dd>Maple output for the dual convex hull in 2-d or 3-d.</dd>
<dt><a href="qh-optg.htm#G">G</a></dt>
<dd>Geomview output for the dual convex hull in 2-d, 3-d, or 4-d.</dd>
</dl>
</blockquote>
</blockquote>
<h3><a href="#TOP">»</a><a name="controls">qhalf controls</a></h3>
<blockquote>
<p>These options provide additional control:</p>
<blockquote>
<dl compact>
<dt><a href="qh-optq.htm#Qt">Qt</a></dt>
<dd>triangulated output. If a 3-d intersection is defined by more than
three hyperplanes, Qhull produces duplicate intersections -- one for
each extra hyperplane.</dd>
<dt><a href="qh-optq.htm#QJn">QJ</a></dt>
<dd>joggle the input instead of merging facets. In 3-d, this guarantees that
each intersection is defined by three hyperplanes.</dd>
<dt><a href="qh-opto.htm#f">f </a></dt>
<dd>facet dump. Print the data structure for each intersection (i.e.,
facet)</dd>
<dt><a href="qh-optt.htm#TFn">TFn</a></dt>
<dd>report summary after constructing <em>n</em>
intersections</dd>
<dt><a href="qh-optq.htm#QVn">QVn</a></dt>
<dd>select intersection points for halfspace <em>n</em>
(marked 'good')</dd>
<dt><a href="qh-optq.htm#QGn">QGn</a></dt>
<dd>select intersection points that are visible to halfspace <em>n</em>
(marked 'good'). Use <em>-n</em> for the remainder.</dd>
<dt><a href="qh-optq.htm#Qb0">Qbk:0Bk:0</a></dt>
<dd>remove the k-th coordinate from the input. This computes the
halfspace intersection in one lower dimension.</dd>
<dt><a href="qh-optt.htm#Tv">Tv</a></dt>
<dd>verify result</dd>
<dt><a href="qh-optt.htm#TO">TI file</a></dt>
<dd>input data from file. The filename may not use spaces or quotes.</dd>
<dt><a href="qh-optt.htm#TO">TO file</a></dt>
<dd>output results to file. Use single quotes if the filename
contains spaces (e.g., <tt>TO 'file with spaces.txt'</tt></dd>
<dt><a href="qh-optq.htm#Qs">Qs</a></dt>
<dd>search all points for the initial simplex. If Qhull can
not construct an initial simplex, it reports a
descriptive message. Usually, the point set is degenerate and one
or more dimensions should be removed ('<a href="qh-optq.htm#Qb0">Qbk:0Bk:0</a>').
If not, use option 'Qs'. It performs an exhaustive search for the
best initial simplex. This is expensive is high dimensions.</dd>
</dl>
</blockquote>
</blockquote>
<h3><a href="#TOP">»</a><a name="graphics">qhalf graphics</a></h3>
<blockquote>
<p>To view the results with Geomview, compute the convex hull of
the intersection points ('qhull FQ H0 Fp | qhull G'). See <a
href="qh-eg.htm#half">Halfspace examples</a>.</p>
</blockquote>
<h3><a href="#TOP">»</a><a name="notes">qhalf notes</a></h3>
<blockquote>
<p>See <a href="qh-impre.htm#halfspace">halfspace intersection</a> for precision issues related to qhalf.</p>
<p>If you do not know an interior point for the halfspaces, use
linear programming to find one. Assume, <em>n</em> halfspaces
defined by: <em>aj*x1+bj*x2+cj*x3+dj<=0, j=1..n</em>. Perform
the following linear program: </p>
<blockquote>
<p>max(x5) aj*x1+bj*x2+cj*x3+dj*x4+x5<=0, j=1..n</p>
</blockquote>
<p>Then, if <em>[x1,x2,x3,x4,x5]</em> is an optimal solution with
<em>x4>0</em> and <em>x5>0</em> we get: </p>
<blockquote>
<p>aj*(x1/x4)+bj*(x2/x4)+cj*(x3/x4)+dj<=(-x5/x4) j=1..n and (-x5/x4)<0,
</p>
</blockquote>
<p>and conclude that the point <em>[x1/x4,x2/x4,x3/x4]</em> is in
the interior of all the halfspaces. Since <em>x5</em> is
optimal, this point is "way in" the interior (good
for precision errors).</p>
<p>After finding an interior point, the rest of the intersection
algorithm is from Preparata & Shamos [<a
href="index.htm#pre-sha85">'85</a>, p. 316, "A simple case
..."]. Translate the halfspaces so that the interior point
is the origin. Calculate the dual polytope. The dual polytope is
the convex hull of the vertices dual to the original faces in
regard to the unit sphere (i.e., halfspaces at distance <em>d</em>
from the origin are dual to vertices at distance <em>1/d</em>).
Then calculate the resulting polytope, which is the dual of the
dual polytope, and translate the origin back to the interior
point [S. Spitz, S. Teller, D. Strawn].</p>
</blockquote>
<h3><a href="#TOP">»</a><a name="conventions">qhalf
conventions</a></h3>
<blockquote>
<p>The following terminology is used for halfspace intersection
in Qhull. This is the hardest structure to understand. The
underlying structure is a convex hull with one vertex per
non-redundant halfspace. See <a href="#conventions">convex hull
conventions</a> and <a href="index.htm#structure">Qhull's data structures</a>.</p>
<ul>
<li><em>interior point</em> - a point in the intersection of
the halfspaces. Qhull needs an interior point to compute
the intersection. See <a href="#input">halfspace input</a>.</li>
<li><em>halfspace</em> - <em>d</em> coordinates for the
normal and a signed offset. The distance to an interior
point is negative.</li>
<li><em>non-redundant halfspace</em> - a halfspace that
defines an output facet</li>
<li><em>vertex</em> - a dual vertex in the convex hull
corresponding to a non-redundant halfspace</li>
<li><em>coplanar point</em> - the dual point corresponding to
a similar halfspace</li>
<li><em>interior point</em> - the dual point corresponding to
a redundant halfspace</li>
<li><em>intersection point</em>- the intersection of <em>d</em>
or more non-redundant halfspaces</li>
<li><em>facet</em> - a dual facet in the convex hull
corresponding to an intersection point</li>
<li><em>non-simplicial facet</em> - more than <em>d</em>
halfspaces intersect at a point</li>
<li><em>good facet</em> - an intersection point that
satisfies restriction '<a href="qh-optq.htm#QVn">QVn</a>',
etc.</li>
</ul>
</blockquote>
<h3><a href="#TOP">»</a><a name="options">qhalf options</a></h3>
<pre>
qhalf- compute the intersection of halfspaces about a point
http://www.qhull.org
input (stdin):
optional interior point: dimension, 1, coordinates
first lines: dimension+1 and number of halfspaces
other lines: halfspace coefficients followed by offset
comments: start with a non-numeric character
options:
Hn,n - specify coordinates of interior point
Qt - triangulated ouput
QJ - joggle input instead of merging facets
Qc - keep coplanar halfspaces
Qi - keep other redundant halfspaces
Qhull control options:
QJn - randomly joggle input in range [-n,n]
Qbk:0Bk:0 - remove k-th coordinate from input
Qs - search all halfspaces for the initial simplex
QGn - print intersection if redundant to halfspace n, -n for not
QVn - print intersections for halfspace n, -n if not
Trace options:
T4 - trace at level n, 4=all, 5=mem/gauss, -1= events
Tc - check frequently during execution
Ts - print statistics
Tv - verify result: structure, convexity, and redundancy
Tz - send all output to stdout
TFn - report summary when n or more facets created
TI file - input data from file, no spaces or single quotes
TO file - output results to file, may be enclosed in single quotes
TPn - turn on tracing when halfspace n added to intersection
TMn - turn on tracing at merge n
TWn - trace merge facets when width > n
TVn - stop qhull after adding halfspace n, -n for before (see TCn)
TCn - stop qhull after building cone for halfspace n (see TVn)
Precision options:
Cn - radius of centrum (roundoff added). Merge facets if non-convex
An - cosine of maximum angle. Merge facets if cosine > n or non-convex
C-0 roundoff, A-0.99/C-0.01 pre-merge, A0.99/C0.01 post-merge
Rn - randomly perturb computations by a factor of [1-n,1+n]
Un - max distance below plane for a new, coplanar halfspace
Wn - min facet width for outside halfspace (before roundoff)
Output formats (may be combined; if none, produces a summary to stdout):
f - facet dump
G - Geomview output (dual convex hull)
i - non-redundant halfspaces incident to each intersection
m - Mathematica output (dual convex hull)
o - OFF format (dual convex hull: dimension, points, and facets)
p - vertex coordinates of dual convex hull (coplanars if 'Qc' or 'Qi')
s - summary (stderr)
More formats:
Fc - count plus redundant halfspaces for each intersection
- Qc (default) for coplanar and Qi for other redundant
Fd - use cdd format for input (homogeneous with offset first)
FF - facet dump without ridges
FI - ID of each intersection
Fm - merge count for each intersection (511 max)
FM - Maple output (dual convex hull)
Fn - count plus neighboring intersections for each intersection
FN - count plus intersections for each non-redundant halfspace
FO - options and precision constants
Fp - dim, count, and intersection coordinates
FP - nearest halfspace and distance for each redundant halfspace
FQ - command used for qhalf
Fs - summary: #int (8), dim, #halfspaces, #non-redundant, #intersections
for output: #non-redundant, #intersections, #coplanar
halfspaces, #non-simplicial intersections
#real (2), max outer plane, min vertex
Fv - count plus non-redundant halfspaces for each intersection
Fx - non-redundant halfspaces
Geomview output (2-d, 3-d and 4-d; dual convex hull)
Ga - all points (i.e., transformed halfspaces) as dots
Gp - coplanar points and vertices as radii
Gv - vertices (i.e., non-redundant halfspaces) as spheres
Gi - inner planes (i.e., halfspace intersections) only
Gn - no planes
Go - outer planes only
Gc - centrums
Gh - hyperplane intersections
Gr - ridges
GDn - drop dimension n in 3-d and 4-d output
Print options:
PAn - keep n largest facets (i.e., intersections) by area
Pdk:n- drop facet if normal[k] <= n (default 0.0)
PDk:n- drop facet if normal[k] >= n
Pg - print good facets (needs 'QGn' or 'QVn')
PFn - keep facets whose area is at least n
PG - print neighbors of good facets
PMn - keep n facets with most merges
Po - force output. If error, output neighborhood of facet
Pp - do not report precision problems
. - list of all options
- - one line descriptions of all options
</pre>
<!-- Navigation links -->
<hr>
<p><b>Up:</b> <a href="http://www.qhull.org">Home page</a> for Qhull<br>
<b>Up:</b> <a href="index.htm#TOC">Qhull manual</a>: Table of Contents<br>
<b>To:</b> <a href="qh-quick.htm#programs">Programs</a>
• <a href="qh-quick.htm#options">Options</a>
• <a href="qh-opto.htm#output">Output</a>
• <a href="qh-optf.htm#format">Formats</a>
• <a href="qh-optg.htm#geomview">Geomview</a>
• <a href="qh-optp.htm#print">Print</a>
• <a href="qh-optq.htm#qhull">Qhull</a>
• <a href="qh-optc.htm#prec">Precision</a>
• <a href="qh-optt.htm#trace">Trace</a>
• <a href="../src/libqhull_r/index.htm">Functions</a><br>
<b>To:</b> <a href="#synopsis">sy</a>nopsis
• <a href="#input">in</a>put • <a href="#outputs">ou</a>tputs
• <a href="#controls">co</a>ntrols • <a href="#graphics">gr</a>aphics
• <a href="#notes">no</a>tes • <a href="#conventions">co</a>nventions
• <a href="#options">op</a>tions
<!-- GC common information -->
<hr>
<p><a href="http://www.geom.uiuc.edu/"><img src="qh--geom.gif"
align="middle" width="40" height="40"></a><i>The Geometry Center
Home Page </i></p>
<p>Comments to: <a href=mailto:qhull@qhull.org>qhull@qhull.org</a>
</a><br>
Created: Sept. 25, 1995 --- <!-- hhmts start --> Last modified: see top <!-- hhmts end --> </p>
</body>
</html>
|
