changes.txt

关于网格剖分的

         Please set qh ATinfinity if you explicitly add the point "at-infinity"
         Please set qh ATinfinity if you explicitly call qh_projectinput.
         Please set qh UPPERdelaunay if you explicitly cleared qh ATinfinity.
	 Other users do not need to change their code.         
   Now you can build a Delaunay triangulation without creating a point 
   "at-infinity".  This removes a potential, hard-to-understand error.  
   qh_readpoints sets qh ATinfinity for options 'd' or 'v' without 'Qu'.
   qh_initB sets qh ATinfinity for qh PROJECTdelaunay w/o qh UPPERdelaunay.
   qh_projectinput adds a point "at-infinity" only if qh ATinfinity is set.
 - added qh_setdelaunay to geom2.c to project points to paraboloid
 - added qh_findbestfacet() to poly2.c to replace qh_findfacet()
 - removed procedure qh_findfacet().  It does not always work.
 - removed NULL option for facet in qh_addpoint().  It does not always work.
 - added noupper parameter to qh_findbest.
 - added search of upperdelaunay facets to qh_findbest()
 - allowed qh_findbest() to start with a flipped or upperdelaunay facet
 - removed qh_nonupper() -- it is no longer needed
 - allow space at end of options
 - fixed qh_projectinput for furthest-site Delaunay (qh PROJECTdelaunay 'd Qu')
 - added voids to procedure declarations with empty parameter lists

qhull V2.3 96/3/25
 - fixed missing qh_check_maxout when coplanar points and no merged facets.
 - fixed qh_freeqhull/allmem (e.g., if qh_NOmem) [only custom code] [E. Voth]
 - fixed qh_freeqhull to free qh interior_point [E. Voth]
 - fixed main() to free all of memory if qh_NOmem.  Include "mem.h" [E. Voth]
 - reset f.newcycle link in qh_mergecycle_all [E. Voth]
 - fixed false error if 'Tc', coplanar points, and a narrow hull
 - turn off 'Rn' when computing statistics, checking code, or tracing code
 - removed ={0} from global.c and stat.c to reduce compiler warnings
 - changed Makefile dependences to $(HFILES) for all but unix.o, set.o, mem.o
 - pulled out qh_printpointid and reordered qh_pointid [E. Voth]
 - removed some compiler warnings
 - moved 'FO' print of options to just before qh_buildhull
 - changed 'FO' to list difference from -1 for _narrow-hull

qhull V2.2 96/2/15
 - detect narrow initial hulls (cosine of min angle < qh_MAXnarrow in user.h).
   Write warning if cosine < qh_WARNnarrow in user.h.  If narrow (qh NARROWhull), 
   partition coplanar points as outside points and delay coplanar test to end.
   See 'limitations' in qh-impre.html for further discussion.
 - corrected some confusions between 'FV' and 'Fv' in qh-opt.html
 - fixed initialization error for small Voronoi diagrams (e.g., [0,0], [1,0], [0,1]) [J. Velez]
  - fixed bad return from qh_mindiff in geom2.c
 - for initial hull, first process facet with furthest outside point (qh_furthestnext)
 - added facet->notfurthest flag for recomputing furthest point
 - added check for __STDC__ (needs ANSI C) [E. Voth]
 - reduced warning messages from [E. Voth].  e[1] in setT still reports a warning.
 - added a cube to the discussion of option 'v' (Voronoi) in qh-opt.html [J. Velez]
 - added notes about adjacent vertices to "Calling Qhull" in qh-man.html [R. Lewis & J. Velez]
 - added note about 'lines closer' when viewing 3-d Delaunay triangulations [P. Kallberg]
 - added option 'Q9' to always process furthest of furthest outside points.
 - removed option 'Pp' from q_eg and qh-eg.html.

