changes.txt

关于网格剖分的

.............This file lists all changes to qhull and rbox.....................

qhull 2.6 1999/04/19
 - fixed memory overwrite (no effect) in qh_initstatistics() [K. Ford]
 - added zdoc11 to qh-stat.h#ZZdef for !qh_KEEPstatistics [K. Ford]
 - enhanced qh_initqhull_globals() test of qh_RANDOMint and qh_RANDOMmax
 - added debugging option to always return qh_RANDOMmax from qh_rand()
 - fixed option 'Qr', qh_initialvertices(), to allow a broken qh_rand() 
   fixed option 'Qr', qh_nextfurthest(), to allow narrow hulls  
     Option 'Qr' simulates the random incremental algorithm for convex hulls
 - added note that qh.num_outside includes coplanar points for narrow hulls
 - added FAQ items for triangles/ridges of 3-d Delaunay triangulation[P. Kumar]
 - added FAQ item about on-line processing with the Qhull library [O. Skare]
 - changed name of option 'Error-roundoff' to 'Distance-roundoff'

qhull 2.6 1998/12/30
 - for the unbounded rays of the Voronoi diagram, use a large box [Schmidt]
     e.g., 'rbox P4,4,4 P4,2,4 P2,4,4 P4,4,2 10 | qhull v Fv' fails for point 0
     while 'rbox P4,4,4 P4,2,4 P2,4,4 P4,4,2 10 c G5 | qhull v Fv' is OK.
 - fixed qh_new_qhull() to use outfile/errfile instead of stdout/stderr [Ford]
 - clarified COPYING.txt for use in other programs [Archer]
 - improved qh_readpoints() error message for incorrect point count.
 - added FAQ item for closest triangle to a point [Sminchisescu & Heijting]
 - added FAQ item for is a point outside of a facet [Beardsley]
 - added FAQ item for visiting facets of the Delaunay triangulation [Heijting]
 - added link to Erickson's Computational Geometry Software
 - added link to Sharman's HTML version of the comp.graphics.algorithms FAQ
 - added link to Owen's Meshing Research Corner
 - added note to 'd' about quadratic size of 'rbox 100 l | qhull d' [Kumar]
 - added 'about a point' to mentions of halfspace intersection
 - added request to qh-in.htm to compute largest empty circle [Hase]
 - the DOS window in Windows NT is better than the DOS window in Windows 95
 - removed obsolete qh_findfacet() from qh-c.htm [Sminchisescu]

qhull 2.6 1998/8/12
 new and modified features
 - rbox: added option Mn,m,r to generate a rotated lattice or mesh
 - rbox: report error if more than one of 'l', 'x', 'L', 's', or 'M'

 Qhull library changes
 - added qh_new_qhull() to user.c for calling qhull() from a program [D. Zwick]
   rewrote user_eg.c to use qh_new_qhull().  Added qh_QHpointer example.
 - added qh_CLOCKtype 2 in user.h to call times() for CPU time [B. Hemkemeier]
 - renamed set.c/set.h to avoid conflict with STL's set.h [G. van den Bergen] 
   can also use '#include <qhull/qhull_a.h>' for Qhull library

 fixed errors
 - fixed qh_init_B() to call qh_initqhull_mem() once only [D. Zwick]
   This only effects Qhull library users of qh_QHpointer.
 - fixed qh_mergecycle_all() to check for redundant vertices [J. Nagle]
   e.g., 'rbox M3,4 64 | qhull Qc' should report 8 vertices & 48 coplanars
 - fixed gmcoord initialization in qh_setfacetplane() for qh.RANDOMdist
 - turn off qh.RANDOMdist during qh_printfacetheader()
 - fixed error messages for unknown option flags

 documentation changes
 - added note to FAQ on the Voronoi diagram of cospherical points [H. Hase]
 - added note to 'Qu' on furthest-site Delaunay triangulation via convex hull
 - added note to 'QJ' about coplanar points on the convex hull of the input
 - added note that 'o' and 'FN' list Voronoi regions in site id order [Arvind]
 - added links to Fukuda's introduction to convex hulls, etc. [H. Hase]
 - added .c and .h source files to web distribution and qh-c.htm [J. Sands]
  
 modified code
 - replaced computed minnorm in qh_sethyperplane_det with distance test
 - removed 'qh rand_seed' since random number generator is independent of qhull
 - dropt 'qhull-PPC.sit.bin' from the distribution (out-of-date) [M. Harris]

