changes.txt

关于网格剖分的

  - added halfspace intersection ('Hn,n,n')
  - facet merging is better, especially for high dimensions 
  -   added 'Qx' for exact merges of coplanar points and precision faults
  - facet merging is faster, especially for high dimensions.
      e.g., convex hull of the 8-d hypercube is seven times faster
  - added 'F' output formats for printing each aspect of the convex hull
  - format 'Fa' computes facet areas, total area, and total volume
  - format 'FO' writes a descriptive list of selected options to stderr
  - moved all customization options to user.h
  - changed the default precision to 'double' since it's needed for Delaunay.
      using 'float' is faster and takes less space (REALfloat in user.h)
  - option 'Qm' is no longer important for facet merging
  - removed need for 'Qs' by selecting initial simplex with pos. determinants
  - renamed 'Qv' to 'Q7' since virtual memory does not work well for qhull
  - Qhull is available for the Power Mac (no graphical output)

                 ====== other new and modified options ===========
  - changed default MINvisible ('Vn') to a multiple of premerge_centrum ('C-n')
  - added 'Un' option to set width of facet for coplanar points.
       This replaces the previous rules for determining coplanar points.
  - changed default MINoutside ('Wn') to twice MINvisible ('Vn')
  - Geomview output adjusts point radii for MINvisible 'Vn' 
  - the input format allows the number of points to precede the dimension
  - options 'v' 'd' 'FAn' and 'FMn' record good facets ('Pg')
  - added 'Fd' and 'FD' options for homogeneous coordinates in cdd format
  -   in rbox, added 'h' flag to generate homogeneous coordinates in cdd format
  - option 'PAn' prints out the n facets with the largest area 
  - option 'PMn' prints out the n facets with the most merges
  - option 'Po' under tracing ('Tn') no longer tries to write erroneous facets
  - option 'TCn' only prints the old 'visible' facets for 'f'
  - 'TFn' reports intermediate results when post-merging
  -   option 'Ts' with option 'TFn' prints intermediate statistics
  - the message for 'Tv' reports if it is checking outer planes
  - 'Tz' sends stderr output to stdout
  - added 'Q1' to ignore angle when sorting merges (merges are worse)
  - added 'Q2' to not perform merges in independent sets (merges are worse)
  - added 'Q3' to not remove redundant vertices (faster)
  - added 'Q4' to avoid merges of old facets into new facets (does worse)
  - added 'Q5' to skip qh_check_maxout (faster, but less accurate)
  - added 'Q6' to skip pre-merge of concave and coplanar facets
  - added 'Qv' for testing vertex neighbors for convexity (needs merge option) 
  - added warning if mix Geomview output with other outputs ('Po' turns off)
  - options 'o v' for 3-d and higher sort the Voronoi vertices by index

		======= documentation =======
  - rewrote the introduction and precision sections 
  - added a section on performance
  - added an example on halfspace intersection
  - installed examples of Qhull in
    <http://www.geom.umn.edu/pix/archive/subjects/computational_geometry.html>

		======= Makefile, user.h, and messages =======
  - Makefile calls ./qhull, ./rbox, and prints short prompt for qhull
  - added new statistics, e.g., for buildhull
  - changed default qh_RANDOMtype to RAND_MAX with rand()
  - added comment about numeric overflow to printhelp_singular
  - reorganized the code to improve locality of reference
  - option in mem.h (qh_NOmem) to turn off memory management in qhull
  - option in user.h (qh_NOtrace) to turn off tracing in qhull
  - option in user.h (qh_NOmerge) to turn off merging in qhull.
  -   use this instead of redefining qh_merge_nonconvex in user.c
  - simplified user_eg.c.  See qh_call_qhull() in user.c for the full version
  
		======== bug fixes ============
  - fixed error in number of points for 'rbox 100 r' (odd distribution)
  - fixed performance error in qh_degen_redundant_neighbors
  - qh_partitionpoint now sets facet->maxoutside for first outside point
  - fixed performance error in partitioning when merging a large, regular cone
  - removed memory leak in qh_appendmergeset
  - removed double free of qh line under errors in qh_readinput()
  - forcing output on error ('Po') fixed for options 'n' 'o' 'i' 's'
  - fixed optimization error on HP machines [fprintf(... *p++)]

                ======== changes to qhull.h for user code =======
  - qh_collectstatistics and qh_printstatistics removed from qhull.h.
      should use qh_printallstatistics instead
  - qh_findbest uses boolT for newfacets
  - added qh_findbestnew for non-simplicial facets.  qh_findbest is
    too slow in this case since it needs to look at many nearly coplanar
    facets.
  - renamed qh_voronoi/qh_centrum to qh_ASvoronoi, qh_AScentrum
  - changed facet->id to 32-bits, added new flags for merging
  - added facet->f for facet pointers while merging and for facet area
  - added dfacet/dvertex for printing facets/vertices while debugging
  - added qh_produce_output and qh_printsummary
   
		======== changes to code ==========
  - moved qh_setfacetplane from qh_makenewfacets to qh_makenewplanes
  - added qh_setfree2, qh_setcompact, and qh_setduplicate to set.c
  - qh_findgooddist returns list of visible facets instead of setting global
  - in qh_check_maxout, inside points may be added to coplanar list.
  - qh_findbestnew used for qh_partitionall.  It is faster.
  - in qh_findbest, changed searchdist to MINvisible+max_outside+DISTround.
      MINvisible is the default MAXcoplanar.
  - cleaned up list management via qh_resetlists
  - uses facet->dupridge to indicate duplicated ridges instead of ->seen
  - qh_buildtracing records CPU time relative to qh hulltime instead of 0

		========== changes to merging =======
  - many performance improvements, especially in high-d.
  - when merging, qh_findbest and qh_findbestnew stops search at qh_DISToutside
  - vertex neighbors delayed until first merge
  - post merges reported every TFn/2 merges
  - vertex merging turned off in 7-d and higher (lots of work, no benefit).
      vertex merging moved to qh_qhull_postmerging in 6-d.
  - replaced qh min_vertex with MAXcoplanar for determining coplanarity
  - pick closest facets to merge in duplicate ridge instead of flip/flip
      (see qh_matchduplicates in poly2.c)
  - optimize merge of simplex into a facet
  - optimize merge of a "samecycle" of facets into a coplanar horizon facet
  - cleaned up qh_forcedmerges/qh_flippedmerges and removed facet->newmerge
  - rewrote qh_merge_degenredundant with separate queue
  - qh_facetdegen replaced by facet->degenredun
  - flipped neighbors no longer merged in preference to flip/non-flip pairs
  - removed angle argument from qh_merge_degenredundant and qh_mergefacet
       only used for tracing
  - getmergeset_initial had extra test of neighbor->simplicial
  - ridge->nonconvex is now set on only one ridge between non-convex facets 
  - moved centrum deletion to qh_updatetested
  - qh_isnewmerge(facet) changed to facet->newmerge (removed NEWmerges)
  - qh_findbestneighbor reports correct distance even if testcentrum
  - added hull_dim factor to qh_BESTcentrum
  - removed horizon preference in qh_merge_nonconvex (qh AVOIDold)
  - facet->keepcentrum if qh WIDEfacet or qh_MAXnewcentrum extra vertices