qhull V2.2 95/12/28
 - added option 'Qbb' to scale the last coordinate to [0,m] (max prev coord).
   This reduces roundoff errors for Delaunay triangulations with integer coordinates.
 - changed option 'Qu d' to print out the furthest-site Delaunay triangulation
   Use options 'Qu d PD2' to compute the normal 2-d Delaunay triangulation without
   the point at infinity. 
 - added notes to the documentation of option 'd'
 - added notes to limitations of how Qhull handles imprecision
 - added warning if options 'FP', 'Fc', or 'Gp' without option 'Qc' or 'Qi'
 - added note to options 'PDk:n' and 'Pdk:n' that closest facet is returned if none match
 - added check that 'Qbk' and 'QBk' does not invert paraboloid for 'd'
 - added notes that qh_findfacet and qh_addpoint require lifted points for Delaunay triangulations
 - fixed 'rbox s 5000 W1e-13 D2 | qhull d Qcu C-0 Qbb'
 - fixed option 'QbB' (qh SCALEpoints was not set)
 - fixed minor confusion between 'Gc' (print centrums) and 'Gp' (print points)
 - rewrote qh_findbestnew for upper convex hull, Delaunay facets
 - changed option name for 'Gp' from 'Gcoplanar' to 'Gpoints' 
 - changed "nearest" facet for 'Pdk' to threshold - normal
 - reworked qh GOODclosest for 'Qg'
 - added note that 'Qg' does not always work
 - recorded option 'C-0' as "_zero-merge" in option 'FO'
 - refined qh DISTround in qh_maxmin/geom2.c for Delaunay triangulations

