qhull.txt

DT三角化实现

	      the topology of the convex hull.

       Qbk:n  Scale  the  k'th	coordinate  of	the input points.
	      After scaling, the lower bound of	the input  points
	      will be n.  'Qbk'	scales to -0.5.



Geometry Center		     2003/12/30		       13





qhull(1)						 qhull(1)


       QBk:n  Scale  the  k'th	coordinate  of	the input points.
	      After scaling, the upper bound will  be  n.   'QBk'
	      scales to	+0.5.

       Qc     Keep  coplanar points with the nearest facet.  Out-
	      put formats 'p', 'f', 'Gp', 'Fc',	 'FN',	and  'FP'
	      will print the points.

       Qf     Partition	points to the furthest outside facet.

       Qg     Only  build  good	 facets.   With	 the 'Qg' option,
	      Qhull will only build those facets that it needs to
	      determine	 the  good  facets  in	the  output.  See
	      'QGn', 'QVn', and	'PdD' for defining  good  facets,
	      and  'Pg'	 and  'PG'  for	 printing good facets and
	      their neighbors.

       QGn    A	facet is good (see 'Qg'	and 'Pg') if it	is  visi-
	      ble  from	point n.  If n < 0, a facet is good if it
	      is not visible from point	n.  Point n is not  added
	      to  the  hull  (unless 'TCn' or 'TPn').  With rbox,
	      use the 'Pn,m,r' option to define	 your  point;  it
	      will be point 0 (QG0).

       Qi     Keep  interior points with the nearest facet.  Out-
	      put formats 'p', 'f', 'Gp', 'FN',	 'FP',	and  'Fc'
	      will print the points.

       QJn    Joggle  each  input  coordinate  by adding a random
	      number in	[-n,n].	 If  a	precision  error  occurs,
	      then  qhull  increases  n	and tries again.  It does
	      not increase n beyond a certain value, and it stops
	      after  a	certain	 number	of attempts [see user.h].
	      Option 'QJ' selects a default  value  for	 n.   The
	      output will be simplicial.  For Delaunay triangula-
	      tions, 'QJn' sets	'Qbb' to scale the  last  coordi-
	      nate (not	if 'Qbk:n' or 'QBk:n' is set).  See also
	      'Qt'.

       Qm     Only  process  points that would otherwise increase
	      max_outside.  Other points are treated as	 coplanar
	      or interior points.

       Qr     Process  random  outside points instead of furthest
	      ones.  This makes	Qhull equivalent to  the  random-
	      ized  incremental	 algorithms.   CPU  time  is  not
	      reported since the randomization is inefficient.

       QRn    Randomly rotate the input	points.	 If n=0, use time
	      as  the  random  number seed.  If	n>0, use n as the
	      random number seed.  If n=-1, don't rotate but  use
	      time  as the random number seed.	For Delaunay tri-
	      angulations ('d' and 'v'), rotate	 about	the  last
	      axis.




Geometry Center		     2003/12/30		       14