qhull 2.5 1998/5/4

 fixed errors
 - removed zero-area Delaunay triangles and furthest-site triangles [I. Beichl]
   Zero-area triangles occur for points coplanar with the input's convex hull.
 - replaced qh.MINnorm with computed minnorm in qh_sethyperplane_det [J. Nagle]
   qh.MINnorm was incorrect for the convex hull of the "teapot" example.
   Qhull runs 0-20% slower in 3-d and 4-d.
 - allow 'Qg' with furthest-site Delaunay triangulation (may be faster)
 - removed extra space in definition of FOREACHmerge_() for Alpha cc [R. LeRoy]
 - fixed innerouter type in qh_printvdiagram2 [does not effect code, R. Adams]

 documentation changes
 - to browse qh-c.htm, set MIME type of .c and .h files to text/html
 - added example of 3-d Delaunay triangulation to q-faq.htm
 - added Delaunay and Voronoi examples to qh-optv.htm
 
qhull 2.5 1998/2/4
 - added option 'v Fi' for separating hyperplanes of bounded Voronoi regions
 - added option 'v Fo' for separating hyperplanes of unbounded Voronoi regions
 - option 'Pp' turns off the warning, "initial hull is narrow"
 - fixed partial, 3-d Voronoi diagrams (i.e., 'v Fv QVn Tc')
 - fixed missing statistics in qh_allstat* [T. Johnson]
 - rearranged qh_printvdiagram.  Use qh_eachvoronoi to iterate Voronoi ridges.
 - added qh_check_points to qh-math.c
 
qhull 2.5 1998/1/28
 - added option 'Fv' to print the Voronoi diagram
 - added rbox option 'x' to generate random points in a simplex
 - added rbox option 'y' to generate a simplex and random points
 - added rbox option 'On' to offset the output 
 - add unpacking instructions to README.txt
 - updated discussion of forced output, 'Po'
 - sorted the options alphabetically
 - removed __STDC__ check from qhull.h for VisualC++
 - moved qh_markvoronoi from qh_printvoronoi and cleared facet->seen flags
 - added facet->seen2 flag for 'Fv'

qhull 2.5 1998/1/16
 - fixed initialization of qh.last_low on restart of 'd QJ' 
 - renamed qh_JOGGLEmax to qh_JOGGLEmaxincrease
 - updated URL for Fukuda's cdd program
  
qhull 2.5 1998/1/12

New or modified features
 - added option 'Fx' to print vertices by point id [G. Harris, T. McClendon]
     in 2-d, the vertices are printed in counter-clockwise order
     for Delaunay triangl., 'Fx' lists the extreme points of the input sites
 - added option 'QJ' to randomly joggle input instead of merging facets
 - added option 'TO file' to output results to a file.  Needed for Windows95.
 - added option 'TRn' to rerun Qhull n times. Use to collect joggle statistics

Corrections
 - fixed 2-d facet orientation for 'i' and 'o' outputs
 - for Mathematica 2.2 ('m') changed %10.8g to %16.8f [A. Zhaxybayev]
 - fixed incorrect warning for 'QV0 Qg' in qh_initbuild [B. Wythoff]
 - fixed unaccessible statistic if !qh_KEEPstatistics for Wnewvertexmax
 - fixed overestimate of qh ONEmerge for point sets outside of 
     first quadrant and far from the origin
 - fixed overestimate of 'Qbb' for point sets far from the origin
 - fixed potential overestimate of qh DISTround under 'Qbb'
 - fixed 'p' printing coplanar points of unselected facets
 - fixed 'Ft' printing centrums unnecessarily in 2-d
  