qhull V2.2 95/12/4
 - Version 2.2 fixes an important bug in computing Delaunay triangulations 
   and convex hulls with edges sharper than ninety degrees.  The problem 
   occurs when processing a point at a sharp edge.  A directed search can 
   not be used for partitioning because one side may hide facets from the 
   other side.  The new lens-shaped distribution for rbox demonstrates the 
   problem.  For example, 'rbox 100 L3 G0.5 s | qhull Tv' fails for Version 2.1.
   O. Schramm found the bug when computing the Delaunay triangulation of points
   near an outside edge.  

   I rewrote qh_findbest and related functions.  Qh_findbest 
   uses an exhaustive test for sharp edges (qh_findbest_sharp).  
   Qh_findbest avoids the upper convex hull of Delaunay triangulations.

   Options 'd' and 'v' no longer assign coplanar points to the upper convex hull.
    
   Qh_check_maxout tests near-inside points.  It ignores fully inside points.
   When done, it removes near-inside points from the coplanar sets.

   If you use qh_addpoint or qh_findbest, please review the function headers.  
   They do not work for lens-shaped hulls for arbitrary facets.  They do work for 
   Delaunay triangulations.

 Changes to options for V2.2
 - added 'Qu' for computing the furthest-site Delaunay triangulation (upper hull)
   and furthest-site Voronoi vertices.
 - added 'FP' to print nearest vertex for coplanar points
 - added coplanar count to 'Fs' and 's'
 - added number of similar points to summary for Delaunay/Voronoi
 - Option 'Qc' is no longer necessary when merging.  
 - 'o' format for Voronoi vertices ('v') generates "0" lines for similar points
 - 'QRn' for Delaunay ('d' or 'v') now rotates about the Z axis (see qh_init_B).
   Otherwise Qhull does not identify the upper hull
 - removed option 'Qa' for "all points outside".  In V2.1 it was automatically
   set for 'd'.  Even though it was a bad idea, it revealed the above bug.
 - for option list ('FO'), added version, values for one-merge, maxpos, maxneg,
   and near-inside, and flags for zero-centrum
 - optimized 'C-0' and 'Qx'.  These options ("zero-centrum") test vertices 
   instead of centrums for adjacent simplicial facets.
 - if 'Tv', report number of points that are not verified due to qh_findbest
 - Option 'Q8' ignores near-inside points.

 rbox 95/12/3
 - added lens distribution ('Ln')  It may be used with 's', 'r', 'Wn', and 'Gn'
 - removed default point count except for the test case, 'Dn'
 - divided main() of rbox.c into sections

 Documentation changes for V2.2
 - added examples for lens distribution and furthest-site Delaunay triangulation
   and renumbered the examples for q_eg
 - described facet orientation in 'data structure' section [P. Soikkonen]
 - added notes to qh-man.html/"What to do if something goes wrong"
 - added note about using 'Tv' to verify the results [O. Schramm] 
 - expanded definition of f_r in Performance section [S. Grundmann]
 - noted that Geomview display of a Voronoi diagram adds extra edges 
   for unbounded Voronoi cells
 - rewrote error "convexity constraints may be too strong" [D. Newland]
 - added limitations section to "Imprecision in Qhull"
 - added note about zero-area facets to 'Imprecise convex hulls' in qh-impre.html
 - added note to 'Qi' that it does not retain coplanar points
 - added note that option 'Q5' may be used if outer planes are not needed
 - added note to README.txt about Irix 5.1 [C. Goudeseune]
 - added code fragment for visiting Voronoi vertices to "Calling Qhull" [M. Downes]
 - added note about qh_addpoint() to "Calling Qhull" [M. Downes]

 Errors fixed for V2.2
 - use qh_sethyperplane_gauss if 3-d or 4-d norm is less than qh MINnorm
 - count Zcentrumtests if qh_NOstat
 - reversed sign convention for qh_sethyperplane_gauss
   it was opposite to qh_sethyperplane_det
   this effects qh_determinant and qh_detsimplex
 - fixed error in qh_findgood_all with multiple restrictions, e.g., 'QVn Pdk'
 - fixed call to qh_clearcenters for qh_produce_output
 - in qh_errexit, report p0 if last furthest point

 Changes for users of the Qhull library
 - user code needs to define qh_version (see user_eg.c)
 - merged initialization code into qh_init_A and qh_init_B [M. Mazzario] 
   old code works as before.
   qh_initflags also sets qh qhull_command for qh_initthresholds
   redid initialization for user_eg.c
 - simplified user_eg.c.  It computes the convex hull of a cube.
 - added qh_setvoronoi_all in poly2.c to compute Voronoi centers
   added related note to call_qhull
 - added qh_findfacet to use in place of qh_findbest
 - added qh_nearvertex to return nearest vertex in facet to point
 - redid notes on multiple, concurrent calls in call_qhull/user.c
 - changed BoolT to unsigned int (prevent implicit enum conversion warnings)
 - added upperdelaunay to facetT.  It indicates a facet of the upper convex hull.
 - converted qhull-PPC.sit for CodeWarrior 7

 Code changes for V2.2
 - simplified calls to setjmp() for Cray J916 [Salazar & Velez]
 - replaced fprintf(fp,string) with fputs in io.c
 - 'qh num_coplanar' removed (too expensive and not used).
 - added numcoplanars to qh_countfacets()
 - added min norm to qh_normalize2().  qh_normalize() wasn't changed
 - removed type casts from qh_point and qh_pointid [Salazar & Velez]
 - account for roundoff error in detecting upper convex hull (qh ANGLEround).
 - post merging uses qh_findbestnew for partitioning
 - qh_findbestnew for qh_partitioncoplanar goes to best facet
 - 'Qm' always processes points above the upper hull of a Delaunay triangulation
 - GOODvertex initialized with qh_findbestnew instead of qh_findbest
 - for 'v', qh_facetcenter returns furthest-neighbor vertex if 'Qu'
 - added test for qh feasible_point if use 'Fp' and qh_sethalfspace_all
 - reviewed Sugihara's algorithm for topologically robust beneath-beyond
 - on error, report if qhull in post-merging or has completed
 - if tracing, option 'FO' and qhull command always printed
 - added current furthest point ("during p%d") to 'T-1' events
 - added 'TWn' tracing for vertices of new facets (qh_setfacetplane)
 - added 'TWn' tracing for vertices in an output facet (qh_check_maxout)
 - reorganized split between poly/poly2.c and geom/geom2.c
 - reordered object files in Makefile