qhull V2.02 1/25/95
  - rbox 'z' prints integer coordinates, use 'Bn' to change range
  - fixed rare bug in qh_check_maxout when qh_bestfacet returns NULL
  - fixed performance bug in findbestneighbor, should be + BESTnonconvex
  - renamed 'notgood' flag in 'f' option to 'notG' flag (caused confusion)
  - changed qh.hulltime to (unsigned) to prevent negative CPU times
  - added random perturbations to qh_getangle under the 'Rn' option
  - reviewed the documentation and enhancement list
  - added discussion of how to intersect halfspaces using qhull
  - replaced expression that caused incorrect code under an old version of gcc
  - added buffer after qh.errexit in case 'jmp_buf' has the wrong size
  - rewrote qh_printhelp_singular for lower-dimensional inputs
  - rewrote qh_printhelp_degenerate
  - added options for qh_RANDOMint in qhull_a.h
  - changed time format for 'TFn' to %02d

qhull V2.01 6/20/94
  - fixed bug in qh_matchnewfacets that occured when memory alignment makes
    facet->neighbors larger than necessary.
  - fixed bug in computing worst-case simplicial merge of angle coplanar
    facets (ONEmerge).  This decreases (...x) in printsummary.

qhull V2.01 6/17/94
  - added recommendation for 'Qcm' to documentation and help prompts
  - added an input warning to qh_check_points ('Tv') if coplanars and no 'Qc'
  - qh_partitionpoint: always counts coplanar partitions (Zcoplanarpart)
  - rewrote qh_printhelp_degenerate to emphasize option 'C-0'
  - For Geomview output, roundoff is not needed when printing the inner and 
    outer planes.  This improves Geomview output for the 'Rn' option.
  - For Geomview output without coplanar points or vertices, qh_GEOMepislon 
    is not needed.  This removes the edge gap when displaying a Voronoi cell.
  - For Geomview output 'Gp', direct vertices to the interior point 
    instead of the arithmetic center of the displayed vertices.
    
qhull V2.01 6/11/94
  - if pre-merge, 'Qf' is automatically set.  Otherwise an outside point may 
        be dropt by qh_findbest().  This slows down partitioning.
  - always use 'Qc' if merging and all facet->maxoutside's must be right.
        Otherwise distributions with many coplanar points may occassionally
	miss a coplanar point for a facet.  This is because qh_findbest, when 
	called by qh_check_maxout, can become stuck at a local maximum if 
	the search is started at an arbitrary facet.  With 'Qc', the search 
	is started from a coplanar facet.  For example,
		rbox 1000 W8e-6 t | qhull C-0 Tv
	will (rarely) report that a facet->minoutside is incorrect
  - option 'Pp' turns off "Verifying" message for 'Tv'
  - added qh_copynonconvex to qh_renameridgevertex (fixes rare error)
  - 'rbox tn' sets random seed to n
  - 'rbox t' reports random seed in comment line
  - qh_errexit reports rbox_command | qhull_command and 'QR' random seed
  - added additional tracing to bestdist and setfacetplane
  - in qh_checkconvex, need to test coplanar against 0 instead of -DISTround 
  - in qh_checkconvex, always test centrums if merging.  The opposite
    vertex of a simplicial facet may be coplanar since a vertex of
    a simplicial facet may be above the facet's hyperplane.
  - fixed error handling in qh_checkconvex when merging
  - in qh_printsummary, one merge ratio not printed if less than 'Wn'
  - documented that 'Tv' verifies all facet->maxoutside

