.............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] - added FAQ item for missing ridges [M. Schmidt] - added FAQ item about qh_call_qhull [R. Snyder] - added FAQ item about memory statistics [Masi] - added FAQ item on meshing non-convex objects - added FAQ item on MATLAB and Mathematica interface 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 ' 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] - documented qh_ZEROdelaunay. Delaunay and Voronoi diagrams do not include facets that are coplanar with the convex hull of the input sites. 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'. 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. Needed for RBOX 1000 L100000 s G1e-6 t995127886 | QHULL Tv 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.qhull.org - 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 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