precision problems (corrected unless 'Q0' or an error)
50 coplanar horizon facets for new vertices
Precision problems were detected during construction of the convex hull.
This occurs because convex hull algorithms assume that calculations are
exact, but floating-point arithmetic has roundoff errors.
To correct for precision problems, do not use 'Q0'. By default, Qhull
selects 'C-0' or 'Qx' and merges non-convex facets. With option 'QJ',
Qhull joggles the input to prevent precision problems. See "Imprecision
in Qhull" (qh-impre.htm).
If you use 'Q0', the output may include
coplanar ridges, concave ridges, and flipped facets. In 4-d and higher,
Qhull may produce a ridge with four neighbors or two facets with the same
vertices. Qhull reports these events when they occur. It stops when a
concave ridge, flipped facet, or duplicate facet occurs.
If you need triangular output:
- use option 'Qt' to triangulate the output
- use option 'QJ' to joggle the input points and remove precision errors
- use option 'Ft'. It triangulates non-simplicial facets with added points.
If you must use 'Q0',
try one or more of the following options. They can not guarantee an output.
- use 'QbB' to scale the input to a cube.
- use 'Po' to produce output and prevent partitioning for flipped facets
- use 'V0' to set min. distance to visible facet as 0 instead of roundoff
- use 'En' to specify a maximum roundoff error less than 0.0045.
- options 'Qf', 'Qbb', and 'QR0' may also help
To guarantee simplicial output:
- use option 'Qt' to triangulate the output
- use option 'QJ' to joggle the input points and remove precision errors
- use option 'Ft' to triangulate the output by adding points
- use exact arithmetic (see "Imprecision in Qhull", qh-impre.htm)
+rbox L100 10000 D4 s C1,1e-13 t2 | qhull
+QH6271 qhull precision error (qh_check_dupridge): wide merge (1758701813 times wider) due to duplicate ridge with nearly coincident points (9.7e-014) between f172830 and f172837, merge dist 0.00014, while processing p18865
+- Ignore error with option 'Q12'
+- To be fixed in a later version of Qhull
+ERRONEOUS FACET:
+- f172830
+ - flags: bottom new seen mergehorizon dupridge mergeridge2
+ CPU seconds to compute hull (after input): 0.875
+ Maximum distance of point above facet: 1.1e-013 (10.9x)
+ Maximum distance of vertex below facet: -2.3e-005 (2267021951.3x)
+
+QH6271 qhull precision error (qh_check_dupridge): wide merge (1758701813 times wider) due to duplicate ridge with nearly coincident points (9.7e-014) between f172830 and f172837, merge dist 0.00014, while processing p18865
+- Ignore error with option 'Q12'
+- To be fixed in a later version of Qhull
+rbox 50 C1,1E-13 t1447644703 | qhull d
+QH6271 qhull precision error (qh_check_dupridge): wide merge (1125070907263 times wider) due to duplicate ridge with nearly coincident points (6.5e-014) between f749 and f759, merge dist 0.015, while processing p54
+- Ignore error with option 'Q12'
+- To be fixed in a later version of Qhull
+- A simple workaround is to add a bounding box to the input sites
+ERRONEOUS FACET:
+- f749
+ - flags: bottom upperDelaunay new dupridge mergeridge2 flipped
+ - normal: 0.2935 0.3842 0.4668 0.7405
+ - offset: 0.05514914
+ - vertices: p54(v54) p45(v48) p76(v38) p44(v19)
+ - neighboring facets: f435 f738 f759 f748
+ - ridges:
+ - r412 tested
+ vertices: p45(v48) p76(v38) p44(v19)
+ between f435 and f749
+ - r556
+ vertices: p54(v54) p76(v38) p44(v19)
+ between f749 and f738
+ - r557
+ vertices: p54(v54) p45(v48) p44(v19)
+ between f759 and f749
+ - r558
+ vertices: p54(v54) p45(v48) p76(v38)
+ between f749 and f748
+ERRONEOUS OTHER FACET:
+- f759
+ - flags: bottom upperDelaunay new dupridge mergeridge1 flipped
+ - normal: -0.3214 0.1166 0.5495 0.7623
+ - offset: 0.114967
+ - vertices: p54(v54) p45(v48) p44(v19) p92(v11)
+ - neighboring facets: f435 f738 f760 f749
+ - ridges:
+ - r418 tested
+ vertices: p45(v48) p44(v19) p92(v11)
+ between f435 and f759
+ - r554
+ vertices: p54(v54) p44(v19) p92(v11)
+ between f759 and f738
+ - r555
+ vertices: p54(v54) p45(v48) p92(v11)
+ between f760 and f759
+ - r557
+ vertices: p54(v54) p45(v48) p44(v19)
+ between f759 and f749
+
+While executing: rbox 50 C1,1E-13 t1447644703 | qhull d
+Last point added to hull was p54. Last merge was #126.
+
+At error exit:
+
+Delaunay triangulation by the convex hull of 100 points in 4-d:
+
+ Number of input sites: 54
+ Total number of nearly incident points: 46
+ Number of Delaunay regions: 0
+ Number of non-simplicial Delaunay regions: 39
+
+Statistics for: rbox 50 C1,1E-13 t1447644703 | qhull d
+
+ Number of points processed: 54
+ Number of hyperplanes created: 711
+ Number of facets in hull: 234
+ Number of distance tests for qhull: 3419
+ Number of distance tests for merging: 6140
+ Number of distance tests for checking: 0
+ Number of merged facets: 126
+ Maximum distance of merged point above facet: 8.9e-015 (0.9x)
+ Maximum distance of merged vertex below facet: -9e-015 (0.9x)
+
+rbox 50 C1,1E-13 t1447644703 | qhull d Q12
+
+Delaunay triangulation by the convex hull of 100 points in 4-d:
+
+ Number of input sites: 99
+ Total number of nearly incident points: 1
+ Number of Delaunay regions: 310
+ Number of non-simplicial Delaunay regions: 136
+
+Statistics for: rbox 50 C1,1E-13 t1447644703 | qhull d Q12
+
+ Number of points processed: 99
+ Number of hyperplanes created: 1584
+ Number of facets in hull: 348
+ Number of distance tests for qhull: 8710
+ Number of distance tests for merging: 17689
+ Number of distance tests for checking: 7460
+ Number of merged facets: 507
+ CPU seconds to compute hull (after input): 0
+ Maximum distance of point above facet: 3.2e-014 (3.1x)
+ Maximum distance of vertex below facet: -0.0012 (119810840063.5x)
+
+QH6271 qhull precision error (qh_check_dupridge): wide merge (1125070907263 times wider) due to duplicate ridge with nearly coincident points (6.5e-014) between f749 and f759, merge dist 0.015, while processing p54
+- Ignore error with option 'Q12'
+- To be fixed in a later version of Qhull
+- A simple workaround is to add a bounding box to the input sites
qhull
-qhull- compute convex hulls and related structures. Qhull 2015.0.4.r 2015/09/30
+qhull- compute convex hulls and related structures. Qhull 2015.1.r 2016/01/03
input (stdin): dimension, n, point coordinates
comments start with a non-numeric character
halfspace: use dim+1 and put offsets after coefficients
options (qh-quick.htm):
d - Delaunay triangulation by lifting points to a paraboloid
d Qu - furthest-site Delaunay triangulation (upper convex hull)
v - Voronoi diagram as the dual of the Delaunay triangulation
v Qu - furthest-site Voronoi diagram
H1,1 - Halfspace intersection about [1,1,0,...] via polar duality
Qt - triangulated output
QJ - joggled input instead of merged facets
Tv - verify result: structure, convexity, and point inclusion
. - concise list of all options
- - one-line description of each option
-V - version
Output options (subset):
s - summary of results (default)
i - vertices incident to each facet
n - normals with offsets
p - vertex coordinates (if 'Qc', includes coplanar points)
if 'v', Voronoi vertices
Fp - halfspace intersections
Fx - extreme points (convex hull vertices)
FA - compute total area and volume
o - OFF format (if 'v', outputs Voronoi regions)
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 D4 | qhull Tv rbox 1000 s | qhull Tv s FA
rbox 10 D2 | qhull d QJ s i TO result rbox 10 D2 | qhull v Qbb Qt p
rbox 10 D2 | qhull d Qu QJ m rbox 10 D2 | qhull v Qu QJ o
rbox c d D2 | qhull Qc s f Fx | more rbox c | qhull FV n | qhull H Fp
rbox d D12 | qhull QR0 FA rbox c D7 | qhull FA TF1000
rbox y 1000 W0 | qhull rbox c | qhull n
qhull .
-Qhull 2015.0.4.r 2015/09/30.
+Qhull 2015.1.r 2016/01/03.
Except for 'F.' and 'PG', upper-case options take an argument.
exit_if_err $HERE "Error while checking $zip_file"
}
function check_tgz_file #tgz_file
{
local tgz_file=$1
local HERE=$(ro_here)
log_note $HERE "Check $tgz_file"
ls -l $tgz_file >>$err_log
exit_if_err $HERE "Did not create $tgz_file"
tar -tzf $tgz_file >/dev/null 2>>$err_log
exit_if_err $HERE "Can not extract -- tar -tzf $tgz_file"
}
function convert_to_unix #dir $qhull_2ufiles -- convert files to Unix, preserving modtime from $root_dir
{
local temp_dir=$1
local HERE=$(ro_here)
log_note $HERE "Convert files to unix format in $1"
for f in $(find $temp_dir -type f | grep -E '^([^.]*|.*\.(ac|am|bashrc|c|cfg|cpp|css|d|dpatch|h|htm|html|man|pl|pri|pro|profile|sh|sql|termcap|txt|xml|xsd|xsl))$'); do
Geomview provides a good visualization of Qhull's 2-d and 3-d results.
<p>Qhull includes <a href="qh-eg.htm">Examples of Qhull</a> that may be viewed with Geomview.
<p>Geomview can help visulalize a 3-d Delaunay triangulation or the surface of a 4-d convex hull,
Use option '<a href="qh-optq.htm#QVn">QVn</a>' to select the 3-D facets adjacent to a vertex.
<p>You may use Geomview to create movies that animate your objects (c.f., <a href="http://www.geomview.org/FAQ/answers.shtml#mpeg">How can I create a video animation?</a>).
Geomview helped create the <a href="http://www.geom.uiuc.edu/video/">mathematical videos</a> "Not Knot", "Outside In", and "The Shape of Space" from the Geometry Center.
Geomview builds under Linux, Unix, Macintosh OS X, and Windows.
<p>Geomview has <a href="https://packages.debian.org/search?keywords=geomview">installable packages</a> for Debian and Ubuntu.
The OS X build needs Xcode, an X11 SDK, and Lesstif or Motif.
The Windows build uses Cygwin (see <a href="#geomview-win">Building Geomview</a> below for instructions).
<p>If using Xforms (e.g., for Geomview's <a href="http://www.geomview.org/docs/html/Modules.html">External Modules</a>), install the 'libXpm-devel' package from cygwin and move the xforms directory into your geomview directory, e.g.,<br><tt>mv xforms-1.2.4 geomview-1.9.5/xforms</tt>
<p>Geomview's <a href="http://www.geom.uiuc.edu/software/geomview/docs/NDview/manpagehelp.html">ndview<a/> provides multiple views into 4-d and higher objects.
This module is out-of-date (<a href="http://sourceforge.net/p/geomview/mailman/message/2004152/">geomview-users: 4dview</a>).
Download NDview-sgi.tar.Z at <a href="ftp://www.geom.uiuc.edu/pub/software/geomview/newpieces/sgi">newpieces</a> and 4dview at <a href="https://stuff.mit.edu/afs/sipb/project/3d/arch/sgi_62/lib/Geomview/modules/">Geomview/modules</a>.
<p>Use Geomview to view <a href="qh-eg.htm">Examples of Qhull</a>. You can spin the convex hull, fly a camera through its facets,
and see how Qhull produces thick facets in response to round-off error.
<p>Follow these instructions to view 'eg,01.cube' from Examples of Qhull
<ol>
<li>Launch an XTerm command shell
<ul>
<li>If needed, start the X terminal server, Use 'xinit' or 'startx' in /usr/X11R6/bin<br><tt>xinit -- -multiwindow -clipboard</tt><br><tt>startx</tt>
<li>Start an XTerm command shell. In Windows, click the Cygwin/bash icon on your desktop.
<li>Set the DISPLAY variable, e.g.,<br><tt>export DISPLAY=:0</tt><br><tt>export DISPLAY=:0 >>~/.bashenv</tt>
</ul>
<li>Use Qhull's <a href="qh-optg.htm">Geomview options</a> to create a geomview object
<ul>
<li><tt>rbox c D3 | qconvex G >eg.01.cube</tt>
<li>On windows, convert the output to Unix text format with 'd2u'<br><tt>rbox c D3 | qconvex G | d2u >eg.01.cube</tt><br><tt>d2u eg.*</tt>
</ul>
<li>Run Geomview
<ul>
<li>Start Geomview with your example<br><tt>./geomview eg.01.cube</tt>
<li>Follow the instructions in <a href="http://www.geomview.org/docs/html/Tutorial.html">Gemoview Tutorial</a>
<li>Geomview creates the <i>Geomview control panel</i> with Targets and External Module, the <i>Geomview toolbar</i> with buttons for controlling Geomview, and the <i>Geomview camera window</i> showing a cube.
<li>Clear the camera window by selecting your object in the Targets list and 'Edit > Delete' or 'dd'
<li>Load the <i>Geomview files panel</i>. Select 'Open' in the 'File' menu.
<li>Set 'Filter' in the files panel to your example directory followed by '/*' (e.g., '/usr/local/qhull-2015.1/eg/*')
<li>Click 'Filter' in the files panel to view your examples in the 'Files' list.
<li>Load another example into the camera window by selecting it and clicking 'OK'.
<li>Review the instructions for <a href="http://www.geomview.org/docs/html/Interaction.html">Interacting with Geomview</a>
<li>When viewing multiple objects at once, you may want to turn off normalization. In the 'Inspect > Apperance' control panel, set 'Normalize' to 'None'.
</ul>
</ol>
-<p>Geomview defines GGL (a textual API for controlling Geomview) and OOGL (a textual file format for defining objects).
+<p>Geomview defines GCL (a textual API for controlling Geomview) and OOGL (a textual file format for defining objects).
<ul>
<li>To control Geomview, you may use any program that reads and writes from stdin and stdout. For example, it could report Qhull's information about a vertex identified by a double-click 'pick' event.
<li><a href="http://www.geomview.org/docs/html/GCL.html">GCL</a> command language for controlling Geomview
<li><a href="http://www.geomview.org/docs/html/OOGL-File-Formats.html">OOGL</a> file format for defining objects (<a href="http://www.geomview.org/docs/oogltour.html">tutorial</a>).
<li><a href="http://www.geomview.org/docs/html/Modules.html">External Modules</a> for interacting with Geomview via GCL
<li>Interact with your objects via <a href="http://www.geomview.org/docs/html/pick.html">pick</a> commands in response to right-mouse double clicks. Enable pick events with the <a href="http://www.geomview.org/docs/html/interest.html">interest</a> command.
</ul>
</blockquote>
<h3><a href="#TOC">»</a><a name="geomview-win">Building Geomview for Windows</a></h3>
<blockquote>
<p>Compile Geomview under Cygwin. For detailed instructions, see
>Building Savi and Geomview under Windows</a>. These instructions are somewhat out-of-date. Updated
instructions follow.
-<p>How to compile Geomview under Cygwin (October 2015)</p>
+<p>How to compile Geomview under 32-bit Cygwin (October 2015)</p>
<ol>
-<li>Install <a href="http://cygwin.com/">Cygwin</a> as follows.
+<li><b>Note:</b> L. Wood has run into multiple issues with Geomview on Cygwin. He recommends Virtualbox/Ubuntu
+and a one-click install of geomview via the Ubuntu package. See his Savi/Geomview link above.
+<li>Install 32-bit <a href="http://cygwin.com/">Cygwin</a> as follows.
For additional guidance, see Cygwin's <a href="https://cygwin.com/install.html">Installing and Updating Cygwin Packages</a>
and <a href="http://www.qhull.org/road/road-faq/xml/cmdline.xml#setup-cygwin">Setup cygwin</a>.
<ul>
<li>Launch the cygwin installer.
<li>Select a mirror from <a href="http://cygwin.com/mirrors.html">Cygwin mirrors</a> (e.g., http://mirrors.kernel.org/sourceware/cygwin/ in California).
<li>Select the packages to install. Besides the cygwin packages listed in the Savi/Windows instructions consider adding
<ul>
<li><b>Default</b> -- libXm-devel (required for /usr/include/Xm/Xm.h)
<li><b>Devel</b> -- bashdb, gcc-core (in place of gcc), gdb
<li><b>Utils</b> -- dos2unix (required for qhull), keychain
<li>If installing perl, ActiveState Perl may be a better choice than cygwin's perl. Perl is not used by Geomview or Qhull.
<li><a href="https://cygwin.com/cgi-bin2/package-grep.cgi">Cygwin Package Search</a> -- Search for cygwin programs and packages
</ul>
<li>Click 'Next' to download and install the packages.
<li>If the download is incomplete, try again.
<li>If you try again after a successful install, cygwin will uninstall and reinstall all modules..
<li>Click on the 'Cywin Terminal' icon on the Desktop. It sets up a user directory in /home from /etc/skel/...
<li>Mount your disk drives<br>mount c: /c # Ignore the warning /c does not exist
-<li>Consider adding 'cygwin\bin' to '<tt>Control Panel > System > Advanced > Environment > PATH</tt>'. If so, cygwin commands such as 'ls' may be used from the Windows command shell.
</ul>
<li>Consider installing the <a href="http://www.qhull.org/bash/doc/road-bash.html">Road Bash</a> scripts (/etc/road-*) from <a href="http://www.qhull.org/road/">Road</a>.
They define aliases and functions for Unix command shells (Unix, Linux, Mac OS X, Windows),
<ul>
<li>Download Road Bash and unzip the downloaded file
<li>Copy .../bash/etc/road-* to the Cywin /etc directory (by default, C:\cygwin\etc).
<li>Using the cygwin terminal, convert the road scripts to Unix format<br>d2u /etc/road-*
<li>Launch the X terminal server from '<tt>Start > All programs > Cygwin-X > Xwin Server</tt>'. Alternatively, run 'startx'
<li>Launch an XTerm shell
<ul>
<li>Right click the Cywin icon on the system tray in the Windows taskbar.
<li>Select '<tt>System Tools > XTerm</tt>'
</ul>
<li>Download and extract Geomview -- <a href="http://www.geomview.org/download/">Downloading Geomview</a>
<li>Compile Geomview
<ul>
<li>./configure
<li>make
</ul>
<li>If './configure' fails, check 'config.log' at the failing step. Look carefully for missing libraries, etc. The <a href="http://www.geomview.org/FAQ/answers.shtml">Geomview FAQ</a> contains suggestions (e.g., "configure claims it can't find OpenGl").
<li>If 'make' fails, read the output carefully for error messages. Usually it is a missing include file or package. Locate and install the missing cygwin packages
A QhullFacetSet is a <a href="#set-cpp">QhullSet</a> of <a href="#facet-cpp">QhullFacet</a>. QhullFacetSet may be ordered or unordered. The neighboring facets of a QhullFacet is a QhullFacetSet.
The neighbors of a <a href="#facet-cpp">QhullFacet</a> is a QhullFacetSet.
The neighbors are ordered for simplicial facets, matching the opposite vertex of the facet.
A QhullPointSet is a <a href="#set-cpp">QhullSet</a> of <a href="#point-cpp">QhullPoint</a>. The QhullPointSet of a <a href="#facet-cpp">QhullFacet</a> is its coplanar points.
A QhullRidgeSet is a <a href="#set-cpp">QhullSet</a> of <a href="#ridge-cpp">QhullRidge</a>. Each <a href="#facet-cpp">QhullFacet</a> contains a QhullRidgeSet.
A QhullVertex is a vertex of the convex hull. A simplicial <a href="#facet-cpp">QhullFacet</a> has qh.hull_dim-1 vertices. A QhullVertex contains a <a href="#point-cpp">QhullPoint</a>.
It may list its neighboring <a href="#facet-cpp">QhullFacet</a>'s.
RboxPoints is a std::vector of point coordinates (<a href="#point-cpp">QhullPoint</a>).
It's iterator is <a href="#coordinate-cpp">CoordinateIterator</a>.
</p>
<p>
<code>RboxPoints.appendRandomPoints()</code> 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.
</p>
<h3><a href="#TOC">»</a><a name="questions-cpp">Cpp questions for Qhull</a></h3>
Developing C++ code requires many conventions, idioms, and technical details.
The following questions have either
mystified the author or do not have a clear answer. See also
<a href="http://www.qhull.org/road/road-faq/xml/cpp-guideline.xml">C++ and Perl Guidelines</a>.
and FIXUP notes in the code.
Please add notes to <a href="http://github.com/qhull/qhull/wiki">Qhull Wiki</a>.
<ul>
<li>FIXUP QH11028 Should return reference, but get reference to temporary
<li>How to avoid copy constructor while logging, maybeThrowQhullMessage()
<li>How to configure Qhull output. Trace and results should go to stdout/stderr
<li>Qhull and RboxPoints messaging. e.g., ~Qhull, hasQhullMessage(). Rename them as QhullErrorMessage?
<li>How to add additional output to an error message, e.g., qh_setprint
<li>Is idx the best name for an index? It's rather cryptic, but BSD strings.h defines index().
<li>Qhull::feasiblePoint Qhull::useOutputStream as field or getter?
<li>Define virtual functions for user customization of Qhull (e.g., qh_fprintf, qh_memfree,etc.)
<li>Figure out RoadError::global_log. clearQhullMessage currently clearGlobalLog
<li>Should the false QhullFacet be NULL or empty? e.g., QhullFacet::tricoplanarOwner() and QhullFacetSet::end()
<li>Should output format for floats be predefined (qh_REAL_1, 2.2g, 10.7g) or as currently set for stream
<li>Should cout << !point.defined() be blank or 'undefined'
<li>Infinite point as !defined()
<li>qlist and qlinkedlist define pointer, reference, size_type, difference_type, const_pointer, const_reference for the class but not for iterator and const_iterator
>voronoin</a>. V. Brumberg update MATLAB R14 for Qhull 2003.1 and triangulated output.
<p>Engwirda wrote <a href="http://www.mathworks.com/matlabcentral/fileexchange/loadFile.do?objectId=10307&objectType=file">mesh2d</a> for unstructured mesh generation in MATLAB.
It is based on the iterative method of Persson and generally results in better quality meshes than delaunay refinement.
<p>If two facets are not clearly convex, then Qhull removes one
or the other facet by merging the facet into a neighbor. It
selects the merge which minimizes the distance from the
neighboring hyperplane to the facet's vertices. Qhull also
performs merges when a facet has fewer than <i>d</i> neighbors (called a
degenerate facet), when a facet's vertices are included in a
neighboring facet's vertices (called a redundant facet), when a
facet's orientation is flipped, or when a ridge occurs between
more than two facets.</p>
<p>Qhull performs merges in a series of passes sorted by merge
angle. Each pass merges those facets which haven't already been
merged in that pass. After a pass, Qhull checks for redundant
vertices. For example, if a vertex has only two neighbors in 3-d,
the vertex is redundant and Qhull merges it into an adjacent
vertex.</p>
<p>Merging two simplicial facets creates a non-simplicial facet
of <em>d+1</em> vertices. Additional merges create larger facets.
When merging facet A into facet B, Qhull retains facet B's
hyperplane. It merges the vertices, neighbors, and ridges of both
facets. It recomputes the centrum if a wide merge has not
occurred (qh_WIDEcoplanar) and the number of extra vertices is
smaller than a constant (qh_MAXnewcentrum).</p>
<h2><a href="#TOC">»</a><a name="limit">Limitations of merged
facets</a></h2>
<ul>
<li><b>Uneven dimensions</b> --
If one coordinate has a larger absolute value than other
coordinates, it may dominate the effect of roundoff errors on
distance computations. You may use option '<a
href="qh-optq.htm#QbB">QbB</a>' to scale points to the unit cube.
For Delaunay triangulations and Voronoi diagrams, <a href=qdelaun.htm>qdelaunay</a>
and <a href=qvoronoi.htm>qvoronoi</a> always set
option '<a href="qh-optq.htm#Qbb">Qbb</a>'. It scales the last
coordinate to [0,m] where <i>m</i> is the maximum width of the
other coordinates. Option '<a href="qh-optq.htm#Qbb">Qbb</a>' is
needed for Delaunay triangulations of integer coordinates
and nearly cocircular points.
<p>For example, compare
<pre>
rbox 1000 W0 t | qconvex Qb2:-1e-14B2:1e-14
</pre>
with
<pre>
rbox 1000 W0 t | qconvex
</pre>
The distributions are the same but the first is compressed to a 2e-14 slab.
<p>
<li><b>Post-merging of coplanar facets</b> -- In 5-d and higher, option '<a href="qh-optq.htm#Qx">Qx</a>'
(default) delays merging of coplanar facets until post-merging.
This may allow "dents" to occur in the intermediate
convex hulls. A point may be poorly partitioned and force a poor
approximation. See option '<a href="qh-optq.htm#Qx">Qx</a>' for
further discussion.</p>
<p>This is difficult to produce in 5-d and higher. Option '<a href="qh-optq.htm#Q6">Q6</a>' turns off merging of concave
facets. This is similar to 'Qx'. It may lead to serious precision errors,
for example,
<pre>
rbox 10000 W1e-13 | qhull Q6 Tv
</pre>
<p>
<li><b>Maximum facet width</b> --
Qhull reports the maximum outer plane and inner planes (if
more than roundoff error apart). There is no upper bound
for either figure. This is an area for further research. Qhull
does a good job of post-merging in all dimensions. Qhull does a
good job of pre-merging in 2-d, 3-d, and 4-d. With the '<a
href="qh-optq.htm#Qx">Qx</a>' option, it does a good job in
higher dimensions. In 5-d and higher, Qhull does poorly at
detecting redundant vertices. </p>
<p>In the summary ('<a href="qh-opto.htm#s">s</a>'), look at the
ratio between the maximum facet width and the maximum width of a
single merge, e.g., "(3.4x)". Qhull usually reports a
ratio of four or lower in 3-d and six or lower in 4-d. If it
reports a ratio greater than 10, this may indicate an
implementation error. Narrow distributions (see following) may
produce wide facets.
<p>For example, if special processing for narrow distributions is
turned off ('<a href="qh-optq.htm#Q10">Q10</a>'), qhull may produce
a wide facet:</p>
<pre>
rbox 1000 L100000 s G1e-16 t1002074964 | qhull Tv Q10
</pre>
<p>
<li><b>Narrow distribution</b> -- In 3-d, a narrow distribution may result in a poor
approximation. For example, if you do not use qdelaunay nor option
'<a href="qh-optq.htm#Qbb">Qbb</a>', the furthest-site
Delaunay triangulation of nearly cocircular points may produce a poor
approximation:
<pre>
rbox s 5000 W1e-13 D2 t1002151341 | qhull d Qt
rbox 1000 s W1e-13 t1002231672 | qhull d Tv
</pre>
<p>During
construction of the hull, a point may be above two
facets with opposite orientations that span the input
set. Even though the point may be nearly coplanar with both
facets, and can be distant from the precise convex
hull of the input sites. Additional facets leave the point distant from
a facet. To fix this problem, add option '<a href="qh-optq.htm#Qbb">Qbb</a>'
(it scales the last coordinate). Option '<a href="qh-optq.htm#Qbb">Qbb</a>'
is automatically set for <a href=qdelaun.htm>qdelaunay</a> and <a href=qvoronoi.htm>qvoronoi</a>.
<p>Qhull generates a warning if the initial simplex is narrow.
For narrow distributions, Qhull changes how it processes coplanar
points -- it does not make a point coplanar until the hull is
finished.
Use option '<a href="qh-optq.htm#Q10">Q10</a>' to try Qhull without
special processing for narrow distributions.
For example, special processing is needed for:
<pre>
rbox 1000 L100000 s G1e-16 t1002074964 | qhull Tv Q10
</pre>
<p>You may turn off the warning message by reducing
qh_WARNnarrow in <tt>user.h</tt> or by setting option
'<a href="qh-optp.htm#Pp">Pp</a>'. </p>
<p>Similar problems occur for distributions with a large flat facet surrounded
with many small facet at a sharp angle to the large facet.
Qhull 3.1 fixes most of these problems, but a poor approximation can occur.
A point may be left outside of the convex hull ('<a href="qh-optt.htm#Tv">Tv</a>').
Examples include
the furthest-site Delaunay triangulation of nearly cocircular points plus the origin, and the convex hull of a cone of nearly cocircular points. The width of the band is 10^-13.
<pre>
rbox s 1000 W1e-13 P0 D2 t996799242 | qhull d Tv
rbox 1000 s Z1 G1e-13 t1002152123 | qhull Tv
rbox 1000 s Z1 G1e-13 t1002231668 | qhull Tv
</pre>
<p>
<li><b>Quadratic running time</b> -- If the output contains large, non-simplicial
facets, the running time for Qhull may be quadratic in the size of the triangulated
output. For example, <tt>rbox 1000 s W1e-13 c G2 | qhull d</tt> is 4 times
faster for 500 points. The convex hull contains two large nearly spherical facets and
many nearly coplanar facets. Each new point retriangulates the spherical facet and repartitions the remaining points into all of the nearly coplanar facets.
In this case, quadratic running time is avoided if you use qdelaunay,
add option '<a href="qh-optq.htm#Qbb">Qbb</a>',
or add the origin ('P0') to the input.
<p>
-<li><b>Nearly coincident points on an edge</b> -- Nearly coincident points on an edge may lead to wide facets or quadratic running time.
-For example, the convex hull in 4-D of a narrow lens with nearly coincident points and the Delaunay triangulation of
+<li><b>Nearly coincident points on an edge</b> -- Multiple, nearly coincident points on
+an edge with non-simplicial facets may lead to wide facets or quadratic running time.
+For example, either the convex hull
+in 4-D of a narrow lens with coincident points or the Delaunay triangulation of
nearly coincident points may lead to very wide facets (e.g., 2267021951.3x).
-A very wide facet can occur for nearly coincident points at the
-boundary of the upper and lower convex hull. Four facets share the same ridge and must be merged.
-Some of these facets may be long and narrow, leading to a very wide merged facet. Starting with Qhull 2015.1, an error is reported.
-<p>Duplicate ridges occur when the horizon for a new point is "pinched" (i.e., a sub-ridge, a line segment in 3-d, is shared by two horizon facets).
-The new 'Cn,r,m' option for rbox generates nearly coincident points. For example, every point of the following
-distributions has a nearly coincident point within a 1e-13 ball. Substantially smaller and larger balls do not lead to pinched horizons.
+<p>For Delaunay triangulations an edge occurs between the corresponding upper
+and lower convex hull. Points on this edge correspond to vertices of the convex hull of the input sites.
+After multiple facet merges, four facets may share the same, duplicate ridge and must be merged.
+Some of these facets may be long and narrow, leading to a very wide merged facet.
+Starting with Qhull 2015.1, an error is reported.
+
+<p>Duplicate ridges occur when the horizon facets for a new point is "pinched".
+In a duplicate ridge, a subridge (e.g., a line segment in 3-d) is shared by two horizon facets.
+At least two of its vertices are nearly coincident. Qhull 2015.1 adds the 'Cn,r,m' option to rbox.
+This option generates nearly coincident points. For example, every point of the following
+distributions has a nearly coincident point within a 1e-13 ball.
+Substantially smaller or larger balls do not lead to pinched horizons.
<pre>
- rbox L100 10000 D4 s C1,1e-13 t2 | qhull
- rbox 50 C1,1E-13 t1447644703 | qhull d
+ rbox L100 1000 D4 s C1,1e-13 t | qhull
+ rbox 75 C1,1E-13 t | qhull d
</pre>
-For Delaunay triangulations, a simple workaround is to surround the input sites with a bounding box. Then the boundary between upper and lower convex hulls is well defined.
-A later release of qhull will avoid pinched horizons by merging duplicate sub-ridges. A sub-ridge is merged by merging adjacent vertices.
+For Delaunay triangulations, a simple workaround is to surround the input sites with a bounding box.
+The boundary between upper and lower convex hulls is defined by the bounding box.
+A later release of qhull will avoid pinched horizons by merging duplicate subridges. A subridge is
+merged by merging adjacent vertices.
<p>
<li><b>Facet with zero-area</b> --
It is possible for a zero-area facet to be convex with its
neighbors. This can occur if the hyperplanes of neighboring
facets are above the facet's centrum, and the facet's hyperplane
is above the neighboring centrums. Qhull computes the facet's
hyperplane so that it passes through the facet's vertices. The
vertices can be collinear. </p>
<p>
<li><b>No more facets</b> -- Qhull reports an error if there are <em>d+1</em> facets left
and two of the facets are not clearly convex. This typically
occurs when the convexity constraints are too strong or the input
points are degenerate. The former is more likely in 5-d and
higher -- especially with option '<a href="qh-optc.htm#Cn">C-n</a>'.</p>
<p>
<li><b>Deleted cone</b> -- Lots of merging can end up deleting all
of the new facets for a point. This is a rare event that has
only been seen while debugging the code.
<p>
<li><b>Triangulated output leads to precision problems</b> -- With sufficient
merging, the ridges of a non-simplicial facet may have serious topological
and geometric problems. A ridge may be between more than two
neighboring facets. If so, their triangulation ('<a href="qh-optq.htm#Qt">Qt</a>')
will fail since two facets have the same vertex set. Furthermore,
a triangulated facet may have flipped orientation compared to its
neighbors.</li>
<p>The triangulation process detects degenerate facets with
only two neighbors. These are marked degenerate. They have
zero area.
<p>
<li><b>Coplanar points</b> --
Option '<a href="qh-optq.htm#Qc">Qc</a>' is determined by
qh_check_maxout() after constructing the hull. Qhull needs to
retain all possible coplanar points in the facets' coplanar sets.
This depends on qh_RATIOnearInside in <tt>user.h.</tt>
Furthermore, the cutoff for a coplanar point is arbitrarily set
at the minimum vertex. If coplanar points are important to your
application, remove the interior points by hand (set '<a
href="qh-optq.htm#Qc">Qc</a> <a href="qh-optq.htm#Qi">Qi</a>') or
make qh_RATIOnearInside sufficiently large.</p>
<p>
<li><b>Maximum roundoff error</b> -- Qhull computes the maximum roundoff error from the maximum
coordinates of the point set. Usually the maximum roundoff error
is a reasonable choice for all distance computations. The maximum
roundoff error could be computed separately for each point or for
each distance computation. This is expensive and it conflicts
with option '<a href="qh-optc.htm#Cn">C-n</a>'.
<p>
<li><b>All flipped or upper Delaunay</b> -- When a lot of merging occurs for
Delaunay triangulations, a new point may lead to no good facets. For example,
<p>The first line is the number of facets. The remainder is the
number of merges for each facet, one per line. At most 511 merges
-are reported for a facet. See '<A href="qh-optp.htm#PMn">PMn</a>'
+are reported for a facet. See '<a href="qh-optp.htm#PMn">PMn</a>'
for printing the facets with the most merges. </p>
<h3><a href="#format">»</a><a name="FM">FM - print Maple
output </a></h3>
<p>Qhull writes a Maple file for 2-d and 3-d convex hulls,
2-d and 3-d halfspace intersections,
and 2-d Delaunay triangulations. Qhull produces a 2-d
or 3-d plot.
<p><i>Warning</i>: This option has not been tested in Maple.
<p>[From T. K. Abraham with help from M. R. Feinberg and N. Platinova.]
The following steps apply while working within the
Maple worksheet environment :
<ol>
<li>Generate the data and store it as an array . For example, in 3-d, data generated
in Maple is of the form : x[i],y[i],z[i]
<p>
<li>Create a single variable and assign the entire array of data points to this variable.
Use the "seq" command within square brackets as shown in the following example.
(The square brackets are essential for the rest of the steps to work.)
<p>
>data:=[seq([x[i],y[i],z[i]],i=1..n)]:# here n is the number of data points
<li>Next we need to write the data to a file to be read by qhull. Before
writing the data to a file, make sure that the qhull executable files and
the data file lie in the same subdirectory. If the executable files are
stored in the "C:\qhull3.1\" subdirectory, then save the file in the same
subdirectory, say "C:\qhull3.1\datafile.txt". For the sake of integrity of
the data file , it is best to first ensure that the data file does not
exist before writing into the data file. This can be done by running a
delete command first . To write the data to the file, use the "writedata"
and the "writedata[APPEND]" commands as illustrated in the following example :
<p>
>system("del c:\\qhull3.1\\datafile.txt");#To erase any previous versions of the file
<br>>writedata("c:\\qhull3.1\\datafile.txt ",[3, nops(data)]);#writing in qhull format
<br>>writedata[APPEND]("c:\\ qhull3.1\\datafile.txt ", data);#writing the data points
<li>
Use the 'FM' option to produce Maple output. Store the output as a ".mpl" file.
For example, using the file we created above, we type the following (in DOS environment)
<p>
qconvex s FM <datafile.txt >dataplot.mpl
<li>
To read 3-d output in Maple, we use the 'read' command followed by
a 'display3d' command. For example (in Maple environment):
<p>
>with (plots):
<br>>read `c:\\qhull3.1\\dataplot.mpl`:#IMPORTANT - Note that the punctuation mark used is ' and NOT '. The correct punctuation mark is the one next to the key for "1" (not the punctuation mark near the enter key)
<br>> qhullplot:=%:
<br>> display3d(qhullplot);
</ol>
<p>For Delaunay triangulation orthogonal projection is better.
<p>For halfspace intersections, Qhull produces the dual
convex hull.
<p>See <a href="qh-faq.htm#math">Is Qhull available for Maple?</a>
occurs after lifting the input sites to a paraboloid and computing the convex hull.
</p>
<p>Option 'Qt' is deprecated for Voronoi diagrams (<a href=qvoronoi.htm>qvoronoi</a>).
It triangulates cospherical points, leading to duplicated Voronoi vertices.</p>
<p>Option 'Qt' may produce degenerate facets with zero area.</p>
<p>Facet area and hull volumes may differ with and without
'Qt'. The triangulations are different and different triangles
may be ignored due to precision errors.
<p>With sufficient merging, the ridges of a non-simplicial facet may share more than two neighboring facets. If so, their triangulation ('<a href="#Qt">Qt</a>') will fail since two facets have the same vertex set. </p>
Qhull computes the convex hull, Delaunay triangulation, Voronoi diagram,
halfspace intersection about a point, furthest-site Delaunay
triangulation, and furthest-site Voronoi diagram. The source code runs in
2-d, 3-d, 4-d, and higher dimensions. Qhull implements the Quickhull
algorithm for computing the convex hull. It handles roundoff
errors from floating point arithmetic. It computes volumes,
surface areas, and approximations to the convex hull.</p>
<!-- duplicated in index.htm and html/index.htm -->
<p>Qhull does <i>not</i> support triangulation of non-convex surfaces, mesh
generation of non-convex objects, medium-sized inputs in 9-D
and higher, alpha shapes, weighted Voronoi diagrams, Voronoi volumes, or
constrained Delaunay triangulations, </p>
-<p>Qhull 2012.1 fixes qhull-go for Windows 64-bit. If you use Qhull 2003.1. please upgrade to 2012.1 or apply <a href="http://www.qhull.org/download/poly.c-qh_gethash.patch">poly.c-qh_gethash.patch</a>.</p>
-<!--
<p>Qhull 2015.1 introduces reentrant Qhull. It allows concurrent Qhull runs and simplifies the C++ interface to Qhull.
If you call Qhull from your program, you should use reentrant Qhull (libqhull_r) instead of qh_QHpointer (libqhull).
If you use Qhull 2003.1. please upgrade or apply <a href="http://www. qhull.org/download/poly.c-qh_gethash.patch">poly.c-qh_gethash.patch</a>.
<li><a href=http://www.voronoi.com>Voronoi Web Site</a> for all things Voronoi
<li>Young's <a href="http://homepage.usask.ca/~ijm451/finite/fe_resources/">Internet Finite Element Resources</a>
<li><a href="http://www.uic.nnov.ru/~zny/skeleton/">Zolotykh's Skeleton</a> generates all extreme rays of a polyhedral cone using the Double Description Method</li>
- 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 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
qh_fprintf(qh ferr, 6010, "qhull error: the current joggle for 'QJn', %.2g, is too large for the width\nof the input. If possible, recompile Qhull with higher-precision reals.\n",
qh JOGGLEmax);
qh_errexit(qh_ERRqhull, NULL, NULL);
}
/* for some reason, using qh ROTATErandom and qh_RANDOMseed does not repeat the run. Use 'TRn' instead */
seed= qh_RANDOMint;
qh_option("_joggle-seed", &seed, NULL);
trace0((qh ferr, 6, "qh_joggleinput: joggle input by %2.2g with seed %d\n",
scale last coordinate to [0,m] for Delaunay triangulations
input points given by points, numpoints, dim
returns:
changes scale of last coordinate from [low, high] to [0, newhigh]
overwrites last coordinate of each point
saves low/high/newhigh in qh.last_low, etc. for qh_setdelaunay()
notes:
when called by qh_setdelaunay, low/high may not match actual data
design:
compute scale and shift factors
apply to last coordinate of each point
*/
void qh_scalelast(coordT *points, int numpoints, int dim, coordT low,
coordT high, coordT newhigh) {
realT scale, shift;
coordT *coord;
int i;
boolT nearzero= False;
trace4((qh ferr, 4013, "qh_scalelast: scale last coordinate from [%2.2g, %2.2g] to [0,%2.2g]\n",
low, high, newhigh));
qh last_low= low;
qh last_high= high;
qh last_newhigh= newhigh;
scale= qh_divzero(newhigh, high - low,
qh MINdenom_1, &nearzero);
if (nearzero) {
if (qh DELAUNAY)
qh_fprintf(qh ferr, 6019, "qhull input error: can not scale last coordinate. Input is cocircular\n or cospherical. Use option 'Qz' to add a point at infinity.\n");
else
qh_fprintf(qh ferr, 6020, "qhull input error: can not scale last coordinate. New bounds [0, %2.2g] are too wide for\nexisting bounds [%2.2g, %2.2g] (width %2.2g)\n",
set flags and initialized constants from commandStr
+ calls qh_exit() if qh->NOerrexit
returns:
sets qh.qhull_command to command if needed
notes:
ignores first word (e.g., "qhull d")
use qh_strtol/strtod since strtol/strtod may or may not skip trailing spaces
see:
qh_initthresholds() continues processing of 'Pdn' and 'PDn'
'prompt' in unix.c for documentation
design:
for each space-delimited option group
if top-level option
check syntax
append appropriate option to option string
set appropriate global variable or append printFormat to print options
else
for each sub-option
check syntax
append appropriate option to option string
set appropriate global variable or append printFormat to print options
*/
void qh_initflags(char *command) {
int k, i, lastproject;
char *s= command, *t, *prev_s, *start, key;
boolT isgeom= False, wasproject;
realT r;
if(qh NOerrexit){/* without this comment, segfault in gcc 4.4.0 mingw32 */
qh_fprintf(qh ferr, 6245, "qhull initflags error: qh.NOerrexit was not cleared before calling qh_initflags(). It should be cleared after setjmp(). Exit qhull.");
qh_fprintf(qh ferr, 7039, "qhull warning: real epsilon, %2.2g, is probably too large for joggle('QJn')\nRecompile with double precision reals(see user.h).\n",
REALepsilon);
#ifdef qh_NOmerge
if (qh MERGING) {
qh_fprintf(qh ferr, 6045, "qhull input error: merging not installed(qh_NOmerge + 'Qx', 'Cn' or 'An')\n");
qh_errexit(qh_ERRinput, NULL, NULL);
}
#endif
if (qh DELAUNAY && qh KEEPcoplanar && !qh KEEPinside) {
qh KEEPinside= True;
qh_option("Qinterior-keep", NULL, NULL);
}
if (qh DELAUNAY && qh HALFspace) {
qh_fprintf(qh ferr, 6046, "qhull input error: can not use Delaunay('d') or Voronoi('v') with halfspace intersection('H')\n");
qh_errexit(qh_ERRinput, NULL, NULL);
}
if (!qh DELAUNAY && (qh UPPERdelaunay || qh ATinfinity)) {
qh_fprintf(qh ferr, 6047, "qhull input error: use upper-Delaunay('Qu') or infinity-point('Qz') with Delaunay('d') or Voronoi('v')\n");
qh_errexit(qh_ERRinput, NULL, NULL);
}
if (qh UPPERdelaunay && qh ATinfinity) {
qh_fprintf(qh ferr, 6048, "qhull input error: can not use infinity-point('Qz') with upper-Delaunay('Qu')\n");
qh_errexit(qh_ERRinput, NULL, NULL);
}
if (qh SCALElast && !qh DELAUNAY && qh PRINTprecision)
qh_fprintf(qh ferr, 7040, "qhull input warning: option 'Qbb' (scale-last-coordinate) is normally used with 'd' or 'v'\n");
qh_fprintf(qh ferr, 6056, "qhull input error: Mathematica and Maple output is only available for 2-d and 3-d convex hulls and 2-d Delaunay triangulations\n");
qh_errexit(qh_ERRinput, NULL, NULL);
}
if (printgeom) {
if (qh hull_dim > 4) {
qh_fprintf(qh ferr, 6057, "qhull input error: Geomview output is only available for 2-d, 3-d and 4-d\n");
qh_errexit(qh_ERRinput, NULL, NULL);
}
if (qh PRINTnoplanes && !(qh PRINTcoplanar + qh PRINTcentrums
Report error if library does not agree with caller
notes:
NOerrors -- qh_lib_check can not call qh_errexit()
*/
void qh_lib_check(int qhullLibraryType, int qhTsize, int vertexTsize, int ridgeTsize, int facetTsize, int setTsize, int qhmemTsize) {
boolT iserror= False;
if (qhullLibraryType==QHULL_NON_REENTRANT) { /* 0 */
if (qh_QHpointer) {
qh_fprintf_stderr(6246, "qh_lib_check: Incorrect qhull library called. Caller uses a static qhT while library uses a dynamic qhT via qh_QHpointer. Both caller and library are non-reentrant.\n");
iserror= True;
}
}else if (qhullLibraryType==QHULL_QH_POINTER) { /* 1 */
if (!qh_QHpointer) {
qh_fprintf_stderr(6247, "qh_lib_check: Incorrect qhull library called. Caller uses a dynamic qhT via qh_QHpointer while library uses a static qhT. Both caller and library are non-reentrant.\n");
iserror= True;
}
}else if (qhullLibraryType==QHULL_REENTRANT) { /* 2 */
qh_fprintf_stderr(6248, "qh_lib_check: Incorrect qhull library called. Caller uses reentrant Qhull while library is non-reentrant\n");
qh_fprintf_stderr(6249, "qh_lib_check: Incorrect qhull library called. Size of qhT for caller is %d, but for library is %d.\n", qhTsize, sizeof(qhT));
iserror= True;
}
if (vertexTsize != sizeof(vertexT)) {
qh_fprintf_stderr(6250, "qh_lib_check: Incorrect qhull library called. Size of vertexT for caller is %d, but for library is %d.\n", vertexTsize, sizeof(vertexT));
iserror= True;
}
if (ridgeTsize != sizeof(ridgeT)) {
qh_fprintf_stderr(6251, "qh_lib_check: Incorrect qhull library called. Size of ridgeT for caller is %d, but for library is %d.\n", ridgeTsize, sizeof(ridgeT));
iserror= True;
}
if (facetTsize != sizeof(facetT)) {
qh_fprintf_stderr(6252, "qh_lib_check: Incorrect qhull library called. Size of facetT for caller is %d, but for library is %d.\n", facetTsize, sizeof(facetT));
iserror= True;
}
if (setTsize && setTsize != sizeof(setT)) {
qh_fprintf_stderr(6253, "qh_lib_check: Incorrect qhull library called. Size of setT for caller is %d, but for library is %d.\n", setTsize, sizeof(setT));
iserror= True;
}
if (qhmemTsize && qhmemTsize != sizeof(qhmemT)) {
qh_fprintf_stderr(6254, "qh_lib_check: Incorrect qhull library called. Size of qhmemT for caller is %d, but for library is %d.\n", qhmemTsize, sizeof(qhmemT));
iserror= True;
}
if (iserror) {
if(qh_QHpointer){
qh_fprintf_stderr(6255, "qh_lib_check: Cannot continue. Library '%s' uses a dynamic qhT via qh_QHpointer (e.g., qhull_p.so)\n", qh_version2);
qh_fprintf(qh ferr, 6069, "qhull internal error (qh_printend): number of ridges %d != number printed %d and at end %d\n", qh ridgeoutnum, qh printoutvar, num);
qh_fprintf_stderr(6244, "qh_memcheck error: either qhmem is overwritten or qhmem is not initialized. Call qh_meminit() or qh_new_qhull() before calling qh_mem routines. ferr 0x%x IsTracing %d ALIGNmask 0x%x", qhmem.ferr, qhmem.IStracing, qhmem.ALIGNmask);
qh_exit(qhmem_ERRqhull); /* can not use qh_errexit() */
}
if (qhmem.IStracing != 0)
qh_fprintf(qhmem.ferr, 8143, "qh_memcheck: check size of freelists on qhmem\nqh_memcheck: A segmentation fault indicates an overwrite of qhmem\n");
for (i=0; i < qhmem.TABLEsize; i++) {
count=0;
for (object= qhmem.freelists[i]; object; object= *((void **)object))
count++;
totfree += qhmem.sizetable[i] * count;
}
if (totfree != qhmem.totfree) {
qh_fprintf(qhmem.ferr, 6211, "Qhull internal error (qh_memcheck): totfree %d not equal to freelist total %d\n", qhmem.totfree, totfree);
qh_errexit(qhmem_ERRqhull, NULL, NULL);
}
if (qhmem.IStracing != 0)
qh_fprintf(qhmem.ferr, 8144, "qh_memcheck: total size of freelists totfree is the same as qhmem.totfree\n", totfree);
qh_fprintf(qh ferr, 6096, "qhull internal error (qh_forcedmerges): f%d and f%d had a duplicate ridge but as f%d and f%d they are no longer neighbors\n",
qh_fprintf(qh ferr, 6109, "qhull precision error: point p%d is outside facet f%d, distance= %6.8g maxoutside= %6.8g\n",
facet_i, bestfacet->id, dist, maxoutside);
if (errfacet1 != bestfacet) {
errfacet2= errfacet1;
errfacet1= bestfacet;
}
}
}else if (unassigned && dist < -qh MAXcoplanar)
notverified++;
}
qh_settempfree(&facets);
if (notverified && !qh DELAUNAY && !qh_QUICKhelp && qh PRINTprecision)
qh_fprintf(qh ferr, 8092, "\n%d points were well inside the hull. If the hull contains\n\
a lens-shaped component, these points were not verified. Use\n\
options 'Qci Tv' to verify all points.\n", notverified);
if (maxdist > qh outside_err) {
qh_fprintf(qh ferr, 6110, "qhull precision error (qh_check_bestdist): a coplanar point is %6.2g from convex hull. The maximum value(qh.outside_err) is %6.2g\n",
maxdist, qh outside_err);
qh_errexit2(qh_ERRprec, errfacet1, errfacet2);
}else if (waserror && qh outside_err > REALmax/2)
qh_errexit2(qh_ERRprec, errfacet1, errfacet2);
/* else if waserror, the error was logged to qh.ferr but does not effect the output */
trace0((qh ferr, 20, "qh_check_bestdist: max distance outside %2.2g\n", maxdist));
+ trace0((qh ferr, 16, "qh_check_dupridge: duplicate ridge between f%d and f%d due to nearly-coincident vertices (%2.2g), dist %2.2g, reverse dist %2.2g, ratio %2.2g while processing p%d\n",
+ qh_fprintf(qh ferr, 6271, "qhull precision error (qh_check_dupridge): wide merge (%.0f times wider) due to duplicate ridge with nearly coincident points (%2.2g) between f%d and f%d, merge dist %2.2g, while processing p%d\n- Ignore error with option 'Q12'\n- To be fixed in a later version of Qhull\n",
+ qh_fprintf(qh ferr, 8145, "- A simple workaround is to add a bounding box to the input sites\n");
+ if(minvertex > qh_WIDEduplicate*prevdist)
+ qh_fprintf(qh ferr, 8146, "- Vertex distance %2.2g is greater than %d times maximum distance %2.2g\n Please report to bradb@shore.net with steps to reproduce and all output\n",
qh_fprintf(qh ferr, 6112, "qhull precision error (qh_check_points): a coplanar point is %6.2g from convex hull. The maximum value(qh.outside_err) is %6.2g\n",
maxdist, qh outside_err );
qh_errexit2( qh_ERRprec, errfacet1, errfacet2 );
}else if (errfacet1 && qh outside_err > REALmax/2)
qh_errexit2( qh_ERRprec, errfacet1, errfacet2 );
/* else if errfacet1, the error was logged to qh.ferr but does not effect the output */
trace0((qh ferr, 21, "qh_check_points: max distance outside %2.2g\n", maxdist));
qh_fprintf(qh ferr, 6151, "qhull input error: 'Qg QVn' (only good vertex) does not work with merging.\nUse 'QJ' to joggle the input or 'Q0' to turn off merging.\n");
if (!qh_checkflipped(facet, NULL, qh_ALL)) {/* due to axis-parallel facet */
trace1((qh ferr, 1031, "qh_initialhull: initial orientation incorrect. Correct all facets\n"));
facet->flipped= False;
FORALLfacets {
facet->toporient ^= (unsigned char)True;
qh_orientoutside(facet);
}
break;
}
}
FORALLfacets {
if (!qh_checkflipped(facet, NULL, !qh_ALL)) { /* can happen with 'R0.1' */
if (qh DELAUNAY && ! qh ATinfinity) {
if (qh UPPERdelaunay)
- qh_fprintf(qh ferr, 6240, "Qhull input error: Can not compute the upper Delaunay triangulation or upper Voronoi diagram of cocircular/cospherical points.\n");
+ qh_fprintf(qh ferr, 6240, "Qhull precision error: Initial simplex is cocircular or cospherical. Option 'Qs' searches all points. Can not compute the upper Delaunay triangulation or upper Voronoi diagram of cocircular/cospherical points.\n");
else
- qh_fprintf(qh ferr, 6239, "Qhull input error: Use option 'Qz' for the Delaunay triangulation or Voronoi diagram of cocircular/cospherical points. Option 'Qz' adds a point \"at infinity\" (above the corresponding paraboloid).\n");
+ qh_fprintf(qh ferr, 6239, "Qhull precision error: Initial simplex is cocircular or cospherical. Use option 'Qz' for the Delaunay triangulation or Voronoi diagram of cocircular/cospherical points. Option 'Qz' adds a point \"at infinity\". Use option 'Qs' to search all points for the initial simplex.\n");
qh_errexit(qh_ERRinput, NULL, NULL);
}
- qh_precision("initial facet is coplanar with interior point");
- qh_fprintf(qh ferr, 6154, "qhull precision error: initial facet %d is coplanar with the interior point\n",
- facet->id);
- qh_errexit(qh_ERRsingular, facet, NULL);
+ qh_precision("initial simplex is flat");
+ qh_fprintf(qh ferr, 6154, "Qhull precision error: Initial simplex is flat (facet %d is coplanar with the interior point)\n",
returns size of qh.hash_table of at least newsize slots
notes:
assumes qh.hash_table is NULL
qh_HASHfactor determines the number of extra slots
size is not divisible by 2, 3, or 5
*/
int qh_newhashtable(int newsize) {
int size;
size= ((newsize+1)*qh_HASHfactor) | 0x1; /* odd number */
while (True) {
if (newsize<0 || size<0) {
qh_fprintf(qhmem.ferr, 6236, "qhull error (qh_newhashtable): negative request (%d) or size (%d). Did int overflow due to high-D?\n", newsize, size); /* WARN64 */
qh_errexit(qhmem_ERRmem, NULL, NULL);
}
if ((size%3) && (size%5))
break;
size += 2;
/* loop terminates because there is an infinite number of primes */
while (*s && !isspace(*s)) /* skip program name */
s++;
while (*s) {
while (*s && isspace(*s))
s++;
if (*s == '-')
s++;
if (!*s)
break;
if (isdigit(*s)) {
numpoints= qh_strtol(s, &s);
continue;
}
/* ============= read flags =============== */
switch (*s++) {
case 'c':
addcube= 1;
t= s;
while (isspace(*t))
t++;
if (*t == 'G')
cube= qh_strtod(++t, &s);
break;
case 'd':
adddiamond= 1;
t= s;
while (isspace(*t))
t++;
if (*t == 'G')
diamond= qh_strtod(++t, &s);
break;
case 'h':
iscdd= 1;
break;
case 'l':
isspiral= 1;
break;
case 'n':
NOcommand= 1;
break;
case 'r':
isregular= 1;
break;
case 's':
issphere= 1;
break;
case 't':
istime= 1;
if (isdigit(*s)) {
seed= qh_strtol(s, &s);
israndom= 0;
}else
israndom= 1;
break;
case 'x':
issimplex= 1;
break;
case 'y':
issimplex2= 1;
break;
case 'z':
rbox.isinteger= 1;
break;
case 'B':
box= qh_strtod(s, &s);
isbox= 1;
break;
+ case 'C':
+ if (*s)
+ coincidentpoints= qh_strtol(s, &s);
+ if (*s == ',') {
+ ++s;
+ coincidentradius= qh_strtod(s, &s);
+ }
+ if (*s == ',') {
+ ++s;
+ coincidenttotal= qh_strtol(s, &s);
+ }
+ if (*s && !isspace(*s)) {
+ qh_fprintf_rbox(rbox.ferr, 7080, "rbox error: arguments for 'Cn,r,m' are not 'int', 'float', and 'int'. Remaining string is '%s'\n", s);
+ qh_errexit_rbox(qh_ERRinput);
+ }
+ if (coincidentpoints==0){
+ qh_fprintf_rbox(rbox.ferr, 6268, "rbox error: missing arguments for 'Cn,r,m' where n is the number of coincident points, r is the radius (default 0.0), and m is the number of points\n");
+ qh_errexit_rbox(qh_ERRinput);
+ }
+ if (coincidentpoints<0 || coincidenttotal<0 || coincidentradius<0.0){
+ qh_fprintf_rbox(rbox.ferr, 6269, "rbox error: negative arguments for 'Cn,m,r' where n (%d) is the number of coincident points, m (%d) is the number of points, and r (%.2g) is the radius (default 0.0)\n", coincidentpoints, coincidenttotal, coincidentradius);
+ qh_errexit_rbox(qh_ERRinput);
+ }
+ break;
case 'D':
dim= qh_strtol(s, &s);
if (dim < 1
|| dim > MAXdim) {
qh_fprintf_rbox(rbox.ferr, 6189, "rbox error: dimension, D%d, out of bounds (>=%d or <=0)", dim, MAXdim);
qh_errexit_rbox(qh_ERRinput);
}
break;
case 'G':
if (isdigit(*s))
gap= qh_strtod(s, &s);
else
gap= 0.5;
isgap= 1;
break;
case 'L':
if (isdigit(*s))
radius= qh_strtod(s, &s);
else
radius= 10;
islens= 1;
break;
case 'M':
ismesh= 1;
if (*s)
meshn= qh_strtod(s, &s);
if (*s == ',') {
++s;
meshm= qh_strtod(s, &s);
}else
meshm= 0.0;
if (*s == ',') {
++s;
meshr= qh_strtod(s, &s);
}else
meshr= sqrt(meshn*meshn + meshm*meshm);
if (*s && !isspace(*s)) {
qh_fprintf_rbox(rbox.ferr, 7069, "rbox warning: assuming 'M3,4,5' since mesh args are not integers or reals\n");
meshn= 3.0, meshm=4.0, meshr=5.0;
}
break;
case 'O':
rbox.out_offset= qh_strtod(s, &s);
break;
case 'P':
if (!first_point)
first_point= s-1;
addpoints++;
while (*s && !isspace(*s)) /* read points later */
s++;
break;
case 'W':
width= qh_strtod(s, &s);
iswidth= 1;
break;
case 'Z':
if (isdigit(*s))
radius= qh_strtod(s, &s);
else
radius= 1.0;
isaxis= 1;
break;
default:
qh_fprintf_rbox(rbox.ferr, 7070, "rbox error: unknown flag at %s.\nExecute 'rbox' without arguments for documentation.\n", s);
qh_errexit_rbox(qh_ERRinput);
}
if (*s && !isspace(*s)) {
qh_fprintf_rbox(rbox.ferr, 7071, "rbox error: missing space between flags at %s.\n", s);
qh_errexit_rbox(qh_ERRinput);
}
}
/* ============= defaults, constants, and sizes =============== */
if (rbox.isinteger && !isbox)
box= qh_DEFAULTzbox;
if (addcube) {
cubesize= (int)floor(ldexp(1.0,dim)+0.5);
if (cube == 0.0)
cube= box;
}else
cubesize= 0;
if (adddiamond) {
diamondsize= 2*dim;
if (diamond == 0.0)
diamond= box;
}else
diamondsize= 0;
if (islens) {
if (isaxis) {
qh_fprintf_rbox(rbox.ferr, 6190, "rbox error: can not combine 'Ln' with 'Zn'\n");
qh_errexit_rbox(qh_ERRinput);
}
if (radius <= 1.0) {
qh_fprintf_rbox(rbox.ferr, 6191, "rbox error: lens radius %.2g should be greater than 1.0\n",
+ qh_fprintf_rbox(rbox.ferr, 6270, "rbox error: 'Cn,r,m' requested n coincident points for each of m points. Either there is no points or m (%d) is greater than the number of points (%d).\n", coincidenttotal, numpoints);
+ qh_errexit_rbox(qh_ERRinput);
+ }
+ if (coincidenttotal == 0)
+ coincidenttotal= numpoints;
/* ============= print header with total points =============== */
if (issimplex || ismesh)
totpoints= numpoints;
else if (issimplex2)
totpoints= numpoints+dim+1;
else if (isregular) {
totpoints= numpoints;
if (dim == 2) {
if (islens)
totpoints += numpoints - 2;
}else if (dim == 3) {
if (islens)
totpoints += 2 * numpoints;
else if (isgap)
totpoints += 1 + numpoints;
else
totpoints += 2;
}
}else
totpoints= numpoints + isaxis;
totpoints += cubesize + diamondsize + addpoints;
+ totpoints += coincidentpoints*coincidenttotal;
/* ============= seed randoms =============== */
if (istime == 0) {
for (s=command; *s; s++) {
if (issimplex2 && *s == 'y') /* make 'y' same seed as 'x' */
i= 'x';
else
i= *s;
seed= 11*seed + i;
}
}else if (israndom) {
seed= (int)time(&timedata);
sprintf(seedbuf, " t%d", seed); /* appends an extra t, not worth removing */
if (qh->build_cnt > 1 && qh->JOGGLEmax > fmax_(qh->MAXwidth/4, 0.1)) {
qh_fprintf(qh, qh->ferr, 6010, "qhull error: the current joggle for 'QJn', %.2g, is too large for the width\nof the input. If possible, recompile Qhull with higher-precision reals.\n",
qh->JOGGLEmax);
qh_errexit(qh, qh_ERRqhull, NULL, NULL);
}
/* for some reason, using qh->ROTATErandom and qh_RANDOMseed does not repeat the run. Use 'TRn' instead */
seed= qh_RANDOMint;
qh_option(qh, "_joggle-seed", &seed, NULL);
trace0((qh, qh->ferr, 6, "qh_joggleinput: joggle input by %2.2g with seed %d\n",
scale last coordinate to [0,m] for Delaunay triangulations
input points given by points, numpoints, dim
returns:
changes scale of last coordinate from [low, high] to [0, newhigh]
overwrites last coordinate of each point
saves low/high/newhigh in qh.last_low, etc. for qh_setdelaunay()
notes:
when called by qh_setdelaunay, low/high may not match actual data
design:
compute scale and shift factors
apply to last coordinate of each point
*/
void qh_scalelast(qhT *qh, coordT *points, int numpoints, int dim, coordT low,
coordT high, coordT newhigh) {
realT scale, shift;
coordT *coord;
int i;
boolT nearzero= False;
trace4((qh, qh->ferr, 4013, "qh_scalelast: scale last coordinate from [%2.2g, %2.2g] to [0,%2.2g]\n",
low, high, newhigh));
qh->last_low= low;
qh->last_high= high;
qh->last_newhigh= newhigh;
scale= qh_divzero(newhigh, high - low,
qh->MINdenom_1, &nearzero);
if (nearzero) {
if (qh->DELAUNAY)
qh_fprintf(qh, qh->ferr, 6019, "qhull input error: can not scale last coordinate. Input is cocircular\n or cospherical. Use option 'Qz' to add a point at infinity.\n");
else
qh_fprintf(qh, qh->ferr, 6020, "qhull input error: can not scale last coordinate. New bounds [0, %2.2g] are too wide for\nexisting bounds [%2.2g, %2.2g] (width %2.2g)\n",
set flags and initialized constants from commandStr
calls qh_exit() if qh->NOerrexit
returns:
sets qh.qhull_command to command if needed
notes:
ignores first word (e.g., "qhull d")
use qh_strtol/strtod since strtol/strtod may or may not skip trailing spaces
see:
qh_initthresholds() continues processing of 'Pdn' and 'PDn'
'prompt' in unix_r.c for documentation
design:
for each space-delimited option group
if top-level option
check syntax
append appropriate option to option string
set appropriate global variable or append printFormat to print options
else
for each sub-option
check syntax
append appropriate option to option string
set appropriate global variable or append printFormat to print options
*/
void qh_initflags(qhT *qh, char *command) {
int k, i, lastproject;
char *s= command, *t, *prev_s, *start, key;
boolT isgeom= False, wasproject;
realT r;
if(qh->NOerrexit){
qh_fprintf(qh, qh->ferr, 6245, "qhull initflags error: qh.NOerrexit was not cleared before calling qh_initflags(). It should be cleared after setjmp(). Exit qhull.");
qh_fprintf(qh, qh->ferr, 6266, "qhull input warning: qh.fout was not set by caller. Cannot use option 'TO' to redirect output. Ignoring option 'TO'\n");
}else if (!freopen(filename, "w", qh->fout)) {
qh_fprintf(qh, qh->ferr, 6044, "qhull error: could not open file \"%s\".", filename);
qh_errexit(qh, qh_ERRinput, NULL, NULL);
}else {
qh_option(qh, "TOutput-file", NULL, NULL);
qh_option(qh, filename, NULL, NULL);
}
}
break;
case 'P':
if (!isdigit(*s))
qh_fprintf(qh, qh->ferr, 7029, "qhull warning: missing point id for trace option 'TPn'. Ignored\n");
if (qh->MERGING && !qh->POSTmerge && qh->premerge_cos > REALmax/2
&& qh->premerge_centrum == 0) {
qh->ZEROcentrum= True;
qh->ZEROall_ok= True;
qh_option(qh, "_zero-centrum", NULL, NULL);
}
if (qh->JOGGLEmax < REALmax/2 && REALepsilon > 2e-8 && qh->PRINTprecision)
qh_fprintf(qh, qh->ferr, 7039, "qhull warning: real epsilon, %2.2g, is probably too large for joggle('QJn')\nRecompile with double precision reals(see user.h).\n",
REALepsilon);
#ifdef qh_NOmerge
if (qh->MERGING) {
qh_fprintf(qh, qh->ferr, 6045, "qhull input error: merging not installed(qh_NOmerge + 'Qx', 'Cn' or 'An')\n");
qh_errexit(qh, qh_ERRinput, NULL, NULL);
}
#endif
if (qh->DELAUNAY && qh->KEEPcoplanar && !qh->KEEPinside) {
qh->KEEPinside= True;
qh_option(qh, "Qinterior-keep", NULL, NULL);
}
if (qh->DELAUNAY && qh->HALFspace) {
qh_fprintf(qh, qh->ferr, 6046, "qhull input error: can not use Delaunay('d') or Voronoi('v') with halfspace intersection('H')\n");
qh_errexit(qh, qh_ERRinput, NULL, NULL);
}
if (!qh->DELAUNAY && (qh->UPPERdelaunay || qh->ATinfinity)) {
qh_fprintf(qh, qh->ferr, 6047, "qhull input error: use upper-Delaunay('Qu') or infinity-point('Qz') with Delaunay('d') or Voronoi('v')\n");
qh_errexit(qh, qh_ERRinput, NULL, NULL);
}
if (qh->UPPERdelaunay && qh->ATinfinity) {
qh_fprintf(qh, qh->ferr, 6048, "qhull input error: can not use infinity-point('Qz') with upper-Delaunay('Qu')\n");
qh_errexit(qh, qh_ERRinput, NULL, NULL);
}
if (qh->SCALElast && !qh->DELAUNAY && qh->PRINTprecision)
qh_fprintf(qh, qh->ferr, 7040, "qhull input warning: option 'Qbb' (scale-last-coordinate) is normally used with 'd' or 'v'\n");
else if (qh->PRINTout[i] == qh_PRINTmathematica || qh->PRINTout[i] == qh_PRINTmaple)
printmath= True;
else if (qh->PRINTout[i] == qh_PRINTcoplanars)
printcoplanar= True;
else if (qh->PRINTout[i] == qh_PRINTpointnearest)
printcoplanar= True;
else if (qh->PRINTout[i] == qh_PRINTpointintersect && !qh->HALFspace) {
qh_fprintf(qh, qh->ferr, 6053, "qhull input error: option 'Fp' is only used for \nhalfspace intersection('Hn,n,n').\n");
qh_errexit(qh, qh_ERRinput, NULL, NULL);
}else if (qh->PRINTout[i] == qh_PRINTtriangles && (qh->HALFspace || qh->VORONOI)) {
qh_fprintf(qh, qh->ferr, 6054, "qhull input error: option 'Ft' is not available for Voronoi vertices or halfspace intersection\n");
qh_errexit(qh, qh_ERRinput, NULL, NULL);
}else if (qh->PRINTout[i] == qh_PRINTcentrums && qh->VORONOI) {
qh_fprintf(qh, qh->ferr, 6055, "qhull input error: option 'FC' is not available for Voronoi vertices('v')\n");
qh_errexit(qh, qh_ERRinput, NULL, NULL);
}else if (qh->PRINTout[i] == qh_PRINTvertices) {
if (qh->VORONOI)
qh_option(qh, "Fvoronoi", NULL, NULL);
else
qh_option(qh, "Fvertices", NULL, NULL);
}
}
if (printcoplanar && qh->DELAUNAY && qh->JOGGLEmax < REALmax/2) {
if (qh->PRINTprecision)
qh_fprintf(qh, qh->ferr, 7041, "qhull input warning: 'QJ' (joggle) will usually prevent coincident input sites for options 'Fc' and 'FP'\n");
}
if (printmath && (qh->hull_dim > 3 || qh->VORONOI)) {
qh_fprintf(qh, qh->ferr, 6056, "qhull input error: Mathematica and Maple output is only available for 2-d and 3-d convex hulls and 2-d Delaunay triangulations\n");
qh_errexit(qh, qh_ERRinput, NULL, NULL);
}
if (printgeom) {
if (qh->hull_dim > 4) {
qh_fprintf(qh, qh->ferr, 6057, "qhull input error: Geomview output is only available for 2-d, 3-d and 4-d\n");
qh_errexit(qh, qh_ERRinput, NULL, NULL);
}
if (qh->PRINTnoplanes && !(qh->PRINTcoplanar + qh->PRINTcentrums
Report error if library does not agree with caller
notes:
NOerrors -- qh_lib_check can not call qh_errexit()
*/
void qh_lib_check(int qhullLibraryType, int qhTsize, int vertexTsize, int ridgeTsize, int facetTsize, int setTsize, int qhmemTsize) {
boolT iserror= False;
if (qhullLibraryType==QHULL_NON_REENTRANT) { /* 0 */
qh_fprintf_stderr(6257, "qh_lib_check: Incorrect qhull library called. Caller uses non-reentrant Qhull with a static qhT. Library is reentrant.\n");
iserror= True;
}else if (qhullLibraryType==QHULL_QH_POINTER) { /* 1 */
qh_fprintf_stderr(6258, "qh_lib_check: Incorrect qhull library called. Caller uses non-reentrant Qhull with a dynamic qhT via qh_QHpointer. Library is reentrant.\n");
iserror= True;
}else if (qhullLibraryType!=QHULL_REENTRANT) { /* 2 */
qh_fprintf_stderr(6249, "qh_lib_check: Incorrect qhull library called. Size of qhT for caller is %d, but for library is %d.\n", qhTsize, sizeof(qhT));
iserror= True;
}
if (vertexTsize != sizeof(vertexT)) {
qh_fprintf_stderr(6250, "qh_lib_check: Incorrect qhull library called. Size of vertexT for caller is %d, but for library is %d.\n", vertexTsize, sizeof(vertexT));
iserror= True;
}
if (ridgeTsize != sizeof(ridgeT)) {
qh_fprintf_stderr(6251, "qh_lib_check: Incorrect qhull library called. Size of ridgeT for caller is %d, but for library is %d.\n", ridgeTsize, sizeof(ridgeT));
iserror= True;
}
if (facetTsize != sizeof(facetT)) {
qh_fprintf_stderr(6252, "qh_lib_check: Incorrect qhull library called. Size of facetT for caller is %d, but for library is %d.\n", facetTsize, sizeof(facetT));
iserror= True;
}
if (setTsize && setTsize != sizeof(setT)) {
qh_fprintf_stderr(6253, "qh_lib_check: Incorrect qhull library called. Size of setT for caller is %d, but for library is %d.\n", setTsize, sizeof(setT));
iserror= True;
}
if (qhmemTsize && qhmemTsize != sizeof(qhmemT)) {
qh_fprintf_stderr(6254, "qh_lib_check: Incorrect qhull library called. Size of qhmemT for caller is %d, but for library is %d.\n", qhmemTsize, sizeof(qhmemT));
if (num != qh->ridgeoutnum || qh->printoutvar != qh->ridgeoutnum) {
qh_fprintf(qh, qh->ferr, 6069, "qhull internal error (qh_printend): number of ridges %d != number printed %d and at end %d\n", qh->ridgeoutnum, qh->printoutvar, num);
qh_fprintf(qh, qh->ferr, 8120, "qh_addpoint: add p%d(v%d) to hull of %d facets(%2.2g above f%d) and %d outside at %4.4g CPU secs. Previous was p%d.\n",
qh_fprintf(qh, qh->ferr, 6096, "qhull internal error (qh_forcedmerges): f%d and f%d had a duplicate ridge but as f%d and f%d they are no longer neighbors\n",
if (facet2 == qh->tracefacet || (qh->tracevertex && qh->tracevertex->newlist)) {
qh_fprintf(qh, qh->ferr, 8085, "qh_tracemerge: trace facet and vertex after merge of f%d and f%d, furthest p%d\n", facet1->id, facet2->id, qh->furthest_id);
FOREACHfacet_i_(qh, facets) { /* for each point with facet assignment */
if (facet)
unassigned= False;
else {
unassigned= True;
facet= qh->facet_list;
}
point= qh_point(qh, facet_i);
if (point == qh->GOODpointp)
continue;
qh_distplane(qh, point, facet, &dist);
numpart++;
bestfacet= qh_findbesthorizon(qh, !qh_IScheckmax, point, facet, qh_NOupper, &dist, &numpart);
/* occurs after statistics reported */
maximize_(maxdist, dist);
if (dist > maxoutside) {
if (qh->ONLYgood && !bestfacet->good
&& !((bestfacet= qh_findgooddist(qh, point, bestfacet, &dist, &facetlist))
&& dist > maxoutside))
notgood++;
else {
waserror= True;
qh_fprintf(qh, qh->ferr, 6109, "qhull precision error: point p%d is outside facet f%d, distance= %6.8g maxoutside= %6.8g\n",
facet_i, bestfacet->id, dist, maxoutside);
if (errfacet1 != bestfacet) {
errfacet2= errfacet1;
errfacet1= bestfacet;
}
}
}else if (unassigned && dist < -qh->MAXcoplanar)
notverified++;
}
qh_settempfree(qh, &facets);
if (notverified && !qh->DELAUNAY && !qh_QUICKhelp && qh->PRINTprecision)
qh_fprintf(qh, qh->ferr, 8092, "\n%d points were well inside the hull. If the hull contains\n\
a lens-shaped component, these points were not verified. Use\n\
options 'Qci Tv' to verify all points.\n", notverified);
if (maxdist > qh->outside_err) {
qh_fprintf(qh, qh->ferr, 6110, "qhull precision error (qh_check_bestdist): a coplanar point is %6.2g from convex hull. The maximum value(qh.outside_err) is %6.2g\n",
+ trace0((qh, qh->ferr, 16, "qh_check_dupridge: duplicate ridge between f%d and f%d due to nearly-coincident vertices (%2.2g), dist %2.2g, reverse dist %2.2g, ratio %2.2g while processing p%d\n",
+ qh_fprintf(qh, qh->ferr, 6271, "qhull precision error (qh_check_dupridge): wide merge (%.0f times wider) due to duplicate ridge with nearly coincident points (%2.2g) between f%d and f%d, merge dist %2.2g, while processing p%d\n- Ignore error with option 'Q12'\n- To be fixed in a later version of Qhull\n",
+ qh_fprintf(qh, qh->ferr, 8145, "- A simple workaround is to add a bounding box to the input sites\n");
+ if(minvertex > qh_WIDEduplicate*prevdist)
+ qh_fprintf(qh, qh->ferr, 8146, "- Vertex distance %2.2g is greater than %d times maximum distance %2.2g\n Please report to bradb@shore.net with steps to reproduce and all output\n",
qh_fprintf(qh, qh->ferr, 7061, "qhull warning (qh_check_points): missing normal for facet f%d\n", facet->id);
continue;
}
if (testouter) {
#if qh_MAXoutside
maxoutside= facet->maxoutside + 2* qh->DISTround;
/* one DISTround to actual point and another to computed point */
#endif
}
FORALLpoints {
if (point != qh->GOODpointp)
qh_check_point(qh, point, facet, &maxoutside, &maxdist, &errfacet1, &errfacet2);
}
FOREACHpoint_(qh->other_points) {
if (point != qh->GOODpointp)
qh_check_point(qh, point, facet, &maxoutside, &maxdist, &errfacet1, &errfacet2);
}
}
if (maxdist > qh->outside_err) {
qh_fprintf(qh, qh->ferr, 6112, "qhull precision error (qh_check_points): a coplanar point is %6.2g from convex hull. The maximum value(qh.outside_err) is %6.2g\n",
qh_fprintf(qh, qh->ferr, 6122, "qhull internal error (qh_checkfacet): vertices of f%d are not in descending id order at v%d\n", facet->id, vertex->id);
if (qh_pointid(qh, vertex->point) == qh_IDunknown) {
qh_fprintf(qh, qh->ferr, 6139, "qhull internal error (qh_checkpolygon): unknown point %p for vertex v%d first_point %p\n",
vertex->point, vertex->id, qh->first_point);
waserror= True;
}
}
}
}
qh->vertex_visit += (unsigned int)numfacets;
if (facetlist == qh->facet_list) {
if (numfacets != qh->num_facets - qh->num_visible) {
qh_fprintf(qh, qh->ferr, 6140, "qhull internal error (qh_checkpolygon): actual number of facets is %d, cumulative facet count is %d - %d visible facets\n",
numfacets, qh->num_facets, qh->num_visible);
waserror= True;
}
qh->vertex_visit++;
if (qh->VERTEXneighbors) {
FORALLvertices {
qh_setcheck(qh, vertex->neighbors, "neighbors for v", vertex->id);
qh_fprintf(qh, qh->ferr, 6151, "qhull input error: 'Qg QVn' (only good vertex) does not work with merging.\nUse 'QJ' to joggle the input or 'Q0' to turn off merging.\n");
if (!qh_checkflipped(qh, facet, NULL, qh_ALL)) {/* due to axis-parallel facet */
trace1((qh, qh->ferr, 1031, "qh_initialhull: initial orientation incorrect. Correct all facets\n"));
facet->flipped= False;
FORALLfacets {
facet->toporient ^= (unsigned char)True;
qh_orientoutside(qh, facet);
}
break;
}
}
FORALLfacets {
if (!qh_checkflipped(qh, facet, NULL, !qh_ALL)) { /* can happen with 'R0.1' */
if (qh->DELAUNAY && ! qh->ATinfinity) {
if (qh->UPPERdelaunay)
- qh_fprintf(qh, qh->ferr, 6240, "Qhull input error: Can not compute the upper Delaunay triangulation or upper Voronoi diagram of cocircular/cospherical points.\n");
+ qh_fprintf(qh, qh->ferr, 6240, "Qhull precision error: Initial simplex is cocircular or cospherical. Option 'Qs' searches all points. Can not compute the upper Delaunay triangulation or upper Voronoi diagram of cocircular/cospherical points.\n");
else
- qh_fprintf(qh, qh->ferr, 6239, "Qhull input error: Use option 'Qz' for the Delaunay triangulation or Voronoi diagram of cocircular/cospherical points. Option 'Qz' adds a point \"at infinity\" (above the corresponding paraboloid).\n");
+ qh_fprintf(qh, qh->ferr, 6239, "Qhull precision error: Initial simplex is cocircular or cospherical. Use option 'Qz' for the Delaunay triangulation or Voronoi diagram of cocircular/cospherical points. Option 'Qz' adds a point \"at infinity\". Use option 'Qs' to search all points for the initial simplex.\n");
qh_errexit(qh, qh_ERRinput, NULL, NULL);
}
- qh_precision(qh, "initial facet is coplanar with interior point");
- qh_fprintf(qh, qh->ferr, 6154, "qhull precision error: initial facet %d is coplanar with the interior point\n",
+ qh_precision(qh, "initial simplex is flat");
+ qh_fprintf(qh, qh->ferr, 6154, "Qhull precision error: Initial simplex is flat (facet %d is coplanar with the interior point)\n",
returns size of qh.hash_table of at least newsize slots
notes:
assumes qh.hash_table is NULL
qh_HASHfactor determines the number of extra slots
size is not divisible by 2, 3, or 5
*/
int qh_newhashtable(qhT *qh, int newsize) {
int size;
size= ((newsize+1)*qh_HASHfactor) | 0x1; /* odd number */
while (True) {
if (newsize<0 || size<0) {
qh_fprintf(qh, qh->qhmem.ferr, 6236, "qhull error (qh_newhashtable): negative request (%d) or size (%d). Did int overflow due to high-D?\n", newsize, size); /* WARN64 */
qh_errexit(qh, qhmem_ERRmem, NULL, NULL);
}
if ((size%3) && (size%5))
break;
size += 2;
/* loop terminates because there is an infinite number of primes */
<li><a href="usermem_r.c#qh_exit">qh_exit</a> exit program, same as exit(). May be redefined as throw "QH10003.." by libqhullcpp/usermem_r-cpp.cpp</li>
<li><a href="usermem_r.c#qh_fprintf_stderr">qh_fprintf_stderr</a> print to stderr when qh->ferr is not defined.</li>
<li><a href="usermem_r.c#qh_free">qh_free</a> free memory, same as free().</li>
<li><a href="usermem_r.c#qh_malloc">qh_malloc</a> allocate memory, same as malloc()</li>
while (*s && !isspace(*s)) /* skip program name */
s++;
while (*s) {
while (*s && isspace(*s))
s++;
if (*s == '-')
s++;
if (!*s)
break;
if (isdigit(*s)) {
numpoints= qh_strtol(s, &s);
continue;
}
/* ============= read flags =============== */
switch (*s++) {
case 'c':
addcube= 1;
t= s;
while (isspace(*t))
t++;
if (*t == 'G')
cube= qh_strtod(++t, &s);
break;
case 'd':
adddiamond= 1;
t= s;
while (isspace(*t))
t++;
if (*t == 'G')
diamond= qh_strtod(++t, &s);
break;
case 'h':
iscdd= 1;
break;
case 'l':
isspiral= 1;
break;
case 'n':
NOcommand= 1;
break;
case 'r':
isregular= 1;
break;
case 's':
issphere= 1;
break;
case 't':
istime= 1;
if (isdigit(*s)) {
seed= qh_strtol(s, &s);
israndom= 0;
}else
israndom= 1;
break;
case 'x':
issimplex= 1;
break;
case 'y':
issimplex2= 1;
break;
case 'z':
qh->rbox_isinteger= 1;
break;
case 'B':
box= qh_strtod(s, &s);
isbox= 1;
break;
+ case 'C':
+ if (*s)
+ coincidentpoints= qh_strtol(s, &s);
+ if (*s == ',') {
+ ++s;
+ coincidentradius= qh_strtod(s, &s);
+ }
+ if (*s == ',') {
+ ++s;
+ coincidenttotal= qh_strtol(s, &s);
+ }
+ if (*s && !isspace(*s)) {
+ qh_fprintf_rbox(qh, qh->ferr, 7080, "rbox error: arguments for 'Cn,r,m' are not 'int', 'float', and 'int'. Remaining string is '%s'\n", s);
+ qh_errexit_rbox(qh, qh_ERRinput);
+ }
+ if (coincidentpoints==0){
+ qh_fprintf_rbox(qh, qh->ferr, 6268, "rbox error: missing arguments for 'Cn,r,m' where n is the number of coincident points, r is the radius (default 0.0), and m is the number of points\n");
+ qh_errexit_rbox(qh, qh_ERRinput);
+ }
+ if (coincidentpoints<0 || coincidenttotal<0 || coincidentradius<0.0){
+ qh_fprintf_rbox(qh, qh->ferr, 6269, "rbox error: negative arguments for 'Cn,m,r' where n (%d) is the number of coincident points, m (%d) is the number of points, and r (%.2g) is the radius (default 0.0)\n", coincidentpoints, coincidenttotal, coincidentradius);
+ qh_errexit_rbox(qh, qh_ERRinput);
+ }
+ break;
case 'D':
dim= qh_strtol(s, &s);
if (dim < 1
|| dim > MAXdim) {
qh_fprintf_rbox(qh, qh->ferr, 6189, "rbox error: dimension, D%d, out of bounds (>=%d or <=0)", dim, MAXdim);
qh_errexit_rbox(qh, qh_ERRinput);
}
break;
case 'G':
if (isdigit(*s))
gap= qh_strtod(s, &s);
else
gap= 0.5;
isgap= 1;
break;
case 'L':
if (isdigit(*s))
radius= qh_strtod(s, &s);
else
radius= 10;
islens= 1;
break;
case 'M':
ismesh= 1;
if (*s)
meshn= qh_strtod(s, &s);
if (*s == ',') {
++s;
meshm= qh_strtod(s, &s);
}else
meshm= 0.0;
if (*s == ',') {
++s;
meshr= qh_strtod(s, &s);
}else
meshr= sqrt(meshn*meshn + meshm*meshm);
if (*s && !isspace(*s)) {
qh_fprintf_rbox(qh, qh->ferr, 7069, "rbox warning: assuming 'M3,4,5' since mesh args are not integers or reals\n");
meshn= 3.0, meshm=4.0, meshr=5.0;
}
break;
case 'O':
qh->rbox_out_offset= qh_strtod(s, &s);
break;
case 'P':
if (!first_point)
first_point= s-1;
addpoints++;
while (*s && !isspace(*s)) /* read points later */
s++;
break;
case 'W':
width= qh_strtod(s, &s);
iswidth= 1;
break;
case 'Z':
if (isdigit(*s))
radius= qh_strtod(s, &s);
else
radius= 1.0;
isaxis= 1;
break;
default:
qh_fprintf_rbox(qh, qh->ferr, 7070, "rbox error: unknown flag at %s.\nExecute 'rbox' without arguments for documentation.\n", s);
qh_errexit_rbox(qh, qh_ERRinput);
}
if (*s && !isspace(*s)) {
qh_fprintf_rbox(qh, qh->ferr, 7071, "rbox error: missing space between flags at %s.\n", s);
qh_errexit_rbox(qh, qh_ERRinput);
}
}
/* ============= defaults, constants, and sizes =============== */
if (qh->rbox_isinteger && !isbox)
box= qh_DEFAULTzbox;
if (addcube) {
cubesize= (int)floor(ldexp(1.0,dim)+0.5);
if (cube == 0.0)
cube= box;
}else
cubesize= 0;
if (adddiamond) {
diamondsize= 2*dim;
if (diamond == 0.0)
diamond= box;
}else
diamondsize= 0;
if (islens) {
if (isaxis) {
qh_fprintf_rbox(qh, qh->ferr, 6190, "rbox error: can not combine 'Ln' with 'Zn'\n");
qh_errexit_rbox(qh, qh_ERRinput);
}
if (radius <= 1.0) {
qh_fprintf_rbox(qh, qh->ferr, 6191, "rbox error: lens radius %.2g should be greater than 1.0\n",
+ qh_fprintf_rbox(qh, qh->ferr, 6270, "rbox error: 'Cn,r,m' requested n coincident points for each of m points. Either there is no points or m (%d) is greater than the number of points (%d).\n", coincidenttotal, numpoints);
+ qh_errexit_rbox(qh, qh_ERRinput);
+ }
+ if (coincidenttotal == 0)
+ coincidenttotal= numpoints;
/* ============= print header with total points =============== */
if (issimplex || ismesh)
totpoints= numpoints;
else if (issimplex2)
totpoints= numpoints+dim+1;
else if (isregular) {
totpoints= numpoints;
if (dim == 2) {
if (islens)
totpoints += numpoints - 2;
}else if (dim == 3) {
if (islens)
totpoints += 2 * numpoints;
else if (isgap)
totpoints += 1 + numpoints;
else
totpoints += 2;
}
}else
totpoints= numpoints + isaxis;
totpoints += cubesize + diamondsize + addpoints;
+ totpoints += coincidentpoints*coincidenttotal;
/* ============= seed randoms =============== */
if (istime == 0) {
for (s=command; *s; s++) {
if (issimplex2 && *s == 'y') /* make 'y' same seed as 'x' */
i= 'x';
else
i= *s;
seed= 11*seed + i;
}
}else if (israndom) {
seed= (int)time(&timedata);
sprintf(seedbuf, " t%d", seed); /* appends an extra t, not worth removing */
rbox program for generating input points for qhull.
notes:
50 points generated for 'rbox D4'
*/
#include "libqhull/random.h"
#include "libqhull/libqhull.h"
#include <stdarg.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#ifdef _MSC_VER /* Microsoft Visual C++ -- warning level 4 */
#pragma warning( disable : 4706) /* assignment within conditional function */
#endif
char prompt[]= "\n\
-rbox- generate various point distributions. Default is random in cube.\n\
\n\
-args (any order, space separated): Version: 2015/11/09\n\
+args (any order, space separated): Version: 2016/01/03\n\
3000 number of random points in cube, lens, spiral, sphere or grid\n\
D3 dimension 3-d\n\
c add a unit cube to the output ('c G2.0' sets size)\n\
d add a unit diamond to the output ('d G2.0' sets size)\n\
l generate a regular 3-d spiral\n\
r generate a regular polygon, ('r s Z1 G0.1' makes a cone)\n\
s generate cospherical points\n\
x generate random points in simplex, may use 'r' or 'Wn'\n\
y same as 'x', plus simplex\n\
Cn,r,m add n nearly coincident points within radius r of m points\n\
Pn,m,r add point [n,m,r] first, pads with 0, maybe repeated\n\
\n\
Ln lens distribution of radius n. Also 's', 'r', 'G', 'W'.\n\
Mn,m,r lattice(Mesh) rotated by [n,-m,0], [m,n,0], [0,0,r], ...\n\
'27 M1,0,1' is {0,1,2} x {0,1,2} x {0,1,2}. Try 'M3,4 z'.\n\
W0.1 random distribution within 0.1 of the cube's or sphere's surface\n\
Z0.5 s random points in a 0.5 disk projected to a sphere\n\
Z0.5 s G0.6 same as Z0.5 within a 0.6 gap\n\
\n\
Bn bounding box coordinates, default %2.2g\n\
h output as homogeneous coordinates for cdd\n\
n remove command line from the first line of output\n\
On offset coordinates by n\n\
t use time as the random number seed(default is command line)\n\
tn use n as the random number seed\n\
z print integer coordinates, default 'Bn' is %2.2g\n\
";
/*--------------------------------------------
-rbox- main procedure of rbox application
*/
int main(int argc, char **argv) {
char *command;
int command_size;
int return_status;
QHULL_LIB_CHECK_RBOX
if (argc == 1) {
printf(prompt, qh_DEFAULTbox, qh_DEFAULTzbox);
return 1;
}
if (argc == 2 && strcmp(argv[1], "D4")==0)
qh_fprintf_stderr(0, "\nStarting the rbox smoketest for qhull. An immediate failure indicates\nthat non-reentrant rbox was linked to reentrant routines. An immediate\nfailure of qhull may indicate that qhull was linked to the wrong\nqhull library. Also try 'rbox D4 | qhull T1'\n");
rbox program for generating input points for qhull.
notes:
50 points generated for 'rbox D4'
*/
#include "libqhull_r/libqhull_r.h"
#include <stdarg.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#ifdef _MSC_VER /* Microsoft Visual C++ -- warning level 4 */
#pragma warning( disable : 4706) /* assignment within conditional function */
#endif
char prompt[]= "\n\
-rbox- generate various point distributions. Default is random in cube.\n\
\n\
-args (any order, space separated): Version: 2015/11/09 r\n\
+args (any order, space separated): Version: 2016/01/03 r\n\
3000 number of random points in cube, lens, spiral, sphere or grid\n\
D3 dimension 3-d\n\
c add a unit cube to the output ('c G2.0' sets size)\n\
d add a unit diamond to the output ('d G2.0' sets size)\n\
l generate a regular 3-d spiral\n\
r generate a regular polygon, ('r s Z1 G0.1' makes a cone)\n\
s generate cospherical points\n\
x generate random points in simplex, may use 'r' or 'Wn'\n\
y same as 'x', plus simplex\n\
Cn,r,m add n nearly coincident points within radius r of m points\n\
Pn,m,r add point [n,m,r] first, pads with 0, maybe repeated\n\
\n\
Ln lens distribution of radius n. Also 's', 'r', 'G', 'W'.\n\
Mn,m,r lattice(Mesh) rotated by [n,-m,0], [m,n,0], [0,0,r], ...\n\
'27 M1,0,1' is {0,1,2} x {0,1,2} x {0,1,2}. Try 'M3,4 z'.\n\
W0.1 random distribution within 0.1 of the cube's or sphere's surface\n\
Z0.5 s random points in a 0.5 disk projected to a sphere\n\
Z0.5 s G0.6 same as Z0.5 within a 0.6 gap\n\
\n\
Bn bounding box coordinates, default %2.2g\n\
h output as homogeneous coordinates for cdd\n\
n remove command line from the first line of output\n\
On offset coordinates by n\n\
t use time as the random number seed(default is command line)\n\
tn use n as the random number seed\n\
z print integer coordinates, default 'Bn' is %2.2g\n\
";
/*--------------------------------------------
-rbox- main procedure of rbox application
*/
int main(int argc, char **argv) {
int return_status;
qhT qh_qh;
qhT *qh= &qh_qh;
QHULL_LIB_CHECK_RBOX
if (argc == 1) {
printf(prompt, qh_DEFAULTbox, qh_DEFAULTzbox);
return 1;
}
if (argc == 2 && strcmp(argv[1], "D4")==0)
qh_fprintf_stderr(0, "\nStarting the rbox smoketest for qhull. An immediate failure indicates\nthat reentrant rbox was linked to non-reentrant routines. An immediate\nfailure of qhull may indicate that qhull was linked to the wrong\nqhull library. Also try 'rbox D4 | qhull T1'\n");