changes.txt

DT三角化实现

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

qhull 2003.1  2003/12/30

New Features:
 - Add Maple output ('FM') for 2-d and 3-d convex hulls [T. Abraham]

Bug Fixes and Code Changes:
 - Fixed qh_findbest() for upperdelaunay facets w/o better, lower neighbors
 -   For library users and some qhull users [A. Cutti, E. Milloti, K. Sun]
 - Preserved qhmem.ferr in qh_memfreeshort() for library users
 - Removed 'static' from qh_compare... for io.h and merge.h [V. Brumberg]

Documentation:
 - Add warning to findDelaunay() and qh_in.htm about tricoplanar facets
 - Noted Edelsbrunner's Geometry & Topology for Mesh Generation [qh-impre.htm]
 - Noted Gartner's Miniball algorithm [qh_impre.htm]
 - Noted Veron and Leon's shape preserving simplification [qh_impre.htm]

qhull 2003.1  2003/12/19

Bug Fixes:
 - Reversed coordinate order for qh.ATinfinity in qh_projectinput [V. Brumberg]
 - This effects:
 -   Qhull library 'd' or 'v' users with 'Qz' and unequal coordinate ranges.
 -   qdelaunay/qvoronoi users with 'Qbk:0Bk:0', 'Qz', and unequal coordinate ranges

Changes to code:
 - Replaced qh_VERSION with qh_version in global.c [B. Pearlmutter]
    The previous techniques were either clumsy or caused compiler errors
 - Removed unused variables from qh_findbest and qh_findbestnew [B. Pearlmutter]
 - Note that qh.TESTpoints was added in 2002.1 for tsearch implementation

Changes to distribution:
 - Added Unix distribution including Debian files [R. Laboissiere]
    The previous Unix distribution is now the source distribution
 - Added rpm distribution [L. Mazet]
 - Investigated generation of Win32 dll.  Need to define a C++ interface.

Changes to documentation:
 - Moved Qhull to www.qhull.org (geom.umn.edu is not available)
 - The Geometry Center is archived at http://www.geom.uiuc.edu
 - Reviewed introduction to each program
    Triangulated output ('Qt') is more accurate than joggled input ('QJ')
    qdelaunay is 'qhull d Qbb' [C. Ulbrich]
    qvoronoi is 'qhull v Qbb'
    Added example of non-simplicial intersection to halfspace intersections
 - Added warning about using the Qhull library.
 - Added qhull timings to When to use Qhull [C. Ulbrich]
 - Reorganized the home page index and the manual index
 - Moved qh-home.htm to index.htm

Changes to examples
 - Fixed options for eg/eg.t23.voronoi.imprecise [B. Pearlmutter]


qhull 2002.1  2002/8/20

Changes to distribution:
 - Set up savannah.gnu.org/projects/qhull/ [R. Laboissiere]
 - Set up www.thesa.com as a backup
 - Added qh-get.htm, a local copy of the download page
 - Added Visual C++ interface to Qhull, qhull_interface.cpp [K. Erleben]
 - Use HTTP instead of FTP for downloading Qhull
 - Renamed qhull-1.0.sit.hqx

Bug fixes:
 - Fixed sign of coefficients for cdd halfspaces ('FD','Fd')  [T. Abraham]

Changes to code:
 - Replace qh_version with qh_VERSION in qhull.h.
   Allows shared libraries and single point of definition
 - Added qh.TESTpoints for future implementation of tsearch

Changes to build
 - Makefile.txt works under cygwin
 - Added Make-config.sh to create a Debian build [R. Laboissiere]
 - Added .exe to Makefile.txt#clean.  
 - In README, use -fno-strict-aliasing with gcc-2.95.1 [Karas, Krishnaswami]
 - Fixed chmod in Makefile.txt [B. Karas]

Documentation updates
 - Documented input options for each program [A. Montesinos]
 - FAQ: "How to get the radii of the empty spheres for Voronoi vertices"

URL updates:
 - Changed official URL from locate/qhull to software/qhull
 - Changed URLs from relative to absolute in qh-home.htm and qh-get.htm
 - Added URL for Newsgroup: comp.soft-sys.matlab
 - Added URL for GNU Octave
 - Added URLs for Google and Google Groups
 - Replaced qhull_mail.html and qhull_bug.html with mailto links.
 - Removed URL for Computational Geometry Tribune
 - Changed URL for locate/cglist to software/cglist
 - Used site relative links for qh-home.htm

qhull 3.1 2001/10/04

New features
 - Added option 'Qt' to triangulate non-simplicial facets
 - Added option 'TI file' to input data from file
 - Added option 'Q10' to prevent special processing for narrow distributions
        e.g., RBOX 1000 L100000 s G1e-6 t1001803691 | QHULL Tv Q10
 - Tried to compute Voronoi volumes ('Pv'). Requires dual face graph--not easy
        See Clarkson's hull program for code.