qhull(1)						 qhull(1)


       Qs     Search all points	for the	initial	simplex.

       Qt     Triangulated output.  Triangulate non-simplicial 
              facets.

       Qv     Test  vertex  neighbors  for  convexity after post-
	      merging.	To use the 'Qv'	option,	you also need  to
	      set a merge option (e.g.,	'Qx' or	'C-0').

       QVn    A	 good facet (see 'Qg' and 'Pg')	includes point n.
	      If n<0, then a good facet	does not include point n.
	      The point	is either in the initial simplex or it is
	      the first	point added to the  hull.   Option  'QVn'
	      may not be used with merging.

       Qx     Perform  exact merges while building the hull.  The
	      "exact" merges are merging a point into a	 coplanar
	      facet  (defined  by 'Vn',	'Un', and 'C-n'), merging
	      concave facets, merging duplicate	ridges,	and merg-
	      ing  flipped  facets.   Coplanar	merges	and angle
	      coplanar merges ('A-n') are not performed.  Concav-
	      ity testing is delayed until a merge occurs.

	      After  the  hull	is built, all coplanar merges are
	      performed	(defined by 'C-n' and 'A-n'), then  post-
	      merges are performed (defined by 'Cn' and	'An').

       Qz     Add  a  point  "at  infinity"  that  is  above  the
	      paraboloid for Delaunay triangulations and  Voronoi
	      diagrams.	  This	reduces	 precision  problems  and
	      allows the triangulation of cospherical points.


       Qhull experiments and speedups

       Q0     Turn off pre-merging as  a  default  option.   With
	      'Q0'/'Qx'	 and  without explicit pre-merge options,
	      Qhull ignores precision issues  while  constructing
	      the  convex  hull.   This	 may  lead  to	precision
	      errors.  If so, a	descriptive warning is generated.

       Q1     With  'Q1',  Qhull  sorts	merges by type (coplanar,
	      angle coplanar, concave) instead of by angle.

       Q2     With 'Q2', Qhull merges all facets at once  instead
	      of  using	 independent  sets  of	merges	and  then
	      retesting.

       Q3     With 'Q3', Qhull does  not  remove  redundant  ver-
	      tices.

       Q4     With 'Q4', Qhull avoids merges of	an old facet into
	      a	new facet.

       Q5     With 'Q5', Qhull does not	correct	outer  planes  at
	      the  end.	 The maximum outer plane is used instead.




Geometry Center		     2003/12/30		       15





qhull(1)						 qhull(1)


       Q6     With 'Q6', Qhull	does  not  pre-merge  concave  or
	      coplanar facets.

       Q7     With  'Q7',  Qhull  processes facets in depth-first
	      order instead of breadth-first order.

       Q8     With 'Q8'	and merging, Qhull does	not retain  near-
	      interior	points	for adjusting outer planes.  'Qc'
	      will probably retain all points that  adjust  outer
	      planes.

       Q9     With 'Q9', Qhull processes the furthest of all out-
	      side sets	at each	iteration.

       Q10    With 'Q10', Qhull does not use special processing 
	      for narrow distributions.

       Q11    With 'Q11', Qhull copies normals and recomputes 
	      centrums for tricoplanar facets.

       Trace options

       Tn     Trace at level n.	 Qhull	includes  full	execution
	      tracing.	 'T-1'	traces	events.	  'T1' traces the
	      overall execution	of the program.	  'T2'	and  'T3'
	      trace overall execution and geometric and	topologi-
	      cal  events.   'T4'  traces  the	algorithm.   'T5'
	      includes	information  about  memory allocation and
	      Gaussian elimination.

       Tc     Check frequently during execution.  This will catch
	      most inconsistency errors.

       TCn    Stop  Qhull  after  building the cone of new facets
	      for point	n.  The	output for 'f' includes	the  cone
	      and the old hull.	 See also 'TVn'.

       TFn    Report  progress	whenever  more	than n facets are
	      created During post-merging, 'TFn' reports progress
	      after more than n/2 merges.

       TI file
	      Input data from 'file'.  The filename may not include 
		  spaces or quotes.

       TO file
	      Output results to	'file'.	 The name may be enclosed
	      in single	quotes.

       TPn    Turn on tracing when point n is added to the  hull.
          Trace partitions of point n. If used with TWn, turn off
          tracing after adding point n to the hull.

       TRn    Rerun  qhull  n  times.  Usually used with 'QJn' to
	      determine	the probability	that a given joggle  will
	      fail.

       Ts     Collect  statistics  and print to	stderr at the end
	      of execution.

       Tv     Verify the convex	hull.  This checks the	topologi-
	      cal  structure,  facet  convexity, and point inclu-
	      sion.  If	precision problems occurred,  facet  con-
	      vexity  is  tested whether or not	'Tv' is	selected.
	      Option 'Tv'  does	 not  check  point  inclusion  if



Geometry Center		     2003/12/30		       16