qhull V2.01 6/2/94
  - 's' prints summary to stderr
  - multiple output formats printed in order to stdout
  - added statistic for worst-case distance for merging simplicial facets 
       	can not hope for a better "max distance above/below facet"
        print factor for "max distance.."/"merge simplicial" in printsummary
  - fixed error in scaling input with min/max reversed ('Qb0:1B0:-1')
  - fixed error in scaling if project & Delaunay & scale ('d Qb0:0B1:0b2:0')
  - user_eg.c: qh_delpoint removed since it does not always work
  - user_eg.c now works for either convex hull or Delaunay triangulation
  - added PROJECTdelaunay for Delaunay triangulations and Voronoi diagrams
	with libqhull.a and user_eg.c
  - user_eg.c: if project or scale input, need to copy points
  - user_eg.c: default just defines main, added fprintf's for qh_errprint etc.
  - qh_gausselim: a 0 pivot no longer zeros the rest of the array,
	  need the remaining elements for area computation
  - qh_qhull: restore cos_max, centrum_radius at end of POSTmerging
  - qh_checkflipped with !allerror is >=0.0 instead of >0.0
  - removed -Wall from gcc due to unnecesssary "warning: implicit declaration"
  - renamed 'new' variables and fields to allow compilation by g++
  - added README notes on C++, and "size isn't known"
  - updated manual on 'Qg' with coplanar facets and no merging ('rbox c D7')
      'Qg Pg' and 'Pg' produce different results because of precision problems

Converting from qhull 1.01 to qhull 2.00
  - 'qhull An' is now 'qhull Wn'
	option 'Wn Po' is faster but it doesn't check coplanars
  - 'qhull g' is now 'qhull G', and the output formats are different
  - 'qhull c' is now 'qhull Tc'
  - 'qhull f' is now 'qhull Qf'
  - 'qhull o' is now 'qhull Po'
  - 'qhull b' is now always done
  - qhull and rbox now use floats, change REALfloat in qhull.h for doubles
  - qhull 2.00 fixes several initialization errors and performanace errors
	e.g., "singular input" on data with lots of 0 coordinates
  - 'rbox b' is now 'rbox c G0.48'
  - all rbox distributions are now scaled to a 0.5 box (use 'Bn' to change)
  - rbox now adds a comment line.  This may be removed by 'rbox n'
  - 'rbox r s Z G' no longer includes the positive pole
  - no changes to the Macintosh version 

qhull V2.00 5/23/94
  - if force output ('Po'), facet->maxoutside= 'Wn' since coplanars not updated
        convexity checked if precision problems or verify ('Tv')
  - if merging, new facets always checked for flipped orientation
  - a facet is visible (findhorizon) under 'Qm' if distance > max_vertex
  - if using 'Qm' then min. outside is max_vertex instead of max_outside
  - default is random()/srandom() in qhull_a.h, checked in initqhull_globals
  - created internal strtod since strtod may skip spacing after number
  - removed lower bound (1.0) for qh maxmaxcoord
  - divzero needs to handle 0/0 and large/small
  - decreased size of precise vertices
  - need to initialize qh MINdenom_1 for scalepoints
  - added factor of qh maxmaxcoord into DISTround (needed for offset)
  - 'Rn' perturbs distance computations by random +/-n
  - check_points needs an extra DISTround to get from precise point to computed
  - rewrote some of the IMPRECISION section in qhull.man
  - added the input format to the qhull prompt
  - moved include files to qhull_a.h since some compilers do not use float.h
  - added qhull.1 and rbox.1 since SGI does not ship nroff
  - reduced cutoff for printpointvect
  - use time for qhull random seed only if QR0 or QR-1
  - radius of vertices and coplanar points determined by pre-merge values

qhull V2.00 5/12/94
  - facet2point (io.c) used vertex0 instead of vertex1
  - can't print visible facets after cone is attached
  - shouldn't check output after STOPcone (TCn)
  - statistic 'Wminvertex' and 'Wmaxoutside' only if MERGING or APPROXhull
  - 'make doc' uses lineprinter format for paging
  - warning if Gpv in 4-d

qhull V2.b05 5/9/94
  - decreased size of precise vertices
  - precise facets in 2-d print hyperplanes
  - accounted for GOODpoint in printsummary
  - added IMPRECISION section to qhull.man
  - 'Qg' does work in 7-d unless there's many coplanar facets