Changes to options
 - Added numtricoplanars to 'Fs'. Number of good, triangulated facets for 'Qt'
 - Added Zdelvertextot to 'Fs'.  If non-zero and Delaunay, input is degenerate
 - Qhull command ('FQ') may be repeated.
 - If 'TPn' and 'TWn' defined, trace the addition of point 'n'
     otherwise continue tracing (previously it stopped in 4-d)
 - Removed 'Ft' from qdelaunay.  Use 'Qt o' or 'qhull d QJ Qt' instead.
     For non-simplicial regions, 'Ft' does not satisify the Delaunay property.
 - If 'Po' or 'TVn', qhull checks outer planes.  Use 'Q5' to turn off.
 - If 'T4', print facet lists and check polygon after adding each point
 
Corrections to code
 - rbox: allow 'c' and 'd' with 's r', meshes, etc.
 - qh_findbest: redesigned as directed search. qh_findbesthorizon for coplanar
      qh_findbest is faster for many distributions
 - qh_findbestnew: redesigned to search horizon of coplanar best newfacets
      needed for distributions with a sharp edge, 
	  e.g., rbox 1000 s Z1 G1e-13 | qhull Tv
 - qh_findbest/qh_findbestnew: search neighbors of better horizon facets
      was needed for RBOX 1000 s Z1 G1e-13 t996564279 | qhull Tv  
      and RBOX 1000 s W1e-13 P0 t996547055 | QHULL d Qbb Qc Tv
 - qh_findbest with noupper: could return an upperdelaunay facet if dist>qh.MINoutside.
 - qh_findbestnew: allow facet->upperdelaunay if dist > qh.MINoutside
 - qh_partitioncoplanar: call qh_partitionpoint if outside and perpendicular
      for distributions with a sharp edge
 - qh_partitionvisible: report precision error if all newfacets degenerate.
      was needed for RBOX 1000 s W1e-13 t995138628 | QHULL d
 - qh_createsimplex: clears qh.num_visible, may be non-zero with 'TRn QJ'

Changes to prompts, warnings, and statistics
 - For Delaunay & Voronoi, 's' reports deleted vertices due to facet merging.
   They were incorrectly reported as nearly incident points.
 - Warn if recompute centrum after constructing hull
 - Simplified narrow hull warning and print all digits of cosine.  
     A narrow hull may lead to a point outside of the hull.
 - Print total vertices deleted instead of ave. per iteration (Zdelvertextot)
 - Improved tracing for qh_partitionpoint and qh_partitioncoplanar
 - Added number of distance tests for checking outer planes (qh_check_maxout)
 - Simplified "qhull precision error: Only n facets remain."
 - Included 'TRn' in the causes of a premature exit

Changes to documentation
 - README.txt: Added quickstart instructions for Visual C++
 - rbox: Added example of edge of narrow lens, rbox 1000 L100000 s G1e-6
 - Added cross references between options 'o' and 'p'.
 - qh-eg.html: added examples comparing 'Qt', 'QJ', and neither 'Qt' nor 'QJ' 
	eg.15a.surface, eg.15b.triangle, eg.17a.delaunay.2, etc.
 - Reorganized and enhanced discussion of precision problems in qh_impre.htm
 - Fixed spelling errors [K. Briggs]
 - Fixed link errors, validated HTML, and spell checked [HomeSite]
 - Removed unnecessary #TOP links
 - Added source links to the qh-quick.htm's header and footer
 - qh-geom.htm, qh-poly.htm: add links to Voronoi functions in io.c
 - src/index.htm: Added how to search qhull.h for qhull options
 - qvoronoi.htm/qdelaun.htm: 'Fc' and 'FN' includes deleted vertices

Changes to URLs
 - Added http://www.voronoi.com and http://www.magic-software.com

Changes to code
 - qh_qhull: if 'TVn' or 'TCn' do not call qh_check_maxout and qh_nearcoplanar
 - reviewed time profile.  Qhull is slower.  Optimized qh_findbestnew()
 - qh_addpoint: Added warning note about avoiding a local minimum
 - qh_checkpolygon: report qh.facet_next error if NARROWhull & dist>MINoutside
 - qh_findbest: renamed "newfacets" parameter to "isnewfacets" since it is boolT
 - qh_findbest/qh_findbestnew: testhorizon even if !MERGING
        Otherwise qhull c D6 | qhull Q0 Tv assigns coplanar points 
 - qh_resetlists: add qh_RESETvisible for qh_triangulate
 - qh_findbest: search better facets first.  Rewritten.
 - qh_findbest: increased minminsearch, always check coplanar facets.  
        See: RBOX 1000 s Z1 G1e-13 t996564279 | QHULL Tv
 - qh_findbestnew: report precision error for deleted cones [rare event]
        e.g.:  RBOX 1000 s W1e-13 P0 t1001034076 | QHULL d Qbb Qc Tv
 - qh_findbesthorizon: search horizon of qh.coplanarset.  New.
 - qh_findbestsharp: replaced with qh_sharpnewfacets followed by qh_findbestnew
 - qh_partitionpoint, Delaunay sites can not be inside.  Otherwise points may
       be outside upperDelaunay facets yet not near-inside Delaunay facets
       See: RBOX s 1000 t993602376 | QHULL C-1e-3 d  Qbb FA Tv
 - qh_partitioncoplanar: call qh_findbest/qh_findbestnew with qh DELAUNAY 
 - qh_printlists: format long lines 
 - qh_printvertex: format long lines
 - user.h: tightened qh_WARNnarrow and qh_MAXnarrow.  Do not see problems 
       until they are -1.0.
 - user.h: defined qh_DISToutside, qh_SEARCHdist, and qh_USEfindbestnew 
 - qh_checkfacet: in 3-d, allow #ridges > #vertices.  Can get a vertex twice
   in a ridge list, e.g,  RBOX 1000 s W1e-13 t995849315 D2 | QHULL d Tc Tv 

