$Id: //main/2019/qhull/src/Changes.txt#77 $$Date: 2020/09/03 $
.............This file lists all changes to qhull and rbox.....................
====
== Contents
====
To do
Qhull 2018-2020
Qhull 2015
Qhull 2012.1
Qhull 2011.1
Qhull 2010.1 and 2009.1
Qhull 2003.1
Qhull 2002.1
Qhull 3.1 (2001)
Qhull 2.6 (1999)
Qhull 2.5 (1998)
Qhull 2.4 (1997)
Qhull 2.3 (1996)
Qhull 2.2 (1995-1996)
Qhull 2.1 (1995)
Qhull 2.0 (1994-1995)
====
== To do
====
- For a list of enhancement requests, see
http://www.qhull.org/html/qh-code.htm#enhance
- The C++ interface needs documentation.
Give C++ a try and make it better.
http://github.com/qhull/qhull/wiki
- Expand the C++ interface for Voronoi diagrams
Design for arbitrary dimension with non-simplicial facets
Start with 'user_eg3 eg-voronoi eg-fifo'
Compute the convex hull of each Voronoi region
Compare its facet hyperplanes with eg-fifo
Create a data structure for the Voronoi diagram
Compare your result to CGAL's 2-d Voronoi diagram
Two CGAL halfedges is equivalent to a Qhull ridge
https://doc.cgal.org/4.7/Voronoi_diagram_2/group__PkgVoronoiDiagramAdaptor2.html
==================
== Qhull 2018-2020
==================
------------
Qhull 2020.2 2020/08/31 (8.0.2)
CMake builds
- CMakeLists.txt: Fixed /usr/local/lib/pkgconfig for debug builds
- CMakeLists.txt: Remove qhull_SHARED and qhull_SHAREDP from 'make all'
Remove qhull_SHARED and qhull_SHAREDP from qhull_TARGETS_SHARED
Use reentrant Qhull (libqhull_r) for user code
- CMakeLists.txt: If "MSYS Makefiles", change the default CMAKE_INSTALL_PREFIX to "/usr/local"
Remove WIN32 conditionals from MAN_INSTALL_DIR and DOC_INSTALL_DIR
- CMakeLists.txt: Add 'uninstall' to delete the files listed in install_manifest.txt
- CMakeLists.txt: If LINK_APPS_SHARED, link qhull applications to libqhull_r.so [S. Bruens #69]
If BUILD_STATIC_LIBS=OFF or BUILD_SHARED_LIBS=OFF, exclude those libraries [S. Bruens #69]
libqhullcpp and user_eg3 are built only if BUILD_STATIC_LIBS is true
- CMakeModules/CheckLFS.cmake: Moved CMakeModules to the build/ directory
- CMakeLists.txt: Replace rbox_SOURCES(etc.) with a source file, either reentrant or non-reentrant
- CMakeLists.txt: Add deprecated libqhull and qhull_p to "# Additional build targets"
If not MSVC, add qh_QHpointer to user_egp_DEFINES and qhullp_DEFINES (otherwise qh_lib_check fails)
Other builds
- build/README-build.txt: Add description of build/ directory
- build/qhull*.sln: Remove qhull_p and qhull_p.dll, retain the corresponding DevStudio project files
Remove libqhull and qhull.dll, retain the corresponding DevStudio project files
- Makefile: Add libqhull_r/libqhullstatic_r.a to 'cleanall'
- Makefile: Add note about installing debug libraries (e.g., libqhull_rd)
- Makefile,libqhull*/Makefile: Copy README.txt,...,Changes.txt and html/* to ABS_DOCDIR
- Makefile,libqhull*/Makefile: Add target 'uninstall' to delete installed Qhull files
- libqhull/qhull-exports.def,qhull-nomerge-exports.def: Add qh_nextfacet2d
Documentation
- html/qh-code.htm: Add request for Doxygen documentation of the C++ interface
- html/index.htm,etc: "Contents" instead of "Table of Contents"
Testing
- eg/make-qhull_qh.sh: Redo help prompt
- eg/make-qhull_qh.sh: Create src/qhull_qh/_QH_CONVERTED_FILES as a safety check
- eg/make-qhull_qh.sh: Require destination directory and _QH_CONVERTED_FILES for 'sed-only'
------------
Qhull Github
C++ interface
- libqhullcpp/qt-qhull.cpp: In toQList(), use count() to avoid a type error
- libqhullcpp/qt-qhull.cpp: In toQList(), use nullptr instead of NULL
- libqhullcpp/QhullSet.h: Declare 'QList<T> toQList() const' to avoid a prototype error
Builds
- Qhull build systems: Add wiki page on build systems to GitHub
- CMakeLists.txt: Use same target name for Debug and non-Debug builds [Spacelm #76]
- CMakeLists.txt: Remove functional documentation from /usr/local/include/libqhull*
Most of the links are broken.
- CMakeLists.txt: Move Qhull html documentation to /usr/local/share/doc/qhull/html/
Otherwise index.htm is overwritten and README links are broken
- CMakeLists.txt: Add /usr/local/share/doc/qhull/src/Changes.txt
- Makefile, make install: Remove functional documentation from /usr/local/include/libqhull
and /usr/local/include/libqhullinclude/libqhull_r. Most of the links are broken.
- Makefile, src/libqhull/Makefile: Add DEPRECATED.txt to /usr/local/include/libqhull
- Makefile, src/libqhull*/Makefile: Add 'make install' to the welcome prompt
Documentation
- index.htm: Balance the top-page 'URL:' and 'To:' links
- index.htm: Send the top-page 'Functions' link to www.qhull.org (better 'src' links)
- index.htm: Make the bottom-page 'URL:' and 'To:' links the same as the top-page links
- index.htm: "please use rentrant Qhull (libqhull_r or libqhullstatic_r)"
- html/index.htm: Add rbox.txt to Contents and rename "Table of Contents"
- html/index.htm,qh-code.htm,qh-eg.htm,qh-impre.htm: Remove 'please wait while loading'
- README.txt/Installing Qhull with Qt: The shadow build directory should be at the same level as 'src'
- README.txt/Compiling Qhull with Qt Creator: Copy steps from 'Installing Qhull with Qt'
------------
Qhull 8.0.1 (2020.2 2020/07/24)
C++ interface
- Removed Java-style iterators for Coordinates and PointCoordinates.
std::vector has an expensive copy constructor and copy assignment, and
a pointer to std::vector is vulnerable to mysterious overwrites (e.g., deleting
a returned value and reusing its memory). Qt's 'foreach' should not be used for
Coordinates and PointCoordinates. It copies std::vector
- QHULL_DECLARE_SEQUENTIAL_ITERATOR: allow temporary results
The Jave-style iterator copies the container. Same as Qt's Q_DECLARE_SEQUENTIAL_ITERATOR
- QhullHyperplaneIterator,QhullPointIterator,QhullPointsIterator: allow temporary results
These Java-style iterators copy the container instead of pointing to the container
- QhullLinkedListIterator,QhullFacetListIterator,QhullVertexListIterator: allow temporary results
These Java-style iterators copy the container instead of pointing to the container
- QhullSetIterator,QhullFacetSetIterator,QhullPointSetIterator,QhullVertexSetIterator: add documentation about temporary results
These Java-style iterators have always copied the container
- QhullUser.h, user_eg3_r.cpp: Removed C++11 dependencies [G. Romualdi, S. Grein #65, #66,#67]
QhullUser.cpp: Use intptr_t to avoid C++11 dependencies [S. Grein, Spacelm #68]
- QhullVertex.cpp: moved the copy constructor to the code file. It was inline.
Testing and example programs
- user_eg3_r.cpp: Renamed 'inputSites' to 'voronoiRegions' in qvoronoi_o/qvoronoi_pfn [M. Konecny #72]
- user_eg3_r.cpp: Replaced C++11's range-based for loops with Qhull's Java-style iterators
- qh-code.html: Updated qhullcpp code example [M. Konecny #71]
- QhullFacet_test.cpp: fixed hyperplane epsilon test in t_getSet. The epsilon due to rotation is unknown.
- Qhull*List_test.cpp,Qhull*Set_test.cpp,QhullRidge_test,QhullVertex_test: test Qt's 'foreach' in t_foreach
- Qhull*List_test.cpp,Qhull*Set_test.cpp,QhullRidge_test,QhullVertex_test: test C++11 range for in t_foreach
- Qhull*List_test.cpp,Qhull*Set_test.cpp: test Java-style iterator in t_java_iterator
- Coordinates_test.cpp,PointCoordinates_test.cpp,QhullHyperplane_test.cpp,QhullPoint_test.cpp,QhullPoints_test.cpp,RboxPoints_test.cpp
test C++11 range for, Qt's 'foreach', and Java-style iterators (if available)
Builds
- README.txt: Fixed "cmake -G" for "Installing Qhull with CMake"
- README.txt: Added a note on 'make install' to "Installing Qhull on Unix"
- README.txt: Added 'make test' to "Installing Qhull on Unix"
- README.txt: Added 'ctest' to "Installing Qhull with CMake"
- README.txt: Added pkg-config notes to "Installing Qhull with CMake"
- README.txt: Added usage notes for Windows to "Installing Qhull with CMake"
- README.txt: Added instructions for downloading MinGW-W64-install.exe
- build/qhull_p.pc.in,qhull_r.pc.in: Delete obsolete files [T. Roehling #63]
- build/qhull.pc.in: move qhull.pc.in into the build/ directory [T. Roehling #63]
Documentation
- qh-code.htm, qhull-news.html: Add Toronto and McCarthy, "Practically accurate floating-point math".
------------
Qhull 2020.1 2020/05/29 (8.0.0)
Bugs fixed
- QhullLinkedList::const_iterator: Fixed operator->() for T*. It returned &i [J. Mirabel 5/1/2020 #61]
API changes
- RoadError.cpp: stringGlobalLog returns std::string instead of const char* [M. Gehre #46]
- io_r.c/qh_order_vertexneighbors: order facet neighbors of a vertex by 2-d (orientation), 3-d (adjacency), n-d (f.visitid,id) [I. Gardner]
- poly2_r.c/qh_nextfacet2d: Return next facet and vertex in qh_ORIENTclock order [N. Katzakis #54]
C++ interface
- Qhull.cpp: Add isDelaunay(). True if computing Delaunay or Voronoi regions
Add prepareVoronoi() for Voronoi output. See user_eg3_r.cpp for examples
~Qhull: Change 'Qhull output at end' to 'Qhull messages at ~Qhull()'
- QhullFacet.cpp: Add visitId() for f.visitid. Needed for Voronoi output
Add nextFacet2d(): Iterate 2-d facets and vertices in counter-clockwise order [N. Katzakis #54]
Add setFacetT()
- QhullRidge.cpp: Add setRidgeT() and qh()
- QhullUser.cpp: Add a user-modifiable interface to Qhull using a custom qh_fprintf
Enhanced qh_fprintf with qhull-2019.1 updates to userprintf_r
Option 'Ta' prefixes output with message code, [QHnnnn]
Option 'Tf' flushes the output after each message, for tracing segfaults
Errors and high-level trace messages prefixed with QHnnnn
Debugging traps for qh.tracefacet, qh.traceridge, qh.tracevertex
- QhullVertex.cpp: Add setVertexT()
- QhullQh.cpp: moved qh_fprintf to QhullUser
- RoadLogEvent::toString: do not prepend QHnnnn if format_string starts with QHn or [QHn
- RboxPoints::appendPoints: use current dimension instead of throwing an error
- user_eg3 rbox: set dimension for multiple options (e.g., user_eg3 rbox D4 5 qhull)
- user_eg3 eg-convex: a 3-d convex hull using the C++ interface to Qhull [I. Voutchkov]
- user_eg3 eg-delaunay: a 2-d Delaunay triangulation using the C++ interface to Qhull
- user_eg3 eg-voronoi: a 2-d Voronoi diagram using the C++ interface to Qhull
- user_eg3 eg-fifo: hyperplanes separating Voronoi regions via QhullUser and qh_fprintf
Documentation
- index.htm: Add Teillaud's http://www.computational-geometry.org/
- index.htm: Add When to use Qhull and Performance of Qhull to the Qhull Manual
- html/qconvex.htm: Add orientation for options 'i', 'Fx', and 'o'
qconvex .: keep the option prompt to five columns
- html/qdelaun.htm: qh_findbestfacet may return an adjacent facet for a point
- html/qhalf.htm,qh-optf.htm,qh-opto.htm: Added notes for options to halfspaces, e.g., 'Fp' and -10.101 [E. Huang #53]
- html/qhalf.htm,qhalf.c,qhalf_r.c,qh-optf.htm: Fix documentation for 'qhalf FN'. The output includes all halfspaces.
- html/qvoronoi.htm,qvoron_f.htm: Fix link for control option, 'TI file'
- html/qvoronoi.htm,qvoron_f.htm, qh-optf: the hyperplanes for 'Fi' and 'Fo' include the first vertex
Option 'Fo' uses the midpoint in place of the vertex at infinity.
- html/qh-optf.htm: Voronoi options 'Fi' and 'Fo' orient the hyperplane so that the site is below the hyperplane
- html/qh-optf.htm,qh-optt.htm: Voronoi option 'Fo' does not check the hyperplane with 'Tv'
The hyperplane check for 'Fi Tv' uses the midpoint, which 'Fo' already used in place of infinity
- README.txt/Windows install: install Git for Windows in C:\Git\ instead of Program Files
README.txt/Unix install: add options for 32-bit builds w/o -fpic
README.txt,Makefile: link libqhullcpp before libqhull_r
- COPYING.txt: Add a note to COPYING.txt about C.B. Barber [M. Pryczek]
- libqhull/DEPRECATED.txt: Add link to qh-code.htm#convert
- Qhull::vertexList: ordered by qh.vertex_list, not by adjacency [N. Katzakis #54]
- QhullPoints.cpp/extraCoordinatesCount: must be less than point_dimension (-Wconversion)
- QhullPoints.cpp/indexOf: extra must be less than point_dimension (-Wconversion)
- io_r.c/qh_detvnorm: add note that qh_sethyperplane_gauss returns nearzero for axis-parallel hyperplanes
- user_r.h/qh_CPUclock: may be converted to approximate double (-Wconversion)
- Update copyright to 2020
Build
- Increase SOVERSION to 8.0 due to ABI breakage in 2019.1 [T. Roehling #58]
Change SOVERSION to major.minor due to Qhull's global data structure qhT [T. Roehling #58]
Add symbolic link from SONAME_EXT to libqhull_r [T. Roehling #58]
Add SO and SONAME_EXT to 'make help'
- qhull.pc.in: Added for pkg-config support [T. Roehling #60]
- CMakeLists.txt: Add pkg-config support and change *_INSTALL_DIR to relative paths [T. Roehling #60]
Change CMAKE_SOURCE_DIR to CMAKE_CURRENT_SOURCE_DIR to allow qhull as a subdirectory [Morwenn #53, A. De #59, A. Maloney, futex]
- Makefile:
Add pkg-support [T. Roehling #63]
Renamed $DESTDIR as $PREFIX to conform with GNU Makefile standards [T. Roehling #63]
$DESTDIR is for staged installs as defined by GNU Makefile standards [T. Roehling #63]
Commented out M32=-m32 despite memory savings. It caused build failures, e.g., Mac [J. Hollowed]
'-fpic' is required for linking to shared libraries [T. Roehling #63]
Replaced -fpic with FPIC=-fpic for gcc builds
Added FPIC to CXX_OPTS1 (same as CMakeLists.txt for libqhullcpp)
Use 'FPIC=' to disable -fpic (may be faster for 32-bit builds on 64-bit hosts)
Extract qhull_VERSION and qhull_SOVERSION from CMakeLists.txt [T. Roehling #63]
Move the -lm linker flag to the end of the linker command [T. Roehling #63]
Add QhullVertexSet.h to LIBQHULLCPP_HDRS
Invoke q_test via bash to avoid "eg not a valid command"
- Add build/*vcxproj to Unix distribution
Testing and other changes
- q_test: Add list of executables via 'which'
Add tests of user_eg3 with each option and use case
Add "Testing done" notification
Add "set +v" for echoes
- qhull-zip.sh: Add early check for 32-bit release build and modified files
Add link checks for options
Add findf for identifying files for link checks
Add prompts for web.archive and md5sum in qh-get.htm
------------
Qhull 2019.1 github 2019/10/24
Documentation
- Review and fix Qhull html and option links
- README.txt/mingw: Install GitForWindows in C:\Git\
- libqhull_r/index.htm: Fixed Firefox web access to '.c' and '.h' files (http://qhull.org/src/libqhull_r/)
Bugs fixed
- merge_r.c/qh_appendmergeset,qh_appendvertexmerge,qh_mergefacet,qh_tracemerge:
fix error check of index for mergetypes
Build
- CMakeLists.txt: Rename Qhull to QhullExport for QhullConfig. On MacOS, "Qhull" conflicts with "qhull" [tamasmeszaros #48, C. Xu, tschoonj]
- CMakeLists.txt: Add POSITION_INDEPENDENT_CODE "TRUE" to set_target_properties for libqhullcpp [J Anderson 11/20/2019 #47]
------------
Qhull 2019.1 2019/06/21 (7.3.2)
bugs fixed
- Fixed broken HTML links identified by Firefox Link Analyzer. Replace old links with web.archive.org (archive.is)
- Moved live code out of qh_NOtrace regions
- qh-faq.htm#learn: fixed the Delaunay examples (rbox generates a square, but does not generate two squares)
- geom2_r.c/qh_maxmin: qh_scalelast for 'd Qbb' to qh.MAXabs_coord instead of qh.MAXwidth [J.R. Roussel, D. Sterratt]
- geom2_r.c/qh_maxsimplex: estimate targetdet as prevdet*qh.MAXwidth, set mindet to 10*qh_RATIOmaxsimplex [J.R. Roussel, D. Sterratt]
- global_r.c/qh_freebuild: in high-D, simplicial facets may use long memory
- global_r.c/qh_initqhull_globals: set qh.DOcheckmax and qh.KEEPnearinside if qh.APPROXhull ('Wn', rbox 100 D3 W1e-1 | qhull QJ W1e-1 Tv)
- libqhull_r.c/qh_addpoint: add qh.lastmerges to qh_addpoint trace
- libqhull_r.c/qh_buildcone_mergepinched: called qh_partitioncoplanar with uninitialized 'dist'
- libqhull_r.c/qh_build_withrestart: if qh_joggle_restart, set v.partitioned for qh.del_vertices. Avoid error in qh_delvertex from qh_freebuild
- libqhull_r.c/qh_partitionall: if qh.KEEPnearinside, qh_partitionpoint for non-outside pointset
- libqhull_r.c/qh_partitioncoplanar: define qh.coplanar_apex to prevent infinite loop of repartition point
- merge_r.c/qh_checkzero: check opposite vertex against -2*qh.DISTround to account for qh_distround and 'Rn'
- merge_r.c/qh_comparevisit: fix compare of 'unsigned int'
- poly2_r.c/qh_findbestfacet: for Delaunay triangulations, may be an adjacent triangle [F. Drielsma]
Updated discussion at qh-code.htm/findfacet and examples at user_eg_r.c and user_eg2_r.c
- poly2_r.c/qh_findfacet_all: do not search visible facets, and if qh_NOupper, f.upperdelaunay facets [P. Virtanen, S. Dominguez, J.Arkin]
- poly2_r.c/qh_initialhull: reverse orientation if clearly flipped. qh_ERRsingular if maybe flipped [S. Caron, P. Virtanen, D. Sterratt, others]
- poly2_r.c/qh_initialhull: test for coplanar qh.interior_point with 'allerror' (dist >= -qh.DISTround) [S. Caron, P. Virtanen, D. Sterratt, others]
- poly2_r.c/qh_initialhull: call qh_joggle_restart for qh.DELAUNAY if cospherical input sites [P. Celba]
- poly2_r.c/qh_initbuild: qh_scalelast for 'd Qbb' to qh.MAXabs_coord instead of qh.MAXwidth [J.R. Roussel, D. Sterratt]
- random_r.c/qh_argv_to_command_size: returned size may be < 1. If so, rbox.c/main reports an error
- rboxlib_r.c/qh_rboxpoints: report error for coincident, regular points 'rbox r C1,1e-13'
- stat_r.c/qh_initstatistics: missing call to qh_allstatistics for qh_newstats. qh_checkoutput ignored
- userprintf.c/qh_fprintf: fixed 2019.0.1 bug if 'qh_qh' is NULL for qh_QHpointer
- Qhull.cpp/outputQhull: fixed missed conditional if qh.GOODvertex == -qh.GOODpoint
documentation and web site
- Add notes that Qhull 64-bit code uses 50% more memory than 32-bit code. This slows down Qhull.
A future version of Qhull will include memory and performance improvements for 64-bit code.
- Add the Qhull identity pipeline to html/qhalf.htm
- Enabled PDF download from portal.acm.org
- Error exit from qhull,qconvex,etc. returns a 6xxx error code if available
- Rename md5sum files back to *-tgz.md5sum and *-zip.md5sum
Both Firefox and IE convert *.tgz.md5sum and *.zip.md5sum as .tgz/.zip files
- html/qh-code.htm: add sections on debugging Qhull
- html/qh-faq.html: reviewed startup questions for Qhull
- html/qh-opto.htm: the centrum indices for option 'i' are one more than the centrum indices for option 'Ft'
build and test
- CMakeLists.txt: export QhullTargets for config.cmake.in and find_package [tamasmeszaros]
- eg/q_benchmark: add 'uname -a' for host identification
- eg/q_test.bat: update for changes to q_test
removed redirects on every line (invoke with redirection)
- eg/q_test: add some tests for option warnings and errors
- Makefile: add dependencies for 'install', 'test', 'qtest', and 'qconvex-prompt' [V. Delecroix]
- Makefile: set -m32 as default for gcc builds. Uses less memory on 64-bit hosts.
disable with 'make M32='
- Remove 'unused parameter' warnings if qh_NOmerge
- Tested qh_QHpointer, qh_NOmem, qh_NOmerge, qh_NOtrace, qh_KEEPstatistics 0
- Tested qh_NOmerge with qh_NOtrace and qh_KEEPstatistics 0. Simpler code, fewer errors, 35% smaller
- Tested random qh_distplane and qh_setplane qh_RANDOMdist 1e-5, qh_RANDOMdist 1e-13
- user_r.h: define qh_RANDOMdist to perturb all calls to qh_distplane, qh_newfacetplane by 'Rn'
other changes
- Replace 'unsigned' with 'unsigned int', for consistency
- Replace warning 6263 with 7079 in qconvex_r.c, etc.
- Resolved C warnings for -Wsign-conversion, mostly type casts
Continue to use -Wno-sign-conversion for C++ due to countT, boolT, int vs. size_t mismatches
- Reviewed gcc 8.1.0 warnings. See Makefile CC_WARNINGS and CXX_WARNINGS
Type cast (int)sizeof(facetT),etc. as needed
- Reviewed error and warning codes for multiple instances of the same code
- Reviewed file references such as libqhull_r.c vs libqhull.c
- Reviewed multi-line, error message width for 80 column output
- global.c/qh_initflags: Add 'qh_QHpointer' to qh_option for option list
- geom2_r.c/qh_joggleinput: report QH6010, current joggle is too large, as qh_ERRinput
- geom2_r.c/qh_maxsimplex: report error if qh.MAXwidth not defined, for estimating the determinates
- geom2_r.c/qh_minmax: if tracing, log min and max coordinates [J.R. Roussel, D. Sterratt]
- io_r.c/qh_printbegin: rewrote warning QH7053, use 'p' or 'o' for Voronoi centers
- io_r.c/qh_produce_output2: fflush to maintain execution order of output
- libqhull_r.c/qh_buildtracing: change qh.lastfacets, qh.lastplanes, qh.lastdist to 'int'
- libqhull_r.c/qh_build_withrestart: change error QH6229, 101 attempts to joggle input, to qh_ERRinput and 51 attempts
- merge_r.c/qh_renameridgevertex: report error if old vertex not found
- poly_r.c/qh_update_vertexneighbors: use qh_setappend instead of qh_setunique for newly created facets (restores 2015.2 code)
- poly2_r.c/qh_check_point: limit 'Tv' errors to qh_MAXcheckpoint per facet
- poly2_r.c/qh_initialhull: rewrite QH6329 for cospherical input sites and add qh_printvertexlist [P. Celba]
- qset_r.c/qh_setlarger_quick: optimize qh_setlarger for quick memory
- rboxlib_r.c/qh_rboxpoints2: fix strncat to resolve -Wstringop-truncation warning [D. Sterratt]
increased command[] to 250 and decreased seedbuf[] to 50
- user_r.h/qh_JOGGLEmaxretry: reduced from 100 iterations to 50 iterations
- user_r.c/qh_new_qhull: allow "qhull" for the qhull_cmd parameter
- user_eg_r.c/findDelaunay: qh_findbestfacet returns the closest Delaunay triangle or an adjacent triangle
- user_eg2_r.c/findDelaunay: qh_findbestfacet returns the closest Delaunay triangle or an adjacent triangle
- userprintf_r.c/qh_fprintf: set qh.last_errcode for MSG_ERROR (6000) codes
- RboxPoints::qh_fprintf_rbox: print error message to stderr if cpp_object undefined
------------
Qhull 2019.0.1 2019/05/24 (7.3.1)
Qhull options
- Disallow unknown options and other option errors, allow option warnings with 'Qw'
- New option 'Qallow-short': allow input with fewer or more points than coordinates
- New option 'Qwarn-allow': allow option warnings
- New option 'TAn': stop after adding n vertices
- New option 'Tf': flush after qh_fprintf for debugging segfaults
- New experimental option 'Q14-merge-pinched-vertices': merge pinched vertices due to dupridge
Excessive merging leads to additional topological and wide facet errors
- New experimental option 'Q15-check-duplicates': check for duplicate ridges with the same vertices
- Option 'Q1' merges by mergetype/angle instead of mergetype/distance, coplanar merges first
In 2015.2 by default, Qhull merged by mergetype/angle with lower angles first
- Option 'TP-1' turns on tracing after qh_buildhull and qh_postmerge
It traces qh_check_maxout, qh_prepare_output, qh_triangulate, qh_voronoi_center
- Options '--help', '-?', and '--' display a short help message
Qhull does not support '--' options. Git for Windows v2.21.0 does not support isatty ('winpty qhull' is OK)
- Allow Qhull extra options Q12 and Q14 for qconvex/qdelaunay/qhalf/qvoronoi
- Allow option 'QRn' (random rotate) for qdelaunay/qhalf/qvoronoi
- Alphabetize short prompts (qhull .)
- Alphabetize long prompts w/ normal options first (qhull -)
- Alphabetize option help by option code
- Add 'Number of merged pinched vertices' to summary ('s')
- Add 'TI file' to help message for qconvex/qdelaunay/qhalf/qvoronoi
- Dropped experimental option 'Q16-simplex-merge'. Centrums are required for convexity
- Error if 'd', 'v', or 'Hn,n,n' are used together
- Ignore missing space after 'TI' or 'TO'. Allow 'TIinputfile' and 'TOoutputfile'
- Prefix option errors and warnings with 'qhull option error:' or 'qhull option warning:'
- Remove hidden option 'normals' from help prompts for qdelaunay, qhalf, qvoronoi
- Reword short prompts to 'Pdrop-d0:0D0', 'QbBound-0:0.5', and 'off_format'
- Updated qh-quick.htm, 'qhull -', and 'qhull .' for 'T...' and 'Q...' options.
Separate help prompts for 'T options' and 'Trace options'
- Use '-' instead of '_' for word delimiter in option names
Qhull builds, scripts, and debugging
- Add qh.traceridge, qh.traceridge_id, and qh_delridge for debugging by ridge in qh_fprintf
- Check for qhull with 'which qhull' instead of 'qhull', avoids hangs in git bash
- Makefile/CC_WARNINGS: Add instructions for collecting and testing gcc warnings
- Makefile/benchmark: Add q_benchmark, 10 runs of each
- Makefile/clean: Delete linked files from src/libqhull and src/libqhull_r, as in their Makefiles
- Makefile/help: Add 'make all' to 'make help' prompts
- Makefile/qhullx: Add test of testqset and testqset_r
- Makefile/qhullx: Create bin/ directory if missing
- Makefile/test: Add user_eg3 help prompt
- Makefile/testall: Add q_benchmark, 1 run of each
- eg/make-vcproj.sh/qhullx: Build bin/qhullx from src/qhullx/ for comparison
- eg/q_benchmark: new script for measuring Qhull precision and performance with qtest.sh
- eg/q_test: update error messages for missing bin/ and bin/libqhull_r.dll
- eg/q_test: tests of Tf and TAn
- eg/qhull-zip.sh: add note that it requires road-script.sh from http://www.qhull.org/road/
- eg/qhull-zip.sh: check source depencencies for prompts
- eg/qtest.sh: new script for testing Qhull and summarizing its trace files
- libqhull_r/Makefile: install target creates $INCDIR/libqhull_r and $LIBDIR
- libqhull_r.h/qh_ERRdebug: define error status for debugging exits
Qhull fixed bugs
- html/qh-optp.htm: options 'PDk' and 'Pdk' require option 'Pg' to return the closest facet
- Makefile/qhullx: fixed qhullx compile of testqset and testqset_r
- PointCoordinates.cpp/appendPoints: read 'in >> p' instead of 'in >> p >> ws'
otherwise istream fails if file does not end with whitespace
- geom_r.c/qh_findbesthorizon: fix test for Zfindjump (bestdist jumps by searchdist)
- geom_r.c/qh_findbesthorizon: increased minsearch of coplanar facets if ischeckmax and more than 100 neighbors
- geom_r.c/qh_sethyperplane_det: dropped precision statistic Znearlysingular (it's Zminnorm)
- geom2_r.c/qh_detjoggle: use 'En' (roundoff) if specified by options
- geom2_r.c/qh_distround: move adjustment for 'Rn' into qh_distround. 'QJn' did not account for 'Rn'
- global_r.c/qh_checkflags: handle two-digit Q options in hiddenflags
- global_r.c/qh_freebuild: do not delete unattached ridges, otherwise a double delete. Should not occur
- global_r.c/qh_option: fix potential overflow of qh.qhull_options
- global_r.c/qh_initflags: fixed incorrect indentation for option 'TO file'
- global_r.c/qh_initqhull_start2: set qh.NOerrexit True
- io_r.c/qh_eachvoronoi: allow fp==NULL for QhullQh::qh_fprintf to appendQhullMessage
- io_r.c/qh_readpoints: error if 'd' or 'v' with 'H', otherwise memory corruption
- libqhull_r.h/qh.MERGEvertices: fixed comment, 'Q3' disables this feature
- libqhull_r.c/qh_buildcone_onlygood: cannot qh_delfacet inside FORALLnew_facets
- libqhull_r.c/qh_partitionpoint: if qh.NARROWhull and bestdist>qh.MINoutside and isnewoutside,
may need to move facet to qh.newfacet_list for qh.next_facet
- libqhull_r.c/qh_printsummary: Zdistconvex is for checking convexity instead of testing convexity
- libqhull_r.c/qh_findhorizon: coplanar horizon if apex >= -qh.MAXcoplanar, instead of > -qh.MAXcoplanar
- mem_r.c/qh_memcheck: define null qh_memcheck if qh_NOmem
- merge_r.c/qh_mergecycle_all: turn on tracing, 'TMn', for coplanar horizon merge of one facet
- merge_r.c/qh_mergefacet2d: do not create ridges for neighborB. The opposite neighbor may be tested
- merge_r.c/qh_test_centrum_merge: coplanar if centrum >= -qh.centrum_radius, instead of > -qh.centrum_radius
- merge_r.c/qh_test_nonsimplicial_merge: coplanar if centrum >= -qh.centrum_radius, instead of > -qh.centrum_radius
- merge_r.c/qh_tracemerging: fixed "qhull has merged" prompt
- merge_r.c/qh_willdelete: empty f.neighbors and f.ridges, references are no longer valid, will be deleted
- poly_r.c/qh_checkflipped: flipped if qh.interior_point >= -qh.DISTround, instead of > -qh.DISTround
- poly2_r.c/qh_addfacetvertex: initialize vertex_i in case f.vertices is empty
- poly2_r.c/qh_check_maxout: need to include qh.DISTround when checking f.maxoutside with qh.maxoutside
- poly2_r.c/qh_checkconvex: fix documentation for qh_DATAfault. It is restricted to qh_initialhull with qh.ZEROcentrum
- poly2_r.c/qh_checkconvex: coplanar if >= -qh.DISTround, instead of > -qh.DISTround
- poly2_r.c/qh_checkconvex: check simplicial ridges if !qh.MERGING && qh.ZEROcentrum (unlikely or not-possible)
- poly2_r.c/qh_findgood: restrict qh.GOODvertex ('QVn') to good facets
- poly2_r.c/qh_findgood_all: unless 'Pg', ignore qh.GOODclosest for nearest facet to thresholds.
'PdD' reports 0 good facets
- poly2_r.c/qh_replacefacetvertex: initialize vertex_n in case f.vertices is empty
- qconvex.c,qdelaunay.c,etc.: remove automatic 'Qx' for 5-d and higher. Set by default in qh_initqhull_globals
- qvoronoi_r.c/qh_prompt: remove disabled option 'TRn' from help prompt
- random_r.c/qh_argv_to_command: fixed missing braces, same behavior as before
- rbox_r.c: return 0 exit status on prompt
- rboxlib.c/qh_rboxpoints: use qh_fprintf_stderr instead of qh_fprintf_rbox. Avoid qh_errexit_rbox
- rboxlib.c/qh_rboxpoints2: clear rbox_inuse on exit, as in error exit
- rboxlib_r.c/qh_rboxpoints2: incorrect string arg to 'rbox error: unknown flag'
- rboxlib_r.c/qh_rboxpoints2: remove superfluous qh_free(*simplex)
- stat_r.c/qh_initstatistics: due to NOerrors cannot use qh_fprintf, use qh_fprintf_stderr instead
- stat_r.c/qh_stddev: return sqrt of absolute value
- testqset_r.c: if qh_NOmem, do not call qh_memfreeshort
- user_eg_r.c,user_eg2_r.c: if qh_NOmem, call qh_freeqhull(qh, qh_ALL) instead of qh_memfreeshort
- user_eg3_r.cpp: return 0 exit status on prompt
Qhull fixed bugs introduced by 2018.0
- libqhull_r.c/qh_addpoint: clear qh.retry_addpoint on success
- libqhull_r.c/qh_buildcone_mergepinched: cannot qh_delfacet inside FORALLnew_facets
- libqhull_r.c/qh_partitioncoplanar: clear qh.repart_id on exit for infinite recursion detect
- geom2_4.c/qh_detmaxoutside: move qh_option call to qh_errexit
- merge_r.c/mergetypes[]: fixed order by mergeT
- merge_r.c/qh_all_vertexmerges: fix retryfacet for repeated calls
- merge_r.c/qh_forcedmerge: f.dupridge retained after MRGdupridge
hides MRGdegenerate in qh_test_degen_neighbors and qh_test_redundant_neighbors
- merge_r.c/qh_postmerge: call qh_freemergesets
- merge_r.c/qh_test_nonsimplicial_merge: clear iscoplanar if isconcave and any vertex is not coplanar
- poly2_r.c/qh_triangulate: move reset of f.degenerate into delete facet loop
Qhull C++
- QhullFacet.cpp: add hasNext() and hasPrevious()
- QhullVertex.cpp: add hasNext() and hasPrevious()
- qhulltest-64/QhullFacet_test.cpp,QhullVertex_test.cpp: test hasNext, hasPrevious, and hasPrevious iterator
- user_eg3.cpp: use 'qhull-cout' for option 'Tz' (trace to cout)
Qhull errors, warnings, and tracing
- Error messages rewritten and error codes changed (see qh_fprintf)
Renumbered Qhull warnings as 'QH7xxx' if needed (e.g., QH9375)
Reused unused error and message codes ("def counters" in user_r.h/msgcode)
Please check your code if it depends on error and message codes
- Initialize variables to avoid potential uninitialized warnings
- Use qh_ERRqhull for Qhull internal errors, "qhull internal error (qh_...): ..."
- Use 'defined()' for qh_QHpointer_dllimport and qh_dllimport (-Wundef)
- Use 'defined()' for __cplusplus, _MSC_VER, __MWERKS__, and __POWERPC__ (-Wundef)
- Use 'Early exit' instead of 'At a premature exit'
- libqhull_r.h/qh_ERRother: define error status for non-internal errors
- libqhull_r.h/qh_ERRtopology: define error status for qhull topology errors
- libqhull_r.h/qh_ERRwide: define error status for wide facets due to qhull precision error
- geom_r.c/qh_setfacetplane: add qh_printfacet if qh.tracefacet for qh.tracefacet_id
- global_r.c/qh_freebuild: record previousfacet/ridge/vertex in case a memory fault occurs
- global_r.c/qh_init_flags: improved error message for 'cannot open file' for 'TO f'
- global_r.c/qh_init_flags: improved warning message for 'unknown option'
- global_r.c/qh_initbuild: add trace options to "Trace level ..."
- global_r.c/qh_initqhull_globals: error if qh.VORONOI without qh.DELAUNAY
- global_r.c/qh_initqhull_globals: error if numpoints is <1 or >qh_POINTSmax (INT_MAX-16)
- global_r.c/qh_lib_check: use C-style comment for _CrtSetBreakAlloc
- io_r.c/qh_printfacetheader: add "max" if f.merges==qh_MAXnummerge (511)
- io_r.c/qh_readpoints: error if numinput is <1 or >qh_POINTSmax (INT_MAX-16)
- io_r.c/qh_readpoints: moved up 'chop' of qh.rbox_command to report short input errors
- io_r.c/qh_readpoints: replace warning QH7073 with error message. Override with Qallow-short
- libqhull_r.c/qh_addpoint: if 'T4', check qh.visible_list before qh_partitionvisible
- libqhull_r.c/qh_buildtracing: add delta cpu/facets/hyperplanes to QH1049 'qh_addpoint: add p%d...'
- merge_r.c/qh_findbest_pinchedvertex: replaced assert with a 'qhull internal error'
- merge_r.c/qh_check_dupridge: drop advice about reporting wide merges for error QH6271
- merge_r.c/qh_mark_dupridges: topological error if multiple dupridges for one facet, not handled
- merge_r.c/qh_test_nonsimplicial_merge: if Qx and many merges, replace centrum_radius with maxoutside
- poly_r.c/qh_matchneighbor: drop extra warnings for duplicate facet (QH7084)
- poly_r.c/qh_matchnewfacets: check for simplicial facets on qh.newfacet_list, otherwise memory overwrite by qh_matchneighbor
- poly2_r.c/qh_checkconvex: identify simplicial checking of vertices (qh.ZEROcentrum, default)
- poly2_r.c/qh_checkconvex: distinguish above from coplanar for non-convex initial simplex
- poly2_r.c/qh_checkconvex: "non-convex initial simplex" for qh_joggle_restart
- poly2_r.c/qh_checkfacet: check f.id and f.vertex_visit
- poly2_r.c/qh_checklists: check and repair facet and vertex lists for infinite loops or overwritten facets/vertices
- poly2_r.c/qh_checkpolygon: if qh.NEWfacets, check visible facets for empty f.neighbors and f.ridges
- poly2_r.c/qh_checkpolygon: add qh_checkvertex
- poly2_r.c/qh_checkpolygon: check f.previous and v.previous links (for C++)
- poly2_r.c/qh_checkvertex: add parameters for allchecks and waserror (like qh_checkfacet)
- poly2_r.c/qh_checkvertex: check v.id and v.vertex_visit
- qvoronoi.c/hidden_options: hide option 'FM'. Maple output is not available
- rboxlib_r.c/qh_rboxpoints: use QH6... for error codes instead of warnings
- stat_r.c/qh_stddev: check for division by 0
- testqset_r.c: send all messages, except 'OK' to stderr
- testqset_r.c: reassign unique QH8nnn codes, 8001/etc in use by libqhull_r
- user_r.c/qh_printhelp_internal: add descriptive message for a Qhull internal error
- user_r.c/qh_printhelp_narrowhull: add option 'Qs' (search all points)
- user_r.c/qh_printhelp_topology: add descriptive message for a Qhull topology error
- user_r.c/qh_printhelp_wide: add descriptive message for a wide merge error
- user_eg_r.c: add fflush and '=======' markers to interleave stdout with stderr (MSYS2)
- user_eg2_r.c: add fflush and '=======' markers to interleave stdout with stderr (MSYS2)
- user_eg2_r.c: add warning about calling qh_addpoint after qh_qhull with 'QJ' (joggle)
Qhull documentation and statistics
- Add Index to README.txt
- Add links to Wiki, http://github.com/qhull/qhull/wiki
- Add links to local home page (index.htm)
- Add GitHub, Scholar, and Code to navigation bar on home page
- Change numbered fixups to 'QH110nn FIX:' and renamed as MSG_FIX
- Chrome and Internet Explorer load '.c' and '.h' files as text/html from the Web
These browsers along with Firefox do not read disk files as text/html
Changed 'Functions' link from a local link to "http://www.qhull.org/src/libqhull_r/index.htm"
- Document implicit parameters at end of parameter list with '/* qh. ... */'
- Limit maximum length of literals to 1800 characters
- Move 'called by' comments to start of 'notes:'
- Option 'QRn' appends the actual QRn to the summary line ('s')
- Remove references to 'Qx' in 5-d and higher. It is automatically set by default.
- Replace references to 'src/libqhull/*.htm' with reentrant 'src/libqhull_r/*_r.htm'
- Retitle 'Qhull internals' as 'Qhull code'
- Use 'nearly adjacent vertices' instead of 'nearly coincident points'
- Use 'dupridge' instead of 'duplicate ridge' for ridges with more than two neighbors.
Reserve 'duplicate ridge' for two ridges with the same vertices.
- Various edits to documentation (*.htm)
- Update copyright to 2019
- eg/q_test: Add examples to q_test "front ends"
- html/index.htm: Add 'Limitations of merged facets' to the Qhull manual
- html/index.htm: Add links to qdelaun_f.htm and qvoroin_f.htm (furthest-site)
- html/qconvex.htm,etc: update synopsis and options
- html/qh-code.htm: Add 'qh_addpoint' trace to 'Performance of Qhull'
- html/qh-code.htm: Add a section on 'Debugging Qhull' with subsections for error codes,
infinite loops, trace options, core dumps, segfaults, qtest.sh, and memory errors.
- html/qh-impre.htm: Add 'Topological error' to 'Precision problems'
- html/qh-impre.htm: Add 'Topological errors' to 'Limitations of merged facets'
- html/qh-impre.htm: Add "narrow range of values" to 'Uneven dimensions'
- html/qh-optq.htm: Add note to 'QJ' (joggle) about calls to qh_addpoint
- html/qh-optt.htm#'Tc': 'T4' makes additional checks beyond check-frequently
- html/qhalf.htm: Split the first example to clarify the "feasible point" for qhalf
- html/qhalf.htm: Use 'feasible point' instead of 'interior point' for halfspace intersection
Same as Qhull::feasiblePoint and distinguished from qh.interior_point
- html/qhull.man,qhull.txt: updated man page
- libqhull_r.h: update documentation for PRINTgood, GOODpoint, GOODvertex
- qhull_ra.h: include '<limits.h>'. Used for INT_MAX,etc.
- stat.h: add zretryadd stats for qh_merge_pinchedvertices
- stat.h: add zvertextests for distance tests of vertices for merging
- libqhull_r/*: document global variables as 'qh.'
- libqhull_r/*: fix libqhull/... links
- libqhull_r.c/qh_partitioncoplanar: reword Zpartflip as Zpartcorner with updated messages
- merge_r.c/qh_merge_degenredundant: rename statistic Zneighbor to Zredundant
- stat_r.c: new or reworded statistics for Zpartcorner, Zparthidden, Zparttwisted, Zpinchduplicate, Zpinchedvertex
- stat_r.c: rename 'renamed vertex statistics' to 'statistics for vertex merges'
- stat_r.c: add merge statistics for MRGconcavecoplanar
- stat_r.c/qh_allstat: add ' ' before parens in statistics
- user_eg_r.c,user_eg2_r.c: rewrote prompt
Qhull changes
- For simple initializers, remove spaces (e.g., 'for (i=0; ...')
- Normalize spacing for libqhull
- Normalize spacing as 'for (i=0; ...' for simple initializers
- Review use of '>' for comparison to negative quantities. Usually should be '>=', e.g., for coplanar tests
- Reassigned 8xxx and 9xxx codes as trace codes if traced at T3 or lower
- Remove unused variables
- Test floating point values with 0.0 instead of 0 (qh.premerge_centrum,lower_bound,upper_bound)
- Use SETsecondt_() and SETelemt_() instead of SETelem_() when assigning to a specific type
- Use '(type *)' for pointer casts. It makes the cast more visible.
- Use void for empty parameter lists
- geom_r.c/qh_findbesthorizon: mark startfacet visited, avoids unnecessary visit
- geom2_r.c/qh_detmaxoutside: determine precision target qh.MAXoutside (option _maxoutside at error exit)
replaces 'maxoutside' computation
- geom2_r.c/qh_maxsimplex: add ratio test for false narrow hull with search for prevdet [J. Romain]
- global_r.c/qh_freebuild: free global sets first instead of last, otherwise dangling references
- io_r.c/qh_compare_nummerge: renamed qh_compare_facetmerge due to conflict with merge_r.h
- io_r.c/qh_compare_vertexpoint: remove this routine. Not usable in libqhull_r due to 'qh'
- io_r.c/qh_printfacetridges: do not print ridge if already printed (e.g., duplicate neighbors for merge of simplicial facets)
- io_r.c/qh_produce_output2: fflush of qh.fout to show statistics and verification after output (MSYS2)
- libqhull_r.h/qh.ALLOWwide: rename qh.NOwide to qh.ALLOWwide for 'Q12-allow-wide'
- libqhull_r.h/qh.IGNOREpinched: replaced qh.MERGEpinched with reversed meaning
- libqhull_r.c/qh_addpoint: 'TVn' stops after qh_all_vertexmerges, not before qh_resetlists. Matches documentation
- merge_r.h/MRGdupridge: renamed MRGridge
- merge_r.h/qh_ANGLEconcave,etc.: replace mergetype indicators with qh_ANGLEnone and m.mergetype
- merge_r.c/qh_all_vertexmerges: replace qh_getmergeset_initial with qh_getmergeset. No facets created
- merge_r.c/qh_all_vertexmerges: move while loop into qh_all_vertexmerges
- merge_r.c/qh_append_mergeset: ignore merges into a MRGdegen facet (f.degenerate)
- merge_r.c/qh_buildcone_mergepinched: clean up code and design documentation
- merge_r.c/qh_compare_anglemerge: renamed qh_compareangle and sort by mergetype as well as angle
- merge_r.c/qh_compare_facetmerge: merge MRGcoplanar before MRGconcave, opposite order from 2015.2
sort MRGanglecoplanar by angle
- merge_r.c/qh_degen_redundant_facet,qh_test_degen_neighbors: moved into qh_mergefacet due to qh_willdelete
- merge_r.c/qh_getmergeset,qh_getmergeset_initial: set f.tested after testing ridges, not before
- merge_r.c/qh_next_facetmerge: split out next merge from qh_all_merges and replace qsort
- merge_r.c/qh_findbest_pinchedvertex,qh_findbest_ridgevertex: dropped selecting merge direction via qh_vertex_isbelow. Expensive and evidence mixed
- merge_r.c/qh_freemergesets,qh_initmergesets: pair qh_initmergesets with qh_freemergesets
- merge_r.c/qh_freemergesets,qh_initmergesets: drop the 'all' parameter
- merge_r.c/qh_mergecycle_all: move qh_merge_degenredundant, etc. to end from qh_premerge
- merge_r.c/qh_mergesimplex: delete facet1 from facet2.neighbors at end, not at ridge
- merge_r.c/qh_post_merges,qh_all_merges: remove setting of v.delridge on all vertices, not needed
- merge_r.c/qh_premerge: replace parameter 'apex' with 'apexpointid'. Only used for logging
- merge_r.c/qh_premerge: add qh.newfacet_list as an implicit parameter
- merge_r.c/qh_test_degen_neighbors: split from qh_degen_redundant_neighbors and qh_mergefacet
- merge_r.c/qh_test_redundant_neighbors: split from qh_degen_redundant_neighbors and qh_mergefacet
- poly_r.c/qh_attachnewfacets: clear f.neighbors and f.ridges for visible facets, will be deleted
- poly_r.c/qh_matchnewfacets: remove call to qh_checkflipped_all for qh.FORCEoutput, checked by qh_setfacetplane
- poly_r.c/qh_update_vertexneighbors: renamed qh_updatevertices. A future version will optimize
qh_update_vertexneighbors_cone: optimization for cone of new facets
- poly2_r.c/qh_checkconvex: immediate skip of f.tricoplanar facets. Tricoplanar facets not tested. Called before qh_triangulate
- poly2_r.c/qh_initbuild: move 'create sentinels' before qh_createsimplex so that qh.vertex_tail is v0 like f0
- poly2_r.c/qh_initialvertices: cleaned up code for qh_INITIALmax (8-d)
- poly2_r.c/qh_makenewfacets: clear f.neighbors and f.ridges for visible facets, will be deleted
- poly2_r.c/qh_matchdupridge: optimize dupridge for flipped->!flipped, good merge, not !flipped->flipped
- poly2_r.c/qh_matchdupridge_coplanarhorizon: dropped routine. Results same or slightly worse. Complex addition, rarely used
- poly2_r.c/qh_triangulate: rename facet and vertex lists as triangulated_facet_list,etc.
qh_triangulate does not maintain qh.newfacet_list or qh.visible_list
- poly2_r.c/qh_triangulate: ignore qh.NEWfacets. qh_checkpolygon is not valid inside qh_triangulate
- rboxlib_r.c/qh_rboxpoints2: split function from qh_rboxpoints to avoid -Wclobbered
- stat_r.c/qh_printstatlevel: remove unused NULLfield
Qhull C++ changes
- Use NULL instead of 0 for pointers
- Remove old style casts such as '(size_t)...'
- Define initializers for default constructors even if explicitly assigned
- Update static initializer list for s_empty_facet, s_empty_ridge, s_empty_vertex
- Coordinates.h: default constructor clears coordinate_array
- Coordinates.h: default iterator constructor clears i
- RboxPoints.cpp/qh_fprintf_rbox: add empty default to switch statement
------------
Qhull 2018.0.1 2018/12/28 (7.3.0)
Qhull options
- If unknown option, report error QH6035 instead of warning QH7035. Override with Qw
- Add option 'Tf' to flush each qh_fprintf for debugging segfaults
- Add Q14-ignore-pinched-vertices: ignore pinched vertices due to dupridge
Default if post-merge only ('Cn'), 'Qgood-only', or 2-d convex hulls
- Expand Q12-allow-wide to include wide facet errors reported by qh_check_maxout and qh_merge_facet
- Add Q16-simplex-merge: test opposite vertex instead of centrum for merges
- option 'f' (print facets): updated flags for facets
'seen' and 'seen2' flags not listed (listed if tracing)
Renamed 'new' to 'newfacet'
'isarea' if area is listed for the facet
'cycledone' if qh_mergefacet completed
Renamed 'MERGE' to 'MERGEridge' in the facet neighors (for merging)
Renamed 'DUP' to 'DUPLICATEridge' in the facet neighors (for merging)
Comment '- horizon ridge to visible facet' added for tentative new facets
- option 'f' (print facets): updated flags for ridges
'mergevertex' and 'mergevertex2' if a ridge vertex will be merged
'simplicialtop' and 'simplicialbot' if the top/bottom facet is simplicial
- option 'f' (print facets): updated flags for vertices
Renamed 'ridgedeleted' to 'delridge'
'newfacet' if the vertex belongs to a new facet on qh.newfacet_list
'seen' and 'seen2' listed if tracing
- Option 'T3' prepend message number for trace levels 0-3
e.g., "[QH1040]qh_findhorizon: find horizon..."
- Option 'TCone_stop' stops before vertex merge due to duplicate ridges (unlikely)
- Option 'Ts' (qh_initbuild): print command prompt at start of run for segfaults
- Rename option 'U-coplanar-distance' to 'U-max-coplanar' (qh.MAXcoplanar)
Qhull documentation
- Explanation of clobbered warning for Qhull::runQhull and qh_new_qhull
- html/index.htm: Add "Nearly coincident points" to "When to use Qhull"
- html/index.htm: Add Tomilov's qhullhull.hpp for general position input.
- html/qh-eg.htm: Add 'Q0' link to eg.14.sphere.corner
- html/qh-faq.htm,qh-code.htm: merge slivers in a Delaunay triangulation [M. Treacy]
- html/qh-optq.htm: Update documentation for 'Qx' and its default behavior
- html/qh-impre.htm: Rewrote notes on 'Nearly coincident points within 1e-13'
- geom_r.c/qh_distplane: nearly coplanar points may return the same distance for different points
Qhull builds
- Move 'extern "C" {}' logic from C++ to C headers [C. Atkins, nine7nine, W. Scullin, M. Culpo]
- build/*-64.vcxproj Updated for tool set 8.1
- CMakeLists.txt: Add note for "dynamic linking" of qhull executables [M. Atzeri]
- CMakeLists.txt: Revert accidental commit cea6d22 [pchilds, QuLogic, fabiencastan, daniel-packard]
Bugs fixed
- html/*.htm: fix trailing </a></br> after 'Comments to:'
- libqulll_r.c/qh_findbest: search from newfacet_list instead of f.next if !bestfacet
- merge_r.c/qh_find_newvertex: use v.seen to avoid maxvisit > qh.vertex_visit
- merge_r.c/qh_merge_simplex: repeat with next ridge after qh_delridge_merge
- merge_r.c/qh_vertexridges: 'qh.visit_id += 2' to avoid visit_id collision
- poly_r.c/qh_appendfacet: update qh.visible_list if qh.newfacet_list/visible_list are empty
- poly2_r.c/qh_check_maxout: check qh.min_vertex if qh.VERIFYoutput/CHECKfrequently
- poly2_r.c/qh_checkpolygon: do not report qh.visible_list error if visible_list and newfacet_list are defined but empty
- Qhull.cpp/outputQhull: do not call qh_check_points if qh.FORCEoutput
- stat_r.c/qh_printallstatistics,qh_printstatistics: 'const char *string' instead of 'char *string' for !qh_KEEPstatistics
- user_r.c/qh_new_qhull: do not call qh_check_points if qh.FORCEoutput
- user_eg2.c: do not call qh_check_points if qh.FORCEoutput
Qhull error reporting
- io_r.c/qh_readpoints: improved formating of error "QH6410 ... instead of n points"
- libqulll_r.c/qh_findhorizon: error if no neighbors for a visible facet
- libqulll_r.c/qh_findbestnew: error if facet sentinel (!facet->next)
- libqhull_r.c/qh_nextfurthest: error if infinite loop
- libqhull_r.c/qh_partitioncoplanar: error if partition into a visible facet
- libqhull_r.c/qh_partitionpoint: error if partition into a visible facet
- libqhull_r.c/qh_partitionvisible: error if deleted vertex with an empty qh.newfacet_list
- libqulll_r.c/qh_printsummary: if qh.ERREXITcalled and qh.DELAUNAY, update f.good and qh.num_good (qh_findgood_all)
- merge_r.c/qh_checkdelfacet: check that mergeset does not reference facet
- merge_r.c/qh_checkdelridge: check that qh_delridge_merge is not needed for deleted ridges
Call from qh_mergecycle, qh_makenewfacets, qh_attachnewfacets
- merge_r.c/qh_maydropneighbor: error if simplicial facet or neighbor
- merge_r.c/qh_merge_facet: error if wide merge (allow with 'Q12')
- merge_r.c/qh_merge_nonconvex: error if unexected mergetype
- poly_r.c/qh_matchneighbor: convert error QH6106 (two facets with same vertices) to a warning (QH7084) and automatic fix
- poly2_r.c/qh_check_maxout: error if wide qh.max_outside/min_vertex (allow with 'Q12')
- poly2_r.c/qh_check_maxout: warn if wide maxout for vertices (for diagnosing errors)
- poly2_r.c/qh_check_maxout: warn if point is outside f.outside (for diagnosing errors)
- poly2_r.c/qh_check_maxout: warn if 'f.maxoutside > qh.max_outside'
- poly2_r.c/qh_check_maxout: changed comparison from 'dist==maxoutside' to 'dist >= maxoutside' (allow multiple warnings)
- poly2_r.c/qh_checkfacet: error if 'redundant' or 'degenerate', but neither 'visible' nor qh.degen_mergeset
- poly2_r.c/qh_checkfacet: error if 'dupridge' or 'newmerge', but not 'newfacet'
- poly2_r.c/qh_checkfacet: error if neighbor of facet is 'visible' (i.e., deleted)
- poly2_r.c/qh_checkfacet: report 'Repaired by qh_remove_extravertices' as trace4 (QH4025) instead of error QH6134
- poly2_r.c/qh_checkpolygon: error if qh.visible_list is after qh.newfacet_list
- poly2_r.c/qh_checkpolygon: error if f.newfacet before qh.visible_list or qh.newfacet_list
- poly2_r.c/qh_checkpolygon: error if qh.newfacet_list without f.newfacet
- poly2_r.c/qh_checkpolygon: error if f.visible not on qh.visible_list
- poly2_r.c/qh_checkpolygon: error if qh.visible_list without f.visible
- poly2_r.c/qh_checkpolygon: error if qh.newfacet_list is not on qh.facet_list
- poly2_r.c/qh_checkpolygon: error if v.newfacet not on qh.newvertex_list
- poly2_r.c/qh_checkpolygon: error if qh.newvertex_list is not on qh.vertex_list
- poly2_r.c/qh_checkpolygon: error if a facet occurs twice in v.neighbors
- poly2_r.c/qh_checkpolygon: error if vertex not in f.vertices for facets in v.neighbors
- poly2_r.c/qh_checkpolygon: error if facet not in v.neighbors for vertices in f.vertices
- poly2_r.c/qh_delvertex: error if vertex previously deleted but not partitioned as a coplanar point
- user_r.c/qh_errexit: clear printed flags on statistics (qh_allstatistics)
- user_r.c/qh_errprint: print vertex and ridge before facets
- user_r.c/qh_printfacetlist: add 'qh_printfacetlist:' for rapid navigation
Source code additions
- mergeT: expanded for vertices and ridges
- mergeType: add MRGconcavecoplanar, MRGtwisted, MRGsubridge, MRGvertices, and MRGcoplanarhorizon
- qtT.FLUSHprint: true if 'Tf', flush output on qh_fprintf
- qtT.MERGEpinched: false if 'Q14', merge pinched vertex due to duplicate ridge
- qtT.SIMPLEXmerge: true if 'Q16', test_appendmerge tests opposite vertex instead of centrum
- qtT.first_newfacet: id of first new facet in qh_buildcone, other new facets were merged
- qtT.isRenameVertex: true during qh_merge_pinchedvertices
- qtT.NEWtentative: true while new facets are tentative due to qh.MERGEpinched or ONLYgood
- qtT.repart_facetid: previous facetid to prevent recursive qh_partitioncoplanar
- qtT.retry_addpoint: number of retries of qh_addpoint due to qh.MERGEpinched
- qtT.vertex_mergeset: set of vertex merges for qh_next_vertexmerge
- ridgeT.mergevertex and mergevertex2 if a ridge vertex will be merged
- ridgeT.simplicialtop and simplicialbot if the top/bottom facet is simplicial
- vertexT.partitioned: true if deleted vertex partitioned by qh_partitionvisible
- geom2_r.c/qh_furthestnewvertex: return furthest unvisited, new vertex to a facet
- geom2_r.c/qh_furthestvertex: return furthest unvisited vertex to a facet
- geom2_r.c/qh_vertex_bestdist: return nearest distance between vertices
- geom2_r.c/qh_vertex_bestdist2: return nearest vertex pair between vertices
- geom2_r.c/qh_vertex_isbelow: test vertexA distance to vertexB's simplicial facets and vice versa
- libqhull_r.c/qh_buildcone: split out qh_makenewfacets,etc. from qh_addpoint
- merge_r.c/qh_all_vertexmerges: perform vertex merges in qh.vertex_mergeset
- merge_r.c/qh_appendvertexmerge: append vertex merge to qh.vertex_mergeset
- merge_r.c/qh_delridge_merge: split out ridge maintenance from qh_renameridgevertex and qh_merge_simplex
- merge_r.c/qh_hasmerge: True if mergeset has mergetype for facetA and facetB
- merge_r.c/qh_initmergesets,qh_freemergesets: init/free of qh.*_mergeset with error reporting
- merge_r.c/qh_maybe_duplicateridge: add MRGvertices if neighboring facet has another ridge with the same vertices
- merge_r.c/qh_maybe_duplicateridges: add MRGvertices if ridges with the same vertices
- merge_r.c/qh_merge_dupridges: split out conversion of dupridges to MRGridge merges from qh_makeridges
- merge_r.c/qh_merge_pinchedvertices- merge pinched vertices in qh.vertex_mergeset to avoid qh_forcedmerges of duplicated ridges
- merge_r.c/qh_merge_twisted: merge twisted facets that are above and below their neighbors (4D+ and non-simplicial)
- merge_r.c/qh_neighbor_vertices,qh_neighbor_vertices_facet: return neighboring vertices for a vertex (not in subridge)
- merge_r.c/qh_next_vertexmerge: select next vertex merge by distance, allow one MRGsubridge merge
- merge_r.c/qh_opposite_horizonfacet: return horizon facet for a merge facet and its opposite vertex
- merge_r.c/qh_reducevertices: qh_merge_degenredundant if qh_remove_extravertices or qh_rename_sharedvertex
- merge_r.c/qh_remove_mergetype: remove mergetype merges from mergeset
- merge_r.c/qh_rename_adjacentvertex: rename oldvertex as newvertex, must be adjacent (i.e., in the same subridge)
- merge_r.c/qh_test_cemtrum_merge: split out test centrum convexity from qh_test_appendmerge
- merge_r.c/qh_test_nonsimplicial_merge: test nonsimplicial convexity and append non-convex facets to qh.facet_mergeset
- merge_r.h/FOREACHmergeA_,FOREACHmerge_i_: add macros for mergeset iteration
- poly_r.c/qh_getreplacement: split out new facet for visible facet from qh_partitionvisible and qh_merge_degenredunant
- poly2_r.c/qh_addfacetvertex: split out add newvertex to f.vertices if not already there from qh_merge_simplex
- poly2_r.c/qh_matchdupridge_coplanarhorizon: match duplicate ridges with the same coplanar horizon, instead of qh_matchdupridge
- poly2_r.c/qh_opposite_vertex: return the opposite vertex in facetA to neighbor
- poly2_r.c/qh_replacefacetvertex: replace oldvertex with newvertex in f.vertices
- user_r.h/qh_RATIOconcavehorizon: ratio of horizon vertex distance to qh.max_outside for concave, twisted new facets in qh_test_nonsimplicial_merge
- user_r.h/qh_RATIOconvexmerge: ratio of vertex distance to qh.min_vertex for clearly convex new facets in qh_test_nonsimplicial_merge
- user_r.h/qh_RATIOcoplanarapex: ratio of best distance for coplanar apex vs. vertex merge in qh_getpinchedmerges
- user_r.h/qh_RATIOcoplanaroutside: ratio to repartition a coplanar point as an outside point in qh_partitioncoplanar and qh_check_maxout
- user_r.h/qh_RATIOpinchedsubridge: ratio to qh.ONEmerge to accept vertices in qh_findbest_pinchedvertex
- user_r.h/qh_RATIOtrypinched: ratio to qh.ONEmerge to merge twisted facets in qh_merge_twisted
- user_r.h/qh_RATIOtwisted: maximum ratio to qh.ONEmerge to merge twisted facets in qh_merge_twisted
- user_r.h/qh_WIDEmaxoutside: precision ratio for maximum increase for qh.max_outside in qh_check_maxout
- user_r.h/qh_WIDEmaxoutside2: precision ratio for maximum qh.max_outside in qh_check_maxout
- user_r.h/qh_WIDEpinched: merge ratio for distance between pinched vertices compared to current facet width for qh_getpinchedmerges and qh_next_vertexmerge
Source code changes
- Change " = " to "= " (avoid confusion with "==")
- Improved tracing and code comments throughout
- Moved qh_check_dupridge from poly2_r.c to merge_r.c. It is used for merging
- Removed qh_compareangle and qh_comparemerge. Replaced by qh_next_facetmerge
- Renamed 'qh_precision' to 'qh_joggle_restart'. It restarts qhull to avoid a precision error.
- Renamed 'Qhull internal error' to 'qhull internal error' for consistency
- Renamed mergeT.type to mergetype. Same as parameters and local variables
- Renamed vertexT.newlist to newfacet. True if on a new facet
- Renamed qh_matchduplicates to qh_matchdupridge (poly2_r.c). A 'duplicates' is ridges with duplicate vertices
- Use coordT for distances instead of realT. Needs further review.
- qh_NOmerge: include comments in #ifndef
- global_r.c/qh_freebuffers: use the same order as qh_initbuffers
- global_r.c/qh_freebuild: free the global sets, qh.degen_mergeset,etc.
- io_r.c/qh_printfacetheader: print 'MERGEridge' instead of 'MERGE' to match name of flag
- io_r.c/qh_printfacetheader: print 'DUPLICATEridge' instead of 'DUP' to match name of flag
- libqhull_r.c/qh_partitioncoplanar: change qh.findbestnew to a parameter (search all new facets)
- libqhull_r.c/qh_partitioncoplanar: repartition a coplanar point if far outside
typically due to a twisted facet in D4+ with almost coincident vertices
- libqhull_r.c/qh_partitionpoint: if outside set is empty, set f.newfacet and adjust qh.facet_next
- libqhull_r.c/qh_partitionvisible: prevent duplicate partitions of deleted vertices
- libqhull_r.c/qh_partitionvisible: test against !f.next instead of qh.facet_tail. Both indicate sentinel
- mrege_r.h/mergeType: reordered mergetypes is preference order
- merge_r.c: identify MRGconcavecoplanar facets that are above and coplanar with their neighbors
- merge_r.c/mergetypes: string names for mergeType
- merge_r.c/qh_all_merges: clear wasmerge and othermerge on qh_reducevertices. Avoids extra calls
- merge_r.c/qh_appendmergeset: add parameters for m.dist and m.angle
- merge_r.c/qh_appendmergeset: initialize all fields of mergeT
- merge_r.c/qh_copynonconvex: clear old r.nonconvex for consistency. Ridge will be deleted soon
- merge_r.c/qh_degen_redundant_neighbors: check neighbors of delfacet instead of facet. Faster and it matches definition
- merge_r.c/qh_mark_dupridges: add 'allmerges' parameter for dupridges vs. pinched vertices
- merge_r.c/qh_mark_dupridges: test for duplicate vertices to avoid duplicate MRGridge
- merge_r.c/qh_merge_cycle_all: test for duplicate ridges at end of merge_cycle_all (qh_maybe_duplicateridges)
- merge_r.c/qh_merge_dupridges: clear mergeridge/mergeridge2 flags (not needed on first call)
- merge_r.c/qh_merge_facet: test for qh_degen_redundant_facet and qh_maybe_duplicateridges
- merge_r.c/qh_merge_facet: add mergeType parameter for logging
- merge_r.c/qh_merge_facet: rename 'apex' to 'opposite' (not always apex)
- merge_r.c/qh_merge_simplex: identify 'isnew' instead of 'issame' (more accurate)
- merge_r.c/qh_remove_extravertices: skip for simplicial facets
- merge_r.c/qh_renamevertex: test qh_maybe_duplicateridge if qh_renameridgevertex
- merge_r.c/qh_renamevertex: test qh_degen_redundant_facet for oldvertex neighbors
- merge_r.c/qh_renamevertex: test qh_degen_redundant_neighbors for oldvertex nonsimplicial neighbors
- merge_r.c/qh_renamevertex: test qh_maybe_duplicateridge if qh_renameridgevertex
- merge_r.c/qh_renamevertex: test qh_degen_redundant_facet oldfacet
- merge_r.c/qh_tracemerge: add mergeType parameter for logging
- merge_r.c/qh_test_appendmerge: calls qh_test_centrum_merge or qh_test_nonsimplicial_merge as needed
- merge_r.c/qh_vertexridges: add 'allneighbors' parameter to test all neighbors of a vertex
- merge_r.c/qh_vertexridges_facet: optimize qh_setin by common cases
- poly_r.c/qh_checkflipped: move call from qh_matchnewfacets to qh_setfacetplane. Allow call of qh_setfacetplane from qh_initialhull to reverse orientation
- poly_r.c/qh_matchneighbor: call qh_setfacetplane/qh_checkflipped on-demand to support qh.NEWtentative
- poly_r.c/qh_matchnewfacets: returns maxdupdist for duplicate ridges
- poly_r.c/qh_matchnewfacets: move qh_joggle_restart from qh_matchduplicates ("ridge with multiple neighbors")
- poly_r.c/qh_matchnewfacets: try to match ridges with coplanar horizon (qh_matchdupridge_coplanarhorizon)
- poly_r.c/qh_update_vertexneighbors: use qh_setunique to pdate vertex neighbors (due to pinched vertex merge)
- poly2_r.c/qh_checkfacet: optimize qh_setequal of ridges with the same vertices
- poly2_r.c/qh_checkpolygon: do not include visible facets in totvertices
- poly2_r.c/qh_initialhull: use f.flipped instead of qh_distplane/qh_checkflipped (qh_checkflipped called from qh_setfacetplane)
- poly2_r.c/qh_matchdupridge: was qh_matchduplicates in qhull 2015.2
- poly2_r.c/qh_matchdupridge: detect duplicate facets/ridges and force vertex merge
- poly2_r.c/qh_matchdupridge: separate code for qh_DUPLICATEridge/f.tricoplanar for improved logging
- poly2_r.c/qh_matchdupridge: if !makematch, collect best match via flipped and qh_getdistance between facets
- poly2_r.c/qh_resetlists: clear f.dupridge
- poly2_r.c/qh_triangulate: clear f.degenerate at end (degenerate tricoplanar facets)
- poly2_r.c/qh_triangulate_link: skip duplicate MRGmirror merges
- poly2_r.c/qh_triangulate_mirror: skip duplicate MRGmirror merges and previously deleted MRGmirror facets
------------
Qhull github 2018
- Fixed confusing indentation [A. Lee 2018/12/28]
- Add labels for each release [A. Mailaga 2016/7/5]
- Add 'typename qualifier to QhullSet [D. Gomes 2016/6/16]
- Make C headers safe for C++ inclusion [C. Atkins 2016/01/20]
- build/qhull*.pc.in: Removed templates for pkg-config (not updated for Qhull 2015)
=============
== Qhull 2015
=============
------------
Qhull 2015.2 2016/01/18 (7.2.0)
- Fixed memory leak in ~QhullQh [M. Sandim]
QhullQh.cpp: call checkAndFreeQhullMemory() in the destructor. Otherwise memT is not freed.
Remove checkAndFreeQhullMemory() from Qhull.h. It is not needed.
Remove calls to checkAndFreeQhullMemory in qhulltest. It is called by ~QhullQh()
libqhull_r.h: Document qh_ASvornoi and facetT.center
qh_freeqhull: if qh_NOmem, use qh_ALL
qh_memalloc: short memory is freed by qh_memfreeshort unless qh_NOmem
qh_memstatistics (mem.c): call qh_memcheck() as done in mem_r.c
qh_new_qhull calls qh_memcheck
qh_newvertex: free vertex on error
qh_projectinput: Free memory allocations on error
qh_rboxpoints: free simplex on error
qh_sethalfspace_all: Fixed memory leak on error QH8032 feasible not inside halfspace
qh_triangulate_facet: For TRInormals ('Q11') replace qh_copypoints with qh_memalloc
qh_triangulate_facet: Document qh.TRInormals
qh_voronoi_center: Free center on error
qhulltest: Fixed memory leak of s_testcases by calling RoadTest::deleteTests()
qhulltest: The 'add_*_test' functions append the test object to RoadTest::s_testcases
~RoadTest: declare virtual for Q_OBJECT, removeAll not needed
user_eg2: Check memory at end of each run
user_r.h: Add QHULL_CRTDBG for invoking Microsoft's memory leak detector
use _MSC_VER instead of QHULL_OS_WIN for QHULL_CRTDBG
Call qh_freeqhull with qh_ALL/!qh_ALL instead of 'True/False'
Include user_r.h with RoadError,h for QHULL_CRTDBG
Invoke _CrtSetDbgFlag... at beginning of program
Moved user_r.h/libqhull_r.h/qhull_ra.h as first include (for QHULL_CRTDBG)
Moved QHULL_OS_WIN from qhull_ra.h to user_r.h
Removed __CYGWIN__ from QHULL_OS_WIN (same as Qt's qglobal.h)
- check_dupridge: A bounding box is not sufficient to avoid dupridge errors
- qh_findbestneighor: Error if qh.CENTERtype is qh_ASvoronoi (i.e., no merging now)
- qh_printstatlevel: Remove unused parameter, 'start'
- QhullLinkedList::last() and back(): Return T instead of T& (T is computed)
- qh-code.htm: "How to convert code to reentrant Qhull"
Update "Nearly coincident points on an edge"
Add 2012 size of data structures to "Qhull on 64-bit computers"
- html/index.htm: Add CGAL to "When to use"
- qh-optq.htm: Add documentation for option 'Q12'
- Move suggestions from Changes.txt to qh-code.htm#enhance
- user_r.h: Fixed qh-us_r.html links
- Fixed links in html pages
- QhullIterator and QhullLinkedList: Include <iterator> [B. Boeckel]
- Moved include file for each C++ source file to the top of the includes
- Prepend cpp includes with "libqhullcpp/"
- RoadLogEvent includes RoadLogEvent.h
- QhullIterator.h: Only QHULL_DECLARE_SEQUENTIAL_ITERATOR is used.
- Compared src/libqhull/* to src/libqhull_r/* and resolved differences
- qh_printpoint in io.c skips qh_IDnone like io_r.c
- qhull_p-exports.def: Added three missing exports
- set_r.h: Removed countT. Too many issues
- libqhull_r/Makefile: Add help prompts to 'make qtest'
- libqhull.pro: Add '../libqhull/' to sources and headers
- libqhull/Makefile: Fixed -I,./,,/src
- qhull-zip.sh: Add CMakeModules to tarball [C. Rosenvik]
- CMakeLists.txt: Add targets qhullp and user_egp for qh_QHpointer and libqhull_p
- Reorganized 'make help'
- Makefile cleanall: Delete testqset and qhulltest from bin/
- Fix filetype of Unix-only files
- Fix Unix line endings for Makefile and check in qhull-zip.sh
- Fix Windows line-endings and check in qhull-zip.sh
- qhull-zip.sh: Check for Unix text files
------------
Qhull 2015.1 2016/01/03 (7.1.0)
- Add Rbox option 'Cn,r,m' to add nearly coincident points. Trigger for duplicate ridges
- Add Qhull option 'Q12' to allow wide merge due to a dupridge
- qh_findbestlower: Call qh_findfacet_all to fix rare "flipped or upper Delaunay" error QH6228 (now QH3025)
QH6228 input provided by J. Metz. Reported (date order): L. Fiaschi, N. Bowler, A. Liebscher, V. Vieira, N. Rhinehart, N. Vance, P. Shafer
- qh_check_dupridge: Check if wide merge due to duplicate ridge from nearly coincident points
- qh_initialhull: Fix error messages for initial simplex is flat
- qh_determinant: increased 2-d and 3-d nearzero by 10x due to a counter-example
- rbox: Add qh_outcoord() to output coordinates w/ or w/o iscdd
- qh_meminit (mem.c): Add call to qh_memcheck
- Compare libqhull/... to libqhull_r/... and resolve differences
- Update builds for DevStudio (qhull.sln for msdev 2005..2009, qhull-32.sln and qhull-64.sln for recent releases)
- qh-impre.htm: Add a section about precision errors for 'Nearly coincident points on an edge'
- html/index.htm#geomview: Document how to install, build, and use Geomview.
- html/index.htm: Emphasize program links and move related urls to end
- qhull/index.htm: Emphasize manual, geomview, and imprecision
- Fix documentation links in libqhull_r/index.htm
- Add 'Functions' link to documentation headers
- Change '<A>...</A>' to '<a>...</a>'
- libqhull_r/index.htm -- Add instructions for configuring web browsers for source links.
- libqhull_r/ -- Fix source links for ..._r.htm files
------------
Qhull 2015.0.7 2015/11/09 (7.0.7)
- Fix return type of operator-> in QhullLinkedList and other collection classes [F. Jares]
- Fix return types for QhullLinkedList
- Fix return types for QhullPoints
- Simplify return type for Coordinates::operator[] (same as QList)
- Add const to operators for QhullSet::iterator and add documentation
- Coordinates.h: Fix return types for operations of iterator and const_iterator
- Drop use of Perforce changelist number in qhull_VERSION of CMakeLists.txt
- Rename the md5sum files as *.tgz.md5sum instead of *-tgz.md5sum
- Fix build dependency for testqset_r [asekez]
- rbox.c depends on Qhull due to qh_lib_check which uses qh_version2 for error messages
- QhullFacet_test.cpp: Annotate Qhull invocations. Allows their repetition.
- QhullFacet_test.cpp: Adjust epsilon on distance tests
- Do not create libqhullcpp as a shared library. Qhull C++ classes may change layout and size.
- qhull-cpp.xml: Make a relative path to road-faq.xsl
------------
Qhull 2015.0.6 2015/10/20 (7.0.6.2013)
- In the libraries, exit() is only called from qh_exit(). qh_exit may be redefined.
- Add qh_fprintf_stderr to usermem.c. May be overridden to avoid use of stderr [D. Sterratt]
Add usermem to testqset builds
Used by qh_fprintf_rbox
- Remove most instances of stderr/stdout from libqhull, libqhull_r, and libqhullcpp [D. Sterratt]
qh_fprintf_stderr may be redefined. qh_meminit and qh_new_qhull use stderr as the default ferr
- qh_initflags: Use qh.fout instead of stdout for 'TO file'. A library caller may define a different qh.fout.
- qh_settemppush: Call qh_fprintf() instead of fprintf() on error.
- Rename qh_call_qhull as "Qhull-template" from user.c. Updated its references.
- qh-code.htm: "How to avoid</a> exit(), fprintf(), stderr, and stdout"
- html/index.htm: Fix table of contents for qh-code
- libqhull_r/index.htm: Rewrite introduction to Reentrant Qhull
- qh-faq.htm: Rewrite "Can Qhull use coordinates without placing them in a data file?"
- qh-get.html: Link to github
- Remove qhull_interface.cpp from the documentation
------------
Qhull 2015.0.5 2015/10/12 (7.0.5.1995)
- qh_new_qhull: default 'errfile' is 'stderr'. outfile and errfile are optional [B. Pearlmutter]
- qh_new_qhull: returns qh_ERRinput instead of exit() if qhull_cmd is not "qhull ..." [B. Pearlmutter]
- qhalf_r.c,etc: Add clear of qh.NOerrexit
- global.c: gcc 4.4.0 mingw32 segfault cleared by adding comment
- usermem_r-cpp.cpp: Optional file to redefine qh_exit() as throw "QH10003.." [B. Pearlmutter]
qh_exit() is called by qhull_r when qh_errexit() is not available.
- html/index.htm: Add bibliographic reference to Golub & van Loan and other references [R. Gaul]
- qhalf.htm: A halfspace is the points on or below a hyperplane [D. Strawn]
- qh-opto.htm#n: Defined inside, outside, on, above, and below a hyperplane [D. Strawn]
- qhalf.htm#notes: Recast the linear program using negative halfspaces (as used by Qhull) [D. Strawn]
- qhull_a.h: Fix comment '#include "libqhull/qhull_a.h" [fe rew]
- build/qhull*.pc.in: Templates for pkg-config (derived from Fedorra) [P. McMunn]
https://bitbucket.org/mgorny/pkg-config-spec/src/c1bf12afe0df6d95f2fe3f5e1ffb4c50f018825d/pkg-config-spec.txt?at=master&fileviewer=file-view-default
- Makefile: Remove user_eg3.o from LIBQHULLCPP_OBJS
- Makefile: Add .h dependencies for unix_r.o, etc.
- libqhull/Makefile: Fix build of rbox
- libqhull_r/Makefile: Fix build -I
- qhull.sln/user_eg3: Add dependency on libcpp
- Removed bin/libqhull_r.dll (should be qhull_r.dll)
- Removed build/qhulltest.vcproj (see build/qhulltest/qhulltest.vcproj)
------------
Qhull 2015.0.4 2015/9/30 (7.0.4.1984)
- qh-get.htm: Unix tarball includes version number (e.g., qhull-2015-src-7.1.0.1940.tgz) [Hauptman]
- qglobal.c: Add qh_version2 with Unix version for "-V" option [Hauptman]
- build/qhull-32.sln, *-32.vcxproj: Add Visual Studio 32-bit build for 2010+
- build/qhull-64.sln, *-64.vcxproj: Add Visual Studio 64-bit build for 2010+ [G. Lodron]
- make-vcproj.sh: Restore to eg/... It is required for Visual Studio builds
- README.txt: updated builds and reentrant Qhull
- Add documentation for QHULL_LIB_CHECK
- qh_lib_check: Check for unknown QHULL_LIB_TYPE
- qh-code.htm: Add memory requirements for 32- and 64-bit
------------
Qhull 2015.0.3 2015/9/22
- qh_mem, qh_merge: Log before 'delete' instead of afterwards [Coverity, K. Schwehr]
- qh_merge: Test for NULL horizon in qh_checkzero [Coverity, K. Schwehr]
- qh_matchneighbor: Check for matchfacet not a neighbor of facet [Coverity, K. Schwehr]
- qh_triangulate: Explicit check for visible==NULL [Coverity, K. Schwehr]
- qh_findbestfacet (unused by qhull): Fix test of isoutside [Coverity, K. Schwehr]
- qh_check_maxout: Check bestfacet!=0 for logging its id [Coverity, K. Schwehr]
- qh_nearvertex: Check for bestvertex not found [Coverity, K. Schwehr]
- qh_checkfacet: Check for missing neighbors of simplicial facets [Coverity, K. Schwehr]
- qh_setdelnth: Check 'nth' before using it [Coverity, K. Schwehr]
- Annotate code for Coverity warnings (most of these protected by qh_errexit) [K. Schwehr]
- qh_printfacet3math: explicit format string (duplicates change to io.c) [B. Pearlmutter]
- libqhull_r.h: fix spelling error (duplicates change to libqhull.h) [B. Pearlmutter]
- unix_r.c: fix spelling error (duplicates change to unix.c) [B. Pearlmutter]
- qhull_a.h: define qhullUnused() only if defined(__cplusplus) [R. Stogner]
- qh_version: Use const char str[]= "string" instead of const char * str= "string" [U. Drepper, p. 27]
- qh_newvertex: Use UINT_MAX instead of 0xFFFFFFFF
- qh_newridge: Use UINT_MAX instead of 0xFFFFFFFF
- Reviewed FIXUP notes
- QhullRidge_test: t_foreach use 'foreach(const QhullVertex &v, vertices)
- Made '#include "RoadTest.h" consistent across all C++ tests
- qh-code.htm: May also use libqhull_r (e.g., FOREACHfacet_(...))
- qh-get.htm: Add list of download build repositories
- Add CMakeModules/CheckLFS.cmake: Enables Large File Support [B. Pearlmutter]
- Makefile: Use -fpic at all times instead of -fPIC, [U. Drepper p. 15]
------------
Qhull 2015.0.2 2015/9/1
- global_r.c: Fixed spelling of /* duplicated in...qh_clear_outputflags */ [K. Schwehr]
- Replaced Gitorious with GitHub
- Moved 'to do' comments into Changes.txt
------------
Qhull 2015.0.1 2015/8/31
Source code changes
- Increased size of vertexT.id and ridgeT.id to 2^32 [H. Strandenes, C. Carson, K. Nguyen]
Reworded the warning message for ridgeT.id overflow. It does not affect Qhull output
- Add qh_lib_check to check for a compatible Qhull library.
Programs should call QHULL_LIB_CHECK before calling Qhull.
- Include headers prefixed with libqhull/, libqhull_r/, or libqhullcpp/
- Renamed debugging routines dfacet/dvertex to qh_dfacet/qh_dvertex
- Rewrote user_eg, user_eg2, and user_eg3 as reentrant code
- Renamed 'qh_rand_seed' to 'qh_last_random'. Declare it as DATA
- qh_initqhull_start2 sets qh->NOerrexit on initialization
User must clear NOerrexit after setjmp()
Other source code changes
- Define ptr_intT as 'long long' for __MINGW64__ [A. Voskov]
- poly_r.c: initialize horizon_skip [K. Schwehr]
- Removed vertexT.dim and MAX_vdim. It is not used by reentrant Qhull.
- Removed qhull_inuse. Not used by C++
- Removed old __MWERKS__/__POWERPC__ code that speed up SIOUX I/O
- Moved #include libqhull/... before system includes (e.g., <stdio.h>
- Comment-out _isatty declaration. Avoids "C4273 ... inconsistent dll linkage"
- Add random.h/random_r.h as an include file to random.c/random_r.c
- Rename rbox routines to qh_roundi/qh_out1/qh_out2n/qh_out3n
- Rename dfacet and dvertex to qh_dfacet and qh_dvertex
- Replace 'qhmem .zzz' with 'qhmem.zzz'
- Removed spaces between function name and parentheses
- Rename 'enum statistics' to 'enum qh_statistics'
- Declare rbox as DATA in qhull-exports.def and qhull_p-exports.def
- In comments, use 'qh.zzz' to reference qhT fields
- In qh_fprintf, use qhmem.ferr to report errors
- qh_fprintf may be called for errors in qh_initstatistics and qh_meminit
- qh_pointid returns qh_IDnone, qh_IDinterior, qh_IDunknown in place of -3, -2, -1 resp.
- getid_() returns qh_IDunknown in place of -1
- After qh_meminit, qhmem.ferr is non-zero (stderr is the default)
- Update qh_MEMalign in testqset.c to user.h (with realT and void*)
- Split rboxT into a header file
- Add rboxlib.h to libqhull_a.h
- Rename PI to qh_PI and extend to 30 digits
- Rename MAXdim to qh_MAXdim
- Change spacing for type annotations '*' and '&' in C++ header files
- Test for !rbox_output/cpp_object in qh_fprintf_rbox
- Remove 'inline' annotation from explicit inline declarations
- Column 25 formatting for iterators, etc.
- Use '#//!\name' for section headers
- QhullFacet.cpp: zinc_(Zdistio);
- Clear qhT.ALLOWrestart in qh_errexit
- Replace longjmp with qh_errexit_rbox in qh_rboxpoints
- Add jmpExtra after rbox_errexit to protect against compiler errors
- Add qh.ISqhullQh to indicate initialization by QhullQh()
- Add library warnings to 'rbox D4', user_eg, user_eg2, user_eg3
- Add headers to q_eg, q_egtest, and q_test
- Check that qh.NOerrexit is cleared before call to qh_initflags
Qhull documentation
- README.txt: Added references to qh-code.htm
- README.txt: Added section 'Calling Qhull from C programs'
- qh-code.htm: Moved Performance after C++ and C interface
- qh-code.htm: Moved Cpp Questions to end of the C++ section
- qh-code.htm: Fixed documentation for 'include' path. It should be include/libqhull
- qconvex.htm: Fixed documentation for 'i'. It triangulates in 4-d and higher [ref]
- Clarified qhalf space documentation for the interior point [J. Santos]
- rbox.c: Version is same date as qh_version in global.c
- gobal_r.c: Version includes a '.r' suffix to indicate 'reentrant'
Qhull builds
- Development moved to http://github.com/qhull/qhull
git clone git@github.com:qhull/qhull.git
- Exchanged make targets for testing.
'make test' is a quick test of qhull programs.
'make testall' is a thorough test
- Added 'make help' and 'make test' to libqhull and libqhull_r Makefiles
- CMakeLists.txt: Remove libqhull, libqhull_r, and libqhullcpp from include_directories
- CMakeLists.txt: Add qhull_SHAREDR for qhull_r
- CMakeLists.txt: Retain qhull_SHARED and qhull_SHAREDP (qh_QHpointer)
- CMakeLists.txt: Move qhull_SHARED and qhull_SHAREDP (qh_QHpointer) to qhull_TARGETS_OLD
Drop qhull_STATICP (use qhull_SHAREDP or qhull_STATIC)
Set SOVERSION and VERSION for shared libraries
- Move qhull_p-exports.def back to libqhull
- Switched to mingw-w64-install for gcc
- Improved prompts for 'make'
- qhull-all.pro: Remove user_eg3.cpp from OTHER_FILES
- libqhull.pro: Ordered object files by frequency of execution, as done before
- Add the folder name to C++ includes and remove libqhullcpp from INCLUDEPATH
- Changed CONFIG+=qtestlib to QT+=testlib
- Changed Makefile to gcc -O3 (was -O2)
- Changed libqhull/libqhull_r Makefiles to both produce rbox, qhull, ..., user_eg, and user_eg2
- Removed Debian 'config/...'. It was needed for Qhull 2012.
libqhull_r (reentrant Qhull)
- Replaced qh_qh with a parameter to each procedure [P. Klosterman]
No more globally defined data structures in Qhull
Simplified multithreading and C++ user interface
All functions are reentrant (Qt: "A reentrant function can ... be called simultaneously from multiple threads, but only if each invocation uses its own data.")
No more qh_QHpointer.
See user_eg3 and qhulltest
New libraries
libqhull_r -- Shared library with reentrant sources (e.g., poly_r.h and poly_r.c which replace libqhull's poly.h and poly.c)
libqhullstatic_r -- Static library with the same sources as libqhull_r
libqhullcpp -- The C++ interface using libqhullstatic_r (further notes below)
New executables
testqset_r -- Test qset_r.c (the reentrant version of qset.c
Source code changes for libqhull_r
- Add qh_zero() to initialize and zero memory for qh_new_qhull
- Remove qh_save_qhull(), qh_restore_qhull(), and qh.old_qhstat from global_r.c
- Remove qh_freeqhull2() (global_r.c)
- Remove qh_freestatistics() (stat_r.c)
- Remove qh_compare_vertexpoint (qhT is not available, unused code)
- Remove conditional code for __POWERPC__ from unix_r.c and rbox_r.c
- Move qh_last_random into qh->last_random (random_r.c)
- Rename sources files with a '_r' suffix. qhull_a.h becomes qhull_ra.h
- Replace 'qh' macro with 'qh->'
- Replace global qhT with parameter-0
- Add qhmemT to beginning of qhT. It may not be used standalone.
- Add qhstatT to end of qhT
- Remove qhull_inuse
- Change qhmem.zzz to qh->qhmem.zzz
- Replace qh_qhstat with qh->qhstat
- Remove qh_freestatistics
- Replace qh_last_random with qh->last_random
- Replace rboxT with qh->rbox_errexit, rbox_isinteger, rbox_out_offset
- Replace rbox.ferr/fout with qh->ferr/fout
- No qh for qh_exit, qh_free, qh_malloc, qh_strtod, qh_strtol, qh_stddev
- New qmake include files qhull-app-c_r.pri, qhull-app-shared_r.pri, qhull-libqhull-src_r.pri
- Replace 'int' with 'countT' and 'COUNTmax' for large counts and identifiers
- qhset converted to countT
- Removed vertexT.dim -- No longer needed by cpp
Removed MAX_vdim
- Guarantee that qh->run_id!=0. Old code assumed that qh_RANDOMint was 31 bits
Changes to libqhullcpp
- Added QhullVertexSet.h to libqhullcpp.pro and libqhullpcpp.pro
- QhullVertexSet: error if qhsettemp_defined at copy constructor/assignment (otherwise double free)
- Enable QhullSet.operator=. Copy constructor and assignment only copies pointers
- Changed QhullPoint.operator==() to sqrt(distanceEpsilon)
- Added assignment of base class QhullPoints to PointCoordinates.operator=
- Enable QhullPoints.operator=
- Rename PointCoordinates.point_comment to describe_points
- Add 'typename T' to definition of QhullSet<T>::value()
C++ interface
- Reimplemented C++ interface on reentrant libqhull_r instead of libqhull
- Prepend include files with libqhullcpp/
- Replaced UsingLibQhull with QhullQh and macro QH_TRY
Removed UsingLibQhull.currentAngleEpsilon and related routines
Removed UsingLibQhull_test.cpp
Replaced globalDistanceEpsilon with QhullQh.distanceEpsilon
Replaced globalAngleEpsilon with QhullQh.angleEpsilon
Moved UsingQhullLib.checkQhullMemoryEmpty to QhullQh.checkAndFreeQhullMemory
Replaced FACTORepsilon=10 with QhullQh.factor_epsilon=1.0
- To avoid -Wshadow for QhullQh*, use 'qqh' for parameters and 'qh()' for methods
- Moved messaging from Qhull to QhullQh
- Add check of RboxPoints* in qh_fprintf_rbox
- Renamed Qhull.initializeQhull to Qhull.allocateQhullQh
Added qh_freeqhull(!qh_ALL) as done by unix.c and other programs
- Moved QhullPoints.extraCoordinatesCount into QhullPoints.cpp
- Replaced section tags with '#//!\name ...'
- Removed qhRunId from print() to ostream.
- Removed print() to ostream. Use '<< qhullPoint' or '<< qhullPoint.print("message")'
C++ interface for most classes
- Remove qhRunId
- Add QhullQh *qh_qh to all types
Pointer comparisons of facetT,etc. do not test corresponding qh_qh
Added to end of type for debugging information, unless wasteful alignment
- Add QhullQh * to all constructors
- All constructors may use Qhull & instead of QhullQh *
- For inherited QhullQh types, change to 'protected'
- Renamed 'o' to 'other' except where used extensively in iterators
- Except for conditional code, merged the Conversion section into GetSet
- Removed empty(). Use isEmpty() instead
- Add operator= instead of keeping it private
- print_message=0 not allowed. Use "" instead.
- Rename isDefined() to isValid() to match Qt conventions
C++ interface by class
- Coordinates
Removed empty(). Use isEmpty() instead
Added append(dim, coordT*)
Reformated the iterators
Convert to countT
- PointCoordinates
Added constructors for Qhull or QhullQh* (provides access to QhullPoint.operator==)
Removed PointCoordinates(int pointDimension) since PointCoordinates should have a comment. Also, it is ambiguous with PointCoordinates(QhullQh*)
Renamed point_comment to describe_points
Convert to countT
- Qhull
Remove qhull_run_i
Remove qh_active
Replace property feasiblePoint with field feasible_point and methods setFeasiblePoint/feasiblePoint
Returns qh.feasible_point if defined
Moved useOutputStream to QhullQh use_output_stream
Renamed useOutputStream() to hasOutputStream()
Replaced qhull_dimension with qh->input_dim //! Dimension of result (qh.hull_dim or one less for Delaunay/Voronoi)
Removed global s_qhull_output= 0;
Move qhull_status, qhull_message, error_stream, output_stream to QhullQh
Renamed qhullQh() to qh()
Added check of base address to allocateQhullQh(), Was not needed for qhullpcpp
- QhullFacet
Constructor requires Qhull or QhullQh* pointer
Convert to countT
Dropped implicit conversion from facetT
Dropped runId
Add print("message") to replace print()
- QhullFacetList
Constructor requires Qhull or QhullQh* pointer
Convert to countT
Dropped runId
- QhullFacetSet
Removed empty(). Use isEmpty() instead
Constructor requires Qhull or QhullQh* pointer
Convert to countT
Dropped runId
Add operator=
Implement print("message")
- QhullHyperplane
Add hyperplaneAngle() method
Rewrite operator==to use hyperplaneAngle()
Reorganize fields to keep pointers aligned
Except for default constructor requires Qhull or QhullQh* pointer
Enable copy assignment
Reorganized header
- QhullLinkedList
Add operator=
Removed empty(). Use isEmpty() instead
Convert to countT
iterator(T) made iterator(const T &)
const_iterator(T) made const_iterator(const T &)
const_iterator(iterator) made const_iterator(const iterator &)
- QhullPoint
Add constructors for Qhull or QhullQh* pointer (for id() and operator==)
Add defineAs(coordT*)
Add getBaseT() and base_type for QhullSet<QhullPoint>
Added checks for point_coordinates==0
Removed static QhullPoint::id(), use QhullPoint.id() instead
distance() throws an error if dimension doesn't agree or if a point is undefined
Convert to countT
If !qh_qh, operator==() requires equal coordinates
Use cout<<p instead of cout<<p.print()
Reorganized
- QhullPoints
Add constructors for Qhull and QhullQh* (for qh.hull_dim, QhullPoint::operator==)
Remove QhullPoints(int pointDimension) since it is ambiguous with QhullPoints(QhullQh *qqh)
Add operator=
Removed empty(). Use isEmpty() instead
Convert to countT
operator==() tests if pointers are the same. Ituses distanceEpsilon if qh_qh is defined
Reorganized
- QhullPoints::Iterator and ConstIterator
Removed default constructors
Add constructors for Qhull and QhullQh* (for qh.hull_dim, QhullPoint::operator==)
Moved test of dimension from QHULL_ASSERT to operator==
Added QHULL_ASSERT of qh_qh
Convert to countT
- QhullPointSet
Constructor requires Qhull or QhullQh* instead of dimension()
Add operator=
Removed empty(). Use isEmpty() instead
Convert to countT
Always print print_message
Drop print(). Replace with print("")
- QhullQh
Added methods hasOutputStream(), disableOutputStream(), and enableOutputStream() (was Qhull UseOutputStream)
Add test of qh.NOerrexit to maybeThrowQhullMessage()
Add qhull_status, qhull_message, error_stream, output_stream from Qhull
Add factor_epsilon
- QhullRidge
Constructor requires Qhull or QhullQh* pointer
Dropped implicit conversion from ridgeT
Converted otherFacet() to 'const &'
Converted nextRidge3d() to 'const &'
Message for '<< QhullRidge' replaces " - " instead of preceding it
- QhullSet
Removed empty(). Use isEmpty() instead
Constructor requires Qhull or QhullQh* pointer
Convert to countT
Add operator=
- QhullVertex
Constructor requires Qhull or QhullQh* pointer
Convert to countT
Dropped implicit conversion from vertexT
Add message to '<< QhullVertex'
- QhullVertexSet
Removed empty(). Use isEmpty() instead
Constructor requires Qhull or QhullQh* pointer
Convert to countT
- UsingQhullLib
Removed
Replace setGlobalDistanceEpsilon with setFactorEpsilon
Replace globalDistanceEpsilon with distanceEpsilon
=============
== Qhull 2012.1
=============
------------
Qhull 2012.1 2012/02/18 6.3.1.1494
- Fix CMakeLists for libqhull with MATCHES [P. Gajdos]
------------
Qhull 2012.1 2012/02/18 6.3.1.1490
Code changes
- Require option 'Qz' for Delaunay triangulation/Voronoi diagram
of cocircular/cospherical points [D. Sheehy]
- qh_errexit: Do not call qh_printsummary or qh_printstats on qh_ERRinput
- Change error QH6227 (all degenerate) from qh_ERRinput to qh_ERRprec
- Change error QH6159 (ID overflow) from qh_ERRinput to qh_ERRqhull
- eg/q_eg, q_egtest, q_test: Run if qconvex is in $PATH [M. Atzeri]
Build changes [M. Atzeri]
- Install to share/doc/qhull instead of share/doc/packages/qhull
- On Unix systems, install to share/man/man1 instead of man/man1
- CMakeLists: Remove the installation of user_eg* and testqset
- CMakeLists: Remove VERSION from qhull executables and libraries
- CMakeLists: Define qhull_SOVERSION instead of qhull_MAJOR
- CMakeLists: Set SOVERSION for shared libraries
- Rename libraries to qhull, qhull_d, qhull_p, and qhull_pd
libqhull6_p.vcproj is now libqhull_p.vcproj
mingw builds as libqhull.dll
cygwin builds as cygqhull-6.dll
linux builds as libqhull.so.6.3.1 with symbolic link as libqhull.so
- Developers using qhull 2011:
libqhull6.so is now libqhull_p.so. Do not use libqhull.so.
qhull6.dll is now qhull_p.dll. Do not use qhull.dll.
- Merged road/ into libqhullcpp/ and qhulltest/
Moved RoadLogEvent.* and RoadError.* to libqhullcpp
Moved RoadTest.* to qhulltest (requires Qt)
Installed RoadTest.h in libqhullcpp
Doc changes
- index.htm: Mathworks uses qhull for n-d
- qhull.htm: Fix qhull for qconvex
- qdelaun.htm/qvoronoi.htm: Use option 'Qz' for circular/cospherical inputs
- make help: Display targets
- Makefile: Better messaging
------------
Qhull 2012.1 2012/02/02 6.3.0.1483
Bug fixes
- Fixed qset.c for -fno-strict-aliasing. This gcc option is no longer needed
(disallow two pointers of differing types to the same memory location)
- Fixed error in qh_setappend_set if first set full and second set empty
- qh_setdelnth, qh_setdelnth_sorted: fixed wording of error message
- qh_setcheck: error message listed size and max backwards.
- qh_setequal: Allow NULL set as documented
- qh_setindex: Allow NULL set as documented
- qh_settemppush: report error if NULL
Code changes
- Add testqset: low level test of qset.c with mem.c
- qh_setendpointer: Implements QSet::endPointer()
- Assigned unique error code for qh_gethash
Build changes
- Added qhull.dll(.so) for Octave and other Debian builds
The global data structure qh_qh is statically defined (no qh_QHpointer)
Linked user_eg2 with qhull.dll (libqhull.so) instead of qhullstatic
Added qh_dllimport to libqhull.h for qhull.dll with MSVC
Changed qhull-app-shared.pri to use libqhull (without qh_QHpointer)
- Renamed libqhull6.so to libqhull6_p.so
Renamed qhull6.dll to qhull6_p.dll
The _p libraries (e.g., libqhull6_p.so) require -Dqh_QHpointer
Renamed qhull6.vcproj to libqhull6_p.vcproj
Added libqhullp/libqhullp.pro for shared library (libqhull6_p.so)
Added qhull-app-sharedp.pri for shared libraries with qh_QHpointer
- Install libqhull/*.htm files into include/libqhull
- Removed libqhull/qhull.h-deprecated [J. Eaton]
- Other changes to Makefile builds
Added 'make qtestall' as a smoketest of each qhull program
src/libqhull/Makefile: Use 'ar -rs ...' instead of ranlib
src/libqhull/Makefile: Fixed targets for cleanall
- Other changes to DevStudio builds
Moved pdb files for qhull libraries to lib/
AdditionalIncludeDirectories: Removed ../src/libqhullcpp
Use build-cmake/ for the DevStudio CMake build
- Other changes to Qt builds
Renamed qhull-libsrc.pri to qhull-libqhull-src.pri
- Added explicit d2u conversions to qhull-zip.sh
- Fixed \n vs. \r\n issues for Windows source files
Draft of Debian/AutoConf build (untested)
- Adjusted the Makefile.am's for the new directory structure.
- Added testqset to bin_PROGRAMS
- config/bootstrap.sh copies program sources into src/libqhull
- Kept qh_QHpointer=0 (static global data structure, qh_qh). It is faster.
Planning a new interface (qhull7?) which passes qh_qh as a parameter
- Added config/changelog from the 2003.1 Debian build
- Moved the debian/patches directory to config/
Optional patches to change smoketest message and turn on qh_QHpointer
- Deleted the debian directory. It was the old Debian build from 2003.1
Rafael Laboissiere's config directory replaced this build..
- Deleted Make-conf.sh (also the old Debian build)
Doc changes
- FAQ: Updated notes on computing volume of a Voronoi region
- Added direct link to ACM Digital Library for downloading the qhull paper
- Added link to Qhull in R
- qset.c: Updated notes about NULL sets
- qh_setappend: clarify qh_setappend for NULL newelem
- qh_setdellast: Fix head note
- Add build/README.txt
- Add uninstall instructions to README.txt and CMakeLists.txt
- Added instructions to create build/*.vcproj to CMakeLists.txt
- Update copyright to 2012
- Updated page links. Added Google books, patents, and blogs.
-----------
Qhull 2009.1.3 2011/12/06
configure: Add -fno-strict-aliasing if $GCC, Required for gcc 4.1+
------------
Qhull 2011.2 2011/11/29 6.2.1.1446
Bug fixes
- qh_new_qhull: Call qh_prepare_output if !outfile [A. Aldoma]
No effect on qhull users since qh_prepare_output is always called.
- Replace Qhull-go.pif with Qhull-go.lnk for Windows 7 64-bit [lots]
- Error if qh_newhashtable, qh_setnew, or qh_memalloc overflows [X. Cheng]
For example, 'rbox 64 D32' overflows hash table for qh_matchnewfacets
Qhull uses 32-bit ints for identifiers, counts, and sizes. See "WARN64"
- q_eg, q_test: change tail +3 to tail -n +3 [N. Dubray, M. Atzeri]
- Qhull-go.bat: Changed 'cmd' to '%comspec%'
Build changes
- Added src/libqhull/Makefile for simple gcc build of executables and lib
- qhulltest.vcproj: Replaced full path to QT with $QTDIR (e.g., c:/qt/4.7.4)
- Split userprintf_rbox.c from userprintf.c,
Otherwise qhull brings in rboxlib and rbox brings in libqhull
- Makefile: qhullx target must be after LIBQHULLS_OBJS
- Makefile: Explicitly list rbox dependencies for qhullx target
- MBorland: Fixed tabs
- Placed $LIBQHULLS_OBJS in same order. Frequently called ones together.
- Update file lists for Make-config.sh [O. Lahaye]
- CMakeLists: add README.txt,etc. to DOC_INSTALL_DIR [M. Atzeri]
- Restored qhull.h-deprecated.
qhull.h conflicts with Qhull.h on Windows systems [C. Abela]
- make-config.sh: Add warning that it is out-of-date
- Remove extra space in '#! /bin/sh' in q_eg, etc. [P. Cheeseman]
Source changes
- libqhull.h: Added qh_True and qh_False for True/False [A. Mutzel]
Did not remove or replace True/False since it is used everywhere
- Moved error message from qh_argv_to_command to caller. Avoids dependency.
- user_eg3.c: Use '10 D2' as default rbox (e.g., 'user_eg3 rbox qhull d')
- user.c, user_eg2.c: Add test of qh_qh as done in user_eg.c
- q_test: Removed duplicate test of qhull C-0.02
Documentation
- index.html: Added ACM Authorizer link to ACM Trans. Math. Software
- Split Delaunay and Voronoi FAQs
- FAQ: How to compute the volume of a Voronoi region [C, Brinch]
- Add 'FS' to qconvex prompt (total area and volume)
- Add clarification to 'Fv' about corner input sites [O. Can]
- Qhull-go.bat: Removed out-of-date advice. Added title.
- qh-code.htm: Updated the discussion of multi-threading for C++ [I. Pirwani]
Qhull 2009.1.2 2011/11/21
- Revert to LF line endings [P. Cheeseman]
- Remove out-of-date material from qhull-go.bat
- Replaced QHULL-GO with a lnk file
=============
== Qhull 2011.1
=============
Qhull 2011.1 2011/05/23 6.2.0.1385 (exe/dll files unchanged)
- delaunay.vcproj: Fixed qhullstatic_d.lib for debug and minrelsize builds
- Did not redate the distribution
Qhull 2011.1 2011/05/18 6.2.0.1385 (exe/dll files unchanged)
- Add 'm' library to shared and static targets on Unix [A. Bouchard]
Qhull 2011.1 2011/05/14 6.2.0.1383 (exe/dll files unchanged)
- PointCoordinates.cpp: Add #include <iterator> [R. Richter, S. Pasko]
- Remove deprecated libqhull/qhull.h
Use libqhull/libqhull.h instead. Avoids confusion with libqhullcpp/Qhull.h
- Makefile: Add LIBDIR, INCDIR, and DESTDIR to install [L.H. de Mello]
Separate MAN install from DOC install
Create install directories
Installs headers to include/libqhull, include/libqhullcpp, include/road
- CMakeLists.txt: Add MAN_INSTALL_DIR for qhull.1 and rbox.1 man pages
Add RoadTest.h to include/road for Qt users (road_HEADERS)
- Renamed md5sum files to avoid two extensions
- qh-get.htm: Add Readme links and 2009.1 note.
- qh-optf.htm: Fix link
- index.htm: Updated Google Scholar link
- qhull-zip.sh: Improved error message.
------------
Qhull 2011.1 2011/04/17 6.2.0.1373
Changes to deliverables
- qvoronoi: Deprecated 'Qt' and 'QJn'. Removed from documentation and prompts.
These options produced duplicate Voronoi vertices for cospherical data.
- Removed doskey from Qhull-go.bat. It is incompatible with Windows 7
- Added 'facets' argument to user_eg3.cpp
- user_eg links with shared library
- qhulltest.cpp: Add closing prompt.
Changes to build system
- Reorganized source directories
- Moved executables to bin directory
- Add CMake build for all targets (CMakeFiles.txt) [M. Moll assisted]
- Add gcc build for all targets (Makefile)
- Fixed location of qhull.man and rbox.man [M. Moll]
- Add DevStudio builds for all targets (build/*.vcproj)
- Added shared library (lib/qhull6.dll)
Added qh_QHpointer_dllimport to work around problems with MSVC
- Added static libraries with and without qh_QHpointer (lib/qhullstatic.lib)
- Added eg/make-vcproj.sh to create vcproj/sln files from cmake and qmake
- Document location of qh_QHpointer
- Use shadow build directory
- Made -fno-strict-aliasing conditional on gcc version
- Added src/qhull-app-cpp.pri, src/qhull-app-c.pri, etc. for common settings
- Add .gitignore with ignored files and directories.
- Use .git/info/exclude for locally excluded files.
- Fixed MBorland for new directory structure
- cleanall (Makefile): Delete 'linked' programs due to libqhull_r and libqhull/Makefile
Changes to documentation
- qvoronoi.htm: Remove quotes from qvoronoi example
- qhull-cpp.xml: Add naming conventions
- index.htm: Add Google Scholar references
- qh-optf.htm: Add note about order of 'Fn' matching 'Fv' order [Q. Pan]
- Add patch for old builds in qh-get.htm
- Added C++ compiling instructions to README.txt
- Add instructions for fixing the DOS window
- Changed DOS window to command window
- Fixed html links
- qh-get.htm: Dropped the Spanish mirror site. It was disabled.
Changes to C code
- mem.h: Define ptr_intT as 'long long' for Microsoft Windows _win64 builds.
On Linux and Mac, 'long' is 64-bits on a 64-bit host
- Added qh_QHpointer_dllimport to work around MSVC problem
- qconvex.c,etc.: Define prototype for _isatty
- Define MSG_QHULL_ERROR in user.h
- Move MSG_FIXUP to 11000 and updated FIXUP QH11...
Changes to test code
- Add note to q_test than R1e-3 may error (qh-code.htm, Enhancements)
- Add test for executables to q_eg, etc.
- Fixed Qhull-go.bat. QHULL-GO invokes it with command.com,
Changes to C++ interface
- QhullFacet: Added isSimplicial, isTopOrient, isTriCoplanar, isUpperDelaunay
- Added Qhull::defineVertexFacetNeighbors() for facetNeighbors of vertices.
Automatically called for facet merging and Voronoi diagrams
Do not print QhullVertex::facetNeighbors is !facetNeighborsDefined()
- Assigned FIXUP identifiers
- QhullError: Add copy constructor, assignment operator, and destructor
- Add throw() specifiers to RoadError and QhullError
- Renamed RoadError::defined() to RoadError::isDefined()
- Add #error to Qhull.h if qh_QHpointer is not defined
Changes to C++ code
- Fixed bug reported by renangms. Vertex output throws error QH10034
and defineVertexNeighbors() does not exist.
- Define QHULL_USES_QT for qt-qhull.cpp [renangms]
- Reviewed all copy constructors and copy assignments. Updated comments.
Defined Qhull copy constructor and copy assignment [G. Rivet-Sabourin]
Disabled UsingQhullLib default constructor, copy construct, and copy assign
- Merged changes from J. Obermayr in gitorious/jobermayrs-qhull:next
- Fix strncat limit in rboxlib.c and global.c
- Changes to CMakeLists.txt for openSUSE
- Fixed additional uses of strncat
- Fixed QhullFacet::PrintRidges to check hasNextRidge3d()
- Removed gcc warnings for shadowing from code (src/qhull-warn.pri)
- Removed semicolon after extern "C" {...}
- Removed experimental QhullEvent/QhullLog
- Use fabs() instead of abs() to avoid accidental conversions to int
- Fixed type of vertex->neighbors in qh_printvoronoi [no effect on results]
- Removed unnecessary if statement in qh_printvoronoi
=============
== Qhull 2010.1 and 2009.1
=============
------------
qhull 2010.1 2010/01/14
- Fixed quote for #include in qhull.h [U.Hergenhahn, K.Roland]
- Add qt-qhull.cpp with Qt conditional code
- Add libqhullp.proj
- Add libqhull5 to Readme, Announce, download
- Reviewed #pragma
- Reviewed FIXUP and assigned QH tags
- All projects compile with warnings enabled
- Replaced 'up' glyphs with »
- Moved cpp questions to qh-code.htm#questions-cpp
- Moved suggestions to qh-code.htm#enhance
- Moved documentation requests to qh-code.htm#enhance
- Add md5sum file to distributions
- Switched to DevStudio builds to avoid dependent libraries, 10% slower
Removed user_eg3.exe and qhullcpp.dll from Windows build
Fix qhull.sln and project files for qh_QHpointer
- Add eg/qhull-zip.sh to build qhull distribution files
------------
qhull 2010.1 2010/01/10
- Test for NULL fp in qh_eachvoronoi [D. Szczerba]
qhull 2010.1 2010/01/09
Changes to build and distribution
- Use qh_QHpointer=0 for libqhull.a, qhull, rbox, etc.
Use -Dqh_QHpointer for libqhullp.a, qhullcpp.dll, etc.
qh_QHpointer [2010, gcc] 4% time 4% space, [2003, msvc] 8% time 2% space
- Add config/ and project/debian/ for Autoconf build [R. Laboissiere]
from debian branch in git and http://savannah.nongnu.org/cvs/?group=qhull
- Add CMakeLists.txt [kwilliams]
- Fix tabs in Makefile.txt [mschamschula]
- Add -fno-strict-aliasing to Makefile for gcc 4.1, 4.2, and 4.3 qset segfault
- Remove user_eg.exe and user_eg2.exe from Windows distribution
- Order object files by frequency of execution for better locality.
Changes to source
- Remove ptr_intT from qh_matchvertices. It was int since the beginning.
- user.h requires <time.h> for CLOCKS_PER_SEC
- Move ostream<<QhullFacetList from inline to compiled.
- Removed ConvexHull/ from git. Not used.
------------
qhull 2009.1.1 2010/01/09
- Patch release of 2009.1.
qh_gethash allowed a negative result, causing overwrite or segfault
See git:qhull/project/patch/qhull-2003.1/poly.c-qh_gethash.patch
Compared results of q_test, q_eg, q_egtest with patched poly.c, qhull-2003.1
------------
qhull 2010.1 2010/01/07
- Assign type to qh.old_qhstat and memT.tempstack [amorilia]
- Replace tabs with spaces.
- Fix qh_pointid in case ptr_intT is unsigned
qhull 2010.1 2010/01/06
- Fixed serious bug in qh_gethash [poly.c]
- Documentation and build system are incomplete (see above)
- First release of C++ interface [qh-code.htm]
- Development moved to http://gitorious.org/qhull
git clone git@gitorious.org:qhull/qhull.git
- Did not fix conformant tesselations for 'Qt'.
For details, see http://www.qhull.org/news#bugs of May 2007 and Dec 2006.
- Use g++ builds for Windows distribution (10% faster than msvc2005)
Combined vcproj/ and qtproj/ into project/
vcproj will be replaced by qmake generated files
------------
qhull 2010.0.3 2010/01/05
Fixed bugs
- 'QJn': Fix qh.STOPcone in qh_build_withrestart(). It was not cleared.
- qh_initqhull_outputflags [global.c]: warn about Qc only if QHULLfinished
otherwise set if needed
qhull 2010.0.2 2010/01/04
Fixed bugs
- qh_gethash [poly.c]: fix sign conversion.
Previously, the result may be negative, leading to a segfault.
The bug is more likely with large address spaces
Reviewed all uses of %(modulo) for remainder with negative arguments
- Reviewed output of q_test and compared to results from 2003.1
Breaking code changes
- Return type of qh_gethash changed from unsigned to int. Matches 'size'
- addhash takes a signed hash
qh_addhash( newelem, hashtable, hashsize, hash )
Code changes
- Test for qh_qh in qh_printf
- Makefile.txt corrected for libqhull build [amorilia]
- Renamed index to idx to avoid shadowing BSD strings.h [kwilliams]
qhull 2010.0.1 2010/01/03
New Features:
- Added option 'Ta' to annotate output with message codes
Preliminary C++ support:
- C++ declarations may change without warning
- Preliminary documentation for Qhull's C++ interface [qh-code.htm#cpp, qhull-cpp.xml]
- Added user_eg3 as an example of Qhull.cpp
- Removed qhull_interface.cpp. Use Qhull.cpp instead.
If math.h breaks '#include qhull_a.h', preceed it with '#include math.h'
Changes to qhull options and results
- Allow 'd' and 'v' as the filename for 'TO ..' and 'TI ...' in qdelaunay [M. Jambon]
- 'rbox tN' requires an integer (previously allowed floats)
- Allow quoted filenames for 'TO ...' and 'TI ...'
- Prefix error messages and warnings with a message code (e.g., QH6012)
- Fixed rbox ignoring flags that were not separated by spaces
- Report all hidden options before exiting in qh_checkflags()
- Defined qh_OPTIONline [user.h] as max length of option line ('FO')
- Report error if negative arguments to rbox 'G', 'L', 'Z'
- Unknown rbox flag changed from a warning to an error
- Set error status 4 qh_ERRmem if rbox runs out of memory
- Removed extra spaces at end of line
Breaking Code Changes:
- Renamed qh.coplanarset to coplanarfacetset. Avoids conflict with facetT.coplanarset
- qh_restore_qhull() zeroes out qh.old_qhstat and qh.old_tempstack. Ownership moved.
- Rewrote save_qhull/restore_qhull
- Add Ztotcheck to zzdef_ [R. Gardener]
- Changed qh_malloc to size_t (was unsigned long)
- Declare qh_PRINT instead of int [kwilliams]
- In qh_printafacet(), changed error output to 'qh ferr'
Bug fixes to C code:
- Use gcc 4.4.0 or later. gcc 4.2.1, 4.2.2, and 4.3.2 -O2 segfaults in qset.c . gcc 4.1.1 was OK
See bug report http://gcc.gnu.org/ml/gcc-bugs/2007-09/msg00474.html
- Rewrite qh_setappend to avoid g++ 4.1, 4.2, and 4.3 strict_aliasing error.
Orion Poplawski (orion@cora.nwra.com)
http://www.rpmfind.net/linux/RPM/fedora/12/ppc/qhull-devel-2003.1-13.fc12.ppc64.html
- Fixed qh_findfacet_all(), "REALmin" should be "-REALmax" [L.A. Taylor].
Effects library users for convex hulls and halfspace intersections.
- qh_printfacet [io.c] Removed extra space for neighboring facets
- Report error if d points, Delaunay, and not Qz
- Fixed double-free of facet->centrum for triangulated facets
- Fixed mindist initialization if !testcentrum in io.c findbest_test [Ratcliff]
- Fixed parentheses around warning for missing 'Qc' [qh_initqhull_outputflags]
- Fixed rbox buffer overflow of 'command' when appending seedbuf
- Fixed option string for 'rbox t t999'. Although seed was correctly set to 999,
a random seed was appended to the rbox comment (e.g., 'rbox t t999 t32343')
- Fixed upper bound of sanity check for qh_RANDOMmax in qh_initqhull_globals()
Changes to C code
- Reordered #include from specific to general. Move up .h for module.
- Removed qh.old_stat -- never used
- Removed qh_clearcenters from qh_freeqhull. Duplicated by qh_delfacet
- qh_printcenter [io.c] removed unreachable fprintf argument
- qh_getarea() [geom2.c] ignored on multiple calls (qh.hasAreaVolume)
- qh_getarea() [geom2.c] checks facet->isarea. Set by QhullFacet.facetArea()
- qh_triangulate() [poly2.c] ignored on multiple calls (qh.hasTriangulation)
- Add statistics for vertex_visit and visit_id to buildtracing
- Defined scale and offset parameters for qh_randomfactor
Bug fixes and changes to mem.c/mem.h
- Fixed qhmem.totshort (total short memory in use)
- Memory tracing (T5) redone for sort order by object
- Added full tracing for short memory allocations.
- Added qhmem.totfree (total short memory on freelists)
Increases size of qh_memalloc_ and qh_memfree_
- Added qhmem.totdropped (leftover freesize at end of each short buffer)
- Added qhmem.totunused (short size - request size)
- Added qhmem.totbuffer (total short memory buffer w/o links)
- Added memory statistics to qh_NOmem;
- Added qh_memtotal to track allocated memory
- Renamed qh_memfree parameter to 'insize' for consistency with qh_memalloc
- Removed qhmem.curlong. qa_memfreeshort computes curlong from cntlong and cntfree
- In mem.h, changed ptr_intT to long. qh_meminit() checks that it holds a 'void*'
Fixed g++ and devstudio warnings
- Except for bit field conversions, compiles cleanly with
-Wall -Wextra -Wshadow -Wcast-qual -Wwrite-strings -Wno-sign-conversion -Wconversion
- Fixed warnings at VC8, level 4
- Fix data types to remove conversion warnings [kwilliams]
- Use size_t for calls to malloc,etc [kwilliams]
Retained int sizes for qset.h and mem.h. Follows Qt convention
and is easier to work with. int can be 64-bits if 2 billion facets
- Change literal strings to const char* [kwilliams]
- Added type casts to SETfirst and SETsecond [amorilia+alphax]
- getid_() returns an int [kwilliams]
- Add missing const annotations [kwilliams]
- Fixed 64-bit warnings (marked with "WARN64")
- Convert sizeof to (int) for int parameters
- In libqhull.c, added explicit casts from long to float, Avoids warning
- In global.c, cast time() to int for QRandom-seed. Avoids warning
Changes to C code for C++ support
- Add sln, vcproj, and qtpro files for building Qhull -- add to README notes
- Added dim to vertexT for cpp interface. Reduced size of qh.vertex_visit
- qh_produce_output [io.c] may be called multiple times (C++ interface)
- Moved SETsizeaddr_() to qset.h for use by QhullSet.cpp
- Option 'Tz' sets flag qh.USEstdout for QhullPoints.cpp
- Added support for multiple output runs from QhullPoints.outputQhull
- qh_clear_outputflags() resets the output flags
- qh_initqhull_outputflags split from qh_initqhull_globals
- Added qh.run_id, a random identifier for this instance of Qhull (QhullPoints)
- For qh.run_id, initqhull_start initializes qh_RANDOMseed to time instead of 1
- Extracted qh_argv_to_command (random.c) from qh_init_qhull_command and fixed a buffer overflow
- Moved qh_strtod/qh_strtol from global.c to random.c for use in rboxlib.c
- Split out random functions into random.c
- Added message codes to qh_fprintf(). See its definition in user.c
- Replaced exit, malloc, free, fprintf, and fputs with qh_malloc,...[J.W. Ratcliff]
- Added qh_fprintf, qh_malloc, qh_free, ph_printhelp_narrowhull to user.c
- Moved qh_printhelp_degenerate and qh_printhelp_singular from io.c to user.c
- Clear qh.ERREXITcalled at end of qh_errexit().
Documentation:
- Fixed out-of-date CiteSeer references
- Renamed html/qh-in.htm to html/qh-code.htm
- Add reference to 'Qt' to 'i'
- Add reference to 'FS' to 'FA'
- qh-impre.htm discusses precision issues for halfspace intersection
- Add cross references between options 'FA' and 'FS'
- Added link to Wolfram Research's MathWorld site
- Updated Fukuda's links
- Changed copyright to C.B. Barber for C++, documentation, and merge.c
- Updated Qhull citation with page numbers.
- Proposed project: constructing Voronoi diagram
- Proposed project: computing Voronoi volumes
- Replaced tabs with spaces in qhull.txt and rbox.txt
------------
qhull 2009.1 2009/6/11
This is a maintenance release done by Rafael Laboissiere <rafael@debian.org>.
- src/rbox.c (main): Avoid problems of evaluation order when
pre-incrementing arguments of strtod
- src/io.c (qh_produce_output), src/stat.c (qh_initstatistics): Use %lu
instead of %d in the format string for arguments of type size_t
- html/qhull.man, html/rbox.man: Fix several syntax, macros, and hyphen
problems in man pages
- The Autotools files have been generated with modern version of autoconf (2.63),
automake/aclocal (1.10.2), and libtool (2.2.6)
- Some character issues in the man pages are fixed
=============
== Qhull 2003.1
=============
------------
qhull 2003.1 2003/12/30
New Features:
- Add Maple output ('FM') for 2-d and 3-d convex hulls [T. Abraham]
Breaking Code Changes:
- Annotate C code with 'const'. An ANSI compatible compiler is required.
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]
- Split out qh_initqhull_start2() to avoid allocating qh_qh
- Split out qh_freeqhull2() to avoid freeing qh_qh
- Split out qh_produce_output2() and qh_prepare_output()
- qh_initstatistics() frees a previously existing qh_qhstat
- qh_initqhull_start2() checks that qh_initstatistics() called first
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
=============
------------
qhull 2002.1 2002/8/20
Changes to distribution:
- Set up savannah.nongnu.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 libqhull.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)
=============
------------
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 libqhull.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)
=============
------------
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-code.htm to compute largest empty circle [Hase]
- the DOS window in Windows NT is better than the DOS window in Windows 95
- removed obsolete qh_findfacet() from qh-c.htm [Sminchisescu]
------------
qhull 2.6 1998/8/12
new and modified features
- rbox: added option Mn,m,r to generate a rotated lattice or mesh
- rbox: report error if more than one of 'l', 'x', 'L', 's', or 'M'
Qhull library changes
- added qh_new_qhull() to user.c for calling qhull() from a program [D. Zwick]
rewrote user_eg.c to use qh_new_qhull(). Added qh_QHpointer example.
- added qh_CLOCKtype 2 in user.h to call times() for CPU time [B. Hemkemeier]
- renamed set.c/set.h to avoid conflict with STL's set.h [G. van den Bergen]
can also use '#include <qhull/qhull_a.h>' for Qhull library
fixed errors
- fixed qh_init_B() to call qh_initqhull_mem() once only [D. Zwick]
This only effects Qhull library users of qh_QHpointer.
- fixed qh_mergecycle_all() to check for redundant vertices [J. Nagle]
e.g., 'rbox M3,4 64 | qhull Qc' should report 8 vertices & 48 coplanars
- fixed gmcoord initialization in qh_setfacetplane() for qh.RANDOMdist
- turn off qh.RANDOMdist during qh_printfacetheader()
- fixed error messages for unknown option flags
documentation changes
- added note to FAQ on the Voronoi diagram of cospherical points [H. Hase]
- added note to 'Qu' on furthest-site Delaunay triangulation via convex hull
- added note to 'QJ' about coplanar points on the convex hull of the input
- added note that 'o' and 'FN' list Voronoi regions in site id order [Arvind]
- added links to Fukuda's introduction to convex hulls, etc. [H. Hase]
- added .c and .h source files to web distribution and qh-c.htm [J. Sands]
- 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)
=============
------------
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 libqhull.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-code.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 libqhull.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 (1997)
=============
------------
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-code.htm for Qhull code
- 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 2.3 (1996)
=============
------------
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 2.2 (1995-1996)
=============
------------
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 2.1 (1995)
=============
------------
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 libqhull.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, <ftp://ifor13.ethz.ch/pub/fukuda/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
<http://www.geom.uiuc.edu/graphics/pix/Special_Topics/Computational_Geometry/>
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 libqhull.h for user code
- qh_collectstatistics and qh_printstatistics removed from libqhull.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 2.0 (1994-1995)
=============
------------
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 libqhull.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
Generated by dwww version 1.15 on Sun Jun 16 19:26:50 CEST 2024.