qhull(1) General Commands Manual qhull(1) (NAME) qhull - (SYNOPSIS) qhull - (stdin): (#points) () : (qh-quick.htm): d - d Qu - ( ) v - v Qu - H1,1 - [1,1,0,...] Qt - QJ - Tv - : . - - - -? - -V - (): s - () i - n - p - ( 'Qc' ) 'v' FA - Fp - FS - Fx - ( ) G - Geomview ( ) m - Mathematica ( ) o - OFF ( 'v' ) QVn - n -n TI file - TO file - : rbox D4 | qhull Tv rbox 1000 s | qhull Tv s FA rbox 10 D2 | qhull d QJ s i TO result rbox 10 D2 | qhull v Qbb Qt p rbox 10 D2 | qhull d Qu QJ m rbox 10 D2 | qhull v Qu QJ o rbox c d D2 | qhull Qc s f Fx | more rbox c | qhull FV n | qhull H Fp rbox d D12 | qhull QR0 FA rbox c D7 | qhull FA TF1000 rbox y 1000 W0 | qhull Qc rbox c | qhull n - html: html/index.htm - : README.txt - : COPYING.txt REGISTER.txt Changes.txt - : - : - : - (Geomview): - : - : - : qhull@qhull.org - : qhull_bug@qhull.org : - (INTRODUCTION) - (DESCRIPTION) Qhull - (IMPRECISION) Qhull - (OPTIONS) - - / - - Geomview - - Qhull - - (BUGS) - (E-MAIL) - (SEE ALSO) - (AUTHORS) - (ACKNOWLEGEMENTS) Qhull . html Qhull (html/index.htm) . Qhull (furthest-site) . Quickhull . Qhull . . . . 2-d 3-d 4-d Geomview . (DESCRIPTION) : . . . . . . . . Qhull Quickhull . 2-d Quickhull n-d beneath-beyond [.. Preparata & Shamos '85]. [Clarkson et al. '93]. Quickhull . Qhull (vertices) (ridges) (facets) . . d . 3-d . . (simplicial) . Qhull (non-simplicial) . d . (IMPRECISION) Qhull . . Qhull 'C-0' 2-d 3-d 4-d 'Qx' 5-d . . 'QJ' (joggle) . 'C-0' Qhull . . 'Qx' Qhull . . 'Qx' . 'QJ' (joggle ). . (OPTIONS) 'qhull -?' . 'qhull -' . 'qhull .' . . ( 'PG' 'F'). . : ('F') Geomview ('G') ('P') Qhull ('Q') ('T'). : default . . d (paraboloid). 'o' . 'QJ' . 'Ft' . ( centrums) . v . 'p' . 'o' . (site ID) . 'Fv' . . qh_INFINITE (-10.101) . . Hn,n,... [n,n,0,...]. 'n' 'Fo' 'Fi' . 'Fp' . 'Fv' . . [n,n,n,...] (feasible point) (Hx+b <= 0). 0 . . 'H' . "1" . 'FV' . d Qu . 'o' . 'QJ' . 'Ft' . v Qu . 'p' . 'o' . 'Fv' . . qh_INFINITE (-10.101) . . /: f . G Geomview. Geomview . Geomview . . 'G' . 'G' (dual polytope) . i . Qhull . . (0-relative) . . 4d Qhull . ( ) (centrum) . . . 'Fv' . 'Ft' . 'i' 'Ft' . m Mathematica. Qhull Mathematica 2-d 3-d 2-d . Qhull Mathematica : "list= << ". 2-d "Show[Graphics[list]] " . 3-d "Show[Graphics3D[list]]" ..TP n . Qhull ( ) . . o OFF. Qhull (ridges) . . . . . 2-d 3-d . Voronoi 2-d . 3-d Voronoi (index) . 'v' . p . Qhull . 'Gc' 'Gi' (coplanar) . Voronoi Voronoi . s stderr. stdout . ( 'Pg') . ( ) . ( 2.1x) . An . n Qhull . 'n' Qhull (-). 'n' Qhull (-). - - . 'Cn' 'C-n' 'C0' 'C-0' . 'Qx' 'A-n' 'C-n' 'An' 'Cn' . Cn (Centrum radius). n Qhull . 'n' '-0' Qhull . "-" . 'n' Qhull ("-"). - - . 5-d 'C-n' 'Qx' . . En (roundoff) . Rn +/- n * max_coord. (hyperplane) . (seed) 'QR-1' . Vn . 'Vn' . 'Vn' ('En') . - ('C-n') 2-d 3-d . ('Wn') 'Vn' 'Wn' . Un . 'Vn' . Wn . . 'Wn' . 'Wn' 'En' . - 'Wn' 'Wn' 'Cn' maxcoord*(1-An) . / Fa . Delaunay . Voronoi (dual facet) . 'PAn' n 'PFn' 'n' . . . . FA 's'. ('Fa' ). Fc . . . . 'Qi' . ( ) ( ) . FC . . . Fd cdd (homogeneous points). () . . "begin" . 1+ "real" "integer" . "1" "1.0" . "end" . ('Fd Hn,n,...') . . Qhull . FD ('n' 'Fo' 'Fi') ('p') cdd. Qhull . "begin" . 1+ "real" . . 1.0 . . "end" . FF ( 'f') (ridges). Fi . . Fi Voronoi. . . (float) . d . 'QVn' ( ) . 'Tv' . 'Fo' 'Fv' Voronoi . FI . Fm . 511 . 'PMn' . FM Maple. Qhull Maple 2-d 3-d 2-d Delaunay . Qhull '.mpl' ()display3d ..TP Fn . . . . . ('Pg') . ( 'FI'). << >> Delaunay . FN . . . "1" . "0" . ( 'Fn'). Fo 'n'. . Fo Voronoi. (ridges) . . . d (offset) . 'QVn' ( ) . 'Tv' . 'Fi' 'Fv' Voronoi . FO stderr . 'FO' stdout . Fp ( 'Hn,n,...'). (dual polytope) . <<>> [-10.101,-10.101,...] . FP ('Qc') . FQ qhull . Fs . ("8") (simplicial) ("2") . . Qhull . FS (hull). ("0") . ("2") . Qhull . . (non-simplicial) . 'Fa' . Ft (non-simplicial). . . 'Qz' (point-at-infinity) . Fv . . . . ( ). Fv Voronoi. . . . Voronoi . '0' ( ) . 3-d . 'Fi' 'Fo' . FV . (feasible point) . Fx () . . . '0' . 2-d . Delaunay 'Fx' . . Geomview G Geomview. Qhull 2-d 3-d 4-d . . dim-1 . 4-d . 4-d Qhull . 'Gh' . Ga . Gc (centrum) 3-d. . . 'C-n' 'Cn' . GDn n 3-d 4-d. 2-d 3-d . Gh 3-d 4-d. 3-d . ( ('Gc')). 4-d . Gi 2-d 3-d. . . (1-r,1-g,1-b) . . Gn . Geomview ( ) () . Geomview . Go 2-d 3-d. . . . Gp . . maxcoord * (1-An) . 1/20 (post-merging) . Gr 3-d. . 4-d . Gt Delaunay 3-d . 'Gt' . 'Gr' 'GDn' ..TP Gv . . 'Gp' . (Print options) PAn n . 'PG' 'Pg' . Pdk:n normal[k] <= n . 'Pdk' 0 n . PDk:n normal[k] >= n . 'PDk' 0 n . PFn 'n' . 'PG' 'Pg' . Pg . ( 'QGn') ( 'QVn'). 'Pdk' 'PDk' . 'Pg' 'd' 'PAn' 'PFn' 'PMn' . PG . PMn n . 'PG' 'Pg' . Po . ('Tv') . . 'Po' . Qhull 'Po' ( ) . Pp . Qhull (Qhull control options) Qa Qbk:0Bk:0 k . - . Delaunay Voronoi . QbB . -0.5 +0.5 . Delaunay Voronoi (paraboloid) . . Qbb [0, m] m . Delaunay Voronoi . . . Qbk:n k- . n . 'Qbk' -0.5 . QBk:n k- . n . 'QBk' +0.5 . Qc . 'p' 'f' 'Gp' 'Fc' 'FN' 'FP' . Qf . Qg . 'Qg' Qhull . 'QGn' 'QVn' 'PdD' 'Pg' 'PG' . QGn ( 'Qg' 'Pg' ) n . n < 0 n . n ( 'TCn' 'TPn' ). rbox 'Pn,m,r' 0 (QG0). Qi . 'p' 'f' 'Gp' 'FN' 'FP' 'Fc' . QJn (Joggle) [-n,n]. qhull n . [user.h ]. 'QJ' n . . Delaunay 'QJn' 'Qbb' ( 'Qbk:n' 'QBk:n' ). 'QJn' Voronoi . 'Qt' . Qm max_outside . . Qr . Qhull . (CPU time) . QRn . n=0 (seed) . n>0 n . n=-1 . Delaunay ( 'd' 'v') . Qs . Qt . -. 'Qt' Voronoi . 'Qt' . Qv - (post-merging). 'Qv' ( 'Qx' 'C-0'). QVn ( 'Qg' 'Pg' ) n . n<0 n . . 'QVn' . Qw . Qhull . Qx . <<>> ( 'Vn' 'Un' 'C-n') (ridges) . ('A-n') . . ( 'C-n' 'A-n') - ( 'Cn' 'An'). Qz << >> Delaunay Voronoi. (cospherical) . Qhull (Qhull experiments and speedups) Q0 - (pre-merging) . 'Q0'/'Qx' - Qhull . . ..TP Q1 'Q1' Qhull / (mergetype/distance) / (mergetype/angle) . Q2 'Q2' Qhull . Q3 'Q3' Qhull . Q4 'Q4' Qhull . Q5 'Q5' Qhull . . Q6 'Q6' Qhull - (pre-merge) . Q7 'Q7' Qhull - (breadth-first) - (depth-first) . Q8 'Q8' Qhull -- . 'Qc' . Q9 'Q9' Qhull . Q10 'Q10' Qhull . Q11 'Q11' Qhull (centrums) (tricoplanar) . Q12 'Q12' Qhull dupridge . Q14 'Q14' Qhull (pinched) dupridge . Q15 'Q15' Qhull (ridges) . (Trace options) Tn n. Qhull . 'T-1' . 'T1' . 'T2' 'T3' . 'T4' . 'T5' . Ta qh_fprintf() . TAn Qhull n . Tc . . TCn Qhull n. 'f' . 'TVn' . Tf (flush) qh_fprintf. 'Tf' (segfault) . stderr 'Tz' . TFn n . - (post-merging) 'TFn' n/2 . TI file 'file'. . TMn n- . TO file 'file'. . TPn n . n . TWn n . TP-1 qh_buildhull qh_postmerge. TRn qhull n . 'QJn' (joggle) . Ts stderr . Tv (convex hull). (point inclusion) . 'Tv' . 'Po' 'Q5' 'Tv' . Qhull (facet->maxoutside) . - (exhaustive) Qhull (qh_findbest) . . stderr 'Pp' . Qhull . TVn Qhull n. n < 0 Qhull n . . 'TCn' . TWn n . Tz stderr stdout. 'Tf' . Brad Barber qhull_bug@qhull.org . Qhull . ANSI . (man page) . . Qhull (rbox D4) (crash ) . mem.c (memory alignment) . qh_NOmem mem.h . . . . (execution trace) . Qhull . (data set) . . Qhull - . (E-MAIL) qhull@qhull.org qhull_bug@qhull.org . Qhull . . Qhull ( ) ( ) . Qhull (alias) qhull_users . (convex hulls) comp.graphics.algorithms sci.math.num-analysis . (SEE ALSO) rbox(1) Barber, C. B., D.P. Dobkin, and H.T. Huhdanpaa, "The Quickhull Algorithm for Convex Hulls," ACM Trans. on Mathematical Software, 22(4):469-483, Dec. 1996. http://portal.acm.org/citation.cfm?doid=235815.235821 http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.117.405 Clarkson, K.L., K. Mehlhorn, and R. Seidel, "Four results on randomized incremental construction," Computational Geometry: Theory and Applications, vol. 3, p. 185-211, 1993. Preparata, F. and M. Shamos, Computational Geometry, Springer-Verlag, New York, 1985. (AUTHORS) C. Bradford Barber Hannu Huhdanpaa bradb@shore.net hannu@qhull.org .fi (ACKNOWLEDGEMENTS) Albert Marden Victor Milenkovic Geometry Center Harvard University .Endocardial Solutions, Inc . 1.0 2.0 Qhull (National Science Foundation) NSF/DMS-8920161 NSF-CCR-91-15793 750-7504 . David Dobkin (Princeton University) . . Geometry Center DMS-8920161 DOE/DE-FG02-92ER25137 (Department of Energy) (University of Minnesota) .Minnesota Technology, Inc . Qhull http://www.qhull.org . Geometry Center 2003/12/30 qhull(1)