Changes to documentation 
 - wrote internal design documentation (qh-c.htm)
 - started frequently asked questions (qh-faq.htm)
 - added a section on joggled input to qh-impre.htm
 -   added joggle example to qh-eg.htm (eg.15.joggle)
 -   changed q_eg to use 'QJ' instead of 'Q0' were appropriate
 - added an example to each of the main options
 - added examples to rbox.htm
 - added examples to the synopsis
 - added a reference to Mucke, et al ['96], Fast randomized point location ...
 - added code for printing Delaunay triangles to qh-in.htm [A. Tsui]
 - options 'Pdk' and 'PDk' do not drop on equality

Improvements to the code 
 - reviewed warning messages for Qhull options in qh_initflags
 - added warning to 's' if premature exit from 'TCn' or 'TVn'
 - 's' prints max distance above/below only if qh.MERGING
 - reduced maxoutside in qh_check_bestdist/qh_check_points for 'Rn'
 - in post-merging, rebuild centrums of large facets that become small
 - lowered cutoff for coplanar facets for ischeckmax/qh_findbest
 - removed qh_check_maxout for 'Wn Q0'
 - reset tracing after 'TPn' adds point in 4-d and higher

Changes for the Qhull library 
 - changed qh_setdelaunay to call qh_scalelast if used with 'Qbb' or 'QJ'
     Delaunay callers to qh_findbestfacet, qh_addpoint, or qh_findfacet_all
     should always use qh_setdelaunay as in user_eg.c
 - defined qh.outside_err to check points against a given epsilon [E. Voth]
 - added header to user_eg.c to avoid its incorporation into qhull [C. Begnis]
 - added qh_nearcoplanar() calls to user_eg.c
     only needed if use 'QJ'
 - expanded __STDC__ warning message in qhull.h [C. Begnis]
 - renamed qh maxmaxcoord to qh MAXabs_coord
 - replaced qh MAXlowcoord with qh MAXabs_coord
 - random seed ('QR-n') is reset in qh_initqhull_globals after testing
 - replaced 'FO' options "_max-coord/_min-coord" with "_max-width"/qh.MAXwidth

Other changes to Qhull functions
 - report error for !bestfacet in qh_findbest (it shouldn't happen) [H. Meuret]
 - set newbest in qh_findbest only if bestfacet updated 
 - renamed facet parameter for qh_findbest
 - added maxdist argument to qh_checkpoint
 - moved 'FO' output after qh_partitionall
 - separated qh_initbuild from qh_qhull
 -   reinitialize globals modified by qh_buildhull
 -   moved initialization of qh.GOODvertexp & qh.GOODpointp to qh_initbuild
 - separated qh_nearcoplanar from qh_check_maxout
 - separated qh_geomplanes from qh_printfacet2geom, etc.
 - separated qh_freebuild from qh_freeqhull
 - separated qh_outerinner from io.c to return outer and inner planes
 - separated qh_distround and qh_detroundoff from qh_maxmin


qhull 2.4 97/4/2

New or modified features
 - made 'C-0' and 'Qx' default options.  Use 'Q0' to not handle roundoff errors
 - removed point-at-infinity from Delaunay/Voronoi.  
     you no longer need to use 'Qu PDk'
 - added 'Qz' to add a point-at-infinity to Delaunay and Voronoi constructions
 - added published version of qhull article in ACM Trans Math Software
 - ported qhull to Windows95 under Visual C++ and Borland C++
 - added 'Ft' for triangulation by adding the centrums of non-simplicial facets
 - added 'Gt' to display 3-d Delaunay triangulations with a transparent hull
 - changed definition of coplanar point in output to qh min_vertex (see 'Qc')
     it was qh MAXcoplanar ('Un') [could make vertices non-coplanar]
 - automatically set 'Qi' for options 'd Qc' and 'v Qc'.
 - reworded summary ('s') for Delaunay/Voronoi/halfspace.  
     use 'Fs' and 'FS' for summary statistics.
 - for summary 's' of Delaunay/Voronoi, display number of coplanars for facets
     if none, display total number of coplanars (i.e., non-vertices)
 - input comment is first non-numeric text (previously limited to header)
 - added input warning if use 'Qbb' without 'd' or 'v'
 - 'Q3' can not be followed with a numeric option

Corrections
 - fixed qh_partitioncoplanar() to not drop interior points if 'Qi' is used
 - fixed 'FP d' to report distance in point set instead of paraboloid
 - fixed qh_findbest() to search all coplanar facets for qh_check_maxout()
  
Changes to documentation 
 - added example eg.17f.delaunay.3 to show a triangulation of cospherical sites
 - split up qh-opt.htm into multiple pieces
 - split off qh-in.htm for Qhull internals
 - renamed .html files to .htm for Windows95
 - rewrote qh-optv.htm on Delaunay triangulation and Voronoi vertices
 - added 'man' pages qhull.txt and rbox.txt.  These list all the options
 - removed 'txt' versions of html files
 - added note to 'PDk' about avoiding a 'd' option immediately after a float
 - under option 'd', display the triangulation with 'GrD3', not 'GnrD3'
 
Changes to the Qhull library
 - added 'format' argument to qh_printfacetNvertex_nonsimplicial() in io.c
 - removed C++ type errors [J. Stern, S. Marino]
 -  created SETelemt, SETfirstt, etc. for specifying data types.  
 -  use SETelem,etc. for assignments. 
 -  changed setT.maxsize to 'int' to prevent type conversion warnings
 -  changed FOREACH.. to a comma expression for better code and less warning
 -  changed qh.vertex_visit and .visit_id to unsigned int to prevent warnings
 - changed clock() to qh_CPUclock (user.h)
 - qh_init_B() and qh_readpoints() do not set qh.ATinfinity for Delaunay tri.
 - qh_setvoronoi_all() sets upper Delaunay facets if qh.UPPERdelaunay is set
 - qh_nearvertex() returns distance in dim-1 for qh.DELAUNAY
 - removed MSDOS path from qhull_command.  Spaces in Win95 tripped qh_setflags
 - removed memory.h from qhull_a.h.  memset,etc. should be in strings.h
 - split qh_prompt into pieces for Visual C++
 - added note to qh_addpoint that coordinates can not be deallocated
 - added Baker '89 to constrained Delaunay diagrams under Enhancements
    please let me know if you try this
 - added request for unbounded Voronoi rays to Enhancements
    please let me know if you try this

qhull V2.3 96/6/5
 - fixed total area of Delaunay triangulation. [A. Enge]  
      It should ignore facets on the upper-envelope.
 - if 'd Qu FA', the total area is summed over the upper-Delaunay triangles
 - fixed sign of area for Delaunay triangulations. 
 - fixed cdd input format for Delaunay triangulation. [A. Enge]
 - for cdd input, allow feasible point for halfspaces.
 - warning if cdd output format for centrums, halfspace intersections, or OFF.
 - print '0' for area ('Fa') if area is not computed for a facet
 - option 'QR-n' sets random number seed to n without rotating input
 - fixed qh_findbest() to retest coplanar and flipped facets after a restart
 - for 'd Qu Ts' collects angle statistics for upper Delaunay facets
 
 Changes to the Qhull library
 - expanded user_eg.c for incremental constructions and Delaunay triangulation
 - added discussion of incremental construction to qh_man.html#library
 - WARNING: The default value of qh ATinfinity was changed from True to False.
            A new flag, qh UPPERdelaunay, was defined for 'Qu'.