qhull(1)						 qhull(1)


	      forcing output with 'Po',	or if 'Q5' is set.

	      For  point  inclusion  testing, Qhull verifies that
	      all points are below all outer planes  (facet->max-
	      outside).	 Point inclusion is exhaustive if merging
	      or if the	facet-point product is small enough; oth-
	      erwise  Qhull  verifies  each point with a directed
	      search (qh_findbest).

	      Point inclusion testing occurs after producing out-
	      put.   It	 prints	a message to stderr unless option
	      'Pp' is used.  This allows the  user  to	interrupt
	      Qhull without changing the output.

       TVn    Stop  Qhull  after  adding point n.  If n	< 0, stop
	      Qhull before adding point	n.  Output shows the hull
	      at this time.  See also 'TCn'

       TMn    Turn on tracing at n'th merge.

       TWn    Trace  merge  facets when	the width is greater than
	      n.

       Tz     Redirect stderr to stdout.


BUGS
       Please	 report	   bugs	    to	   Brad	    Barber     at
       [e-mail].

       If Qhull	does not compile, it is	due to an incompatibility
       between your system and ours.  The first	thing to check is
       that  your compiler is ANSI standard.  If it is,	check the
       man page	for the	best options, or  find	someone	 to  help
       you.  If	you locate the cause of	your problem, please send
       email since it might help others.

       If Qhull	compiles but crashes on	the test case (rbox  D4),
       there's	still  incompatibility	between	 your  system and
       ours.  Typically	it's been due to mem.c and memory  align-
       ment.   You  can	 use qh_NOmem in mem.h to turn off memory
       management.  Please let us know if you figure out  how  to
       fix these problems.

       If  you	do  find  a  problem,  try  to simplify	it before
       reporting the error.  Try different size	inputs to  locate
       the  smallest one that causes an	error.	You're welcome to
       hunt through the	code  using  the  execution  trace  as	a
       guide.	This  is  especially true if you're incorporating
       Qhull into your own program.

       When you	do report an error, please attach a data  set  to
       the  end	of your	message.  This allows us to see	the error
       for ourselves.  Qhull is	maintained part-time.



Geometry Center		     2003/12/30		       17





qhull(1)						 qhull(1)


E-MAIL
       Please  send  correspondence  to	 [e-mail]   and
       report  bugs  to	 [e-mail].  Let us know how
       you use Qhull.  If you mention it in a paper, please  send
       the reference and an abstract.

       If  you would like to get Qhull announcements (e.g., a new
       version)	and news (any bugs that	get fixed, etc.), let  us
       know  and  we  will  add	 you to	our mailing list.  If you
       would like to communicate with other Qhull users, we  will
       add you to the qhull_users alias.  For Internet news about
       geometric algorithms and	convex hulls, look at comp.graph-
       ics.algorithms and 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 Math-
       ematical		  Software,	      Dec.	    1996.
       http://www.acm.org/pubs/citations/journals/toms/1996-22-4/p469-barber/
       http://citeseer.nj.nec.com/83502.html


       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
	 [e-mail]		       [e-mail]

			   c/o The Geometry Center
			   University of Minnesota
			   400 Lind Hall
			   207 Church Street S.E.
			   Minneapolis,	MN 55455



ACKNOWLEDGEMENTS
       A special thanks	to Albert Marden, Victor Milenkovic,  the
       Geometry	Center,	Harvard	University, and	Endocardial Solu-
       tions, Inc. for supporting this work.

       The software was	developed under	National Science  Founda-
       tion grants NSF/DMS-8920161 and NSF-CCR-91-15793	750-7504.



Geometry Center		     2003/12/30		       18





qhull(1)						 qhull(1)


       David Dobkin guided the original	work at	Princeton Univer-
       sity.  If you find it useful, please let	us know.

       The Geometry Center is supported	by grant DMS-8920161 from
       the  National  Science  Foundation,   by	  grant	  DOE/DE-
       FG02-92ER25137  from the	Department of Energy, by the Uni-
       versity of Minnesota, and by Minnesota Technology, Inc.

       Qhull is available at http://www.qhull.org













































Geometry Center		     2003/12/30		       19