.............This file lists all changes to qhull and rbox.....................
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'.
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,
- 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 ========
- 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
======= 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 half-spaces 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