qhull V2.1 95/9/25
 - converted qhull.man to html format, many edits
 - referenced Shewchuk's triangle program and Schneiders' Mesh Generation page
 - added option 'Qa' to force all points outside 
     automatically set for "precise" Delaunay or Voronoi [Salazar & Velez]
     it is turned off by merging, 'Wn', 'Qc' or 'Qi'
 - added coplanar points to option 'FN'
 - moved option 'FO' to include default precision options
 - changed default random number generator to qh_rand in geom2.c (user.h)

 other code changes
 - fixed option comment Pdrop-facets-dim-less, Qbound-dim-low, QbBound-unit-box
 - defined ptr_intT for converting 64-bit ptrs to 'unsigned long' [D. Bremner]
 - defined setelemT to distinguish actual size from pointers [D. Bremner]
     use either e[...].p or e[...].i (user-level code should use set.h macros)
 - changed %x to %p in format statements for pointers [D. Bremner]
 - added test of REALmax,etc. to qh_maxmin [H. Poulard]
 - added type parameter to qh_memalloc_() macro for type conversion
 - added type conversion to qh_memalloc() calls where missing
 - added type conversion to calls into set.c that return void*

 other documentation changes:
 - new URLs for graphics images
 - fixed comment for facetT.neighbors in qhull.h [P. Soikkonen]
 - changed recommendations for precision errors in qh_printhelp_degenerate()
 -  added recommendation for 'V0' (facet is visible if distance >= 0)
 - added note about 'long double' to user.h [S. Grundmann]
 - added note about zero area Delaunay triangles for the 'v' option
 - added note about locating Delaunay triangles to option 'd' [A. Curtis]
 - added note that coplanar vertices correspond to duplicate points for 'd'
 - added note about option 'd' automatically setting 'PDk' (lower convex hull)
 - added note about precision errors to option 'd' [many users] 
 - added note about qh_findbest() to the Qhull library section [L. Lai]
 - 'make install' renames qhull.man to qhull.1 for Unix [M. Phillips]
 - renamed README, etc. to *.txt to match WWW conventions [D. Cervone]

qhull V2.1 7/10/95
  - in 2-d, 'v o' lists the vertex at infinity in order [R. Critchlow]
  -   it used to always list the vertex at infinity ("0") first
  - rewrote description of 'v' option (Voronoi vertices and 2-d diagrams)
  - added 'PFn' for printing facets whose area is at least 'n' [D. Holland]
  - prefixed 'Q',etc. to the 'Q',etc. options in the long help prompt
  - fixed references to 'Fv' and 'FV' options under option 'Hn,n,n'
  - updated reference to cdd, <ftp://ifor13.ethz.ch/pub/fukuda/cdd/>
  - in set.c, added some missing type coercions for qhmem.tempstack

qhull V2.1 6/12/95
  - replaced qhull.ps with qhull-2.ps (paper submitted to ACM TOMS)
  - use BUFSIZ for setvbuf for Power Macintosh
  - number of good facets printed if QVn, QGn, Pd, or PD
  - added Makefile for Borland C++ 4.02 with Win32 [D. Zwick]
  - added note to Enhancements section of qhull.1 about constrained
       Delaunay triangulations [T. Rasanen]

qhull V2.1 6/7/95
  - fixed qh_facetarea_simplex() for non-simplicial facets [L. Schramm]
  - fixed cast in qh_point and qh_pointid for 64-bit architectures
  - fixed URL for Amenta's list of computational geometry software
  - fixed cast in qh_meminitbuffers for qhmem.freelists
  - added test for !qh half_space in qh readpoints 
  - clarified options for qh_printhelp_singular()
  - discussed non-simplicial facet area under option 'Fa' in qhull.1

qhull V2.1 6/3/95
  - home page for Qhull and new descriptions for the Qhull examples
      http://www.geom.umn.edu/locate/qhull
  - changed SIOUX buffering for Power Macintosh.   It runs fast now.
      added a project file for Metrowerk's C
  - note in README about compiling qhull on the PC

qhull V2.1 beta 5/15/95

		======= main changes ========