# PaCkAgE DaTaStReAm LNFqhull-docs 1 1907 # end of header 0707010002161b000081a400001782000005de0000000156d3a18c000002f5000002600000070d00000000000000000000001600000000LNFqhull-docs/pkginfo CLASSES=none PSTAMP=q20160229024028 LICFILE=qhull.txt LICURL=http://www.qhull.org/COPYING.txt LICINFO=Qhull DESC=This package contains additional information for libqhull. Qhull is a general dimension code for computing convex hulls, Delaunay triangulations, halfspace intersections about a point, Voronoi diagrams, furthest-site Delaunay triangulations, and furthest-site Voronoi diagrams. These structures have applications in science, engineering, statistics, and mathematics. This package contains the shared C libraries and related tools, only. BASEDIR=/usr/share/doc VENDOR=LINOFEE, http://www.linofee.org EMAIL=developers@linofee.org CATEGORY=graphics,utils NAME=Qhull library - documentation SERIALNUM=001 VERSION=2015.2 ARCH=i386 PKG=LNFqhull-docs 0707010002161a000081a400001782000005de0000000156d3a18c00000d1b000002600000070d00000000000000000000001500000000LNFqhull-docs/pkgmap : 1 1907 1 d none libqhull 0755 bin bin 1 f none libqhull/Announce.txt 0644 bin bin 2200 63872 1453161550 1 f none libqhull/COPYING.txt 0644 bin bin 1635 954 1442974264 1 f none libqhull/Changes.txt 0644 bin bin 108516 7328 1453172541 1 f none libqhull/README.txt 0644 bin bin 21849 30394 1453161551 1 f none libqhull/REGISTER.txt 0644 bin bin 958 14475 1262532005 1 d none libqhull/include 0755 bin bin 1 f none libqhull/include/index.htm 0644 bin bin 11265 25659 1453067475 1 f none libqhull/include/qh-geom.htm 0644 bin bin 13148 16386 1453067475 1 f none libqhull/include/qh-globa.htm 0644 bin bin 7659 53657 1453067475 1 f none libqhull/include/qh-io.htm 0644 bin bin 14512 63562 1453067475 1 f none libqhull/include/qh-mem.htm 0644 bin bin 6324 59750 1453067475 1 f none libqhull/include/qh-merge.htm 0644 bin bin 15226 6367 1453067475 1 f none libqhull/include/qh-poly.htm 0644 bin bin 21150 53291 1453067475 1 f none libqhull/include/qh-qhull.htm 0644 bin bin 12777 49848 1453067475 1 f none libqhull/include/qh-set.htm 0644 bin bin 13174 65356 1453067475 1 f none libqhull/include/qh-stat.htm 0644 bin bin 7160 4777 1453067475 1 f none libqhull/include/qh-user.htm 0644 bin bin 11953 23330 1453067475 1 f none libqhull/index.htm 0644 bin bin 43293 24996 1453161551 1 f none libqhull/normal_voronoi_knauss_oesterle.jpg 0644 bin bin 23924 42759 1164160663 1 f none libqhull/qconvex.htm 0644 bin bin 27015 2977 1453067474 1 f none libqhull/qdelau_f.htm 0644 bin bin 18210 17918 1453067474 1 f none libqhull/qdelaun.htm 0644 bin bin 27331 44396 1453067474 1 f none libqhull/qh--4d.gif 0644 bin bin 4372 25068 1021248868 1 f none libqhull/qh--cone.gif 0644 bin bin 2946 53543 1021248868 1 f none libqhull/qh--dt.gif 0644 bin bin 3772 33688 1021248868 1 f none libqhull/qh--geom.gif 0644 bin bin 318 36336 1021248868 1 f none libqhull/qh--half.gif 0644 bin bin 2537 56883 1021248868 1 f none libqhull/qh--rand.gif 0644 bin bin 3875 27112 1021248868 1 f none libqhull/qh-code.htm 0644 bin bin 49978 7292 1453158134 1 f none libqhull/qh-eg.htm 0644 bin bin 30879 29080 1453067474 1 f none libqhull/qh-faq.htm 0644 bin bin 52183 32727 1453067474 1 f none libqhull/qh-get.htm 0644 bin bin 5440 46977 1453161551 1 f none libqhull/qh-impre.htm 0644 bin bin 36261 36702 1453172156 1 f none libqhull/qh-optc.htm 0644 bin bin 11952 16514 1453067474 1 f none libqhull/qh-optf.htm 0644 bin bin 31299 62955 1453067474 1 f none libqhull/qh-optg.htm 0644 bin bin 11081 16226 1453067474 1 f none libqhull/qh-opto.htm 0644 bin bin 15075 39295 1453067474 1 f none libqhull/qh-optp.htm 0644 bin bin 9755 15301 1453067474 1 f none libqhull/qh-optq.htm 0644 bin bin 32924 55120 1453172214 1 f none libqhull/qh-optt.htm 0644 bin bin 11191 23917 1453067474 1 f none libqhull/qh-quick.htm 0644 bin bin 17570 54430 1453067474 1 f none libqhull/qhalf.htm 0644 bin bin 27461 32807 1453067474 1 f none libqhull/qhull-cpp.xml 0644 bin bin 11954 38390 1453067474 1 f none libqhull/qhull.htm 0644 bin bin 19134 42004 1453067474 1 f none libqhull/qhull.txt 0644 bin bin 49490 48525 1453067474 1 f none libqhull/qvoron_f.htm 0644 bin bin 17348 63646 1453067474 1 f none libqhull/qvoronoi.htm 0644 bin bin 28094 12111 1453067474 1 f none libqhull/rbox.htm 0644 bin bin 9535 54503 1453067474 1 f none libqhull/rbox.txt 0644 bin bin 5218 34428 1453067474 1 i pkginfo 757 2045 1456710028 07070100000000000000000000000000000000000000010000000000000000000000000000000000000000000000000000000b00000000TRAILER!!! 0707010002161b000081a400001782000005de0000000156d3a18c000002f5000002600000070d00000000000000000000000800000000pkginfo CLASSES=none PSTAMP=q20160229024028 LICFILE=qhull.txt LICURL=http://www.qhull.org/COPYING.txt LICINFO=Qhull DESC=This package contains additional information for libqhull. Qhull is a general dimension code for computing convex hulls, Delaunay triangulations, halfspace intersections about a point, Voronoi diagrams, furthest-site Delaunay triangulations, and furthest-site Voronoi diagrams. These structures have applications in science, engineering, statistics, and mathematics. This package contains the shared C libraries and related tools, only. BASEDIR=/usr/share/doc VENDOR=LINOFEE, http://www.linofee.org EMAIL=developers@linofee.org CATEGORY=graphics,utils NAME=Qhull library - documentation SERIALNUM=001 VERSION=2015.2 ARCH=i386 PKG=LNFqhull-docs 0707010002161a000081a400001782000005de0000000156d3a18c00000d1b000002600000070d00000000000000000000000700000000pkgmap : 1 1907 1 d none libqhull 0755 bin bin 1 f none libqhull/Announce.txt 0644 bin bin 2200 63872 1453161550 1 f none libqhull/COPYING.txt 0644 bin bin 1635 954 1442974264 1 f none libqhull/Changes.txt 0644 bin bin 108516 7328 1453172541 1 f none libqhull/README.txt 0644 bin bin 21849 30394 1453161551 1 f none libqhull/REGISTER.txt 0644 bin bin 958 14475 1262532005 1 d none libqhull/include 0755 bin bin 1 f none libqhull/include/index.htm 0644 bin bin 11265 25659 1453067475 1 f none libqhull/include/qh-geom.htm 0644 bin bin 13148 16386 1453067475 1 f none libqhull/include/qh-globa.htm 0644 bin bin 7659 53657 1453067475 1 f none libqhull/include/qh-io.htm 0644 bin bin 14512 63562 1453067475 1 f none libqhull/include/qh-mem.htm 0644 bin bin 6324 59750 1453067475 1 f none libqhull/include/qh-merge.htm 0644 bin bin 15226 6367 1453067475 1 f none libqhull/include/qh-poly.htm 0644 bin bin 21150 53291 1453067475 1 f none libqhull/include/qh-qhull.htm 0644 bin bin 12777 49848 1453067475 1 f none libqhull/include/qh-set.htm 0644 bin bin 13174 65356 1453067475 1 f none libqhull/include/qh-stat.htm 0644 bin bin 7160 4777 1453067475 1 f none libqhull/include/qh-user.htm 0644 bin bin 11953 23330 1453067475 1 f none libqhull/index.htm 0644 bin bin 43293 24996 1453161551 1 f none libqhull/normal_voronoi_knauss_oesterle.jpg 0644 bin bin 23924 42759 1164160663 1 f none libqhull/qconvex.htm 0644 bin bin 27015 2977 1453067474 1 f none libqhull/qdelau_f.htm 0644 bin bin 18210 17918 1453067474 1 f none libqhull/qdelaun.htm 0644 bin bin 27331 44396 1453067474 1 f none libqhull/qh--4d.gif 0644 bin bin 4372 25068 1021248868 1 f none libqhull/qh--cone.gif 0644 bin bin 2946 53543 1021248868 1 f none libqhull/qh--dt.gif 0644 bin bin 3772 33688 1021248868 1 f none libqhull/qh--geom.gif 0644 bin bin 318 36336 1021248868 1 f none libqhull/qh--half.gif 0644 bin bin 2537 56883 1021248868 1 f none libqhull/qh--rand.gif 0644 bin bin 3875 27112 1021248868 1 f none libqhull/qh-code.htm 0644 bin bin 49978 7292 1453158134 1 f none libqhull/qh-eg.htm 0644 bin bin 30879 29080 1453067474 1 f none libqhull/qh-faq.htm 0644 bin bin 52183 32727 1453067474 1 f none libqhull/qh-get.htm 0644 bin bin 5440 46977 1453161551 1 f none libqhull/qh-impre.htm 0644 bin bin 36261 36702 1453172156 1 f none libqhull/qh-optc.htm 0644 bin bin 11952 16514 1453067474 1 f none libqhull/qh-optf.htm 0644 bin bin 31299 62955 1453067474 1 f none libqhull/qh-optg.htm 0644 bin bin 11081 16226 1453067474 1 f none libqhull/qh-opto.htm 0644 bin bin 15075 39295 1453067474 1 f none libqhull/qh-optp.htm 0644 bin bin 9755 15301 1453067474 1 f none libqhull/qh-optq.htm 0644 bin bin 32924 55120 1453172214 1 f none libqhull/qh-optt.htm 0644 bin bin 11191 23917 1453067474 1 f none libqhull/qh-quick.htm 0644 bin bin 17570 54430 1453067474 1 f none libqhull/qhalf.htm 0644 bin bin 27461 32807 1453067474 1 f none libqhull/qhull-cpp.xml 0644 bin bin 11954 38390 1453067474 1 f none libqhull/qhull.htm 0644 bin bin 19134 42004 1453067474 1 f none libqhull/qhull.txt 0644 bin bin 49490 48525 1453067474 1 f none libqhull/qvoron_f.htm 0644 bin bin 17348 63646 1453067474 1 f none libqhull/qvoronoi.htm 0644 bin bin 28094 12111 1453067474 1 f none libqhull/rbox.htm 0644 bin bin 9535 54503 1453067474 1 f none libqhull/rbox.txt 0644 bin bin 5218 34428 1453067474 1 i pkginfo 757 2045 1456710028 0707010002161c000041ed00001782000005de0000000356d3a18c00000000000002600000070d00000000000000000000000600000000reloc 0707010002161d000041ed00001782000005de0000000356d3a18d00000000000002600000070d00000000000000000000000f00000000reloc/libqhull 0707010002163a000081a400001782000005de00000001569d6ef60000c33a000002600000070d00000000000000000000001b00000000reloc/libqhull/qh-code.htm
Up: Home page for Qhull
Up: Qhull manual: Table of
Contents
To: Programs
Options
Output
Formats
Geomview
Print
Qhull
Precision
Trace
Functions
To: Qhull code: Table of Contents
(please wait while loading)
Dn: Qhull functions, macros, and data
structures
This section discusses the code for Qhull.
Copyright © 1995-2015 C.B. Barber
Qhull-2015 introduces reentrant Qhull (libqhull_r). Reentrant Qhull uses a qhT* argument instead of global data structures. The qhT* pointer is the first argument to most Qhull routines. It allows multiple instances of Qhull to run at the same time. It simplifies the C++ interface to Qhull.
New code should be written with libqhull_r. Existing users of libqhull should consider converting to libqhull_r. Although libqhull will be supported indefinitely, improvements may not be implemented. Reentrant qhull is 1-2% slower than non-reentrant qhull.
Note: Reentrant Qhull is not thread safe. Do not invoke Qhull routines with the same qhT* pointer from multiple threads.
C++ users need to convert to libqhull_r. The new C++ interface does a better, but not perfect, job of hiding Qhull's C data structures. The previous C++ interface was unusual due to Qhull's global data structures.
All other users should consider converting to libqhull_r. The conversion is straight forward. The original conversion of libqhull to libqhull_r required thousands of changes, mostly global search and replace. The first run of Qhull (unix_r.c) produced the same output, and nearly the same log files, as the original (unix.c).
Suggestions to help with conversion.
Qhull compiles for 64-bit hosts. Since the size of a pointer on a 64-bit host is double the size on a 32-bit host, memory consumption increases about 50% for simplicial facets and up-to 100% for non-simplicial facets.
You can check memory consumption with option Ts. It includes the size of each data structure:
For Qhull 2015, the maximum identifier for ridges, vertices, and facets was increased from 24-bits to 32-bits. This allows for larger convex hulls, but may increase the size of the corresponding data structures. The sizes for Qhull 2012.1 were
Qhull 2015 uses reentrant Qhull for its C++ interface. If you used the C++ interface from qhull 2012.1, you may need to adjust how you initialize and use the Qhull classes. See How to convert code to reentrant Qhull.
Qhull's C++ interface allows you to explore the results of running Qhull. It provides access to Qhull's data structures. Most of the classes derive from the corresponding qhull data structure. For example, QhullFacet is an instance of Qhull's facetT.
You can retain most of the data in Qhull and use the C++ interface to explore its results. Each object contains a reference the Qhull's data structure (via QhullQh), making the C++ representation less memory efficient.
Besides using the C++ interface, you can also use libqhull_r directly. For example, the FOREACHfacet_(...) macro will visit each facet in turn.
The C++ interface to Qhull is incomplete. You may need to extend the interface.
If so, you will need to understand Qhull's data structures and read the code.
Example (c.f., user_eg3 eg-100
). It prints the facets generated by Qhull.
RboxPoints rbox; rbox.appendRandomPoints("100"); Qhull qhull; qhull.runQhull("", rbox); QhullFacetList facets(qhull); cout<< facets;
The C++ iterface for RboxPoints redefines the fprintf() calls in rboxlib.c. Instead of writing its output to stdout, RboxPoints appends the output to a std::vector. The same technique may be used for calling Qhull from C++.
Since the C++ interface uses reentrant Qhull, multiple threads may run Qhull at the same time. Each thread is one run of Qhull.
Do not have two threads accessing the same Qhull instance. Qhull is not thread-safe.
A CoordinateIterator or ConstCoordinateIterator [RboxPoints.cpp] is a std::vector<realT>::iterator
for Rbox and Qhull coordinates.
It is the result type of RboxPoints.coordinates().
Qhull does not use CoordinateIterator for its data structures. A point in Qhull is an array of reals instead of a std::vector. See QhullPoint.
Qhull is the top-level class for running Qhull. It initializes Qhull, runs the computation, and records errors. It provides access to the global data structure QhullQh, Qhull's facets, and vertices.
QhullError is derived from std::exception
. It reports errors from Qhull and captures the output to stderr.
If error handling is not set up, Qhull exits with a code from 1 to 5. The codes are defined by qh_ERR* in libqhull_r.h. The exit is via qh_exit() in usermem_r.c. The C++ interface does not report the captured output in QhullError. Call Qhull::setErrorStream to send output to cerr instead.
A QhullFacet is a facet of the convex hull, a region of the Delaunay triangulation, a vertex of a Voronoi diagram, or an intersection of the halfspace intersection about a point. A QhullFacet has a set of QhullVertex, a set of QhullRidge, and a set of neighboring QhullFacets.
A QhullFacetList is a linked list of QhullFacet. The result of Qhull.runQhull
is a QhullFacetList stored
in QhullQh.
A QhullFacetSet is a QhullSet of QhullFacet. QhullFacetSet may be ordered or unordered. The neighboring facets of a QhullFacet is a QhullFacetSet. The neighbors of a QhullFacet is a QhullFacetSet. The neighbors are ordered for simplicial facets, matching the opposite vertex of the facet.
QhullIterator contains macros for defining Java-style iterator templates from a STL-style iterator template.
A QhullLinkedLIst is a template for linked lists with next and previous pointers. QhullFacetList and QhullVertexList are QhullLinkedLists.
A QhullPoint is an array of point coordinates, typically doubles. The length of the array is QhullQh.hull_dim. The identifier of a QhullPoint is its 0-based index from QhullQh.first_point followed by QhullQh.other_points.
A QhullPointSet is a QhullSet of QhullPoint. The QhullPointSet of a QhullFacet is its coplanar points.
QhullQh is the root of Qhull's data structure. It contains initialized constants, sets, buffers, and variables. It contains an array and a set of QhullPoint, a list of QhullFacet, and a list of QhullVertex. The points are the input to Qhull. The facets and vertices are the result of running Qhull.
Qhull's functions access QhullQh through the global variable, qh_qh
.
The global data structures, qh_stat and qh_mem, record statistics and manage memory respectively.
A QhullRidge represents the edge between two QhullFacet's. It is always simplicial with qh.hull_dim-1 QhullVertex)'s.
A QhullRidgeSet is a QhullSet of QhullRidge. Each QhullFacet contains a QhullRidgeSet.
A QhullSet is a set of pointers to objects. QhullSets may be ordered or unordered. They are the core data structure for Qhull.
A QhullVertex is a vertex of the convex hull. A simplicial QhullFacet has qh.hull_dim-1 vertices. A QhullVertex contains a QhullPoint. It may list its neighboring QhullFacet's.
A QhullVertexList is a QhullLinkedList of QhullVertex. The global data structure, QhullQh contains a QhullVertexList of all the vertices.
A QhullVertexSet is a QhullSet of QhullVertex. The QhullVertexSet of a QhullFacet is the vertices of the facet. It is ordered for simplicial facets and unordered for non-simplicial facets.
RboxPoints is a std::vector of point coordinates (QhullPoint). It's iterator is CoordinateIterator.
RboxPoints.appendRandomPoints()
appends points from a variety of distributions such as uniformly distributed within a cube and random points on a sphere.
It can also append a cube's vertices or specific points.
iterator Coordinates::operator++() { return iterator(++i); }
reference operator[](difference_type _Off) const
iterator &operator++() { return iterator(i++); }
Warning: Qhull was not designed for calling from C programs. You may find the C++ interface easier to use. You will need to understand the data structures and read the code. Most users will find it easier to call Qhull as an external command.
For examples of calling Qhull, see GNU Octave's computational geometry code, and Qhull's user_eg_r.c, user_eg2_r.c, and user_r.c. To see how Qhull calls its library, read unix_r.c, qconvex.c, qdelaun.c, qhalf.c, and qvoronoi.c. The '*_r.c' files are reentrant, otherwise they are non-reentrant. Either version may be used. New code should use reentrant Qhull.
See Reentrant Qhull functions, macros, and data structures for internal documentation of Qhull. The documentation provides an overview and index. To use the library you will need to read and understand the code. For most users, it is better to write data to a file, call the qhull program, and read the results from the output file.
If you use non-reentrant Qhull, be aware of the macros "qh" and "qhstat", e.g., "qh hull_dim". They are defined in libqhull.h. They allow the global data structures to be pre-allocated (faster access) or dynamically allocated (allows multiple copies).
Qhull's Makefile produces a library, libqhull_r.a, for inclusion in your programs. First review libqhull_r.h. This defines the data structures used by Qhull and provides prototypes for the top-level functions. Most users will only need libqhull_r.h in their programs. For example, the Qhull program is defined with libqhull_r.h and unix_r.c. To access all functions, use qhull_ra.h. Include the file with "#include <libqhull_r/qhull_ra.h>". This avoids potential name conflicts.
If you use the Qhull library, you are on your own as far as bugs go. Start with small examples for which you know the output. If you get a bug, try to duplicate it with the Qhull program. The 'Tc' option will catch many problems as they occur. When an error occurs, use 'T4 TPn' to trace from the last point added to the hull. Compare your trace with the trace output from the Qhull program.
Errors in the Qhull library are more likely than errors in the Qhull program. These are usually due to feature interactions that do not occur in the Qhull program. Please report all errors that you find in the Qhull library. Please include suggestions for improvement.
Qhull sends output to qh.fout and errors, log messages, and summaries to qh.ferr. qh.fout is normally stdout and qh.ferr is stderr. qh.fout may be redefined by option 'TO' or the caller. qh.ferr may be redirected to qh.fout by option 'Tz'.
Qhull does not use stderr, stdout, fprintf(), or exit() directly.
Qhull reports errors via qh_errexit() by writting a message to qh.ferr and invoking longjmp(). This returns the caller to the corresponding setjmp() (c.f., QH_TRY_ in QhullQh.h). If qh_errexit() is not available, Qhull functions call qh_exit(). qh_exit() normally calls exit(), but may be redefined by the user. An example is libqhullcpp/usermem_r-cpp.cpp. It redefines qh_exit() as a 'throw'.
If qh_meminit() or qh_new_qhull() is called with ferr==NULL, then they set ferr to stderr. Otherwise the Qhull libraries use qh->ferr and qh->qhmem.ferr for error output.
If an error occurs before qh->ferr is initialized, Qhull invokes qh_fprintf_stderr(). The user may redefine this function along with qh_exit(), qh_malloc(), and qh_free().
The Qhull libraries write output via qh_fprintf() [userprintf_r.c]. Otherwise, the Qhull libraries do not use stdout, fprintf(), or printf(). Like qh_exit(), the user may redefine qh_fprintf().
You can use mem_r.c and qset_r.c individually. Mem_r.c implements quick-fit memory allocation. It is faster than malloc/free in applications that allocate and deallocate lots of memory.
Qset_r.c implements sets and related collections. It's the inner loop of Qhull, so speed is more important than abstraction. Set iteration is particularly fast. qset_r.c just includes the functions needed for Qhull.
Here some unchecked code to print the point indices of each Delaunay triangle. Use option 'QJ' if you want to avoid non-simplicial facets. Note that upper Delaunay regions are skipped. These facets correspond to the furthest-site Delaunay triangulation.
facetT *facet; vertexT *vertex, **vertexp; FORALLfacets { if (!facet->upperdelaunay) { printf ("%d", qh_setsize (facet->vertices); FOREACHvertex_(facet->vertices) printf (" %d", qh_pointid (vertex->point)); printf ("\n"); } }
The routine qh_findbestfacet in poly2_r.c is particularly useful. It uses a directed search to locate the facet that is furthest below a point. For Delaunay triangulations, this facet is the Delaunay triangle that contains the lifted point. For convex hulls, the distance of a point to the convex hull is either the distance to this facet or the distance to a subface of the facet.
Warning: If triangulated output ('Qt') and the best facet is triangulated, qh_findbestfacet() returns one of the corresponding 'tricoplanar' facets. The actual best facet may be a different tricoplanar facet.
See qh_nearvertex() in poly2.c for sample code to visit each tricoplanar facet. To identify the correct tricoplanar facet, see Devillers, et. al., ['01] and Mucke, et al ['96]. If you implement this test in general dimension, please notify qhull@qhull.org.
qh_findbestfacet performs an exhaustive search if its directed search returns a facet that is above the point. This occurs when the point is inside the hull or if the curvature of the convex hull is less than the curvature of a sphere centered at the point (e.g., a point near a lens-shaped convex hull). When the later occurs, the distance function is bimodal and a directed search may return a facet on the far side of the convex hull.
Algorithms that retain the previously constructed hulls usually avoid an exhaustive search for the best facet. You may use a hierarchical decomposition of the convex hull [Dobkin and Kirkpatrick '90].
To use qh_findbestfacet with Delaunay triangulations, lift the point to a paraboloid by summing the squares of its coordinates (see qh_setdelaunay in geom2_r.c). Do not scale the input with options 'Qbk', 'QBk', 'QbB' or 'Qbb'. See Mucke, et al ['96] for a good point location algorithm.
The intersection of a ray with the convex hull may be found by locating the facet closest to a distant point on the ray. Intersecting the ray with the facet's hyperplane gives a new point to test.
The Qhull library may be used for the on-line construction of convex hulls, Delaunay triangulations, and halfspace intersections about a point. It may be slower than implementations that retain intermediate convex hulls (e.g., Clarkson's hull program). These implementations always use a directed search. For the on-line construction of convex hulls and halfspace intersections, Qhull may use an exhaustive search (qh_findbestfacet).
You may use qh_findbestfacet and qh_addpoint (libqhull.c) to add a point to a convex hull. Do not modify the point's coordinates since qh_addpoint does not make a copy of the coordinates. For Delaunay triangulations, you need to lift the point to a paraboloid by summing the squares of the coordinates (see qh_setdelaunay in geom2.c). Do not scale the input with options 'Qbk', 'QBk', 'QbB' or 'Qbb'. Do not deallocate the point's coordinates. You need to provide a facet that is below the point (qh_findbestfacet).
You can not delete points. Another limitation is that Qhull uses the initial set of points to determine the maximum roundoff error (via the upper and lower bounds for each coordinate).
For many applications, it is better to rebuild the hull from scratch for each new point. This is especially true if the point set is small or if many points are added at a time.
Calling qh_addpoint from your program may be slower than recomputing the convex hull with qh_qhull. This is especially true if the added points are not appended to the qh first_point array. In this case, Qhull must search a set to determine a point's ID. [R. Weber]
See user_eg.c for examples of the on-line construction of convex hulls, Delaunay triangulations, and halfspace intersections. The outline is:
initialize qhull with an initial set of points qh_qhull(); for each additional point p append p to the end of the point array or allocate p separately lift p to the paraboloid by calling qh_setdelaunay facet= qh_findbestfacet (p, !qh_ALL, &bestdist, &isoutside); if (isoutside) if (!qh_addpoint (point, facet, False)) break; /* user requested an early exit with 'TVn' or 'TCn' */ call qh_check_maxout() to compute outer planes terminate qhull
With a fair amount of work, Qhull is suitable for constrained Delaunay triangulation. See Shewchuk, ACM Symposium on Computational Geometry, Minneapolis 1998.
Here's a quick way to add a constraint to a Delaunay triangulation: subdivide the constraint into pieces shorter than the minimum feature separation. You will need an independent check of the constraint in the output since the minimum feature separation may be incorrect. [H. Geron]
Option 'Qt' triangulates non-simplicial facets (e.g., a square facet in 3-d or a cubical facet in 4-d). All facets share the same apex (i.e., the first vertex in facet->vertices). For each triangulated facet, Qhull sets facet->tricoplanar true and copies facet->center, facet->normal, facet->offset, and facet->maxoutside. One of the facets owns facet->normal; its facet->keepcentrum is true. If facet->isarea is false, facet->triowner points to the owning facet.
Qhull sets facet->degenerate if the facet's vertices belong to the same ridge of the non-simplicial facet.
To visit each tricoplanar facet of a non-simplicial facet, either visit all neighbors of the apex or recursively visit all neighbors of a tricoplanar facet. The tricoplanar facets will have the same facet->center.
See qh_detvridge for an example of ignoring tricoplanar facets.
The following code iterates over all Voronoi vertices for each Voronoi region. Qhull computes Voronoi vertices from the convex hull that corresponds to a Delaunay triangulation. An input site corresponds to a vertex of the convex hull and a Voronoi vertex corresponds to an adjacent facet. A facet is "upperdelaunay" if it corresponds to a Voronoi vertex "at-infinity". Qhull uses qh_printvoronoi in io.c for 'qvoronoi o'
/* please review this code for correctness */ qh_setvoronoi_all(); FORALLvertices { site_id = qh_pointid (vertex->point); if (qh hull_dim == 3) qh_order_vertexneighbors(vertex); infinity_seen = 0; FOREACHneighbor_(vertex) { if (neighbor->upperdelaunay) { if (!infinity_seen) { infinity_seen = 1; ... process a Voronoi vertex "at infinity" ... } }else { voronoi_vertex = neighbor->center; ... your code goes here ... } } }
Qhull uses qh_printvdiagram() in io.c to print the ridges of a Voronoi diagram for option 'Fv'. The helper function qh_eachvoronoi() does the real work. It calls the callback 'printvridge' for each ridge of the Voronoi diagram.
You may call qh_printvdiagram2(), qh_eachvoronoi(), or qh_eachvoronoi_all() with your own function. If you do not need the total number of ridges, you can skip the first call to qh_printvdiagram2(). See qh_printvridge() and qh_printvnorm() in io.c for examples.
To visit all of the vertices that share an edge with a vertex:
For non-simplicial facets, the ridges form a simplicial decomposition of the (d-2)-faces between each pair of facets -- if you need 1-faces, you probably need to generate the full face graph of the convex hull.
Empirically, Qhull's performance is balanced in the sense that the average case happens on average. This may always be true if the precision of the input is limited to at most O(log n) bits. Empirically, the maximum number of vertices occurs at the end of constructing the hull.
Let n be the number of input points, v be the number of output vertices, and f_v be the maximum number of facets for a convex hull of v vertices. If both conditions hold, Qhull runs in O(n log v) in 2-d and 3-d and O(n f_v/v) otherwise. The function f_v increases rapidly with dimension. It is O(v^floor(d/2) / floor(d/2)!).
The time complexity for merging is unknown. Options 'C-0' and 'Qx' (defaults) handle precision problems due to floating-point arithmetic. They are optimized for simplicial outputs.
When running large data sets, you should monitor Qhull's performance with the 'TFn' option. The time per facet is approximately constant. In high-d with many merged facets, the size of the ridge sets grows rapidly. For example the product of 8-d simplices contains 18 facets and 500,000 ridges. This will increase the time needed per facet.
As dimension increases, the number of facets and ridges in a convex hull grows rapidly for the same number of vertices. For example, the convex hull of 300 cospherical points in 6-d has 30,000 facets.
If Qhull appears to stop processing facets, check the memory usage of Qhull. If more than 5-10% of Qhull is in virtual memory, its performance will degrade rapidly.
When building hulls in 20-d and higher, you can follow the progress of Qhull with option 'T1'. It reports each major event in processing a point.
To reduce memory requirements, recompile Qhull for single-precision reals (REALfloat in user.h). Single-precision does not work with joggle ('QJ'). Check qh_MEMalign in user.h and the match between free list sizes and data structure sizes (see the end of the statistics report from 'Ts'). If free list sizes do not match, you may be able to use a smaller qh_MEMalign. Setting qh_COMPUTEfurthest saves a small amount of memory, as does clearing qh_MAXoutside (both in user.h).
Shewchuk is working on a 3-d version of his triangle program. It is optimized for 3-d simplicial Delaunay triangulation and uses less memory than Qhull.
To reduce the size of the Qhull executable, consider qh_NOtrace and qh_KEEPstatistics 0 in user.h. By changing user.c you can also remove the input/output code in io.c. If you don't need facet merging, then version 1.01 of Qhull is much smaller. It contains some bugs that prevent Qhull from initializing in simple test cases. It is slower in high dimensions.
The precision options, 'Vn', 'Wn', 'Un'. 'A-n', 'C-n', 'An', 'Cn', and 'Qx', may have large effects on Qhull performance. You will need to experiment to find the best combination for your application.
The verify option ('Tv') checks every point after the hull is complete. If facet merging is used, it checks that every point is inside every facet. This can take a very long time if there are many points and many facets. You can interrupt the verify without losing your output. If facet merging is not used and there are many points and facets, Qhull uses a directed search instead of an exhaustive search. This should be fast enough for most point sets. Directed search is not used for facet merging because directed search was already used for updating the facets' outer planes.
The check-frequently option ('Tc') becomes expensive as the dimension increases. The verify option ('Tv') performs many of the same checks before outputting the results.
Options 'Q0' (no pre-merging), 'Q3' (no checks for redundant vertices), 'Q5' (no updates for outer planes), and 'Q8' (no near-interior points) increase Qhull's speed. The corresponding operations may not be needed in your application.
In 2-d and 3-d, a partial hull may be faster to produce. Option 'QgGn' only builds facets visible to point n. Option 'QgVn' only builds facets that contain point n. In higher-dimensions, this does not reduce the number of facets.
User.h includes a number of performance-related constants. Changes may improve Qhull performance on your data sets. To understand their effect on performance, you will need to read the corresponding code.
GNU gprof reports that the dominate cost for 3-d convex hull of cosperical points is qh_distplane(), mainly called from qh_findbestnew(). The dominate cost for 3-d Delaunay triangulation is creating new facets in qh_addpoint(), while qh_distplane() remains the most expensive function.
There are many ways in which Qhull can be improved.
[Jan 2015] Suggestions ------------ To do for a future verson of Qhull - Add a merge pass before cone creation to remove duplicate subridges between horizon facets - Option to add a bounding box for Delaunay triangulations, e,g., nearly coincident points - Report error when rbox Cn,r,m does not produce points (e.g., 'r' distributions) - Rescale output to match 'QbB' on input [J. Metz, 1/30/2014 12:21p] - Run through valgrind - Notes to compgeom on conformant triangulation and Voronoi volume - Git: Create signed tags for Qhull versions - Implement weighted Delaunay triangulation and weighted Voronoi diagram [A. Liebscher] e.g., Sugihara, "Three-dimensional convex hull as a fruitful source of diagrams," Theoretical Computer Science, 2000, 235:325-337 - testqset: test qh_setdelnth and move-to-front - Makefile: Re-review gcc/g++ warnings. OK in 2011. - Break up -Wextra into its components or figure out how to override -Wunused-but-set-variable unused-but-set-variable is reporting incorrectly. All instances are annotated. - CMakelists.txt: Why are files duplicated for cmake build - CMakeLists.txt: configure the 'ctest' target - The size of maxpoints in qh_maxsimplex should be d+3 unique points to help avoid QH6154 - Can countT be defined as 'int', 'unsigned int', or 64-bit int? countT is currently defined as 'int' in qset_r.h Vertex ID and ridge ID perhaps should be countT, They are currently 'unsigned' Check use of 'int' vs. countT in all cpp code Check use of 'int' vs. countT in all c code qset_r.h defines countT -- duplicates code in user_r.h -- need to add to qset.h/user.h countT -1 used as a flag in Coordinates.mid(), QhullFacet->id() Also QhullPoints indexOf and lastIndexOf Also QhullPointSet indexOf and lastIndexOf Coordinates.indexOf assumes countT is signed (from end) Coordinates.lastIndexOf assumes countT is signed (from end) All error messages with countT are wrong, convert to int? RboxPoints.qh_fprintf_rbox, etc. message 9393 assumes countT but may be int, va_arg(args, countT); Need to split ------------ To do for a furture version of the C++ interface - Fix C++ memory leak in user_eg3 [M. Sandim] - Document C++ using Doxygen conventions (//! and //!<) - Should Qhull manage the output formats for doubles? QH11010 user_r.h defines qh_REAL_1 as %6.8g - Allocate memory for QhullSet using Qhull.qhmem. Create default constructors for QhullVertexSet etc. Also mid() etc. - Add interior point for automatic translation? - Add hasNext() to all next() iterators (e.g., QhullVertex) - Add defineAs() to each object - Write a program with concurrent Qhull - Write QhullStat and QhullStat_test - Add QList and vector instance of facetT*, etc. - Generalize QhullPointSetIterator - qh-code.htm: Document changes to C++ interface. Organize C++ documentation into collection classes, etc. - Review all C++ classes and C++ tests - QhullVertexSet uses QhullSetBase::referenceSetT() to free it's memory. Probably needed elsewhere - The Boost Graph Library provides C++ classes for graph data structures. It may help enhance Qhull's C++ interface [Dr. Dobb's 9/00 p. 29-38; OOPSLA '99 p. 399-414]. [Jan 2010] Suggestions - Generate vcproj from qtpro files cd qtpro && qmake -spec win32-msvc2005 -tp vc -recursive sed -i 's/C\:\/bash\/local\/qhull\/qtpro\///' qhull-all.sln Change qhullcpp to libqhull.dll Allow both builds on same host (keep /tmp separate) - Make distribution -- remove tmp, news, .git, leftovers from project, change CRLF search for 2010.1, Dates qhulltest --all added to output Add md5sum Add test of user_eg3, etc. - C++ class for access to statistics, accumulate vs. add - Add dialog box to RoadError-- a virtual function? - Option 'Gt' does not make visible all facets of the mesh example, rbox 32 M1,0,1 | qhull d Gt - Option to select bounded Voronoi regions [A. Uzunovic] - Merge small volume boundary cells into unbounded regions [Dominik Szczerba] - Postmerge with merge options - Add const to C code - Add modify operators and MutablePointCoordinateIterator to PointCoordinates - Add Qtest::toString() functions for QhullPoint and others. QByteArray and qstrdup() - Fix option Qt for conformant triangulations of merged facets - Investigate flipped facet -- rbox 100 s D3 t1263080158 | qhull R1e-3 Tcv Qc - Add doc comments to c++ code - Measure performance of Qhull, seconds per point by dimension - Report potential wraparound of 64-bit ints -- e.g., a large set or points Documentation - Qhull::addPoint(). Problems with qh_findbestfacet and otherpoints see qh-code.htm#inc on-line construction with qh_addpoint() - How to handle 64-bit possible loss of data. WARN64, ptr_intT, size_t/int - Show custom of qh_fprintf - grep 'qh_mem ' x | sort | awk '{ print $2; }' | uniq -c | grep -vE ' (2|4|6|8|10|12|14|16|20|64|162)[^0-9]' - qtpro/qhulltest contains .pro and Makefile. Remove Makefiles by setting shadow directory to ../../tmp/projectname - Rules for use of qh_qh and multi processes UsingQhull errorIfAnotherUser ~QhullPoints() needs ownership of qh_qh Does !qh_pointer work? When is qh_qh required? Minimize the time. qhmem, qhstat.ferr qhull_inuse==1 when qhull globals active [not useful?] rbox_inuse==1 when rbox globals active - Multithreaded -- call largest dimension for infinityPoint() and origin() - Better documentation for qhmem totshort, freesize, etc. - how to change .h, .c, and .cpp to text/html. OK in Opera - QhullVertex.dimension() is not quite correct, epensive - Check globalAngleEpsilon - Deprecate save_qhull() [Dec 2003] Here is a partial list: - fix finddelaunay() in user_eg.c for tricoplanar facets - write a BGL, C++ interface to Qhull http://www.boost.org/libs/graph/doc/table_of_contents.html - change qh_save_qhull to swap the qhT structure instead of using pointers - change error handling and tracing to be independent of 'qh ferr' - determine the maximum width for a given set of parameters - prove that directed search locates all coplanar facets - in high-d merging, can a loop of facets become disconnected? - find a way to improve inner hulls in 5-d and higher - determine the best policy for facet visibility ('Vn') - determine the limitations of 'Qg' Precision improvements: - For 'Qt', resolve cross-linked, butterfly ridges. May allow retriangulation in qh_addpoint(). - for Delaunay triangulations ('d' or 'v') under joggled input ('QJ'), remove vertical facets whose lowest vertex may be coplanar with convex hull - review use of 'Qbb' with 'd QJ'. Is MAXabs_coord better than MAXwidth? - check Sugihara and Iri's better in-sphere test [Canadian Conf. on Comp. Geo., 1989; Univ. of Tokyo RMI 89-05] - replace centrum with center of mass and facet area - handle numeric overflow in qh_normalize and elsewhere - merge flipped facets into non-flipped neighbors. currently they merge into best neighbor (appears ok) - determine min norm for Cramer's rule (qh_sethyperplane_det). It looks high. - improve facet width for very narrow distributions New features: - implement Matlab's tsearch() using Qhull - compute volume of Voronoi regions. You need to determine the dual face graph in all dimensions [see Clarkson's hull program] - compute alpha shapes [see Clarkson's hull program] - implement deletion of Delaunay vertices see Devillers, ACM Symposium on Computational Geometry, Minneapolis 1999. - compute largest empty circle [see O'Rourke, chapter 5.5.3] [Hase] - list redundant (i.e., coincident) vertices [Spitz] - implement Mucke, et al, ['96] for point location in Delaunay triangulations - implement convex hull of moving points - implement constrained Delaunay diagrams see Shewchuk, ACM Symposium on Computational Geometry, Minneapolis 1998. - estimate outer volume of hull - automatically determine lower dimensional hulls - allow "color" data for input points need to insert a coordinate for Delaunay triangulations Input/output improvements: - Support the VTK Visualization Toolkit, http://www.kitware.com/vtk.html - generate output data array for Qhull library [Gautier] - need improved DOS window with screen fonts, scrollbar, cut/paste - generate Geomview output for Voronoi ridges and unbounded rays - generate Geomview output for halfspace intersection - generate Geomview display of furthest-site Voronoi diagram - use 'GDn' to view 5-d facets in 4-d - convert Geomview output for other 3-d viewers - add interactive output option to avoid recomputing a hull - orient vertex neighbors for 'Fv' in 3-d and 2-d - track total number of ridges for summary and logging Performance improvements: - optimize Qhull for 2-d Delaunay triangulations - use O'Rourke's '94 vertex->duplicate_edge - add bucketing - better to specialize all of the code (ca. 2-3x faster w/o merging) - use updated LU decomposition to speed up hyperplane construction - [Gill et al. 1974, Math. Comp. 28:505-35] - construct hyperplanes from the corresponding horizon/visible facets - for merging in high d, do not use vertex->neighbors
Please let us know about your applications and improvements.
Up: Home
page for Qhull
Up: Qhull manual: Table of
Contents
To: Programs
Options
Output
Formats
Geomview
Print
Qhull
Precision
Trace
Functions
To: Qhull code: Table of Contents
Dn: Qhull functions, macros, and data
structures
Comments to: qhull@qhull.org
Created: Sept. 25, 1995 --- Last modified: see changes.txt
[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 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 The Voronoi diagram is the nearest-neighbor map for a set of
points. Each region contains those points that are nearer
one input site than any other input site. It has many useful properties and applications. See the
survey article by Aurenhammer ['91]
and the detailed introduction by O'Rourke ['94]. The Voronoi diagram is the
dual of the Delaunay triangulation. Qhull computes the Voronoi diagram via the Delaunay
triangulation. Each Voronoi
vertex is the circumcenter of a facet of the Delaunay
triangulation. Each Voronoi region corresponds to a vertex (i.e., input site) of the
Delaunay triangulation. Qhull outputs the Voronoi vertices for each Voronoi region. With
option 'Fv',
it lists all ridges of the Voronoi diagram with the corresponding
pairs of input sites. With
options 'Fi' and 'Fo',
it lists the bounded and unbounded separating hyperplanes.
You can also output a single Voronoi region
for further processing [see graphics]. Use option 'Qz' if the input is circular, cospherical, or
nearly so. It improves precision by adding a point "at infinity," above the corresponding paraboloid.
See Qhull FAQ - Delaunay and
Voronoi diagram questions. The 'qvonoroi' program is equivalent to
'qhull v Qbb' in 2-d to 3-d, and
'qhull v Qbb Qx'
in 4-d and higher. It disables the following Qhull
options: d n v Qbb QbB Qf Qg Qm
Qr QR Qv Qx Qz TR E V Fa FA FC FD FS Ft FV Gt Q0,etc.
Copyright © 1995-2015 C.B. Barber Voronoi image by KOOK Architecture, Silvan Oesterle and Michael Knauss.
Use I/O redirection (e.g., qvoronoi < data.txt), a pipe (e.g., rbox 10 | qvoronoi),
or the 'TI' option (e.g., qvoronoi TI data.txt).
For example, this is four cocircular points inside a square. Their Voronoi
diagram has nine vertices and eight regions. Notice the Voronoi vertex
at the origin, and the Voronoi vertices (on each axis) for the four
sides of the square.
qvoronoi s p < data
These options control the output of Voronoi diagrams. These options provide additional control: In 2-d, Geomview output ('G')
displays a Voronoi diagram with extra edges to close the
unbounded Voronoi regions. To view the unbounded rays, enclose
the input points in a square. You can also view individual Voronoi regions in 3-d. To
view the Voronoi region for site 3 in Geomview, execute The qvoronoi command returns the Voronoi vertices
for input site 3. The qconvex command computes their convex hull.
This is the Voronoi region for input site 3. Its
hyperplane normals (qconvex 'n') are the same as the separating hyperplanes
from options 'Fi'
and 'Fo' (up to roundoff error).
See the Delaunay and Voronoi
examples for 2-d and 3-d examples. Turn off normalization (on
Geomview's 'obscure' menu) when comparing the Voronoi diagram
with the corresponding Delaunay triangulation. You can simplify the Voronoi diagram by enclosing the input
sites in a large square or cube. This is particularly recommended
for cocircular or cospherical input data. See Voronoi graphics for computing
the convex hull of a Voronoi region. Voronoi diagrams do not include facets that are
coplanar with the convex hull of the input sites. A facet is
coplanar if the last coefficient of its normal is
nearly zero (see qh_ZEROdelaunay).
Unbounded regions can be confusing. For example, 'rbox c |
qvoronoi Qz o' produces the Voronoi regions for the vertices
of a cube centered at the origin. All regions are unbounded. The
output is The first line is the dimension. The second line is the number
of vertices and the number of regions. There is one region per
input point plus a region for the point-at-infinity added by
option 'Qz'. The next two lines
lists the Voronoi vertices. The first vertex is the infinity
vertex. It is indicate by the coordinates -10.101. The
second vertex is the origin. The next nine lines list the
regions. Each region lists two vertices -- the infinity vertex
and the origin. The last line is "0" because no region
is associated with the point-at-infinity. A "0" would
also be listed for nearly incident input sites. To use option 'Fv', add an
interior point. For example, The output consists of 20 ridges and each ridge lists a pair
of input sites and a triplet of Voronoi vertices. The first eight
ridges connect the origin ('P0'). The remainder list the edges of
the cube. Each edge generates an unbounded ray through the
midpoint. The corresponding separating planes ('Fo') follow each
pair of coordinate axes. Options 'Qt' (triangulated output)
and 'QJ' (joggled input) are deprecated. They may produce
unexpected results. If you use these options, cocircular and cospherical input sites will
produce duplicate or nearly duplicate Voronoi vertices. See also Merged facets or joggled input. The following terminology is used for Voronoi diagrams in
Qhull. The underlying structure is a Delaunay triangulation from
a convex hull in one higher dimension. Facets of the Delaunay
triangulation correspond to vertices of the Voronoi diagram.
Vertices of the Delaunay triangulation correspond to input sites.
They also correspond to regions of the Voronoi diagram. See convex hull conventions, Delaunay conventions, and
Qhull's data structures. Up: Home page for Qhull Comments to: qhull@qhull.org
The furthest-site Voronoi diagram is the furthest-neighbor map for a set of
points. Each region contains those points that are further
from one input site than any other input site. See the
survey article by Aurenhammer ['91]
and the brief introduction by O'Rourke ['94]. The furthest-site Voronoi diagram is the dual of the furthest-site Delaunay triangulation.
Qhull computes the furthest-site Voronoi diagram via the
furthest-site Delaunay triangulation.
Each furthest-site Voronoi vertex is the circumcenter of an upper
facet of the Delaunay triangulation. Each furthest-site Voronoi
region corresponds to a vertex of the Delaunay triangulation
(i.e., an input site). See Qhull FAQ - Delaunay and
Voronoi diagram questions. The 'qvonoroi' program is equivalent to
'qhull v Qbb' in 2-d to 3-d, and
'qhull v Qbb Qx'
in 4-d and higher. It disables the following Qhull
options: d n m v H U Qb
QB Qc Qf Qg Qi Qm Qr QR Qv Qx TR E V Fa FA FC Fp FS Ft FV Gt Q0,etc.
Copyright © 1995-2015 C.B. Barber The input data on stdin consists of: Use I/O redirection (e.g., qvoronoi Qu < data.txt), a pipe (e.g., rbox 10 | qvoronoi Qu),
or the 'TI' option (e.g., qvoronoi TI data.txt Qu).
For example, this is a square containing four random points.
Its furthest-site Voronoi diagram has on vertex and four unbounded,
separating hyperplanes (i.e., the coordinate axes)
qvoronoi Qu s Fo < data
These options control the output of furthest-site Voronoi diagrams. These options provide additional control: In 2-d, Geomview output ('G')
displays a furthest-site Voronoi diagram with extra edges to
close the unbounded furthest-site Voronoi regions. All regions
will be unbounded. Since the points-in-box example has only
one furthest-site Voronoi vertex, the Geomview output is one
point. See the Delaunay and Voronoi
examples for a 2-d example. Turn off normalization (on
Geomview's 'obscure' menu) when comparing the furthest-site
Voronoi diagram with the corresponding Voronoi diagram. See Voronoi notes. The following terminology is used for furthest-site Voronoi
diagrams in Qhull. The underlying structure is a furthest-site
Delaunay triangulation from a convex hull in one higher
dimension. Upper facets of the Delaunay triangulation correspond
to vertices of the furthest-site Voronoi diagram. Vertices of the
furthest-site Delaunay triangulation correspond to input sites.
They also define regions of the furthest-site Voronoi diagram.
All vertices are extreme points of the input sites. See qconvex conventions, furthest-site delaunay
conventions, and Qhull's data structures. Up: Home page for Qhull Comments to: qhull@qhull.org
The convex hull of a set of points is the smallest convex set
containing the points. See the detailed introduction by O'Rourke
['94]. See Description of Qhull and How Qhull adds a point. Except for rbox, all of the qhull programs compute a convex hull.
By default, Qhull merges coplanar facets. For example, the convex
hull of a cube's vertices has six facets.
If you use 'Qt' (triangulated output),
all facets will be simplicial (e.g., triangles in 2-d). For the cube
example, it will have 12 facets. Some facets may be
degenerate and have zero area.
If you use 'QJ' (joggled input),
all facets will be simplicial. The corresponding vertices will be
slightly perturbed and identical points will be joggled apart.
Joggled input is less accurate that triangulated
output.See Merged facets or joggled input. The output for 4-d convex hulls may be confusing if the convex
hull contains non-simplicial facets (e.g., a hypercube). See
Why
are there extra points in a 4-d or higher convex hull?
Up: Qhull manual: Table of Contents
To: Programs
Options
Output
Formats
Geomview
Print
Qhull
Precision
Trace
Functions
To: synopsis
input outputs
controls graphics
notes conventions
options
qvoronoi -- Voronoi diagram
»qvoronoi synopsis
qvoronoi- compute the Voronoi diagram.
input (stdin): dimension, number of points, point coordinates
comments start with a non-numeric character
options (qh-voron.htm):
Qu - compute furthest-site Voronoi diagram
Tv - verify result: structure, convexity, and in-circle test
. - concise list of all options
- - one-line description of all options
output options (subset):
s - summary of results (default)
p - Voronoi vertices
o - OFF file format (dim, Voronoi vertices, and Voronoi regions)
FN - count and Voronoi vertices for each Voronoi region
Fv - Voronoi diagram as Voronoi vertices between adjacent input sites
Fi - separating hyperplanes for bounded regions, 'Fo' for unbounded
G - Geomview output (2-d only)
QVn - Voronoi vertices for input point n, -n if not
TO file- output results to file, may be enclosed in single quotes
examples:
rbox c P0 D2 | qvoronoi s o rbox c P0 D2 | qvoronoi Fi
rbox c P0 D2 | qvoronoi Fo rbox c P0 D2 | qvoronoi Fv
rbox c P0 D2 | qvoronoi s Qu Fv rbox c P0 D2 | qvoronoi Qu Fo
rbox c G1 d D2 | qvoronoi s p rbox c P0 D2 | qvoronoi s Fv QV0
»qvoronoi input
The input data on stdin consists of:
rbox s 4 W0 c G1 D2 > data
2 RBOX s 4 W0 c D2
8
-0.4941988586954018 -0.07594397977563715
-0.06448037284989526 0.4958248496365813
0.4911154367094632 0.09383830681375946
-0.348353580869097 -0.3586778257652367
-1 -1
-1 1
1 -1
1 1
Voronoi diagram by the convex hull of 8 points in 3-d:
Number of Voronoi regions: 8
Number of Voronoi vertices: 9
Number of non-simplicial Voronoi vertices: 1
Statistics for: RBOX s 4 W0 c D2 | QVORONOI s p
Number of points processed: 8
Number of hyperplanes created: 18
Number of facets in hull: 10
Number of distance tests for qhull: 33
Number of merged facets: 2
Number of distance tests for merging: 102
CPU seconds to compute hull (after input): 0.094
2
9
4.217546450968612e-17 1.735507986399734
-8.402566836762659e-17 -1.364368854147395
0.3447488772716865 -0.6395484723719818
1.719446929853986 2.136555906154247e-17
0.4967882915039657 0.68662371396699
-1.729928876283549 1.343733067524222e-17
-0.8906163241424728 -0.4594150543829102
-0.6656840313875723 0.5003013793414868
-7.318364664277155e-19 -1.188217818408333e-16
» qvoronoi
outputs
» qvoronoi
controls
» qvoronoi
graphics
»qvoronoi
notes
3
2 9 1
-10.101 -10.101 -10.101
0 0 0
2 0 1
2 0 1
2 0 1
2 0 1
2 0 1
2 0 1
2 0 1
2 0 1
0
rbox c P0 | qvoronoi Fv
20
5 0 7 1 3 5
5 0 3 1 4 5
5 0 5 1 2 3
5 0 1 1 2 4
5 0 6 2 3 6
5 0 2 2 4 6
5 0 4 4 5 6
5 0 8 5 3 6
5 1 2 0 2 4
5 1 3 0 1 4
5 1 5 0 1 2
5 2 4 0 4 6
5 2 6 0 2 6
5 3 4 0 4 5
5 3 7 0 1 5
5 4 8 0 6 5
5 5 6 0 2 3
5 5 7 0 1 3
5 6 8 0 6 3
5 7 8 0 3 5
»qvoronoi conventions
»qvoronoi options
qvoronoi- compute the Voronoi diagram
http://www.qhull.org
input (stdin):
first lines: dimension and number of points (or vice-versa).
other lines: point coordinates, best if one point per line
comments: start with a non-numeric character
options:
Qu - compute furthest-site Voronoi diagram
Qhull control options:
QJn - randomly joggle input in range [-n,n]
Qs - search all points for the initial simplex
Qz - add point-at-infinity to Voronoi diagram
QGn - Voronoi vertices if visible from point n, -n if not
QVn - Voronoi vertices for input point n, -n if not
Trace options:
T4 - trace at level n, 4=all, 5=mem/gauss, -1= events
Tc - check frequently during execution
Ts - statistics
Tv - verify result: structure, convexity, and in-circle test
Tz - send all output to stdout
TFn - report summary when n or more facets created
TI file - input data from file, no spaces or single quotes
TO file - output results to file, may be enclosed in single quotes
TPn - turn on tracing when point n added to hull
TMn - turn on tracing at merge n
TWn - trace merge facets when width > n
TVn - stop qhull after adding point n, -n for before (see TCn)
TCn - stop qhull after building cone for point n (see TVn)
Precision options:
Cn - radius of centrum (roundoff added). Merge facets if non-convex
An - cosine of maximum angle. Merge facets if cosine > n or non-convex
C-0 roundoff, A-0.99/C-0.01 pre-merge, A0.99/C0.01 post-merge
Rn - randomly perturb computations by a factor of [1-n,1+n]
Wn - min facet width for non-coincident point (before roundoff)
Output formats (may be combined; if none, produces a summary to stdout):
s - summary to stderr
p - Voronoi vertices
o - OFF format (dim, Voronoi vertices, and Voronoi regions)
i - Delaunay regions (use 'Pp' to avoid warning)
f - facet dump
More formats:
Fc - count plus coincident points (by Voronoi vertex)
Fd - use cdd format for input (homogeneous with offset first)
FD - use cdd format for output (offset first)
FF - facet dump without ridges
Fi - separating hyperplanes for bounded Voronoi regions
FI - ID for each Voronoi vertex
Fm - merge count for each Voronoi vertex (511 max)
Fn - count plus neighboring Voronoi vertices for each Voronoi vertex
FN - count and Voronoi vertices for each Voronoi region
Fo - separating hyperplanes for unbounded Voronoi regions
FO - options and precision constants
FP - nearest point and distance for each coincident point
FQ - command used for qvoronoi
Fs - summary: #int (8), dimension, #points, tot vertices, tot facets,
for output: #Voronoi regions, #Voronoi vertices,
#coincident points, #non-simplicial regions
#real (2), max outer plane and min vertex
Fv - Voronoi diagram as Voronoi vertices between adjacent input sites
Fx - extreme points of Delaunay triangulation (on convex hull)
Geomview options (2-d only)
Ga - all points as dots
Gp - coplanar points and vertices as radii
Gv - vertices as spheres
Gi - inner planes only
Gn - no planes
Go - outer planes only
Gc - centrums
Gh - hyperplane intersections
Gr - ridges
GDn - drop dimension n in 3-d and 4-d output
Print options:
PAn - keep n largest Voronoi vertices by 'area'
Pdk:n - drop facet if normal[k] <= n (default 0.0)
PDk:n - drop facet if normal[k] >= n
Pg - print good Voronoi vertices (needs 'QGn' or 'QVn')
PFn - keep Voronoi vertices whose 'area' is at least n
PG - print neighbors of good Voronoi vertices
PMn - keep n Voronoi vertices with most merges
Po - force output. If error, output neighborhood of facet
Pp - do not report precision problems
. - list of all options
- - one line descriptions of all options
Up: Qhull manual: Table of Contents
To: Programs
Options
Output
Formats
Geomview
Print
Qhull
Precision
Trace
Functions
To: synopsis
input outputs
controls graphics
notes conventions
options
Created: Sept. 25, 1995 --- Last modified: see top
Up: Qhull manual: Table of Contents
To: Programs
Options
Output
Formats
Geomview
Print
Qhull
Precision
Trace
Functions
To: synopsis
input outputs
controls graphics
notes conventions
options
qvoronoi Qu -- furthest-site Voronoi diagram
»furthest-site qvoronoi synopsis
See qvoronoi synopsis. The same
program is used for both constructions. Use option 'Qu'
for furthest-site Voronoi diagrams.
»furthest-site qvoronoi
input
rbox c 4 D2 > data
2 RBOX c 4 D2
8
-0.4999921736307369 -0.3684622117955817
0.2556053225468894 -0.0413498678629751
0.0327672376602583 -0.2810408135699488
-0.452955383763607 0.17886471718444
-0.5 -0.5
-0.5 0.5
0.5 -0.5
0.5 0.5
Furthest-site Voronoi vertices by the convex hull of 8 points in 3-d:
Number of Voronoi regions: 8
Number of Voronoi vertices: 1
Number of non-simplicial Voronoi vertices: 1
Statistics for: RBOX c 4 D2 | QVORONOI Qu s Fo
Number of points processed: 8
Number of hyperplanes created: 20
Number of facets in hull: 11
Number of distance tests for qhull: 34
Number of merged facets: 1
Number of distance tests for merging: 107
CPU seconds to compute hull (after input): 0
4
5 4 5 0 1 0
5 4 6 1 0 0
5 5 7 1 0 0
5 6 7 0 1 0
» furthest-site qvoronoi
outputs
» furthest-site qvoronoi
controls
» furthest-site qvoronoi
graphics
»furthest-site qvoronoi
notes
»furthest-site qvoronoi conventions
»furthest-site qvoronoi options
See qvoronoi options. The same
program is used for both constructions. Use option 'Qu'
for furthest-site Voronoi diagrams.
Up: Qhull manual: Table of Contents
To: Programs
Options
Output
Formats
Geomview
Print
Qhull
Precision
Trace
Functions
To: synopsis
input outputs
controls graphics
notes conventions
options
Created: Sept. 25, 1995 --- Last modified: see top
Up: Qhull manual -- Table of Contents
To: Programs
Options
Output
Formats
Geomview
Print
Qhull
Precision
Trace
Functions
To: synopsis
input outputs
controls graphics
notes conventions
options
qconvex -- convex hull
The 'qconvex' program is equivalent to 'qhull' in 2-d to 4-d, and 'qhull Qx' in 5-d and higher. It disables the following Qhull options: d v H Qbb Qf Qg Qm Qr Qu Qv Qx Qz TR E V Fp Gt Q0,etc.
Copyright © 1995-2015 C.B. Barber
qconvex- compute the convex hull. input (stdin): dimension, number of points, point coordinates comments start with a non-numeric character options (qconvex.htm): Qt - triangulated output QJ - joggle input instead of merging facets Tv - verify result: structure, convexity, and point inclusion . - concise list of all options - - one-line description of all options output options (subset): s - summary of results (default) i - vertices incident to each facet n - normals with offsets p - vertex coordinates (includes coplanar points if 'Qc') Fx - extreme points (convex hull vertices) FA - compute total area and volume o - OFF format (dim, n, points, facets) G - Geomview output (2-d, 3-d, and 4-d) m - Mathematica output (2-d and 3-d) QVn - print facets that include point n, -n if not TO file- output results to file, may be enclosed in single quotes examples: rbox c D2 | qconvex s n rbox c D2 | qconvex i rbox c D2 | qconvex o rbox 1000 s | qconvex s Tv FA rbox c d D2 | qconvex s Qc Fx rbox y 1000 W0 | qconvex s n rbox y 1000 W0 | qconvex s QJ rbox d G1 D12 | qconvex QR0 FA Pp rbox c D7 | qconvex FA TF1000
The input data on stdin consists of:
- dimension
- number of points
- point coordinates
Use I/O redirection (e.g., qconvex < data.txt), a pipe (e.g., rbox 10 | qconvex), or the 'TI' option (e.g., qconvex TI data.txt).
Comments start with a non-numeric character. Error reporting is simpler if there is one point per line. Dimension and number of points may be reversed.
Here is the input for computing the convex hull of the unit cube. The output is the normals, one per facet.
rbox c > data
3 RBOX c 8 -0.5 -0.5 -0.5 -0.5 -0.5 0.5 -0.5 0.5 -0.5 -0.5 0.5 0.5 0.5 -0.5 -0.5 0.5 -0.5 0.5 0.5 0.5 -0.5 0.5 0.5 0.5qconvex s n < data
Convex hull of 8 points in 3-d: Number of vertices: 8 Number of facets: 6 Number of non-simplicial facets: 6 Statistics for: RBOX c | QCONVEX s n Number of points processed: 8 Number of hyperplanes created: 11 Number of distance tests for qhull: 35 Number of merged facets: 6 Number of distance tests for merging: 84 CPU seconds to compute hull (after input): 0.081 4 6 0 0 -1 -0.5 0 -1 0 -0.5 1 0 0 -0.5 -1 0 0 -0.5 0 1 0 -0.5 0 0 1 -0.5
These options control the output of qconvex. They may be used individually or together.
- Vertices
- Fx
- list extreme points (i.e., vertices). The first line is the number of extreme points. Each point is listed, one per line. The cube example has eight vertices.
- Fv
- list vertices for each facet. The first line is the number of facets. Each remaining line starts with the number of vertices. For the cube example, each facet has four vertices.
- i
- list vertices for each facet. The first line is the number of facets. The remaining lines list the vertices for each facet. In 4-d and higher, triangulate non-simplicial facets by adding an extra point.
- Coordinates
- o
- print vertices and facets of the convex hull in OFF format. The first line is the dimension. The second line is the number of vertices, facets, and ridges. The vertex coordinates are next, followed by the facets. Each facet starts with the number of vertices. The cube example has four vertices per facet.
- Ft
- print a triangulation of the convex hull in OFF format. The first line is the dimension. The second line is the number of vertices and added points, followed by the number of facets and the number of ridges. The vertex coordinates are next, followed by the centrum coordinates. There is one centrum for each non-simplicial facet. The cube example has six centrums, one per square. Each facet starts with the number of vertices or centrums. In the cube example, each facet uses two vertices and one centrum.
- p
- print vertex coordinates. The first line is the dimension and the second line is the number of vertices. The following lines are the coordinates of each vertex. The cube example has eight vertices.
- Qc p
- print coordinates of vertices and coplanar points. The first line is the dimension. The second line is the number of vertices and coplanar points. The coordinates are next, one line per point. Use 'Qc Qi p' to print the coordinates of all points.
- Facets
- Fn
- list neighboring facets for each facet. The first line is the number of facets. Each remaining line starts with the number of neighboring facets. The cube example has four neighbors per facet.
- FN
- list neighboring facets for each point. The first line is the total number of points. Each remaining line starts with the number of neighboring facets. Each vertex of the cube example has three neighboring facets. Use 'Qc Qi FN' to include coplanar and interior points.
- Fa
- print area for each facet. The first line is the number of facets. Facet area follows, one line per facet. For the cube example, each facet has area one.
- FI
- list facet IDs. The first line is the number of facets. The IDs follow, one per line.
- Coplanar and interior points
- Fc
- list coplanar points for each facet. The first line is the number of facets. The remaining lines start with the number of coplanar points. A coplanar point is assigned to one facet.
- Qi Fc
- list interior points for each facet. The first line is the number of facets. The remaining lines start with the number of interior points. A coplanar point is assigned to one facet.
- FP
- print distance to nearest vertex for coplanar points. The first line is the number of coplanar points. Each remaining line starts with the point ID of a vertex, followed by the point ID of a coplanar point, its facet, and distance. Use 'Qc Qi FP' for coplanar and interior points.
- Hyperplanes
- n
- print hyperplane for each facet. The first line is the dimension. The second line is the number of facets. Each remaining line is the hyperplane's coefficients followed by its offset.
- Fo
- print outer plane for each facet. The output plane is above all points. The first line is the dimension. The second line is the number of facets. Each remaining line is the outer plane's coefficients followed by its offset.
- Fi
- print inner plane for each facet. The inner plane of a facet is below its vertices. The first line is the dimension. The second line is the number of facets. Each remaining line is the inner plane's coefficients followed by its offset.
- General
- s
- print summary for the convex hull. Use 'Fs' and 'FS' if you need numeric data.
- FA
- compute total area and volume for 's' and 'FS'
- m
- Mathematica output for the convex hull in 2-d or 3-d.
- FM
- Maple output for the convex hull in 2-d or 3-d.
- G
- Geomview output for the convex hull in 2-d, 3-d, or 4-d.
- Scaling and rotation
- Qbk:n
- scale k'th coordinate to lower bound.
- QBk:n
- scale k'th coordinate to upper bound.
- QbB
- scale input to unit cube centered at the origin.
- QRn
- randomly rotate the input with a random seed of n. If n=0, the seed is the time. If n=-1, use time for the random seed, but do not rotate the input.
- Qbk:0Bk:0
- remove k'th coordinate from input. This computes the convex hull in one lower dimension.
These options provide additional control:
- Qt
- triangulated output. Qhull triangulates non-simplicial facets. It may produce degenerate facets of zero area.
- QJ
- joggle the input instead of merging facets. This guarantees simplicial facets (e.g., triangles in 3-d). It is less accurate than triangulated output ('Qt').
- Qc
- keep coplanar points
- Qi
- keep interior points
- f
- facet dump. Print the data structure for each facet.
- QVn
- select facets containing point n as a vertex,
- QGn
- select facets that are visible from point n (marked 'good'). Use -n for the remainder.
- PDk:0
- select facets with a negative coordinate for dimension k
- TFn
- report progress after constructing n facets
- Tv
- verify result
- TI file
- input data from file. The filename may not use spaces or quotes.
- TO file
- output results to file. Use single quotes if the filename contains spaces (e.g., TO 'file with spaces.txt'
- Qs
- search all points for the initial simplex. If Qhull can not construct an initial simplex, it reports a descriptive message. Usually, the point set is degenerate and one or more dimensions should be removed ('Qbk:0Bk:0'). If not, use option 'Qs'. It performs an exhaustive search for the best initial simplex. This is expensive is high dimensions.
Display 2-d, 3-d, and 4-d convex hulls with Geomview ('G').
Display 2-d and 3-d convex hulls with Mathematica ('m').
To view 4-d convex hulls in 3-d, use 'Pd0d1d2d3' to select the positive octant and 'GrD2' to drop dimension 2.
Qhull always computes a convex hull. The convex hull may be used for other geometric structures. The general technique is to transform the structure into an equivalent convex hull problem. For example, the Delaunay triangulation is equivalent to the convex hull of the input sites after lifting the points to a paraboloid.
The following terminology is used for convex hulls in Qhull. See Qhull's data structures.
- point - d coordinates
- vertex - extreme point of the input set
- ridge - d-1 vertices between two neighboring facets
- hyperplane - halfspace defined by a unit normal and offset
- coplanar point - a nearly incident point to a hyperplane
- centrum - a point on the hyperplane for testing convexity
- facet - a facet with vertices, ridges, coplanar points, neighboring facets, and hyperplane
- simplicial facet - a facet with d vertices, d ridges, and d neighbors
- non-simplicial facet - a facet with more than d vertices
- good facet - a facet selected by 'QVn', etc.
qconvex- compute the convex hull http://www.qhull.org input (stdin): first lines: dimension and number of points (or vice-versa). other lines: point coordinates, best if one point per line comments: start with a non-numeric character options: Qt - triangulated output QJ - joggle input instead of merging facets Qc - keep coplanar points with nearest facet Qi - keep interior points with nearest facet Qhull control options: Qbk:n - scale coord k so that low bound is n QBk:n - scale coord k so that upper bound is n (QBk is 0.5) QbB - scale input to unit cube centered at the origin Qbk:0Bk:0 - remove k-th coordinate from input QJn - randomly joggle input in range [-n,n] QRn - random rotation (n=seed, n=0 time, n=-1 time/no rotate) Qs - search all points for the initial simplex QGn - good facet if visible from point n, -n for not visible QVn - good facet if it includes point n, -n if not Trace options: T4 - trace at level n, 4=all, 5=mem/gauss, -1= events Tc - check frequently during execution Ts - print statistics Tv - verify result: structure, convexity, and point inclusion Tz - send all output to stdout TFn - report summary when n or more facets created TI file - input data from file, no spaces or single quotes TO file - output results to file, may be enclosed in single quotes TPn - turn on tracing when point n added to hull TMn - turn on tracing at merge n TWn - trace merge facets when width > n TVn - stop qhull after adding point n, -n for before (see TCn) TCn - stop qhull after building cone for point n (see TVn) Precision options: Cn - radius of centrum (roundoff added). Merge facets if non-convex An - cosine of maximum angle. Merge facets if cosine > n or non-convex C-0 roundoff, A-0.99/C-0.01 pre-merge, A0.99/C0.01 post-merge Rn - randomly perturb computations by a factor of [1-n,1+n] Un - max distance below plane for a new, coplanar point Wn - min facet width for outside point (before roundoff) Output formats (may be combined; if none, produces a summary to stdout): f - facet dump G - Geomview output (see below) i - vertices incident to each facet m - Mathematica output (2-d and 3-d) n - normals with offsets o - OFF file format (dim, points and facets; Voronoi regions) p - point coordinates s - summary (stderr) More formats: Fa - area for each facet FA - compute total area and volume for option 's' Fc - count plus coplanar points for each facet use 'Qc' (default) for coplanar and 'Qi' for interior FC - centrum for each facet Fd - use cdd format for input (homogeneous with offset first) FD - use cdd format for numeric output (offset first) FF - facet dump without ridges Fi - inner plane for each facet FI - ID for each facet Fm - merge count for each facet (511 max) FM - Maple output (2-d and 3-d) Fn - count plus neighboring facets for each facet FN - count plus neighboring facets for each point Fo - outer plane (or max_outside) for each facet FO - options and precision constants FP - nearest vertex for each coplanar point FQ - command used for qconvex Fs - summary: #int (8), dimension, #points, tot vertices, tot facets, for output: #vertices, #facets, #coplanar points, #non-simplicial facets #real (2), max outer plane, min vertex FS - sizes: #int (0) #real(2) tot area, tot volume Ft - triangulation with centrums for non-simplicial facets (OFF format) Fv - count plus vertices for each facet FV - average of vertices (a feasible point for 'H') Fx - extreme points (in order for 2-d) Geomview output (2-d, 3-d, and 4-d) Ga - all points as dots Gp - coplanar points and vertices as radii Gv - vertices as spheres Gi - inner planes only Gn - no planes Go - outer planes only Gc - centrums Gh - hyperplane intersections Gr - ridges GDn - drop dimension n in 3-d and 4-d output Print options: PAn - keep n largest facets by area Pdk:n - drop facet if normal[k] <= n (default 0.0) PDk:n - drop facet if normal[k] >= n Pg - print good facets (needs 'QGn' or 'QVn') PFn - keep facets whose area is at least n PG - print neighbors of good facets PMn - keep n facets with most merges Po - force output. If error, output neighborhood of facet Pp - do not report precision problems . - list of all options - - one line descriptions of all options
Up: Home page for Qhull
Up: Qhull manual: Table of Contents
To: Programs
Options
Output
Formats
Geomview
Print
Qhull
Precision
Trace
Functions
To: synopsis
input outputs
controls graphics
notes conventions
options
Comments to: qhull@qhull.org
Created: Sept. 25, 1995 --- Last modified: see top
Up: Home page for Qhull
Up: Qhull manual: Table of Contents
To: Programs
Options
Output
Formats
Geomview
Print
Qhull
Precision
Trace
Functions
Copyright © 1995-2015 C.B. Barber
» Programs Options Output Formats Geomview Print Qhull Precision Trace Functions
Most users will not need to set these options. They are best used for approximating a convex hull. They may also be used for testing Qhull's handling of precision errors.
By default, Qhull uses options 'C-0' for 2-d, 3-d and 4-d, and 'Qx' for 5-d and higher. These options use facet merging to handle precision errors. You may also use joggled input 'QJ' to avoid precision problems. For more information see Imprecision in Qhull.
Pre-merging occurs while Qhull constructs the hull. It is indicated by 'C-n', 'A-n', or 'Qx'.
If the angle between a pair of facet normals is greater than n, Qhull merges one of the facets into a neighbor. It selects the facet that is closest to a neighboring facet.
For example, option 'A-0.99' merges facets during the construction of the hull. If the cosine of the angle between facets is greater than 0.99, one or the other facet is merged. Qhull accounts for the maximum roundoff error.
If 'A-n' is set without 'C-n', then 'C-0' is automatically set.
In 5-d and higher, you should set 'Qx' along with 'A-n'. It skips merges of coplanar facets until after the hull is constructed and before 'An' and 'Cn' are checked.
Post merging occurs after the hull is constructed. For example, option 'A0.99' merges a facet if the cosine of the angle between facets is greater than 0.99. Qhull accounts for the maximum roundoff error.
If 'An' is set without 'Cn', then 'C0' is automatically set.
Qhull handles precision errors by merging facets. The 'C-0' option handles all precision errors in 2-d, 3-d, and 4-d. It is set by default. It may be used in higher dimensions, but sometimes the facet width grows rapidly. It is usually better to use 'Qx' in 5-d and higher. Use 'QJ' to joggle the input instead of merging facets. Use 'Q0' to turn both options off.
Qhull optimizes 'C-0' ("_zero-centrum") by testing vertices instead of centrums for adjacent simplices. This may be slower in higher dimensions if merges decrease the number of processed points. The optimization may be turned off by setting a small value such as 'C-1e-30'. See How Qhull handles imprecision.
Pre-merging occurs while Qhull constructs the hull. It is indicated by 'C-n', 'A-n', or 'Qx'.
The centrum of a facet is a point on the facet for testing facet convexity. It is the average of the vertices projected to the facet's hyperplane. Two adjacent facets are convex if each centrum is clearly below the other facet.
If adjacent facets are non-convex, one of the facets is merged into a neighboring facet. Qhull merges the facet that is closest to a neighboring facet.
For option 'C-n', n is the centrum radius. For example, 'C-0.001' merges facets whenever the centrum is less than 0.001 from a neighboring hyperplane. Qhull accounts for roundoff error when testing the centrum.
In 5-d and higher, you should set 'Qx' along with 'C-n'. It skips merges of coplanar facets until after the hull is constructed and before 'An' and 'Cn' are checked.
Post-merging occurs after Qhull constructs the hull. It is indicated by 'Cn' or 'An'.
For option 'Cn', n is the centrum radius. For example, 'C0.001' merges facets when the centrum is less than 0.001 from a neighboring hyperplane. Qhull accounts for roundoff error when testing the centrum.
Both pre-merging and post-merging may be defined. If only post-merging is used ('Q0' with 'Cn'), Qhull may fail to produce a hull due to precision errors during the hull's construction.
This allows the user to change the maximum roundoff error computed by Qhull. The value computed by Qhull may be overly pessimistic. If 'En' is set too small, then the output may not be convex. The statistic "max. distance of a new vertex to a facet" (from option 'Ts') is a reasonable upper bound for the actual roundoff error.
This option perturbs every distance, hyperplane, and angle computation by up to (+/- n * max_coord). It simulates the effect of roundoff errors. Unless 'En' is explicitly set, it is adjusted for 'Rn'. The command 'qhull Rn' will generate a convex hull despite the perturbations. See the Examples section for an example.
Options 'Rn C-n' have the effect of 'W2n' and 'C-2n'. To use time as the random number seed, use option 'QR-1'.
This allows the user to set coplanarity. When pre-merging ('C-n ', 'A-n' or 'Qx'), Qhull merges a new point into any coplanar facets. The default value for 'Un' is 'Vn'.
This allows the user to set facet visibility. When adding a point to the convex hull, Qhull determines all facets that are visible from the point. A facet is visible if the distance from the point to the facet is greater than 'Vn'.
Without merging, the default value for 'Vn' is the roundoff error ('En'). With merging, the default value is the pre-merge centrum ('C-n') in 2-d or 3-d, or three times that in other dimensions. If the outside width is specified with option 'Wn ', the maximum, default value for 'Vn' is 'Wn'.
Qhull warns if 'Vn' is greater than 'Wn' and furthest outside ('Qf') is not selected; this combination usually results in flipped facets (i.e., reversed normals).
Points are added to the convex hull only if they are clearly outside of a facet. A point is outside of a facet if its distance to the facet is greater than 'Wn'. Without pre-merging, the default value for 'Wn' is 'En '. If the user specifies pre-merging and does not set 'Wn', than 'Wn' is set to the maximum of 'C-n' and maxcoord*(1 - A-n).
This option is good for approximating a convex hull.
Options 'Qc' and 'Qi' use the minimum vertex to distinguish coplanar points from interior points.
Up: Home page for Qhull
Up: Qhull manual: Table of Contents
To: Programs
Options
Output
Formats
Geomview
Print
Qhull
Precision
Trace
Functions
Comments to: qhull@qhull.org
Created: Sept. 25, 1995 --- Last modified: see top