Changes to FAQ
 - Recommended use of triangulated output ('Qt')

Changes to distribution
 - Recompiled in Visual C++ 5.0 with optimization (as was version 2.6)
 - q_test: Added bad cases for Qhull and tests for new features

Changes to Qhull library
 - Added qh_triangulate() to poly2.c.  It triangulates the output.
 - Added option 'Q11' to copy normals and recompute centrums for tricoplanar facets 
        'FP' may not print the nearest vertex for coplanar points
        Use option 'Q11' when adding points after qh_triangulate()

qhull 3.0 2001/02/11

Changes to distribution
 - added qconvex, qdelaunay, qhalf, and qvoronoi
 - added qhull-interface.cpp on calling Qhull from C++ [K. Erleben]
 - renamed to qhull3.0/.   
 - added eg/, html/, and src/ directories 

Changes to URLs
 - MathLab6 qhull: convhulln, delaunayn, griddatan, tsearchn, vororoin [Z. You]
 - Wolfram Research wrote a Mathematica interface for qdelaunay [Hinton]
 - Geomview moved from www.geom.umn.edu to www.geomview.org [M. Phillips}
 - added URLs for tcsh and cygwin to README.txt

Changes to documentation
 - reorganized table of contents and renamed qh-man.htm to index.htm
 - wrote program documentation, dropped qh-opt.htm and qh-optv.htm
 - added quick reference, qh-quick.htm
 - reorganized qh-rbox.htm and renamed it to rbox.htm
 - split up qh-c.htm for quick navigation

Corrections to code
 - fixed type of arg for error message in qh_initqhull_globals [N. Max]
 - fixed incorrect initialization of qh MINdenom_1 for scalepoints
 - fixed drop dim for 'H Qbk:0Bk:0'.  Added qh.feasible_point to qh_projectinput 
 - qh_WARNnarrow is angle between facet normals.  Negate for warning message.
 -   statistics for Wangle/etc. concerns facet normals.  Reworded [E. Voth]
 - fixed error message for 'FC v'
 - report cospherical points if Delaunay and error in qh_scalelast()

Changes to code
 - turn on Pg if (QVn or QGn) and not (Qg or PG)
 - turn on Qc if format option 'Fc', 'FP', or 'Gp' (removes warning)
 - removed last good facet unless ONLYgood ('Qg').
 - added count of non-simplicial or merged facets to 'FS'
 - added count of non-simplicial facets to 's' (OK if #vertices==dim)
 - added Znonsimplicial and Znowsimplicial to 'Ts'
 - allow Mathematica output of dual polytope for halfspace intersection
 - added qh_checkflags to globals.c for multiple front ends
 - qh_initqhull_globals sets qh.MERGING if qh.MERGEexact
 - removed hashentryT.  It is no longer used.

Changes to prompts and warnings
 - reorganized prompts
 - reorganized synopsis for rbox.c
 - print warning if 'Fc' or 'FP' with 'd QJ'.  Coincident points are unlikely.
 - ignore warning if options 'v i Pp'.  qvoronoi users may need Delaunay tri.
 - reworded warning if 'Pg' and 'QVn' is not a vertex.
 - reworded warning for 'Qx Tv', qh_check_points() in poly2.c
 - if 'Pp', turn off warning for 'Qbb' without 'd' or 'v' 
 - in qh_printsummary() of Voronoi and Delaunay, distinguish QVn, QGn, Pdn, PDn 

Changes to FAQ
 - added FAQ item for nearly flat Delaunay triangles [Z. You]
 - added FAQ item for area and volume [R. Konatham]
 - added FAQ item for Voronoi diagram of a square [J. Yong]
 - edited FAQ item on point location in Delaunay triangles [Z. You]
 - added FAQ item on nearly flat Delaunay triangles [Dehghani]
 - added FAQ item about halfspace intersection [V. Tyberghein]