diff --git a/Announce.txt b/Announce.txt
index 51c9d0c..580b6ac 100644
--- a/Announce.txt
+++ b/Announce.txt
@@ -1,51 +1,50 @@
Qhull 2015.0.2 2015/08/30
http://www.qhull.org
- git@gitorious.org:qhull/qhull.git
+ git@github.com:qhull/qhull.git
http://packages.debian.org/sid/libqhull5 [out-of-date]
http://www6.uniovi.es/ftp/pub/mirrors/geom.umn.edu/software/ghindex.html
http://www.geomview.org
http://www.geom.uiuc.edu
Qhull computes convex hulls, Delaunay triangulations, Voronoi diagrams,
furthest-site Voronoi diagrams, and halfspace intersections about a point.
It runs in 2-d, 3-d, 4-d, or higher. It implements the Quickhull algorithm
for computing convex hulls. Qhull handles round-off errors from floating
point arithmetic. It can approximate a convex hull.
The program includes options for hull volume, facet area, partial hulls,
input transformations, randomization, tracing, multiple output formats, and
execution statistics. The program can be called from within your application.
You can view the results in 2-d, 3-d and 4-d with Geomview.
To download Qhull:
http://www.qhull.org/download
- git@gitorious.org:qhull/qhull.git
- http://packages.debian.org/sid/libqhull5 [out-of-date]
-
+ git@github.com:qhull/qhull.git
+
Download qhull-96.ps for:
Barber, C. B., D.P. Dobkin, and H.T. Huhdanpaa, "The
Quickhull Algorithm for Convex Hulls," ACM Trans. on
Mathematical Software, 22(4):469-483, Dec. 1996.
http://www.acm.org/pubs/citations/journals/toms/1996-22-4/p469-barber/
http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.117.405
Abstract:
The convex hull of a set of points is the smallest convex set that contains
the points. This article presents a practical convex hull algorithm that
combines the two-dimensional Quickhull Algorithm with the general dimension
Beneath-Beyond Algorithm. It is similar to the randomized, incremental
algorithms for convex hull and Delaunay triangulation. We provide empirical
evidence that the algorithm runs faster when the input contains non-extreme
points, and that it uses less memory.
Computational geometry algorithms have traditionally assumed that input sets
are well behaved. When an algorithm is implemented with floating point
arithmetic, this assumption can lead to serious errors. We briefly describe
a solution to this problem when computing the convex hull in two, three, or
four dimensions. The output is a set of "thick" facets that contain all
possible exact convex hulls of the input. A variation is effective in five
or more dimensions.
diff --git a/README.txt b/README.txt
index eb4f853..487dd18 100644
--- a/README.txt
+++ b/README.txt
@@ -1,548 +1,548 @@
Name
qhull, rbox 2015.0.2 2015/08/30
Convex hull, Delaunay triangulation, Voronoi diagrams, Halfspace intersection
Documentation:
html/index.htm
http://www.qhull.org/html
Available from:
Up: Home page for Qhull
This section discusses the code for Qhull. Copyright © 1995-2015 C.B. Barber Qhull-2015 introduces reentrant Qhull (libqhull_r). Reentrant Qhull replaces Qhull's global data structures with a qhT pointer.
The pointer is the first argument to most Qhull routines. It allows multiple instances of Qhull to run at the same time.
It simplifies the C++ interface to Qhull.
New code should be written with libqhull_r. Existing users of libqhull should consider converting to libqhull_r.
Although libqhull will be supported indefinitely, improvements may not be implemented.
Reentrant qhull is 1-2% slower than non-reentrant qhull.
C++ users need to convert to libqhull_r. The previous C++ interface was unusual
due to Qhull's global data structures (e.g., UsingLibQhull.cpp).
The new C++ interface does a better, but not perfect, job of hiding Qhull's C data structures.
Note: Reentrant Qhull is not thread safe. Do not invoke Qhull routines with the same qhT pointer from multiple threads.
Qhull compiles for 64-bit hosts. Since the size of a pointer on a 64-bit host is double the size on a 32-bit host,
memory consumption increases about 50% for simplicial facets and up-to 100% for non-simplicial facets. You can check
memory consumption with option Ts.
A custom version of Qhull for 3-D Delaunay triangulations may reduce space requirements substantially.
On 64-bit hosts, reentrant qhull is nearly as fast as non-reentrant qhull.
Qhull 2015 uses reentrant Qhull for its C++ interface. If you used
the C++ interface from qhull 2012.1, you will need to adjust how you initialize and use
the Qhull classes. See Changes.txt for details.
Qhull's C++ interface allows you to explore the results of running Qhull.
It provides access to Qhull's data structures.
Most of the classes derive from the corresponding qhull data structure.
For example, QhullFacet is an instance of Qhull's facetT.
Each object contains a reference the Qhull's data structure (via QhullQh), making the C++ representation less memory efficient.
You should retain most of the data in Qhull and use the C++ interface to explore its results.
The C++ interface to Qhull is incomplete. You may need to extend the interface.
If so, you will need to understand Qhull's data structures and read the code.
Example (c.f.,
The C++ iterface for RboxPoints redefines the fprintf() calls
in rboxlib.c. Instead of writing its output to stdout, RboxPoints appends
the output to a std::vector.
The same technique may be used for calling Qhull from C++.
A more flexible approach extends Qhull's classes. For example,
to access the vertices of a QhullFacet,
define a constructor of QhullVertexSet
that takes a QhullFacet as a parameter.
Since the C++ interface uses reentrant Qhull, multiple threads may run Qhull at the same time. Each thread is
one run of Qhull. Do not have two threads accessing the same Qhull instance.
A CoordinateIterator or ConstCoordinateIterator [RboxPoints.cpp] is a Qhull does not use CoordinateIterator for its data structures. A point in Qhull is an array of reals instead of a std::vector.
See QhullPoint.
Qhull is the top-level class for running Qhull.
It initializes Qhull, runs the computation, and records errors.
It provides access to the global data structure QhullQh,
Qhull's facets, and vertices.
QhullError is derived from
If error handling is not set up, Qhull exits with a code from 1 to 5
[qh_ERR* in libqhull.h via qh_exit() in usermem.c]. The C++ interface does not report the
captured output in QhullError. Call Qhull::setErrorStream to send output to cerr instead.
A QhullFacet is a facet of the convex hull, a region of the Delaunay triangulation, a vertex of a Voronoi diagram,
or an intersection of the halfspace intersection about a point.
A QhullFacet has a set of QhullVertex, a set of QhullRidge, and
a set of neighboring QhullFacets.
A QhullFacetList is a linked list of QhullFacet. The result of
A QhullFacetSet is a QhullSet of QhullFacet. QhullFacetSet may be ordered or unordered. The neighboring facets of a QhullFacet is a QhullFacetSet.
The neighbors of a QhullFacet is a QhullFacetSet.
The neighbors are ordered for simplicial facets, matching the opposite vertex of the facet.
QhullIterator contains macros for defining Java-style iterator templates from a STL-style iterator template.
A QhullLinkedLIst is a template for linked lists with next and previous pointers.
QhullFacetList and QhullVertexList are QhullLinkedLists.
A QhullPoint is an array of point coordinates, typically doubles. The length of the array is QhullQh.hull_dim.
The identifier of a QhullPoint is its 0-based index from QhullQh.first_point followed by QhullQh.other_points.
A QhullPointSet is a QhullSet of QhullPoint. The QhullPointSet of a QhullFacet is its coplanar points.
QhullQh is the root of Qhull's data structure.
It contains initialized constants, sets, buffers, and variables.
It contains an array and a set of QhullPoint,
a list of QhullFacet, and a list of QhullVertex.
The points are the input to Qhull. The facets and vertices are the result of running Qhull.
Qhull's functions access QhullQh through the global variable,
A QhullRidge represents the edge between two QhullFacet's.
It is always simplicial with qh.hull_dim-1 QhullVertex)'s.
A QhullRidgeSet is a QhullSet of QhullRidge. Each QhullFacet contains a QhullRidgeSet.
A QhullSet is a set of pointers to objects. QhullSets may be ordered or unordered. They are the core data structure for Qhull.
A QhullVertex is a vertex of the convex hull. A simplicial QhullFacet has qh.hull_dim-1 vertices. A QhullVertex contains a QhullPoint.
It may list its neighboring QhullFacet's.
A QhullVertexList is a QhullLinkedList of QhullVertex.
The global data structure, QhullQh contains a QhullVertexList of all
the vertices.
A QhullVertexSet is a QhullSet of QhullVertex.
The QhullVertexSet of a QhullFacet is the vertices of the facet. It is
ordered for simplicial facets and unordered for non-simplicial facets.
RboxPoints is a std::vector of point coordinates (QhullPoint).
It's iterator is CoordinateIterator.
Warning: Qhull was not designed for calling from C
programs. You may find the C++ interface easier to use.
You will need to understand the data structures and read the code.
Most users will find it easier to call Qhull as an external
command.
For examples of calling Qhull, see GNU Octave's
computational geometry code,
and Qhull's
user_eg_r.c,
user_eg2_r.c, and
user_r.c. To see how Qhull calls its library, read
unix_r.c,
qconvex.c,
qdelaun.c,
qhalf.c, and
qvoronoi.c. The '*_r.c' files are reentrant, otherwise they are non-reentrant.
Either version may be used. New code should use reentrant Qhull.
The BGL
Boost Graph Library [aka GGCL] provides C++ classes for graph data structures
and algorithms [Dr. Dobb's 9/00 p. 29-38; OOPSLA '99 p. 399-414]. It is modelled after the
Standard Template Library. It would provide a good interface to Qhull.
If you are interested in adapting BGL to Qhull, please contact
bradb@shore.net.
See Qhull functions, macros, and data
structures for internal documentation of Qhull. The
documentation provides an overview and index. To use the library
you will need to read and understand the code. For most users, it
is better to write data to a file, call the qhull program, and
read the results from the output file. If you use non-reentrant Qhull, be aware of the macros "qh"
and "qhstat", e.g., "qh hull_dim". They are
defined in libqhull.h. They allow the global data
structures to be pre-allocated (faster access) or dynamically
allocated (allows multiple copies). Qhull's Makefile produces a library, libqhull_r.a,
for inclusion in your programs. First review libqhull_r.h.
This defines the data structures used by Qhull and provides
prototypes for the top-level functions.
Most users will only need libqhull_r.h in their programs. For
example, the Qhull program is defined with libqhull_r.h and unix_r.c.
To access all functions, use qhull_ra.h. Include the file
with "#include <libqhull_r/qhull_ra.h>". This
avoids potential name conflicts. If you use the Qhull library, you are on your own as far as
bugs go. Start with small examples for which you know the output.
If you get a bug, try to duplicate it with the Qhull program. The
'Tc' option will catch many problems
as they occur. When an error occurs, use 'T4 TPn'
to trace from the last point added to the hull. Compare your
trace with the trace output from the Qhull program. Errors in the Qhull library are more likely than errors in the
Qhull program. These are usually due to feature interactions that
do not occur in the Qhull program. Please report all errors that
you find in the Qhull library. Please include suggestions for
improvement. You can use mem_r.c and qset_r.c individually. Mem_r.c
implements quick-fit memory allocation. It is faster than
malloc/free in applications that allocate and deallocate lots of
memory. Qset_r.c implements sets and related collections. It's
the inner loop of Qhull, so speed is more important than
abstraction. Set iteration is particularly fast. qset_r.c
just includes the functions needed for Qhull. Here some unchecked code to print the point indices of each
Delaunay triangle. Use option 'QJ' if you want to avoid
non-simplicial facets. Note that upper Delaunay regions are
skipped. These facets correspond to the furthest-site Delaunay
triangulation. The routine qh_findbestfacet in poly2_r.c is
particularly useful. It uses a directed search to locate the
facet that is furthest below a point. For Delaunay
triangulations, this facet is the Delaunay triangle that contains
the lifted point. For convex hulls, the distance of a point to
the convex hull is either the distance to this facet or the
distance to a subface of the facet. Warning: If triangulated output ('Qt') and
the best facet is triangulated, qh_findbestfacet() returns one of
the corresponding 'tricoplanar' facets. The actual best facet may be a different
tricoplanar facet.
See qh_nearvertex() in poly2.c for sample code to visit each
tricoplanar facet. To identify the correct tricoplanar facet,
see Devillers, et. al., ['01]
and Mucke, et al ['96]. If you
implement this test in general dimension, please notify
qhull@qhull.org.
qh_findbestfacet performs an exhaustive search if its directed
search returns a facet that is above the point. This occurs when
the point is inside the hull or if the curvature of the convex
hull is less than the curvature of a sphere centered at the point
(e.g., a point near a lens-shaped convex hull). When the later
occurs, the distance function is bimodal and a directed search
may return a facet on the far side of the convex hull. Algorithms that retain the previously constructed hulls
usually avoid an exhaustive search for the best facet. You may
use a hierarchical decomposition of the convex hull [Dobkin and
Kirkpatrick '90]. To use qh_findbestfacet with Delaunay triangulations, lift the
point to a paraboloid by summing the squares of its coordinates
(see qh_setdelaunay in geom2_r.c). Do not scale the input with
options 'Qbk', 'QBk', 'QbB' or 'Qbb'. See Mucke, et al ['96] for a good point location
algorithm. The intersection of a ray with the convex hull may be found by
locating the facet closest to a distant point on the ray.
Intersecting the ray with the facet's hyperplane gives a new
point to test. The Qhull library may be used for the on-line construction of
convex hulls, Delaunay triangulations, and halfspace
intersections about a point. It may be slower than implementations that retain
intermediate convex hulls (e.g., Clarkson's hull
program). These implementations always use a directed search.
For the on-line construction of convex hulls and halfspace
intersections, Qhull may use an exhaustive search
(qh_findbestfacet). You may use qh_findbestfacet and qh_addpoint (libqhull.c) to add a point to
a convex hull. Do not modify the point's coordinates since
qh_addpoint does not make a copy of the coordinates. For Delaunay
triangulations, you need to lift the point to a paraboloid by
summing the squares of the coordinates (see qh_setdelaunay in
geom2.c). Do not scale the input with options 'Qbk', 'QBk', 'QbB'
or 'Qbb'. Do not deallocate the point's coordinates. You need to
provide a facet that is below the point (qh_findbestfacet).
You can not delete points. Another limitation is that Qhull
uses the initial set of points to determine the maximum roundoff
error (via the upper and lower bounds for each coordinate). For many applications, it is better to rebuild the hull from
scratch for each new point. This is especially true if the point
set is small or if many points are added at a time. Calling qh_addpoint from your program may be slower than
recomputing the convex hull with qh_qhull. This is especially
true if the added points are not appended to the qh first_point
array. In this case, Qhull must search a set to determine a
point's ID. [R. Weber] See user_eg.c for examples of the on-line construction of
convex hulls, Delaunay triangulations, and halfspace
intersections. The outline is: With a fair amount of work, Qhull is suitable for constrained
Delaunay triangulation. See Shewchuk, ACM Symposium on
Computational Geometry, Minneapolis 1998. Here's a quick way to add a constraint to a Delaunay
triangulation: subdivide the constraint into pieces shorter than
the minimum feature separation. You will need an independent
check of the constraint in the output since the minimum feature
separation may be incorrect. [H. Geron] Option 'Qt' triangulates non-simplicial
facets (e.g., a square facet in 3-d or a cubical facet in 4-d).
All facets share the same apex (i.e., the first vertex in facet->vertices).
For each triangulated facet, Qhull
sets facet->tricoplanar true and copies facet->center, facet->normal, facet->offset, and facet->maxoutside. One of
the facets owns facet->normal; its facet->keepcentrum is true.
If facet->isarea is false, facet->triowner points to the owning
facet.
Qhull sets facet->degenerate if the facet's vertices belong
to the same ridge of the non-simplicial facet.
To visit each tricoplanar facet of a non-simplicial facet,
either visit all neighbors of the apex or recursively visit
all neighbors of a tricoplanar facet. The tricoplanar facets
will have the same facet->center. See qh_detvridge for an example of ignoring tricoplanar facets. The following code iterates over all Voronoi vertices for each
Voronoi region. Qhull computes Voronoi vertices from the convex
hull that corresponds to a Delaunay triangulation. An input site
corresponds to a vertex of the convex hull and a Voronoi vertex
corresponds to an adjacent facet. A facet is
"upperdelaunay" if it corresponds to a Voronoi vertex
"at-infinity". Qhull uses qh_printvoronoi in io.c
for 'qvoronoi o' Qhull uses qh_printvdiagram() in io.c to print the ridges of a
Voronoi diagram for option 'Fv'.
The helper function qh_eachvoronoi() does the real work. It calls
the callback 'printvridge' for each ridge of the Voronoi diagram.
You may call qh_printvdiagram2(), qh_eachvoronoi(), or
qh_eachvoronoi_all() with your own function. If you do not need
the total number of ridges, you can skip the first call to
qh_printvdiagram2(). See qh_printvridge() and qh_printvnorm() in
io.c for examples. To visit all of the vertices that share an edge with a vertex:
For non-simplicial facets, the ridges form a simplicial
decomposition of the (d-2)-faces between each pair of facets --
if you need 1-faces, you probably need to generate the full face
graph of the convex hull. Empirically, Qhull's performance is balanced in the sense that
the average case happens on average. This may always be true if
the precision of the input is limited to at most O(log n)
bits. Empirically, the maximum number of vertices occurs at the
end of constructing the hull. Let n be the number of input points, v be the
number of output vertices, and f_v be the maximum number
of facets for a convex hull of v vertices. If both
conditions hold, Qhull runs in O(n log v) in 2-d and 3-d
and O(n f_v/v) otherwise. The function f_v
increases rapidly with dimension. It is O(v^floor(d/2) /
floor(d/2)!). The time complexity for merging is unknown. Options 'C-0' and 'Qx'
(defaults) handle precision problems due to floating-point
arithmetic. They are optimized for simplicial outputs. When running large data sets, you should monitor Qhull's
performance with the 'TFn' option.
The time per facet is approximately constant. In high-d with many
merged facets, the size of the ridge sets grows rapidly. For
example the product of 8-d simplices contains 18 facets and
500,000 ridges. This will increase the time needed per facet. As dimension increases, the number of facets and ridges in a
convex hull grows rapidly for the same number of vertices. For
example, the convex hull of 300 cospherical points in 6-d has
30,000 facets. If Qhull appears to stop processing facets, check the memory
usage of Qhull. If more than 5-10% of Qhull is in virtual memory,
its performance will degrade rapidly. When building hulls in 20-d and higher, you can follow the
progress of Qhull with option 'T1'.
It reports each major event in processing a point. To reduce memory requirements, recompile Qhull for
single-precision reals (REALfloat in user.h).
Single-precision does not work with joggle ('QJ'). Check qh_MEMalign in user.h
and the match between free list sizes and data structure sizes
(see the end of the statistics report from 'Ts'). If free list sizes do not match,
you may be able to use a smaller qh_MEMalign. Setting
qh_COMPUTEfurthest saves a small amount of memory, as does
clearing qh_MAXoutside (both in user.h). Shewchuk is working on a 3-d version of his triangle
program. It is optimized for 3-d simplicial Delaunay triangulation
and uses less memory than Qhull. To reduce the size of the Qhull executable, consider
qh_NOtrace and qh_KEEPstatistics 0 in user.h. By
changing user.c you can also remove the input/output
code in io.c. If you don't need facet merging, then
version 1.01 of Qhull is much smaller. It contains some bugs that
prevent Qhull from initializing in simple test cases. It is
slower in high dimensions. The precision options, 'Vn', 'Wn', 'Un'.
'A-n', 'C-n',
'An', 'Cn',
and 'Qx', may have large effects on
Qhull performance. You will need to experiment to find the best
combination for your application. The verify option ('Tv') checks
every point after the hull is complete. If facet merging is used,
it checks that every point is inside every facet. This can take a
very long time if there are many points and many facets. You can
interrupt the verify without losing your output. If facet merging
is not used and there are many points and facets, Qhull uses a
directed search instead of an exhaustive search. This should be
fast enough for most point sets. Directed search is not used for
facet merging because directed search was already used for
updating the facets' outer planes. The check-frequently option ('Tc')
becomes expensive as the dimension increases. The verify option
('Tv') performs many of the same
checks before outputting the results. Options 'Q0' (no pre-merging), 'Q3' (no checks for redundant vertices),
'Q5' (no updates for outer planes),
and 'Q8' (no near-interior points)
increase Qhull's speed. The corresponding operations may not be
needed in your application. In 2-d and 3-d, a partial hull may be faster to produce.
Option 'QgGn' only builds facets
visible to point n. Option 'QgVn'
only builds facets that contain point n. In higher-dimensions,
this does not reduce the number of facets. User.h includes a number of performance-related
constants. Changes may improve Qhull performance on your data
sets. To understand their effect on performance, you will need to
read the corresponding code. GNU gprof reports that the dominate cost for 3-d
convex hull of cosperical points is qh_distplane(), mainly called
from qh_findbestnew(). The dominate cost for 3-d Delaunay triangulation
is creating new facets in qh_addpoint(), while qh_distplane() remains
the most expensive function.
There are many ways in which Qhull can be improved. Please let us know about your applications and improvements. Up: Home
page for Qhull Comments to: qhull@qhull.org
Up: Qhull Home Page Qhull
computes the convex hull, Delaunay triangulation, Voronoi diagram, halfspace
intersection about a point, furthest-site Delaunay
triangulation, and furthest-site Voronoi diagram. It
runs in 2-d, 3-d, 4-d, and higher dimensions. It
implements the Quickhull algorithm for computing the
convex hull. Qhull handles roundoff errors from floating
point arithmetic. It can approximate a convex hull. Visit Qhull News
for news, bug reports, change history, and users.
If you use Qhull 2003.1 or 2009.1, please upgrade to 2015.0.2 or apply
poly.c-qh_gethash.patch. Type: console programs for Windows (32- or 64-bit) Includes 32-bit executables, documentation, and sources files. It runs in a
command window. Qhull may be compiled for 64-bits. Type: C/C++ source code for 32-bit and 64-bit architectures Includes documentation, source files, two Makefile's, CMakeLists.txt, DevStudio projects, and Qt projects.
Includes preliminary C++ support and a preliminary Debian/autoconf build. Debian, rpm, and Autoconf distributions are needed. Type: git repository for Qhull. See Changes.txt Includes documentation, source files, C++ interface, and test programs. It builds with gcc, mingw,
CMake, DevStudio, and Qt Creator.
Type: PDF on ACM Digital Library (from this page only) Barber, C.B., Dobkin, D.P., and Huhdanpaa, H.T.,
"The Quickhull algorithm for convex hulls," ACM
Transactions on Mathematical Software, 22(4):469-483, Dec 1996 [abstract]. Type: C source code for
32-bit architectures Version 1.0 is a fifth the size of version 2.4. It
computes convex hulls and Delaunay triangulations. If a
precision error occurs, it stops with an error message.
It reports an initialization error for inputs made with
0/1 coordinates. Version 1.0 compiles on a PC with Borland C++ 4.02 for
Win32 and DOS Power Pack. The options for rbox are
"bcc32 -WX -w- -O2-e -erbox -lc rbox.c". The
options for qhull are the same. [D. Zwick] Up: Qhull Home Page Comments to: qhull@qhull.org Qhull does not 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, 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 poly.c-qh_gethash.patch.
Up: Qhull manual: Table of
Contents
To: Programs
Options
Output
Formats
Geomview
Print
Qhull
Precision
Trace
To: Qhull code: Table of Contents
(please wait while loading)
Dn: Qhull functions, macros, and data
structures
Qhull code
»Qhull code: Table of
Contents
»Reentrant Qhull
»Qhull on 64-bit hosts
»Calling Qhull from
C++ programs
user_eg3 eg-100
). It prints the facets generated by Qhull.
RboxPoints rbox;
rbox.appendRandomPoints("100");
Qhull qhull;
qhull.runQhull("", rbox);
QhullFacetList facets(qhull);
cout<< facets;
»CoordinateIterator
std::vector<realT>::iterator
for Rbox and Qhull coordinates.
It is the result type of RboxPoints.coordinates().
»Qhull
»QhullError
std::exception
. It reports errors from Qhull and captures the output to stderr.
»QhullFacet
»QhullFacetList
Qhull.runQhull
is a QhullFacetList stored
in QhullQh.
»QhullFacetSet
»QhullIterator
»QhullLinkedList
»QhullPoint
»QhullPointSet
»QhullQh
qh_qh
.
The global data structures, qh_stat and qh_mem, record statistics and manage memory respectively.
»QhullRidge
»QhullRidgeSet
»QhullSet
»QhullVertex
»QhullVertexList
»QhullVertexSet
»RboxPoints
RboxPoints.appendRandomPoints()
appends points from a variety of distributions such as uniformly distributed within a cube and random points on a sphere.
It can also append a cube's vertices or specific points.
»Cpp questions for Qhull
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
C++ and Perl Guidelines.
and FIXUP notes in the code.
-Please add notes to Gitorious wiki.
+Please add notes to Qhull Wiki.
iterator Coordinates::operator++() { return iterator(++i); }
reference operator[](difference_type _Off) const
iterator &operator++() { return iterator(i++); }
»Calling Qhull from
C programs
»sets and quick memory
allocation
»Delaunay triangulations
and point indices
facetT *facet;
vertexT *vertex, **vertexp;
FORALLfacets {
if (!facet->upperdelaunay) {
printf ("%d", qh_setsize (facet->vertices);
FOREACHvertex_(facet->vertices)
printf (" %d", qh_pointid (vertex->point));
printf ("\n");
}
}
»locate a facet with
qh_findbestfacet()
»on-line construction with
qh_addpoint()
initialize qhull with an initial set of points
qh_qhull();
for each additional point p
append p to the end of the point array or allocate p separately
lift p to the paraboloid by calling qh_setdelaunay
facet= qh_findbestfacet (p, !qh_ALL, &bestdist, &isoutside);
if (isoutside)
if (!qh_addpoint (point, facet, False))
break; /* user requested an early exit with 'TVn' or 'TCn' */
call qh_check_maxout() to compute outer planes
terminate qhull
»Constrained
Delaunay triangulation
»Tricoplanar facets and option 'Qt'
»Voronoi vertices of a
region
/* please review this code for correctness */
qh_setvoronoi_all();
FORALLvertices {
site_id = qh_pointid (vertex->point);
if (qh hull_dim == 3)
qh_order_vertexneighbors(vertex);
infinity_seen = 0;
FOREACHneighbor_(vertex) {
if (neighbor->upperdelaunay) {
if (!infinity_seen) {
infinity_seen = 1;
... process a Voronoi vertex "at infinity" ...
}
}else {
voronoi_vertex = neighbor->center;
... your code goes here ...
}
}
}
»Voronoi vertices of a
ridge
»vertex neighbors of
a vertex
»Performance of
Qhull
»Enhancements to Qhull
[Jan 2010] Suggestions
- Generate vcproj from qtpro files
cd qtpro && qmake -spec win32-msvc2005 -tp vc -recursive
sed -i 's/C\:\/bash\/local\/qhull\/qtpro\///' qhull-all.sln
Change qhullcpp to libqhull.dll
Allow both builds on same host (keep /tmp separate)
- Make distribution -- remove tmp, news, .git, leftovers from project, change CRLF
search for 2010.1, Dates
qhulltest --all added to output
Add md5sum
Add test of user_eg3, etc.
- C++ class for access to statistics, accumulate vs. add
- Add dialog box to RoadError-- a virtual function?
- Option 'Gt' does not make visible all facets of the mesh example, rbox 32 M1,0,1 | qhull d Gt
- Option to select bounded Voronoi regions [A. Uzunovic]
- Merge small volume boundary cells into unbounded regions [Dominik Szczerba]
- Postmerge with merge options
- Add const to C code
- Add modify operators and MutablePointCoordinateIterator to PointCoordinates
- Add Qtest::toString() functions for QhullPoint and others. QByteArray and qstrdup()
- Fix option Qt for conformant triangulations of merged facets
- Investigate flipped facet -- rbox 100 s D3 t1263080158 | qhull R1e-3 Tcv Qc
- Add doc comments to c++ code
- Measure performance of Qhull, seconds per point by dimension
- Report potential wraparound of 64-bit ints -- e.g., a large set or points
Documentation
- Qhull::addPoint(). Problems with qh_findbestfacet and otherpoints see
qh-code.htm#inc on-line construction with qh_addpoint()
- How to handle 64-bit possible loss of data. WARN64, ptr_intT, size_t/int
- Show custom of qh_fprintf
- grep 'qh_mem ' x | sort | awk '{ print $2; }' | uniq -c | grep -vE ' (2|4|6|8|10|12|14|16|20|64|162)[^0-9]'
- qtpro/qhulltest contains .pro and Makefile. Remove Makefiles by setting shadow directory to ../../tmp/projectname
- Rules for use of qh_qh and multi processes
UsingQhull
errorIfAnotherUser
~QhullPoints() needs ownership of qh_qh
Does !qh_pointer work?
When is qh_qh required? Minimize the time.
qhmem, qhstat.ferr
qhull_inuse==1 when qhull globals active [not useful?]
rbox_inuse==1 when rbox globals active
- Multithreaded -- call largest dimension for infinityPoint() and origin()
- Better documentation for qhmem totshort, freesize, etc.
- how to change .h, .c, and .cpp to text/html. OK in Opera
- QhullVertex.dimension() is not quite correct, epensive
- Check globalAngleEpsilon
- Deprecate save_qhull()
[Dec 2003] Here is a partial list:
- fix finddelaunay() in user_eg.c for tricoplanar facets
- write a BGL, C++ interface to Qhull
http://www.boost.org/libs/graph/doc/table_of_contents.html
- change qh_save_qhull to swap the qhT structure instead of using pointers
- change error handling and tracing to be independent of 'qh ferr'
- determine the maximum width for a given set of parameters
- prove that directed search locates all coplanar facets
- in high-d merging, can a loop of facets become disconnected?
- find a way to improve inner hulls in 5-d and higher
- determine the best policy for facet visibility ('Vn')
- determine the limitations of 'Qg'
Precision improvements:
- For 'Qt', resolve cross-linked, butterfly ridges.
May allow retriangulation in qh_addpoint().
- for Delaunay triangulations ('d' or 'v') under joggled input ('QJ'),
remove vertical facets whose lowest vertex may be coplanar with convex hull
- review use of 'Qbb' with 'd QJ'. Is MAXabs_coord better than MAXwidth?
- check Sugihara and Iri's better in-sphere test [Canadian
Conf. on Comp. Geo., 1989; Univ. of Tokyo RMI 89-05]
- replace centrum with center of mass and facet area
- handle numeric overflow in qh_normalize and elsewhere
- merge flipped facets into non-flipped neighbors.
currently they merge into best neighbor (appears ok)
- determine min norm for Cramer's rule (qh_sethyperplane_det). It looks high.
- improve facet width for very narrow distributions
New features:
- implement Matlab's tsearch() using Qhull
- compute volume of Voronoi regions. You need to determine the dual face
graph in all dimensions [see Clarkson's hull program]
- compute alpha shapes [see Clarkson's hull program]
- implement deletion of Delaunay vertices
see Devillers, ACM Symposium on Computational Geometry, Minneapolis 1999.
- compute largest empty circle [see O'Rourke, chapter 5.5.3] [Hase]
- list redundant (i.e., coincident) vertices [Spitz]
- implement Mucke, et al, ['96] for point location in Delaunay triangulations
- implement convex hull of moving points
- implement constrained Delaunay diagrams
see Shewchuk, ACM Symposium on Computational Geometry, Minneapolis 1998.
- estimate outer volume of hull
- automatically determine lower dimensional hulls
- allow "color" data for input points
need to insert a coordinate for Delaunay triangulations
Input/output improvements:
- Support the VTK Visualization Toolkit, http://www.kitware.com/vtk.html
- generate output data array for Qhull library [Gautier]
- need improved DOS window with screen fonts, scrollbar, cut/paste
- generate Geomview output for Voronoi ridges and unbounded rays
- generate Geomview output for halfspace intersection
- generate Geomview display of furthest-site Voronoi diagram
- use 'GDn' to view 5-d facets in 4-d
- convert Geomview output for other 3-d viewers
- add interactive output option to avoid recomputing a hull
- orient vertex neighbors for 'Fv' in 3-d and 2-d
- track total number of ridges for summary and logging
Performance improvements:
- optimize Qhull for 2-d Delaunay triangulations
- use O'Rourke's '94 vertex->duplicate_edge
- add bucketing
- better to specialize all of the code (ca. 2-3x faster w/o merging)
- use updated LU decomposition to speed up hyperplane construction
- [Gill et al. 1974, Math. Comp. 28:505-35]
- construct hyperplanes from the corresponding horizon/visible facets
- for merging in high d, do not use vertex->neighbors
Up: Qhull manual: Table of
Contents
To: Programs
Options
Output
Formats
Geomview
Print
Qhull
Precision
Trace
To: Qhull code: Table of Contents
Dn: Qhull functions, macros, and data
structures
Created: Sept. 25, 1995 --- Last modified: see changes.txt
Qhull Downloads
diff --git a/html/qhull.man b/html/qhull.man
index 4ede521..e2de45b 100644
--- a/html/qhull.man
+++ b/html/qhull.man
@@ -1,1005 +1,1005 @@
.\" This is the Unix manual page for qhull, written in nroff, the standard
.\" manual formatter for Unix systems. To format it, type
.\"
.\" nroff -man qhull.man
.\"
.\" This will print a formatted copy to standard output. If you want
.\" to ensure that the output is plain ASCII, free of any control
.\" characters that nroff uses for underlining etc, pipe the output
.\" through "col -b":
.\"
.\" nroff -man qhull.man | col -b
.\"
.\" Warning: a leading quote "'" or dot "." will not format correctly
.\"
.TH qhull 1 "2003/12/30" "Geometry Center"
.SH NAME
qhull \- convex hull, Delaunay triangulation, Voronoi diagram,
halfspace intersection about a point, hull volume, facet area
.SH SYNOPSIS
.nf
qhull- compute convex hulls and related structures
input (stdin): dimension, #points, point coordinates
first comment (non-numeric) is listed in the summary
halfspace: use dim plus one with offsets after coefficients
options (qh-quick.htm):
d - Delaunay triangulation by lifting points to a paraboloid
v - Voronoi diagram via the Delaunay triangulation
H1,1 - Halfspace intersection about [1,1,0,...]
d Qu - Furthest-site Delaunay triangulation (upper convex hull)
v Qu - Furthest-site Voronoi diagram
Qt - triangulated output
QJ - Joggle the input to avoid precision problems
. - concise list of all options
- - one-line description of all options
Output options (subset):
FA - compute total area and volume
Fx - extreme points (convex hull vertices)
G - Geomview output (2-d, 3-d and 4-d)
Fp - halfspace intersection coordinates
m - Mathematica output (2-d and 3-d)
n - normals with offsets
o - OFF file format (if Voronoi, outputs regions)
TO file- output results to file, may be enclosed in single quotes
f - print all fields of all facets
s - summary of results (default)
Tv - verify result: structure, convexity, and point inclusion
p - vertex coordinates (centers for Voronoi)
i - vertices incident to each facet
example:
rbox 1000 s | qhull Tv s FA
.fi
- html manual: index.htm
- installation: README.txt
- see also: COPYING.txt, REGISTER.txt, Changes.txt
- WWW:
To:
News
Download
CiteSeer
Images
Manual
FAQ
Programs
Options
Qhull
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.
Introduction
Qhull Documentation and Support
|
Related URLs
FAQs and Newsgroups
The program includes options for input transformations, randomization, tracing, multiple output formats, and execution statistics. The program can be called from within your application.
You can view the results in 2-d, 3-d and 4-d with Geomview. An alternative is VTK.
For an article about Qhull, download from ACM or CiteSeer:
Barber, C.B., Dobkin, D.P., and Huhdanpaa, H.T., "The Quickhull algorithm for convex hulls," ACM Trans. on Mathematical Software, 22(4):469-483, Dec 1996, http://www.qhull.org
Abstract:
The convex hull of a set of points is the smallest convex set that contains the points. This article presents a practical convex hull algorithm that combines the two-dimensional Quickhull Algorithm with the general dimension Beneath-Beyond Algorithm. It is similar to the randomized, incremental algorithms for convex hull and Delaunay triangulation. We provide empirical evidence that the algorithm runs faster when the input contains non-extreme points, and that it uses less memory.
Computational geometry algorithms have traditionally assumed that input sets are well behaved. When an algorithm is implemented with floating point arithmetic, this assumption can lead to serious errors. We briefly describe a solution to this problem when computing the convex hull in two, three, or four dimensions. The output is a set of "thick" facets that contain all possible exact convex hulls of the input. A variation is effective in five or more dimensions.
Up: Past Software
Projects of the Geometry Center
URL: http://www.qhull.org
To:
News
Download
CiteSeer
Images
Manual
FAQ
Programs
Options
Comments to: qhull@qhull.org
[R. Richter, S. Pasko]
- Remove deprecated libqhull/qhull.h
Use libqhull/libqhull.h instead. Avoids confusion with libqhullcpp/Qhull.h
- Makefile: Add LIBDIR, INCDIR, and DESTDIR to install [L.H. de Mello]
Separate MAN install from DOC install
Create install directories
Installs headers to include/libqhull, include/libqhullcpp, include/road
- CMakeLists.txt: Add MAN_INSTALL_DIR for qhull.1 and rbox.1 man pages
Add RoadTest.h to include/road for Qt users (road_HEADERS)
- Renamed md5sum files to avoid two extensions
- qh-get.htm: Add Readme links and 2009.1 note.
- qh-optf.htm: Fix link
- index.htm: Updated Google Scholar link
- qhull-zip.sh: Improved error message.
------------
Qhull 2011.1 2011/04/17 6.2.0.1373
Changes to deliverables
- qvoronoi: Deprecated 'Qt' and 'QJn'. Removed from documentation and prompts.
These options produced duplicate Voronoi vertices for cospherical data.
- Removed doskey from Qhull-go.bat. It is incompatible with Windows 7
- Added 'facets' argument to user_eg3.cpp
- user_eg links with shared library
- qhulltest.cpp: Add closing prompt.
Changes to build system
- Reorganized source directories
- Moved executables to bin directory
- Add CMake build for all targets (CMakeFiles.txt) [M. Moll assisted]
- Add gcc build for all targets (Makefile)
- Fixed location of qhull.man and rbox.man [M. Moll]
- Add DevStudio builds for all targets (build/*.vcproj)
- Added shared library (lib/qhull6.dll)
Added qh_QHpointer_dllimport to work around problems with MSVC
- Added static libraries with and without qh_QHpointer (lib/qhullstatic.lib)
- Added eg/make-vcproj.sh to create vcproj/sln files from cmake and qmake
- Document location of qh_QHpointer
- Use shadow build directory
- Made -fno-strict-aliasing conditional on gcc version
- Added src/qhull-app-cpp.pri, src/qhull-app-c.pri, etc. for common settings
- Add .gitignore with ignored files and directories.
- Use .git/info/exclude for locally excluded files.
- Fixed MBorland for new directory structure
- cleanall (Makefile): Delete 'linked' programs due to libqhull_r and libqhull/Makefile
Changes to documentation
- qvoronoi.htm: Remove quotes from qvoronoi example
- qhull-cpp.xml: Add naming conventions
- index.htm: Add Google Scholar references
- qh-optf.htm: Add note about order of 'Fn' matching 'Fv' order [Q. Pan]
- Add patch for old builds in qh-get.htm
- Added C++ compiling instructions to README.txt
- Add instructions for fixing the DOS window
- Changed DOS window to command window
- Fixed html links
- qh-get.htm: Dropped the Spanish mirror site. It was disabled.
Changes to C code
- mem.h: Define ptr_intT as 'long long' for Microsoft Windows _win64 builds.
On Linux and Mac, 'long' is 64-bits on a 64-bit host
- Added qh_QHpointer_dllimport to work around MSVC problem
- qconvex.c,etc.: Define prototype for _isatty
- Define MSG_QHULL_ERROR in user.h
- Move MSG_FIXUP to 11000 and updated FIXUP QH11...
Changes to test code
- Add note to q_test than R1e-3 may error (qh-code.htm, Enhancements)
- Add test for executables to q_eg, etc.
- Fixed Qhull-go.bat. QHULL-GO invokes it with command.com,
Changes to C++ interface
- QhullFacet: Added isSimplicial, isTopOrient, isTriCoplanar, isUpperDelaunay
- Added Qhull::defineVertexFacetNeighbors() for facetNeighbors of vertices.
Automatically called for facet merging and Voronoi diagrams
Do not print QhullVertex::facetNeighbors is !facetNeighborsDefined()
- Add Fixup identifiers
- QhullError: Add copy constructor, assignment operator, and destructor
- Add throw() specifiers to RoadError and QhullError
- Renamed RoadError::defined() to RoadError::isDefined()
- Add #error to Qhull.h if qh_QHpointer is not defined
Changes to C++ code
- Fixed bug reported by renangms. Vertex output throws error QH10034
and defineVertexNeighbors() does not exist.
- Define QHULL_USES_QT for qt-qhull.cpp [renangms]
- Reviewed all copy constructors and copy assignments. Updated comments.
Defined Qhull copy constructor and copy assignment [G. Rivet-Sabourin]
Disabled UsingQhullLib default constructor, copy construct, and copy assign
- Merged changes from J. Obermayr in gitorious/jobermayrs-qhull:next
- Fix strncat limit in rboxlib.c and global.c
- Changes to CMakeLists.txt for openSUSE
- Fixed additional uses of strncat
- Fixed QhullFacet::PrintRidges to check hasNextRidge3d()
- Removed gcc warnings for shadowing from code (src/qhull-warn.pri)
- Removed semicolon after extern "C" {...}
- Removed experimental QhullEvent/QhullLog
- Use fabs() instead of abs() to avoid accidental conversions to int
- Fixed type of vertex->neighbors in qh_printvoronoi [no effect on results]
- Removed unnecessary if statement in qh_printvoronoi
------------
qhull 2010.1 2010/01/14
- Fixed quote for #include in qhull.h [U.Hergenhahn, K.Roland]
- Add qt-qhull.cpp with Qt conditional code
- Add libqhullp.proj
- Add libqhull5 to Readme, Announce, download
- Reviewed #pragma
- Reviewed FIXUP and assigned QH tags
- All projects compile with warnings enabled
- Replaced 'up' glyphs with »
- Moved cpp questions to qh-code.htm#questions-cpp
- Moved suggestions to qh-code.htm#enhance
- Moved documentation requests to qh-code.htm#enhance
- Add md5sum file to distributions
- Switched to DevStudio builds to avoid dependent libraries, 10% slower
Removed user_eg3.exe and qhullcpp.dll from Windows build
Fix qhull.sln and project files for qh_QHpointer
- Add eg/qhull-zip.sh to build qhull distribution files
------------
qhull 2010.1 2010/01/10
- Test for NULL fp in qh_eachvoronoi [D. Szczerba]
qhull 2010.1 2010/01/09
Changes to build and distribution
- Use qh_QHpointer=0 for libqhull.a, qhull, rbox, etc.
Use -Dqh_QHpointer for libqhullp.a, qhullcpp.dll, etc.
qh_QHpointer [2010, gcc] 4% time 4% space, [2003, msvc] 8% time 2% space
- Add config/ and project/debian/ for Autoconf build [R. Laboissiere]
from debian branch in git and http://savannah.nongnu.org/cvs/?group=qhull
- Add CMakeLists.txt [kwilliams]
- Fix tabs in Makefile.txt [mschamschula]
- Add -fno-strict-aliasing to Makefile for gcc 4.1, 4.2, and 4.3 qset segfault
- Remove user_eg.exe and user_eg2.exe from Windows distribution
- Order object files by frequency of execution for better locality.
Changes to source
- Remove ptr_intT from qh_matchvertices. It was int since the beginning.
- user.h requires
Created: May 17 1995 ---
diff --git a/src/Changes.txt b/src/Changes.txt
index 3a62b45..8587f5b 100644
--- a/src/Changes.txt
+++ b/src/Changes.txt
@@ -1,1948 +1,1976 @@
$Id: //main/2011/qhull/src/Changes.txt#82 $
.............This file lists all changes to qhull and rbox.....................
------------
Need help
- Qhull needs RPM and Debian builds (CMake's CPackRMP and CPackDeb).
- Qhull needs a mirror/archive site for old and new builds
- Constrained delaunay triangulation via Shewchuk's algorithm (ACM Symp. Comp. Geo., 1998)
- The C++ interface needs work. Give it a try and make it better.
- http://gitorious.org/qhull/
+ http://github.com/qhull/qhull
- Produce conformant triangulations for merged facets using option 'Qt'
- Write an incremental addPoint using bucketed inputs and facet location search
- Compute hyperplanes in parallel (cf. qh_setfactplane)
- Create Voronoi volumes and topology using a parallel implementation
------------
To do for a future verson of Qhull
- Rescale output to match 'QbB' on input [J. Metz, 1/30/2014 12:21p]
- Run through valgrind
- Notes to compgeom on conformant triangulation and Voronoi volume
- Git: Create signed tags for Qhull versions
- Can countT be defined as 'int', 'unsigned int', or 64-bit int?
countT is currently defined as 'int' in qset_r.h
Vertex ID and ridge ID perhaps should be countT
Check use of 'int' vs. countT in all cpp code
Check use of 'int' vs. countT in all c code
qset_r.h defines countT -- duplicates code in user_r.h -- need to add to qset.h/user.h
countT -1 used as a flag in Coordinates.mid(), QhullFacet->id()
Also QhullPoints indexOf and lastIndexOf
Also QhullPointSet indexOf and lastIndexOf
Coordinates.indexOf assumes countT is signed (from end)
Coordinates.lastIndexOf assumes countT is signed (from end)
All error messages with countT are wrong, convert to int?
RboxPoints.qh_fprintf_rbox, etc. message 9393 assumes countT but may be int, va_arg(args, countT); Need to split
------------
To do for a furture version of the C++ interface
- Document C++ using Doxygen conventions (//! and //!<)
- Create a shared library for libqhullcpp. It must include all uses of QH_TRY and setjmp().
- Should Qhull manage the output formats for doubles? QH11010 user_r.h defines qh_REAL_1 as %6.8g
- Allocate memory for QhullSet using Qhull.qhmem. Create default constructors for QhullVertexSet etc. Also mid() etc.
- Add interior point for automatic translation?
- Add hasNext() to all next() iterators (e.g., QhullVertex)
- Add defineAs to each object
- Write a program with concurrent Qhull
- Write QhullStat and QhullStat_test
- Add QList and vector instance of facetT*, etc.
- Generalize QhullPointSetIterator
-----------
-To Do
+To Do for Qhull 2015.1
+ - Review Qhull email
- vertex_id should be 'countT'
+ - Fix rare "no more facets" error at initialization
+ - Compare libqhull to libqhull_r
+ - Review all FIXUP
+ - Review all C++ classes and C++ tests
+ QhullVertexSet uses QhullSetBase::referenceSetT() to free it's memory. Probably needed elsewhere
+ - CMakelists.txt: Fix name of qhull6_p_d.dll
+ - CMakelists.txt: Why all files duplicated for cmake build
+ - Add sln/vcproj builds for Win64
+ - qhull.pro: It should build with reentrant Qhull
+ - qhull-all.pro: Review other files
+ - Review -Wshadow warnings. Need naming convention for parameter vs. member, 'qqh' doesn't genealize
+ - rboxlib.c: Review -Wclobbered warnings. 'simplex' is used at longjmp, add volatile comments
+ - Break up -Wextra into its components or figure out how to override -Wunused-but-set-variable
+ unused-but-set-variable is reporting incorrectly. All instances are annotated.
+ - qh-get.htm: Add list of download build repositories
+ - qh-code.htm: Document changes to C++ interface. See Changes.txt
+ Organize C++ documentation into collection classes, etc.
+ - qh-code.htm: May also use libqhull_r (e.g., FOREACHfacet_(...))
+
+------------
+Qhull 2015.0.2 2015/9/1
+ - global_r.c: Fixed spelling of /* duplicated in...qh_clear_outputflags */ [K. Schwehr]
+ - Replaced Gitorious with GitHub
+ - Moved 'to do' comments into Changes.txt
------------
-Qhull 2015.0.2
+Qhull 2015.0.2 2015/8/31
Source code changes
- Increased size of vertexT.id and ridgeT.id to 2^32
Reworded the warning message for ridgeT.id overflow. It does not affect Qhull output
- Add qh_lib_check to check for a compatible Qhull library.
Programs should call QHULL_LIB_CHECK before calling Qhull.
- Include headers prefixed with libqhull/, libqhull_r/, or libqhullcpp/
- Renamed debugging routines dfacet/dvertex to qh_dfacet/qh_dvertex
- Rewrote user_eg, user_eg2, and user_eg3 as reentrant code
- Renamed 'qh_rand_seed' to 'qh_last_random'. Declare it as DATA
- qh_initqhull_start2 sets qh->NOerrexit on initialization
User must clear NOerrexit after setjmp()
Other source code changes
- Define ptr_intT as 'long long' for __MINGW64__ [A. Voskov]
+ - poly_r.c: initialize horizon_skip [K. Schwehr]
- Removed vertexT.dim and MAX_vdim. It is not used by reentrant Qhull.
- Removed qhull_inuse. Not used by C++
- Removed old __MWERKS__/__POWERPC__ code that speed up SIOUX I/O
- Moved #include libqhull/... before system includes (e.g., ---------------------------------
global.c
initializes all the globals of the qhull application
see README
see libqhull.h for qh.globals and function prototypes
see qhull_a.h for internal functions
Copyright (c) 1993-2015 The Geometry Center.
$Id: //main/2011/qhull/src/libqhull/global.c#23 $$Change: 1951 $
$DateTime: 2015/08/30 21:30:30 $$Author: bbarber $
*/
#include "qhull_a.h"
/*========= qh definition -- globals defined in libqhull.h =======================*/
#if qh_QHpointer
qhT *qh_qh= NULL; /* pointer to all global variables */
#else
qhT qh_qh; /* all global variables.
Add "= {0}" if this causes a compiler error.
Also qh_qhstat in stat.c and qhmem in mem.c. */
#endif
/*----------------------------------
qh_version
version string by year and date
the revision increases on code changes only
notes:
change date: Changes.txt, Announce.txt, index.htm, README.txt,
qhull-news.html, Eudora signatures, CMakeLists.txt
change version: README.txt, qh-get.htm, File_id.diz, Makefile.txt
change year: Copying.txt
check download size
recompile user_eg.c, rbox.c, libqhull.c, qconvex.c, qdelaun.c qvoronoi.c, qhalf.c, testqset.c
*/
const char *qh_version = "2015.0.2 2015/08/30";
/*---------------------------------
qh_appendprint( printFormat )
append printFormat to qh.PRINTout unless already defined
*/
void qh_appendprint(qh_PRINT format) {
int i;
for (i=0; i < qh_PRINTEND; i++) {
if (qh PRINTout[i] == format && format != qh_PRINTqhull)
break;
if (!qh PRINTout[i]) {
qh PRINTout[i]= format;
break;
}
}
} /* appendprint */
/*---------------------------------
qh_checkflags( commandStr, hiddenFlags )
errors if commandStr contains hiddenFlags
hiddenFlags starts and ends with a space and is space delimited (checked)
notes:
ignores first word (e.g., "qconvex i")
use qh_strtol/strtod since strtol/strtod may or may not skip trailing spaces
see:
qh_initflags() initializes Qhull according to commandStr
*/
void qh_checkflags(char *command, char *hiddenflags) {
char *s= command, *t, *chkerr; /* qh_skipfilename is non-const */
char key, opt, prevopt;
char chkkey[]= " ";
char chkopt[]= " ";
char chkopt2[]= " ";
boolT waserr= False;
if (*hiddenflags != ' ' || hiddenflags[strlen(hiddenflags)-1] != ' ') {
qh_fprintf(qh ferr, 6026, "qhull error (qh_checkflags): hiddenflags must start and end with a space: \"%s\"", hiddenflags);
qh_errexit(qh_ERRinput, NULL, NULL);
}
if (strpbrk(hiddenflags, ",\n\r\t")) {
qh_fprintf(qh ferr, 6027, "qhull error (qh_checkflags): hiddenflags contains commas, newlines, or tabs: \"%s\"", hiddenflags);
qh_errexit(qh_ERRinput, NULL, NULL);
}
while (*s && !isspace(*s)) /* skip program name */
s++;
while (*s) {
while (*s && isspace(*s))
s++;
if (*s == '-')
s++;
if (!*s)
break;
key = *s++;
chkerr = NULL;
if (key == 'T' && (*s == 'I' || *s == 'O')) { /* TI or TO 'file name' */
s= qh_skipfilename(++s);
continue;
}
chkkey[1]= key;
if (strstr(hiddenflags, chkkey)) {
chkerr= chkkey;
}else if (isupper(key)) {
opt= ' ';
prevopt= ' ';
chkopt[1]= key;
chkopt2[1]= key;
while (!chkerr && *s && !isspace(*s)) {
opt= *s++;
if (isalpha(opt)) {
chkopt[2]= opt;
if (strstr(hiddenflags, chkopt))
chkerr= chkopt;
if (prevopt != ' ') {
chkopt2[2]= prevopt;
chkopt2[3]= opt;
if (strstr(hiddenflags, chkopt2))
chkerr= chkopt2;
}
}else if (key == 'Q' && isdigit(opt) && prevopt != 'b'
&& (prevopt == ' ' || islower(prevopt))) {
chkopt[2]= opt;
if (strstr(hiddenflags, chkopt))
chkerr= chkopt;
}else {
qh_strtod(s-1, &t);
if (s < t)
s= t;
}
prevopt= opt;
}
}
if (chkerr) {
*chkerr= '\'';
chkerr[strlen(chkerr)-1]= '\'';
qh_fprintf(qh ferr, 6029, "qhull error: option %s is not used with this program.\n It may be used with qhull.\n", chkerr);
waserr= True;
}
}
if (waserr)
qh_errexit(qh_ERRinput, NULL, NULL);
} /* checkflags */
/*---------------------------------
qh_clear_outputflags()
Clear output flags for QhullPoints
*/
void qh_clear_outputflags(void) {
int i,k;
qh ANNOTATEoutput= False;
qh DOintersections= False;
qh DROPdim= -1;
qh FORCEoutput= False;
qh GETarea= False;
qh GOODpoint= 0;
qh GOODpointp= NULL;
qh GOODthreshold= False;
qh GOODvertex= 0;
qh GOODvertexp= NULL;
qh IStracing= 0;
qh KEEParea= False;
qh KEEPmerge= False;
qh KEEPminArea= REALmax;
qh PRINTcentrums= False;
qh PRINTcoplanar= False;
qh PRINTdots= False;
qh PRINTgood= False;
qh PRINTinner= False;
qh PRINTneighbors= False;
qh PRINTnoplanes= False;
qh PRINToptions1st= False;
qh PRINTouter= False;
qh PRINTprecision= True;
qh PRINTridges= False;
qh PRINTspheres= False;
qh PRINTstatistics= False;
qh PRINTsummary= False;
qh PRINTtransparent= False;
qh SPLITthresholds= False;
qh TRACElevel= 0;
qh TRInormals= False;
qh USEstdout= False;
qh VERIFYoutput= False;
- for (k=qh input_dim+1; k--; ) { /* duplicated in qh_initqhull_buffers and qh_clear_ouputflags */
+ for (k=qh input_dim+1; k--; ) { /* duplicated in qh_initqhull_buffers and qh_clear_outputflags */
qh lower_threshold[k]= -REALmax;
qh upper_threshold[k]= REALmax;
qh lower_bound[k]= -REALmax;
qh upper_bound[k]= REALmax;
}
for (i=0; i < qh_PRINTEND; i++) {
qh PRINTout[i]= qh_PRINTnone;
}
if (!qh qhull_commandsiz2)
qh qhull_commandsiz2= (int)strlen(qh qhull_command); /* WARN64 */
else {
qh qhull_command[qh qhull_commandsiz2]= '\0';
}
if (!qh qhull_optionsiz2)
qh qhull_optionsiz2= (int)strlen(qh qhull_options); /* WARN64 */
else {
qh qhull_options[qh qhull_optionsiz2]= '\0';
qh qhull_optionlen= qh_OPTIONline; /* start a new line */
}
} /* clear_outputflags */
/*---------------------------------
qh_clock()
return user CPU time in 100ths (qh_SECtick)
only defined for qh_CLOCKtype == 2
notes:
use first value to determine time 0
from Stevens '92 8.15
*/
unsigned long qh_clock(void) {
#if (qh_CLOCKtype == 2)
struct tms time;
static long clktck; /* initialized first call */
double ratio, cpu;
unsigned long ticks;
if (!clktck) {
if ((clktck= sysconf(_SC_CLK_TCK)) < 0) {
qh_fprintf(qh ferr, 6030, "qhull internal error (qh_clock): sysconf() failed. Use qh_CLOCKtype 1 in user.h\n");
qh_errexit(qh_ERRqhull, NULL, NULL);
}
}
if (times(&time) == -1) {
qh_fprintf(qh ferr, 6031, "qhull internal error (qh_clock): times() failed. Use qh_CLOCKtype 1 in user.h\n");
qh_errexit(qh_ERRqhull, NULL, NULL);
}
ratio= qh_SECticks / (double)clktck;
ticks= time.tms_utime * ratio;
return ticks;
#else
qh_fprintf(qh ferr, 6032, "qhull internal error (qh_clock): use qh_CLOCKtype 2 in user.h\n");
qh_errexit(qh_ERRqhull, NULL, NULL); /* never returns */
return 0;
#endif
} /* clock */
/*---------------------------------
qh_freebuffers()
free up global memory buffers
notes:
must match qh_initbuffers()
*/
void qh_freebuffers(void) {
trace5((qh ferr, 5001, "qh_freebuffers: freeing up global memory buffers\n"));
/* allocated by qh_initqhull_buffers */
qh_memfree(qh NEARzero, qh hull_dim * sizeof(realT));
qh_memfree(qh lower_threshold, (qh input_dim+1) * sizeof(realT));
qh_memfree(qh upper_threshold, (qh input_dim+1) * sizeof(realT));
qh_memfree(qh lower_bound, (qh input_dim+1) * sizeof(realT));
qh_memfree(qh upper_bound, (qh input_dim+1) * sizeof(realT));
qh_memfree(qh gm_matrix, (qh hull_dim+1) * qh hull_dim * sizeof(coordT));
qh_memfree(qh gm_row, (qh hull_dim+1) * sizeof(coordT *));
qh NEARzero= qh lower_threshold= qh upper_threshold= NULL;
qh lower_bound= qh upper_bound= NULL;
qh gm_matrix= NULL;
qh gm_row= NULL;
qh_setfree(&qh other_points);
qh_setfree(&qh del_vertices);
qh_setfree(&qh coplanarfacetset);
if (qh line) /* allocated by qh_readinput, freed if no error */
qh_free(qh line);
if (qh half_space)
qh_free(qh half_space);
if (qh temp_malloc)
qh_free(qh temp_malloc);
if (qh feasible_point) /* allocated by qh_readfeasible */
qh_free(qh feasible_point);
if (qh feasible_string) /* allocated by qh_initflags */
qh_free(qh feasible_string);
qh line= qh feasible_string= NULL;
qh half_space= qh feasible_point= qh temp_malloc= NULL;
/* usually allocated by qh_readinput */
if (qh first_point && qh POINTSmalloc) {
qh_free(qh first_point);
qh first_point= NULL;
}
if (qh input_points && qh input_malloc) { /* set by qh_joggleinput */
qh_free(qh input_points);
qh input_points= NULL;
}
trace5((qh ferr, 5002, "qh_freebuffers: finished\n"));
} /* freebuffers */
/*---------------------------------
qh_freebuild( allmem )
free global memory used by qh_initbuild and qh_buildhull
if !allmem,
does not free short memory (e.g., facetT, freed by qh_memfreeshort)
design:
free centrums
free each vertex
mark unattached ridges
for each facet
free ridges
free outside set, coplanar set, neighbor set, ridge set, vertex set
free facet
free hash table
free interior point
free merge set
free temporary sets
*/
void qh_freebuild(boolT allmem) {
facetT *facet;
vertexT *vertex;
ridgeT *ridge, **ridgep;
mergeT *merge, **mergep;
trace1((qh ferr, 1005, "qh_freebuild: free memory from qh_inithull and qh_buildhull\n"));
if (qh del_vertices)
qh_settruncate(qh del_vertices, 0);
if (allmem) {
while ((vertex= qh vertex_list)) {
if (vertex->next)
qh_delvertex(vertex);
else {
qh_memfree(vertex, (int)sizeof(vertexT));
qh newvertex_list= qh vertex_list= NULL;
}
}
}else if (qh VERTEXneighbors) {
FORALLvertices
qh_setfreelong(&(vertex->neighbors));
}
qh VERTEXneighbors= False;
qh GOODclosest= NULL;
if (allmem) {
FORALLfacets {
FOREACHridge_(facet->ridges)
ridge->seen= False;
}
FORALLfacets {
if (facet->visible) {
FOREACHridge_(facet->ridges) {
if (!otherfacet_(ridge, facet)->visible)
ridge->seen= True; /* an unattached ridge */
}
}
}
while ((facet= qh facet_list)) {
FOREACHridge_(facet->ridges) {
if (ridge->seen) {
qh_setfree(&(ridge->vertices));
qh_memfree(ridge, (int)sizeof(ridgeT));
}else
ridge->seen= True;
}
qh_setfree(&(facet->outsideset));
qh_setfree(&(facet->coplanarset));
qh_setfree(&(facet->neighbors));
qh_setfree(&(facet->ridges));
qh_setfree(&(facet->vertices));
if (facet->next)
qh_delfacet(facet);
else {
qh_memfree(facet, (int)sizeof(facetT));
qh visible_list= qh newfacet_list= qh facet_list= NULL;
}
}
}else {
FORALLfacets {
qh_setfreelong(&(facet->outsideset));
qh_setfreelong(&(facet->coplanarset));
if (!facet->simplicial) {
qh_setfreelong(&(facet->neighbors));
qh_setfreelong(&(facet->ridges));
qh_setfreelong(&(facet->vertices));
}
}
}
qh_setfree(&(qh hash_table));
qh_memfree(qh interior_point, qh normal_size);
qh interior_point= NULL;
FOREACHmerge_(qh facet_mergeset) /* usually empty */
qh_memfree(merge, (int)sizeof(mergeT));
qh facet_mergeset= NULL; /* temp set */
qh degen_mergeset= NULL; /* temp set */
qh_settempfree_all();
} /* freebuild */
/*---------------------------------
qh_freeqhull( allmem )
see qh_freeqhull2
if qh_QHpointer, frees qh_qh
*/
void qh_freeqhull(boolT allmem) {
qh_freeqhull2(allmem);
#if qh_QHpointer
qh_free(qh_qh);
qh_qh= NULL;
#endif
}
/*---------------------------------
qh_freeqhull2( allmem )
free global memory
if !allmem,
does not free short memory (freed by qh_memfreeshort)
notes:
sets qh.NOerrexit in case caller forgets to
see:
see qh_initqhull_start2()
design:
free global and temporary memory from qh_initbuild and qh_buildhull
free buffers
free statistics
*/
void qh_freeqhull2(boolT allmem) {
trace1((qh ferr, 1006, "qh_freeqhull2: free global memory\n"));
qh NOerrexit= True; /* no more setjmp since called at exit and ~QhullQh */
qh_freebuild(allmem);
qh_freebuffers();
qh_freestatistics();
#if qh_QHpointer
memset((char *)qh_qh, 0, sizeof(qhT));
/* qh_qh freed by caller, qh_freeqhull() */
#else
memset((char *)&qh_qh, 0, sizeof(qhT));
#endif
qh NOerrexit= True;
} /* freeqhull2 */
/*---------------------------------
qh_init_A( infile, outfile, errfile, argc, argv )
initialize memory and stdio files
convert input options to option string (qh.qhull_command)
notes:
infile may be NULL if qh_readpoints() is not called
errfile should always be defined. It is used for reporting
errors. outfile is used for output and format options.
argc/argv may be 0/NULL
called before error handling initialized
qh_errexit() may not be used
*/
void qh_init_A(FILE *infile, FILE *outfile, FILE *errfile, int argc, char *argv[]) {
qh_meminit(errfile);
qh_initqhull_start(infile, outfile, errfile);
qh_init_qhull_command(argc, argv);
} /* init_A */
/*---------------------------------
qh_init_B( points, numpoints, dim, ismalloc )
initialize globals for points array
points has numpoints dim-dimensional points
points[0] is the first coordinate of the first point
points[1] is the second coordinate of the first point
points[dim] is the first coordinate of the second point
ismalloc=True
Qhull will call qh_free(points) on exit or input transformation
ismalloc=False
Qhull will allocate a new point array if needed for input transformation
qh.qhull_command
is the option string.
It is defined by qh_init_B(), qh_qhull_command(), or qh_initflags
returns:
if qh.PROJECTinput or (qh.DELAUNAY and qh.PROJECTdelaunay)
projects the input to a new point array
if qh.DELAUNAY,
qh.hull_dim is increased by one
if qh.ATinfinity,
qh_projectinput adds point-at-infinity for Delaunay tri.
if qh.SCALEinput
changes the upper and lower bounds of the input, see qh_scaleinput()
if qh.ROTATEinput
rotates the input by a random rotation, see qh_rotateinput()
if qh.DELAUNAY
rotates about the last coordinate
notes:
called after points are defined
qh_errexit() may be used
*/
void qh_init_B(coordT *points, int numpoints, int dim, boolT ismalloc) {
qh_initqhull_globals(points, numpoints, dim, ismalloc);
if (qhmem.LASTsize == 0)
qh_initqhull_mem();
/* mem.c and qset.c are initialized */
qh_initqhull_buffers();
qh_initthresholds(qh qhull_command);
if (qh PROJECTinput || (qh DELAUNAY && qh PROJECTdelaunay))
qh_projectinput();
if (qh SCALEinput)
qh_scaleinput();
if (qh ROTATErandom >= 0) {
qh_randommatrix(qh gm_matrix, qh hull_dim, qh gm_row);
if (qh DELAUNAY) {
int k, lastk= qh hull_dim-1;
for (k=0; k < lastk; k++) {
qh gm_row[k][lastk]= 0.0;
qh gm_row[lastk][k]= 0.0;
}
qh gm_row[lastk][lastk]= 1.0;
}
qh_gram_schmidt(qh hull_dim, qh gm_row);
qh_rotateinput(qh gm_row);
}
} /* init_B */
/*---------------------------------
qh_init_qhull_command( argc, argv )
build qh.qhull_command from argc/argv
returns:
a space-delimited string of options (just as typed)
notes:
makes option string easy to input and output
argc/argv may be 0/NULL
*/
void qh_init_qhull_command(int argc, char *argv[]) {
if (!qh_argv_to_command(argc, argv, qh qhull_command, (int)sizeof(qh qhull_command))){
/* Assumes qh.ferr is defined. */
qh_fprintf(qh ferr, 6033, "qhull input error: more than %d characters in command line\n",
(int)sizeof(qh qhull_command));
qh_exit(qh_ERRinput); /* error reported, can not use qh_errexit */
}
} /* init_qhull_command */
/*---------------------------------
qh_initflags( commandStr )
set flags and initialized constants from commandStr
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){
qh_fprintf(qh ferr, 6245, "qhull error: qh.NOerrexit not cleared after setjmp() and before qh_initflags(). Exiting with error.");
qh_exit(6245);
}
if (command <= &qh qhull_command[0] || command > &qh qhull_command[0] + sizeof(qh qhull_command)) {
if (command != &qh qhull_command[0]) {
*qh qhull_command= '\0';
strncat(qh qhull_command, command, sizeof(qh qhull_command)-strlen(qh qhull_command)-1);
}
while (*s && !isspace(*s)) /* skip program name */
s++;
}
while (*s) {
while (*s && isspace(*s))
s++;
if (*s == '-')
s++;
if (!*s)
break;
prev_s= s;
switch (*s++) {
case 'd':
qh_option("delaunay", NULL, NULL);
qh DELAUNAY= True;
break;
case 'f':
qh_option("facets", NULL, NULL);
qh_appendprint(qh_PRINTfacets);
break;
case 'i':
qh_option("incidence", NULL, NULL);
qh_appendprint(qh_PRINTincidences);
break;
case 'm':
qh_option("mathematica", NULL, NULL);
qh_appendprint(qh_PRINTmathematica);
break;
case 'n':
qh_option("normals", NULL, NULL);
qh_appendprint(qh_PRINTnormals);
break;
case 'o':
qh_option("offFile", NULL, NULL);
qh_appendprint(qh_PRINToff);
break;
case 'p':
qh_option("points", NULL, NULL);
qh_appendprint(qh_PRINTpoints);
break;
case 's':
qh_option("summary", NULL, NULL);
qh PRINTsummary= True;
break;
case 'v':
qh_option("voronoi", NULL, NULL);
qh VORONOI= True;
qh DELAUNAY= True;
break;
case 'A':
if (!isdigit(*s) && *s != '.' && *s != '-')
qh_fprintf(qh ferr, 7002, "qhull warning: no maximum cosine angle given for option 'An'. Ignored.\n");
else {
if (*s == '-') {
qh premerge_cos= -qh_strtod(s, &s);
qh_option("Angle-premerge-", NULL, &qh premerge_cos);
qh PREmerge= True;
}else {
qh postmerge_cos= qh_strtod(s, &s);
qh_option("Angle-postmerge", NULL, &qh postmerge_cos);
qh POSTmerge= True;
}
qh MERGING= True;
}
break;
case 'C':
if (!isdigit(*s) && *s != '.' && *s != '-')
qh_fprintf(qh ferr, 7003, "qhull warning: no centrum radius given for option 'Cn'. Ignored.\n");
else {
if (*s == '-') {
qh premerge_centrum= -qh_strtod(s, &s);
qh_option("Centrum-premerge-", NULL, &qh premerge_centrum);
qh PREmerge= True;
}else {
qh postmerge_centrum= qh_strtod(s, &s);
qh_option("Centrum-postmerge", NULL, &qh postmerge_centrum);
qh POSTmerge= True;
}
qh MERGING= True;
}
break;
case 'E':
if (*s == '-')
qh_fprintf(qh ferr, 7004, "qhull warning: negative maximum roundoff given for option 'An'. Ignored.\n");
else if (!isdigit(*s))
qh_fprintf(qh ferr, 7005, "qhull warning: no maximum roundoff given for option 'En'. Ignored.\n");
else {
qh DISTround= qh_strtod(s, &s);
qh_option("Distance-roundoff", NULL, &qh DISTround);
qh SETroundoff= True;
}
break;
case 'H':
start= s;
qh HALFspace= True;
qh_strtod(s, &t);
while (t > s) {
if (*t && !isspace(*t)) {
if (*t == ',')
t++;
else
qh_fprintf(qh ferr, 7006, "qhull warning: origin for Halfspace intersection should be 'Hn,n,n,...'\n");
}
s= t;
qh_strtod(s, &t);
}
if (start < t) {
if (!(qh feasible_string= (char*)calloc((size_t)(t-start+1), (size_t)1))) {
qh_fprintf(qh ferr, 6034, "qhull error: insufficient memory for 'Hn,n,n'\n");
qh_errexit(qh_ERRmem, NULL, NULL);
}
strncpy(qh feasible_string, start, (size_t)(t-start));
qh_option("Halfspace-about", NULL, NULL);
qh_option(qh feasible_string, NULL, NULL);
}else
qh_option("Halfspace", NULL, NULL);
break;
case 'R':
if (!isdigit(*s))
qh_fprintf(qh ferr, 7007, "qhull warning: missing random perturbation for option 'Rn'. Ignored\n");
else {
qh RANDOMfactor= qh_strtod(s, &s);
qh_option("Random_perturb", NULL, &qh RANDOMfactor);
qh RANDOMdist= True;
}
break;
case 'V':
if (!isdigit(*s) && *s != '-')
qh_fprintf(qh ferr, 7008, "qhull warning: missing visible distance for option 'Vn'. Ignored\n");
else {
qh MINvisible= qh_strtod(s, &s);
qh_option("Visible", NULL, &qh MINvisible);
}
break;
case 'U':
if (!isdigit(*s) && *s != '-')
qh_fprintf(qh ferr, 7009, "qhull warning: missing coplanar distance for option 'Un'. Ignored\n");
else {
qh MAXcoplanar= qh_strtod(s, &s);
qh_option("U-coplanar", NULL, &qh MAXcoplanar);
}
break;
case 'W':
if (*s == '-')
qh_fprintf(qh ferr, 7010, "qhull warning: negative outside width for option 'Wn'. Ignored.\n");
else if (!isdigit(*s))
qh_fprintf(qh ferr, 7011, "qhull warning: missing outside width for option 'Wn'. Ignored\n");
else {
qh MINoutside= qh_strtod(s, &s);
qh_option("W-outside", NULL, &qh MINoutside);
qh APPROXhull= True;
}
break;
/************ sub menus ***************/
case 'F':
while (*s && !isspace(*s)) {
switch (*s++) {
case 'a':
qh_option("Farea", NULL, NULL);
qh_appendprint(qh_PRINTarea);
qh GETarea= True;
break;
case 'A':
qh_option("FArea-total", NULL, NULL);
qh GETarea= True;
break;
case 'c':
qh_option("Fcoplanars", NULL, NULL);
qh_appendprint(qh_PRINTcoplanars);
break;
case 'C':
qh_option("FCentrums", NULL, NULL);
qh_appendprint(qh_PRINTcentrums);
break;
case 'd':
qh_option("Fd-cdd-in", NULL, NULL);
qh CDDinput= True;
break;
case 'D':
qh_option("FD-cdd-out", NULL, NULL);
qh CDDoutput= True;
break;
case 'F':
qh_option("FFacets-xridge", NULL, NULL);
qh_appendprint(qh_PRINTfacets_xridge);
break;
case 'i':
qh_option("Finner", NULL, NULL);
qh_appendprint(qh_PRINTinner);
break;
case 'I':
qh_option("FIDs", NULL, NULL);
qh_appendprint(qh_PRINTids);
break;
case 'm':
qh_option("Fmerges", NULL, NULL);
qh_appendprint(qh_PRINTmerges);
break;
case 'M':
qh_option("FMaple", NULL, NULL);
qh_appendprint(qh_PRINTmaple);
break;
case 'n':
qh_option("Fneighbors", NULL, NULL);
qh_appendprint(qh_PRINTneighbors);
break;
case 'N':
qh_option("FNeighbors-vertex", NULL, NULL);
qh_appendprint(qh_PRINTvneighbors);
break;
case 'o':
qh_option("Fouter", NULL, NULL);
qh_appendprint(qh_PRINTouter);
break;
case 'O':
if (qh PRINToptions1st) {
qh_option("FOptions", NULL, NULL);
qh_appendprint(qh_PRINToptions);
}else
qh PRINToptions1st= True;
break;
case 'p':
qh_option("Fpoint-intersect", NULL, NULL);
qh_appendprint(qh_PRINTpointintersect);
break;
case 'P':
qh_option("FPoint-nearest", NULL, NULL);
qh_appendprint(qh_PRINTpointnearest);
break;
case 'Q':
qh_option("FQhull", NULL, NULL);
qh_appendprint(qh_PRINTqhull);
break;
case 's':
qh_option("Fsummary", NULL, NULL);
qh_appendprint(qh_PRINTsummary);
break;
case 'S':
qh_option("FSize", NULL, NULL);
qh_appendprint(qh_PRINTsize);
qh GETarea= True;
break;
case 't':
qh_option("Ftriangles", NULL, NULL);
qh_appendprint(qh_PRINTtriangles);
break;
case 'v':
/* option set in qh_initqhull_globals */
qh_appendprint(qh_PRINTvertices);
break;
case 'V':
qh_option("FVertex-average", NULL, NULL);
qh_appendprint(qh_PRINTaverage);
break;
case 'x':
qh_option("Fxtremes", NULL, NULL);
qh_appendprint(qh_PRINTextremes);
break;
default:
s--;
qh_fprintf(qh ferr, 7012, "qhull warning: unknown 'F' output option %c, rest ignored\n", (int)s[0]);
while (*++s && !isspace(*s));
break;
}
}
break;
case 'G':
isgeom= True;
qh_appendprint(qh_PRINTgeom);
while (*s && !isspace(*s)) {
switch (*s++) {
case 'a':
qh_option("Gall-points", NULL, NULL);
qh PRINTdots= True;
break;
case 'c':
qh_option("Gcentrums", NULL, NULL);
qh PRINTcentrums= True;
break;
case 'h':
qh_option("Gintersections", NULL, NULL);
qh DOintersections= True;
break;
case 'i':
qh_option("Ginner", NULL, NULL);
qh PRINTinner= True;
break;
case 'n':
qh_option("Gno-planes", NULL, NULL);
qh PRINTnoplanes= True;
break;
case 'o':
qh_option("Gouter", NULL, NULL);
qh PRINTouter= True;
break;
case 'p':
qh_option("Gpoints", NULL, NULL);
qh PRINTcoplanar= True;
break;
case 'r':
qh_option("Gridges", NULL, NULL);
qh PRINTridges= True;
break;
case 't':
qh_option("Gtransparent", NULL, NULL);
qh PRINTtransparent= True;
break;
case 'v':
qh_option("Gvertices", NULL, NULL);
qh PRINTspheres= True;
break;
case 'D':
if (!isdigit(*s))
qh_fprintf(qh ferr, 6035, "qhull input error: missing dimension for option 'GDn'\n");
else {
if (qh DROPdim >= 0)
qh_fprintf(qh ferr, 7013, "qhull warning: can only drop one dimension. Previous 'GD%d' ignored\n",
qh DROPdim);
qh DROPdim= qh_strtol(s, &s);
qh_option("GDrop-dim", &qh DROPdim, NULL);
}
break;
default:
s--;
qh_fprintf(qh ferr, 7014, "qhull warning: unknown 'G' print option %c, rest ignored\n", (int)s[0]);
while (*++s && !isspace(*s));
break;
}
}
break;
case 'P':
while (*s && !isspace(*s)) {
switch (*s++) {
case 'd': case 'D': /* see qh_initthresholds() */
key= s[-1];
i= qh_strtol(s, &s);
r= 0;
if (*s == ':') {
s++;
r= qh_strtod(s, &s);
}
if (key == 'd')
qh_option("Pdrop-facets-dim-less", &i, &r);
else
qh_option("PDrop-facets-dim-more", &i, &r);
break;
case 'g':
qh_option("Pgood-facets", NULL, NULL);
qh PRINTgood= True;
break;
case 'G':
qh_option("PGood-facet-neighbors", NULL, NULL);
qh PRINTneighbors= True;
break;
case 'o':
qh_option("Poutput-forced", NULL, NULL);
qh FORCEoutput= True;
break;
case 'p':
qh_option("Pprecision-ignore", NULL, NULL);
qh PRINTprecision= False;
break;
case 'A':
if (!isdigit(*s))
qh_fprintf(qh ferr, 6036, "qhull input error: missing facet count for keep area option 'PAn'\n");
else {
qh KEEParea= qh_strtol(s, &s);
qh_option("PArea-keep", &qh KEEParea, NULL);
qh GETarea= True;
}
break;
case 'F':
if (!isdigit(*s))
qh_fprintf(qh ferr, 6037, "qhull input error: missing facet area for option 'PFn'\n");
else {
qh KEEPminArea= qh_strtod(s, &s);
qh_option("PFacet-area-keep", NULL, &qh KEEPminArea);
qh GETarea= True;
}
break;
case 'M':
if (!isdigit(*s))
qh_fprintf(qh ferr, 6038, "qhull input error: missing merge count for option 'PMn'\n");
else {
qh KEEPmerge= qh_strtol(s, &s);
qh_option("PMerge-keep", &qh KEEPmerge, NULL);
}
break;
default:
s--;
qh_fprintf(qh ferr, 7015, "qhull warning: unknown 'P' print option %c, rest ignored\n", (int)s[0]);
while (*++s && !isspace(*s));
break;
}
}
break;
case 'Q':
lastproject= -1;
while (*s && !isspace(*s)) {
switch (*s++) {
case 'b': case 'B': /* handled by qh_initthresholds */
key= s[-1];
if (key == 'b' && *s == 'B') {
s++;
r= qh_DEFAULTbox;
qh SCALEinput= True;
qh_option("QbBound-unit-box", NULL, &r);
break;
}
if (key == 'b' && *s == 'b') {
s++;
qh SCALElast= True;
qh_option("Qbbound-last", NULL, NULL);
break;
}
k= qh_strtol(s, &s);
r= 0.0;
wasproject= False;
if (*s == ':') {
s++;
if ((r= qh_strtod(s, &s)) == 0.0) {
t= s; /* need true dimension for memory allocation */
while (*t && !isspace(*t)) {
if (toupper(*t++) == 'B'
&& k == qh_strtol(t, &t)
&& *t++ == ':'
&& qh_strtod(t, &t) == 0.0) {
qh PROJECTinput++;
trace2((qh ferr, 2004, "qh_initflags: project dimension %d\n", k));
qh_option("Qb-project-dim", &k, NULL);
wasproject= True;
lastproject= k;
break;
}
}
}
}
if (!wasproject) {
if (lastproject == k && r == 0.0)
lastproject= -1; /* doesn't catch all possible sequences */
else if (key == 'b') {
qh SCALEinput= True;
if (r == 0.0)
r= -qh_DEFAULTbox;
qh_option("Qbound-dim-low", &k, &r);
}else {
qh SCALEinput= True;
if (r == 0.0)
r= qh_DEFAULTbox;
qh_option("QBound-dim-high", &k, &r);
}
}
break;
case 'c':
qh_option("Qcoplanar-keep", NULL, NULL);
qh KEEPcoplanar= True;
break;
case 'f':
qh_option("Qfurthest-outside", NULL, NULL);
qh BESToutside= True;
break;
case 'g':
qh_option("Qgood-facets-only", NULL, NULL);
qh ONLYgood= True;
break;
case 'i':
qh_option("Qinterior-keep", NULL, NULL);
qh KEEPinside= True;
break;
case 'm':
qh_option("Qmax-outside-only", NULL, NULL);
qh ONLYmax= True;
break;
case 'r':
qh_option("Qrandom-outside", NULL, NULL);
qh RANDOMoutside= True;
break;
case 's':
qh_option("Qsearch-initial-simplex", NULL, NULL);
qh ALLpoints= True;
break;
case 't':
qh_option("Qtriangulate", NULL, NULL);
qh TRIangulate= True;
break;
case 'T':
qh_option("QTestPoints", NULL, NULL);
if (!isdigit(*s))
qh_fprintf(qh ferr, 6039, "qhull input error: missing number of test points for option 'QTn'\n");
else {
qh TESTpoints= qh_strtol(s, &s);
qh_option("QTestPoints", &qh TESTpoints, NULL);
}
break;
case 'u':
qh_option("QupperDelaunay", NULL, NULL);
qh UPPERdelaunay= True;
break;
case 'v':
qh_option("Qvertex-neighbors-convex", NULL, NULL);
qh TESTvneighbors= True;
break;
case 'x':
qh_option("Qxact-merge", NULL, NULL);
qh MERGEexact= True;
break;
case 'z':
qh_option("Qz-infinity-point", NULL, NULL);
qh ATinfinity= True;
break;
case '0':
qh_option("Q0-no-premerge", NULL, NULL);
qh NOpremerge= True;
break;
case '1':
if (!isdigit(*s)) {
qh_option("Q1-no-angle-sort", NULL, NULL);
qh ANGLEmerge= False;
break;
}
switch (*s++) {
case '0':
qh_option("Q10-no-narrow", NULL, NULL);
qh NOnarrow= True;
break;
case '1':
qh_option("Q11-trinormals Qtriangulate", NULL, NULL);
qh TRInormals= True;
qh TRIangulate= True;
break;
default:
s--;
qh_fprintf(qh ferr, 7016, "qhull warning: unknown 'Q' qhull option 1%c, rest ignored\n", (int)s[0]);
while (*++s && !isspace(*s));
break;
}
break;
case '2':
qh_option("Q2-no-merge-independent", NULL, NULL);
qh MERGEindependent= False;
goto LABELcheckdigit;
break; /* no warnings */
case '3':
qh_option("Q3-no-merge-vertices", NULL, NULL);
qh MERGEvertices= False;
LABELcheckdigit:
if (isdigit(*s))
qh_fprintf(qh ferr, 7017, "qhull warning: can not follow '1', '2', or '3' with a digit. '%c' skipped.\n",
*s++);
break;
case '4':
qh_option("Q4-avoid-old-into-new", NULL, NULL);
qh AVOIDold= True;
break;
case '5':
qh_option("Q5-no-check-outer", NULL, NULL);
qh SKIPcheckmax= True;
break;
case '6':
qh_option("Q6-no-concave-merge", NULL, NULL);
qh SKIPconvex= True;
break;
case '7':
qh_option("Q7-no-breadth-first", NULL, NULL);
qh VIRTUALmemory= True;
break;
case '8':
qh_option("Q8-no-near-inside", NULL, NULL);
qh NOnearinside= True;
break;
case '9':
qh_option("Q9-pick-furthest", NULL, NULL);
qh PICKfurthest= True;
break;
case 'G':
i= qh_strtol(s, &t);
if (qh GOODpoint)
qh_fprintf(qh ferr, 7018, "qhull warning: good point already defined for option 'QGn'. Ignored\n");
else if (s == t)
qh_fprintf(qh ferr, 7019, "qhull warning: missing good point id for option 'QGn'. Ignored\n");
else if (i < 0 || *s == '-') {
qh GOODpoint= i-1;
qh_option("QGood-if-dont-see-point", &i, NULL);
}else {
qh GOODpoint= i+1;
qh_option("QGood-if-see-point", &i, NULL);
}
s= t;
break;
case 'J':
if (!isdigit(*s) && *s != '-')
qh JOGGLEmax= 0.0;
else {
qh JOGGLEmax= (realT) qh_strtod(s, &s);
qh_option("QJoggle", NULL, &qh JOGGLEmax);
}
break;
case 'R':
if (!isdigit(*s) && *s != '-')
qh_fprintf(qh ferr, 7020, "qhull warning: missing random seed for option 'QRn'. Ignored\n");
else {
qh ROTATErandom= i= qh_strtol(s, &s);
if (i > 0)
qh_option("QRotate-id", &i, NULL );
else if (i < -1)
qh_option("QRandom-seed", &i, NULL );
}
break;
case 'V':
i= qh_strtol(s, &t);
if (qh GOODvertex)
qh_fprintf(qh ferr, 7021, "qhull warning: good vertex already defined for option 'QVn'. Ignored\n");
else if (s == t)
qh_fprintf(qh ferr, 7022, "qhull warning: no good point id given for option 'QVn'. Ignored\n");
else if (i < 0) {
qh GOODvertex= i - 1;
qh_option("QV-good-facets-not-point", &i, NULL);
}else {
qh_option("QV-good-facets-point", &i, NULL);
qh GOODvertex= i + 1;
}
s= t;
break;
default:
s--;
qh_fprintf(qh ferr, 7023, "qhull warning: unknown 'Q' qhull option %c, rest ignored\n", (int)s[0]);
while (*++s && !isspace(*s));
break;
}
}
break;
case 'T':
while (*s && !isspace(*s)) {
if (isdigit(*s) || *s == '-')
qh IStracing= qh_strtol(s, &s);
else switch (*s++) {
case 'a':
qh_option("Tannotate-output", NULL, NULL);
qh ANNOTATEoutput= True;
break;
case 'c':
qh_option("Tcheck-frequently", NULL, NULL);
qh CHECKfrequently= True;
break;
case 's':
qh_option("Tstatistics", NULL, NULL);
qh PRINTstatistics= True;
break;
case 'v':
qh_option("Tverify", NULL, NULL);
qh VERIFYoutput= True;
break;
case 'z':
if (qh ferr == qh_FILEstderr) {
/* The C++ interface captures the output in qh_fprint_qhull() */
qh_option("Tz-stdout", NULL, NULL);
qh USEstdout= True;
}else if (!qh fout)
qh_fprintf(qh ferr, 7024, "qhull warning: output file undefined(stdout). Option 'Tz' ignored.\n");
else {
qh_option("Tz-stdout", NULL, NULL);
qh USEstdout= True;
qh ferr= qh fout;
qhmem.ferr= qh fout;
}
break;
case 'C':
if (!isdigit(*s))
qh_fprintf(qh ferr, 7025, "qhull warning: missing point id for cone for trace option 'TCn'. Ignored\n");
else {
i= qh_strtol(s, &s);
qh_option("TCone-stop", &i, NULL);
qh STOPcone= i + 1;
}
break;
case 'F':
if (!isdigit(*s))
qh_fprintf(qh ferr, 7026, "qhull warning: missing frequency count for trace option 'TFn'. Ignored\n");
else {
qh REPORTfreq= qh_strtol(s, &s);
qh_option("TFacet-log", &qh REPORTfreq, NULL);
qh REPORTfreq2= qh REPORTfreq/2; /* for tracemerging() */
}
break;
case 'I':
if (!isspace(*s))
qh_fprintf(qh ferr, 7027, "qhull warning: missing space between 'TI' and filename, %s\n", s);
while (isspace(*s))
s++;
t= qh_skipfilename(s);
{
char filename[qh_FILENAMElen];
qh_copyfilename(filename, (int)sizeof(filename), s, (int)(t-s)); /* WARN64 */
s= t;
if (!freopen(filename, "r", stdin)) {
qh_fprintf(qh ferr, 6041, "qhull error: could not open file \"%s\".", filename);
qh_errexit(qh_ERRinput, NULL, NULL);
}else {
qh_option("TInput-file", NULL, NULL);
qh_option(filename, NULL, NULL);
}
}
break;
case 'O':
if (!isspace(*s))
qh_fprintf(qh ferr, 7028, "qhull warning: missing space between 'TO' and filename, %s\n", s);
while (isspace(*s))
s++;
t= qh_skipfilename(s);
{
char filename[qh_FILENAMElen];
qh_copyfilename(filename, (int)sizeof(filename), s, (int)(t-s)); /* WARN64 */
s= t;
if (!freopen(filename, "w", stdout)) {
qh_fprintf(qh ferr, 6044, "qhull error: could not open file \"%s\".", filename);
qh_errexit(qh_ERRinput, NULL, NULL);
}else {
qh_option("TOutput-file", NULL, NULL);
qh_option(filename, NULL, NULL);
}
}
break;
case 'P':
if (!isdigit(*s))
qh_fprintf(qh ferr, 7029, "qhull warning: missing point id for trace option 'TPn'. Ignored\n");
else {
qh TRACEpoint= qh_strtol(s, &s);
qh_option("Trace-point", &qh TRACEpoint, NULL);
}
break;
case 'M':
if (!isdigit(*s))
qh_fprintf(qh ferr, 7030, "qhull warning: missing merge id for trace option 'TMn'. Ignored\n");
else {
qh TRACEmerge= qh_strtol(s, &s);
qh_option("Trace-merge", &qh TRACEmerge, NULL);
}
break;
case 'R':
if (!isdigit(*s))
qh_fprintf(qh ferr, 7031, "qhull warning: missing rerun count for trace option 'TRn'. Ignored\n");
else {
qh RERUN= qh_strtol(s, &s);
qh_option("TRerun", &qh RERUN, NULL);
}
break;
case 'V':
i= qh_strtol(s, &t);
if (s == t)
qh_fprintf(qh ferr, 7032, "qhull warning: missing furthest point id for trace option 'TVn'. Ignored\n");
else if (i < 0) {
qh STOPpoint= i - 1;
qh_option("TV-stop-before-point", &i, NULL);
}else {
qh STOPpoint= i + 1;
qh_option("TV-stop-after-point", &i, NULL);
}
s= t;
break;
case 'W':
if (!isdigit(*s))
qh_fprintf(qh ferr, 7033, "qhull warning: missing max width for trace option 'TWn'. Ignored\n");
else {
qh TRACEdist= (realT) qh_strtod(s, &s);
qh_option("TWide-trace", NULL, &qh TRACEdist);
}
break;
default:
s--;
qh_fprintf(qh ferr, 7034, "qhull warning: unknown 'T' trace option %c, rest ignored\n", (int)s[0]);
while (*++s && !isspace(*s));
break;
}
}
break;
default:
qh_fprintf(qh ferr, 7035, "qhull warning: unknown flag %c(%x)\n", (int)s[-1],
(int)s[-1]);
break;
}
if (s-1 == prev_s && *s && !isspace(*s)) {
qh_fprintf(qh ferr, 7036, "qhull warning: missing space after flag %c(%x); reserved for menu. Skipped.\n",
(int)*prev_s, (int)*prev_s);
while (*s && !isspace(*s))
s++;
}
}
if (qh STOPcone && qh JOGGLEmax < REALmax/2)
qh_fprintf(qh ferr, 7078, "qhull warning: 'TCn' (stopCone) ignored when used with 'QJn' (joggle)\n");
if (isgeom && !qh FORCEoutput && qh PRINTout[1])
qh_fprintf(qh ferr, 7037, "qhull warning: additional output formats are not compatible with Geomview\n");
/* set derived values in qh_initqhull_globals */
} /* initflags */
/*---------------------------------
qh_initqhull_buffers()
initialize global memory buffers
notes:
must match qh_freebuffers()
*/
void qh_initqhull_buffers(void) {
int k;
qh TEMPsize= (qhmem.LASTsize - sizeof(setT))/SETelemsize;
if (qh TEMPsize <= 0 || qh TEMPsize > qhmem.LASTsize)
qh TEMPsize= 8; /* e.g., if qh_NOmem */
qh other_points= qh_setnew(qh TEMPsize);
qh del_vertices= qh_setnew(qh TEMPsize);
qh coplanarfacetset= qh_setnew(qh TEMPsize);
qh NEARzero= (realT *)qh_memalloc(qh hull_dim * sizeof(realT));
qh lower_threshold= (realT *)qh_memalloc((qh input_dim+1) * sizeof(realT));
qh upper_threshold= (realT *)qh_memalloc((qh input_dim+1) * sizeof(realT));
qh lower_bound= (realT *)qh_memalloc((qh input_dim+1) * sizeof(realT));
qh upper_bound= (realT *)qh_memalloc((qh input_dim+1) * sizeof(realT));
- for (k=qh input_dim+1; k--; ) { /* duplicated in qh_initqhull_buffers and qh_clear_ouputflags */
+ for (k=qh input_dim+1; k--; ) { /* duplicated in qh_initqhull_buffers and qh_clear_outputflags */
qh lower_threshold[k]= -REALmax;
qh upper_threshold[k]= REALmax;
qh lower_bound[k]= -REALmax;
qh upper_bound[k]= REALmax;
}
qh gm_matrix= (coordT *)qh_memalloc((qh hull_dim+1) * qh hull_dim * sizeof(coordT));
qh gm_row= (coordT **)qh_memalloc((qh hull_dim+1) * sizeof(coordT *));
} /* initqhull_buffers */
/*---------------------------------
qh_initqhull_globals( points, numpoints, dim, ismalloc )
initialize globals
if ismalloc
points were malloc'd and qhull should free at end
returns:
sets qh.first_point, num_points, input_dim, hull_dim and others
seeds random number generator (seed=1 if tracing)
modifies qh.hull_dim if ((qh.DELAUNAY and qh.PROJECTdelaunay) or qh.PROJECTinput)
adjust user flags as needed
also checks DIM3 dependencies and constants
notes:
do not use qh_point() since an input transformation may move them elsewhere
see:
qh_initqhull_start() sets default values for non-zero globals
design:
initialize points array from input arguments
test for qh.ZEROcentrum
(i.e., use opposite vertex instead of cetrum for convexity testing)
initialize qh.CENTERtype, qh.normal_size,
qh.center_size, qh.TRACEpoint/level,
initialize and test random numbers
qh_initqhull_outputflags() -- adjust and test output flags
*/
void qh_initqhull_globals(coordT *points, int numpoints, int dim, boolT ismalloc) {
int seed, pointsneeded, extra= 0, i, randi, k;
realT randr;
realT factorial;
time_t timedata;
trace0((qh ferr, 13, "qh_initqhull_globals: for %s | %s\n", qh rbox_command,
qh qhull_command));
qh POINTSmalloc= ismalloc;
qh first_point= points;
qh num_points= numpoints;
qh hull_dim= qh input_dim= dim;
if (!qh NOpremerge && !qh MERGEexact && !qh PREmerge && qh JOGGLEmax > REALmax/2) {
qh MERGING= True;
if (qh hull_dim <= 4) {
qh PREmerge= True;
qh_option("_pre-merge", NULL, NULL);
}else {
qh MERGEexact= True;
qh_option("Qxact_merge", NULL, NULL);
}
}else if (qh MERGEexact)
qh MERGING= True;
if (!qh NOpremerge && qh JOGGLEmax > REALmax/2) {
#ifdef qh_NOmerge
qh JOGGLEmax= 0.0;
#endif
}
if (qh TRIangulate && qh JOGGLEmax < REALmax/2 && qh PRINTprecision)
qh_fprintf(qh ferr, 7038, "qhull warning: joggle('QJ') always produces simplicial output. Triangulated output('Qt') does nothing.\n");
if (qh JOGGLEmax < REALmax/2 && qh DELAUNAY && !qh SCALEinput && !qh SCALElast) {
qh SCALElast= True;
qh_option("Qbbound-last-qj", NULL, NULL);
}
if (qh MERGING && !qh POSTmerge && qh premerge_cos > REALmax/2
&& qh premerge_centrum == 0) {
qh ZEROcentrum= True;
qh ZEROall_ok= True;
qh_option("_zero-centrum", NULL, NULL);
}
if (qh JOGGLEmax < REALmax/2 && REALepsilon > 2e-8 && qh PRINTprecision)
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 DOcheckmax= (!qh SKIPcheckmax && qh MERGING );
qh KEEPnearinside= (qh DOcheckmax && !(qh KEEPinside && qh KEEPcoplanar)
&& !qh NOnearinside);
if (qh MERGING)
qh CENTERtype= qh_AScentrum;
else if (qh VORONOI)
qh CENTERtype= qh_ASvoronoi;
if (qh TESTvneighbors && !qh MERGING) {
qh_fprintf(qh ferr, 6049, "qhull input error: test vertex neighbors('Qv') needs a merge option\n");
qh_errexit(qh_ERRinput, NULL ,NULL);
}
if (qh PROJECTinput || (qh DELAUNAY && qh PROJECTdelaunay)) {
qh hull_dim -= qh PROJECTinput;
if (qh DELAUNAY) {
qh hull_dim++;
if (qh ATinfinity)
extra= 1;
}
}
if (qh hull_dim <= 1) {
qh_fprintf(qh ferr, 6050, "qhull error: dimension %d must be > 1\n", qh hull_dim);
qh_errexit(qh_ERRinput, NULL, NULL);
}
for (k=2, factorial=1.0; k < qh hull_dim; k++)
factorial *= k;
qh AREAfactor= 1.0 / factorial;
trace2((qh ferr, 2005, "qh_initqhull_globals: initialize globals. dim %d numpoints %d malloc? %d projected %d to hull_dim %d\n",
dim, numpoints, ismalloc, qh PROJECTinput, qh hull_dim));
qh normal_size= qh hull_dim * sizeof(coordT);
qh center_size= qh normal_size - sizeof(coordT);
pointsneeded= qh hull_dim+1;
if (qh hull_dim > qh_DIMmergeVertex) {
qh MERGEvertices= False;
qh_option("Q3-no-merge-vertices-dim-high", NULL, NULL);
}
if (qh GOODpoint)
pointsneeded++;
#ifdef qh_NOtrace
if (qh IStracing) {
qh_fprintf(qh ferr, 6051, "qhull input error: tracing is not installed(qh_NOtrace in user.h)");
qh_errexit(qh_ERRqhull, NULL, NULL);
}
#endif
if (qh RERUN > 1) {
qh TRACElastrun= qh IStracing; /* qh_build_withrestart duplicates next conditional */
if (qh IStracing != -1)
qh IStracing= 0;
}else if (qh TRACEpoint != qh_IDunknown || qh TRACEdist < REALmax/2 || qh TRACEmerge) {
qh TRACElevel= (qh IStracing? qh IStracing : 3);
qh IStracing= 0;
}
if (qh ROTATErandom == 0 || qh ROTATErandom == -1) {
seed= (int)time(&timedata);
if (qh ROTATErandom == -1) {
seed= -seed;
qh_option("QRandom-seed", &seed, NULL );
}else
qh_option("QRotate-random", &seed, NULL);
qh ROTATErandom= seed;
}
seed= qh ROTATErandom;
if (seed == INT_MIN) /* default value */
seed= 1;
else if (seed < 0)
seed= -seed;
qh_RANDOMseed_(seed);
randr= 0.0;
for (i=1000; i--; ) {
randi= qh_RANDOMint;
randr += randi;
if (randi > qh_RANDOMmax) {
qh_fprintf(qh ferr, 8036, "\
qhull configuration error (qh_RANDOMmax in user.h):\n\
random integer %d > qh_RANDOMmax(%.8g)\n",
randi, qh_RANDOMmax);
qh_errexit(qh_ERRinput, NULL, NULL);
}
}
qh_RANDOMseed_(seed);
randr = randr/1000;
if (randr < qh_RANDOMmax * 0.1
|| randr > qh_RANDOMmax * 0.9)
qh_fprintf(qh ferr, 8037, "\
qhull configuration warning (qh_RANDOMmax in user.h):\n\
average of 1000 random integers (%.2g) is much different than expected (%.2g).\n\
Is qh_RANDOMmax (%.2g) wrong?\n",
randr, qh_RANDOMmax * 0.5, qh_RANDOMmax);
qh RANDOMa= 2.0 * qh RANDOMfactor/qh_RANDOMmax;
qh RANDOMb= 1.0 - qh RANDOMfactor;
if (qh_HASHfactor < 1.1) {
qh_fprintf(qh ferr, 6052, "qhull internal error (qh_initqhull_globals): qh_HASHfactor %d must be at least 1.1. Qhull uses linear hash probing\n",
qh_HASHfactor);
qh_errexit(qh_ERRqhull, NULL, NULL);
}
if (numpoints+extra < pointsneeded) {
qh_fprintf(qh ferr, 6214, "qhull input error: not enough points(%d) to construct initial simplex (need %d)\n",
numpoints, pointsneeded);
qh_errexit(qh_ERRinput, NULL, NULL);
}
qh_initqhull_outputflags();
} /* initqhull_globals */
/*---------------------------------
qh_initqhull_mem( )
initialize mem.c for qhull
qh.hull_dim and qh.normal_size determine some of the allocation sizes
if qh.MERGING,
includes ridgeT
calls qh_user_memsizes() to add up to 10 additional sizes for quick allocation
(see numsizes below)
returns:
mem.c already for qh_memalloc/qh_memfree (errors if called beforehand)
notes:
qh_produceoutput() prints memsizes
*/
void qh_initqhull_mem(void) {
int numsizes;
int i;
numsizes= 8+10;
qh_meminitbuffers(qh IStracing, qh_MEMalign, numsizes,
qh_MEMbufsize,qh_MEMinitbuf);
qh_memsize((int)sizeof(vertexT));
if (qh MERGING) {
qh_memsize((int)sizeof(ridgeT));
qh_memsize((int)sizeof(mergeT));
}
qh_memsize((int)sizeof(facetT));
i= sizeof(setT) + (qh hull_dim - 1) * SETelemsize; /* ridge.vertices */
qh_memsize(i);
qh_memsize(qh normal_size); /* normal */
i += SETelemsize; /* facet.vertices, .ridges, .neighbors */
qh_memsize(i);
qh_user_memsizes();
qh_memsetup();
} /* initqhull_mem */
/*---------------------------------
qh_initqhull_outputflags
initialize flags concerned with output
returns:
adjust user flags as needed
see:
qh_clear_outputflags() resets the flags
design:
test for qh.PRINTgood (i.e., only print 'good' facets)
check for conflicting print output options
*/
void qh_initqhull_outputflags(void) {
boolT printgeom= False, printmath= False, printcoplanar= False;
int i;
trace3((qh ferr, 3024, "qh_initqhull_outputflags: %s\n", qh qhull_command));
if (!(qh PRINTgood || qh PRINTneighbors)) {
if (qh KEEParea || qh KEEPminArea < REALmax/2 || qh KEEPmerge || qh DELAUNAY
|| (!qh ONLYgood && (qh GOODvertex || qh GOODpoint))) {
qh PRINTgood= True;
qh_option("Pgood", NULL, NULL);
}
}
if (qh PRINTtransparent) {
if (qh hull_dim != 4 || !qh DELAUNAY || qh VORONOI || qh DROPdim >= 0) {
qh_fprintf(qh ferr, 6215, "qhull input error: transparent Delaunay('Gt') needs 3-d Delaunay('d') w/o 'GDn'\n");
qh_errexit(qh_ERRinput, NULL, NULL);
}
qh DROPdim = 3;
qh PRINTridges = True;
}
for (i=qh_PRINTEND; i--; ) {
if (qh PRINTout[i] == qh_PRINTgeom)
printgeom= True;
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 ferr, 6053, "qhull input error: option 'Fp' is only used for \nhalfspace intersection('Hn,n,n').\n");
qh_errexit(qh_ERRinput, NULL, NULL);
}else if (qh PRINTout[i] == qh_PRINTtriangles && (qh HALFspace || qh VORONOI)) {
qh_fprintf(qh ferr, 6054, "qhull input error: option 'Ft' is not available for Voronoi vertices or halfspace intersection\n");
qh_errexit(qh_ERRinput, NULL, NULL);
}else if (qh PRINTout[i] == qh_PRINTcentrums && qh VORONOI) {
qh_fprintf(qh ferr, 6055, "qhull input error: option 'FC' is not available for Voronoi vertices('v')\n");
qh_errexit(qh_ERRinput, NULL, NULL);
}else if (qh PRINTout[i] == qh_PRINTvertices) {
if (qh VORONOI)
qh_option("Fvoronoi", NULL, NULL);
else
qh_option("Fvertices", NULL, NULL);
}
}
if (printcoplanar && qh DELAUNAY && qh JOGGLEmax < REALmax/2) {
if (qh PRINTprecision)
qh_fprintf(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 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
+ qh PRINTdots + qh PRINTspheres + qh DOintersections + qh PRINTridges)) {
qh_fprintf(qh ferr, 6058, "qhull input error: no output specified for Geomview\n");
qh_errexit(qh_ERRinput, NULL, NULL);
}
if (qh VORONOI && (qh hull_dim > 3 || qh DROPdim >= 0)) {
qh_fprintf(qh ferr, 6059, "qhull input error: Geomview output for Voronoi diagrams only for 2-d\n");
qh_errexit(qh_ERRinput, NULL, NULL);
}
/* can not warn about furthest-site Geomview output: no lower_threshold */
if (qh hull_dim == 4 && qh DROPdim == -1 &&
(qh PRINTcoplanar || qh PRINTspheres || qh PRINTcentrums)) {
qh_fprintf(qh ferr, 7042, "qhull input warning: coplanars, vertices, and centrums output not\n\
available for 4-d output(ignored). Could use 'GDn' instead.\n");
qh PRINTcoplanar= qh PRINTspheres= qh PRINTcentrums= False;
}
}
if (!qh KEEPcoplanar && !qh KEEPinside && !qh ONLYgood) {
if ((qh PRINTcoplanar && qh PRINTspheres) || printcoplanar) {
if (qh QHULLfinished) {
qh_fprintf(qh ferr, 7072, "qhull output warning: ignoring coplanar points, option 'Qc' was not set for the first run of qhull.\n");
}else {
qh KEEPcoplanar = True;
qh_option("Qcoplanar", NULL, NULL);
}
}
}
qh PRINTdim= qh hull_dim;
if (qh DROPdim >=0) { /* after Geomview checks */
if (qh DROPdim < qh hull_dim) {
qh PRINTdim--;
if (!printgeom || qh hull_dim < 3)
qh_fprintf(qh ferr, 7043, "qhull input warning: drop dimension 'GD%d' is only available for 3-d/4-d Geomview\n", qh DROPdim);
}else
qh DROPdim= -1;
}else if (qh VORONOI) {
qh DROPdim= qh hull_dim-1;
qh PRINTdim= qh hull_dim-1;
}
} /* qh_initqhull_outputflags */
/*---------------------------------
qh_initqhull_start( infile, outfile, errfile )
allocate memory if needed and call qh_initqhull_start2()
*/
void qh_initqhull_start(FILE *infile, FILE *outfile, FILE *errfile) {
#if qh_QHpointer
if (qh_qh) {
qh_fprintf(errfile, 6205, "qhull error (qh_initqhull_start): qh_qh already defined. Call qh_save_qhull() first\n");
qh_exit(qh_ERRqhull); /* no error handler */
}
if (!(qh_qh= (qhT *)qh_malloc(sizeof(qhT)))) {
qh_fprintf(errfile, 6060, "qhull error (qh_initqhull_start): insufficient memory\n");
qh_exit(qh_ERRmem); /* no error handler */
}
#endif
qh_initstatistics();
qh_initqhull_start2(infile, outfile, errfile);
} /* initqhull_start */
/*---------------------------------
qh_initqhull_start2( infile, outfile, errfile )
start initialization of qhull
initialize statistics, stdio, default values for global variables
assumes qh_qh is defined
notes:
report errors elsewhere, error handling and g_qhull_output [Qhull.cpp, QhullQh()] not in initialized
see:
qh_maxmin() determines the precision constants
qh_freeqhull2()
*/
void qh_initqhull_start2(FILE *infile, FILE *outfile, FILE *errfile) {
time_t timedata;
int seed;
qh_CPUclock; /* start the clock(for qh_clock). One-shot. */
#if qh_QHpointer
memset((char *)qh_qh, 0, sizeof(qhT)); /* every field is 0, FALSE, NULL */
#else
memset((char *)&qh_qh, 0, sizeof(qhT));
#endif
qh ANGLEmerge= True;
qh DROPdim= -1;
qh ferr= errfile;
qh fin= infile;
qh fout= outfile;
qh furthest_id= qh_IDunknown;
qh JOGGLEmax= REALmax;
qh KEEPminArea = REALmax;
qh last_low= REALmax;
qh last_high= REALmax;
qh last_newhigh= REALmax;
qh max_outside= 0.0;
qh max_vertex= 0.0;
qh MAXabs_coord= 0.0;
qh MAXsumcoord= 0.0;
qh MAXwidth= -REALmax;
qh MERGEindependent= True;
qh MINdenom_1= fmax_(1.0/REALmax, REALmin); /* used by qh_scalepoints */
qh MINoutside= 0.0;
qh MINvisible= REALmax;
qh MAXcoplanar= REALmax;
qh outside_err= REALmax;
qh premerge_centrum= 0.0;
qh premerge_cos= REALmax;
qh PRINTprecision= True;
qh PRINTradius= 0.0;
qh postmerge_cos= REALmax;
qh postmerge_centrum= 0.0;
qh ROTATErandom= INT_MIN;
qh MERGEvertices= True;
qh totarea= 0.0;
qh totvol= 0.0;
qh TRACEdist= REALmax;
qh TRACEpoint= qh_IDunknown; /* recompile or use 'TPn' */
qh tracefacet_id= UINT_MAX; /* recompile to trace a facet */
qh tracevertex_id= UINT_MAX; /* recompile to trace a vertex */
seed= (int)time(&timedata);
qh_RANDOMseed_(seed);
qh run_id= qh_RANDOMint;
if(!qh run_id)
qh run_id++; /* guarantee non-zero */
qh_option("run-id", &qh run_id, NULL);
strcat(qh qhull, "qhull");
} /* initqhull_start2 */
/*---------------------------------
qh_initthresholds( commandString )
set thresholds for printing and scaling from commandString
returns:
sets qh.GOODthreshold or qh.SPLITthreshold if 'Pd0D1' used
see:
qh_initflags(), 'Qbk' 'QBk' 'Pdk' and 'PDk'
qh_inthresholds()
design:
for each 'Pdn' or 'PDn' option
check syntax
set qh.lower_threshold or qh.upper_threshold
set qh.GOODthreshold if an unbounded threshold is used
set qh.SPLITthreshold if a bounded threshold is used
*/
void qh_initthresholds(char *command) {
realT value;
int idx, maxdim, k;
char *s= command; /* non-const due to strtol */
char key;
maxdim= qh input_dim;
if (qh DELAUNAY && (qh PROJECTdelaunay || qh PROJECTinput))
maxdim++;
while (*s) {
if (*s == '-')
s++;
if (*s == 'P') {
s++;
while (*s && !isspace(key= *s++)) {
if (key == 'd' || key == 'D') {
if (!isdigit(*s)) {
qh_fprintf(qh ferr, 7044, "qhull warning: no dimension given for Print option '%c' at: %s. Ignored\n",
key, s-1);
continue;
}
idx= qh_strtol(s, &s);
if (idx >= qh hull_dim) {
qh_fprintf(qh ferr, 7045, "qhull warning: dimension %d for Print option '%c' is >= %d. Ignored\n",
idx, key, qh hull_dim);
continue;
}
if (*s == ':') {
s++;
value= qh_strtod(s, &s);
if (fabs((double)value) > 1.0) {
qh_fprintf(qh ferr, 7046, "qhull warning: value %2.4g for Print option %c is > +1 or < -1. Ignored\n",
value, key);
continue;
}
}else
value= 0.0;
if (key == 'd')
qh lower_threshold[idx]= value;
else
qh upper_threshold[idx]= value;
}
}
}else if (*s == 'Q') {
s++;
while (*s && !isspace(key= *s++)) {
if (key == 'b' && *s == 'B') {
s++;
for (k=maxdim; k--; ) {
qh lower_bound[k]= -qh_DEFAULTbox;
qh upper_bound[k]= qh_DEFAULTbox;
}
}else if (key == 'b' && *s == 'b')
s++;
else if (key == 'b' || key == 'B') {
if (!isdigit(*s)) {
qh_fprintf(qh ferr, 7047, "qhull warning: no dimension given for Qhull option %c. Ignored\n",
key);
continue;
}
idx= qh_strtol(s, &s);
if (idx >= maxdim) {
qh_fprintf(qh ferr, 7048, "qhull warning: dimension %d for Qhull option %c is >= %d. Ignored\n",
idx, key, maxdim);
continue;
}
if (*s == ':') {
s++;
value= qh_strtod(s, &s);
}else if (key == 'b')
value= -qh_DEFAULTbox;
else
value= qh_DEFAULTbox;
if (key == 'b')
qh lower_bound[idx]= value;
else
qh upper_bound[idx]= value;
}
}
}else {
while (*s && !isspace(*s))
s++;
}
while (isspace(*s))
s++;
}
for (k=qh hull_dim; k--; ) {
if (qh lower_threshold[k] > -REALmax/2) {
qh GOODthreshold= True;
if (qh upper_threshold[k] < REALmax/2) {
qh SPLITthresholds= True;
qh GOODthreshold= False;
break;
}
}else if (qh upper_threshold[k] < REALmax/2)
qh GOODthreshold= True;
}
} /* initthresholds */
/*---------------------------------
qh_lib_check( isQHpointer, qhTsize, vertexTsize, ridgeTsize, facetTsize, setTsize, qhmemTsize )
Report error if library does not agree with caller
notes:
NOerrors -- qh_lib_check can not call qh_errexit()
*/
void qh_lib_check(int libraryType, int qhTsize, int vertexTsize, int ridgeTsize, int facetTsize, int setTsize, int qhmemTsize) {
boolT iserror= False;
if (libraryType==0 && 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 (libraryType==1 && !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 (libraryType==2) {
qh_fprintf(stderr, 6248, "qh_lib_check: Incorrect qhull library called. Caller uses reentrant Qhull while library is non-reentrant.");
iserror= True;
}
if (qhTsize != sizeof(qhT)) {
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_version);
}else{
qh_fprintf(stderr, 6256, "qh_lib_check: Cannot continue. Library '%s' uses a static qhT (e.g., libqhull.so)\n", qh_version);
}
qh_exit(qh_ERRqhull); /* can not use qh_errexit() */
}
} /* lib_check */
/*---------------------------------
qh_option( option, intVal, realVal )
add an option description to qh.qhull_options
notes:
NOerrors -- qh_option can not call qh_errexit() [qh_initqhull_start2]
will be printed with statistics ('Ts') and errors
strlen(option) < 40
*/
void qh_option(const char *option, int *i, realT *r) {
char buf[200];
int len, maxlen;
sprintf(buf, " %s", option);
if (i)
sprintf(buf+strlen(buf), " %d", *i);
if (r)
sprintf(buf+strlen(buf), " %2.2g", *r);
len= (int)strlen(buf); /* WARN64 */
qh qhull_optionlen += len;
maxlen= sizeof(qh qhull_options) - len -1;
maximize_(maxlen, 0);
if (qh qhull_optionlen >= qh_OPTIONline && maxlen > 0) {
qh qhull_optionlen= len;
strncat(qh qhull_options, "\n", (size_t)(maxlen--));
}
strncat(qh qhull_options, buf, (size_t)maxlen);
} /* option */
#if qh_QHpointer
/*---------------------------------
qh_restore_qhull( oldqh )
restores a previously saved qhull
also restores qh_qhstat and qhmem.tempstack
Sets *oldqh to NULL
notes:
errors if current qhull hasn't been saved or freed
uses qhmem for error reporting
NOTE 1998/5/11:
Freeing memory after qh_save_qhull and qh_restore_qhull
is complicated. The procedures will be redesigned.
see:
qh_save_qhull(), UsingLibQhull
*/
void qh_restore_qhull(qhT **oldqh) {
if (*oldqh && strcmp((*oldqh)->qhull, "qhull")) {
qh_fprintf(qhmem.ferr, 6061, "qhull internal error (qh_restore_qhull): %p is not a qhull data structure\n",
*oldqh);
qh_errexit(qh_ERRqhull, NULL, NULL);
}
if (qh_qh) {
qh_fprintf(qhmem.ferr, 6062, "qhull internal error (qh_restore_qhull): did not save or free existing qhull\n");
qh_errexit(qh_ERRqhull, NULL, NULL);
}
if (!*oldqh || !(*oldqh)->old_qhstat) {
qh_fprintf(qhmem.ferr, 6063, "qhull internal error (qh_restore_qhull): did not previously save qhull %p\n",
*oldqh);
qh_errexit(qh_ERRqhull, NULL, NULL);
}
qh_qh= *oldqh;
*oldqh= NULL;
qh_qhstat= qh old_qhstat;
qhmem.tempstack= qh old_tempstack;
qh old_qhstat= 0;
qh old_tempstack= 0;
trace1((qh ferr, 1007, "qh_restore_qhull: restored qhull from %p\n", *oldqh));
} /* restore_qhull */
/*---------------------------------
qh_save_qhull( )
saves qhull for a later qh_restore_qhull
also saves qh_qhstat and qhmem.tempstack
returns:
qh_qh=NULL
notes:
need to initialize qhull or call qh_restore_qhull before continuing
NOTE 1998/5/11:
Freeing memory after qh_save_qhull and qh_restore_qhull
is complicated. The procedures will be redesigned.
see:
qh_restore_qhull()
*/
qhT *qh_save_qhull(void) {
qhT *oldqh;
trace1((qhmem.ferr, 1045, "qh_save_qhull: save qhull %p\n", qh_qh));
if (!qh_qh) {
qh_fprintf(qhmem.ferr, 6064, "qhull internal error (qh_save_qhull): qhull not initialized\n");
qh_errexit(qh_ERRqhull, NULL, NULL);
}
qh old_qhstat= qh_qhstat;
qh_qhstat= NULL;
qh old_tempstack= qhmem.tempstack;
qhmem.tempstack= NULL;
oldqh= qh_qh;
qh_qh= NULL;
return oldqh;
} /* save_qhull */
#endif
diff --git a/src/libqhull_r/global_r.c b/src/libqhull_r/global_r.c
index ae138ff..6b925b2 100644
--- a/src/libqhull_r/global_r.c
+++ b/src/libqhull_r/global_r.c
@@ -1,2075 +1,2075 @@
/*
---------------------------------
global_r.c
initializes all the globals of the qhull application
see README
see libqhull_r.h for qh.globals and function prototypes
see qhull_ra.h for internal functions
Copyright (c) 1993-2015 The Geometry Center.
$Id: //main/2011/qhull/src/libqhull_r/global_r.c#3 $$Change: 1951 $
$DateTime: 2015/08/30 21:30:30 $$Author: bbarber $
*/
#include "qhull_ra.h"
/*========= qh->definition -- globals defined in libqhull_r.h =======================*/
/*----------------------------------
qh_version
version string by year and date
the revision increases on code changes only
notes:
change date: Changes.txt, Announce.txt, index.htm, README.txt,
qhull-news.html, Eudora signatures, CMakeLists.txt
change version: README.txt, qh-get.htm, File_id.diz, Makefile.txt
change year: Copying.txt
check download size
recompile user_eg_r.c, rbox_r.c, libqhull_r.c, qconvex_r.c, qdelaun_r.c qvoronoi_r.c, qhalf_r.c, testqset_r.c
*/
const char *qh_version = "2015.0.2.r 2015/08/30";
/*---------------------------------
qh_appendprint(qh, printFormat )
append printFormat to qh.PRINTout unless already defined
*/
void qh_appendprint(qhT *qh, qh_PRINT format) {
int i;
for (i=0; i < qh_PRINTEND; i++) {
if (qh->PRINTout[i] == format && format != qh_PRINTqhull)
break;
if (!qh->PRINTout[i]) {
qh->PRINTout[i]= format;
break;
}
}
} /* appendprint */
/*---------------------------------
qh_checkflags(qh, commandStr, hiddenFlags )
errors if commandStr contains hiddenFlags
hiddenFlags starts and ends with a space and is space delimited (checked)
notes:
ignores first word (e.g., "qconvex i")
use qh_strtol/strtod since strtol/strtod may or may not skip trailing spaces
see:
qh_initflags() initializes Qhull according to commandStr
*/
void qh_checkflags(qhT *qh, char *command, char *hiddenflags) {
char *s= command, *t, *chkerr; /* qh_skipfilename is non-const */
char key, opt, prevopt;
char chkkey[]= " ";
char chkopt[]= " ";
char chkopt2[]= " ";
boolT waserr= False;
if (*hiddenflags != ' ' || hiddenflags[strlen(hiddenflags)-1] != ' ') {
qh_fprintf(qh, qh->ferr, 6026, "qhull error (qh_checkflags): hiddenflags must start and end with a space: \"%s\"", hiddenflags);
qh_errexit(qh, qh_ERRinput, NULL, NULL);
}
if (strpbrk(hiddenflags, ",\n\r\t")) {
qh_fprintf(qh, qh->ferr, 6027, "qhull error (qh_checkflags): hiddenflags contains commas, newlines, or tabs: \"%s\"", hiddenflags);
qh_errexit(qh, qh_ERRinput, NULL, NULL);
}
while (*s && !isspace(*s)) /* skip program name */
s++;
while (*s) {
while (*s && isspace(*s))
s++;
if (*s == '-')
s++;
if (!*s)
break;
key = *s++;
chkerr = NULL;
if (key == 'T' && (*s == 'I' || *s == 'O')) { /* TI or TO 'file name' */
s= qh_skipfilename(qh, ++s);
continue;
}
chkkey[1]= key;
if (strstr(hiddenflags, chkkey)) {
chkerr= chkkey;
}else if (isupper(key)) {
opt= ' ';
prevopt= ' ';
chkopt[1]= key;
chkopt2[1]= key;
while (!chkerr && *s && !isspace(*s)) {
opt= *s++;
if (isalpha(opt)) {
chkopt[2]= opt;
if (strstr(hiddenflags, chkopt))
chkerr= chkopt;
if (prevopt != ' ') {
chkopt2[2]= prevopt;
chkopt2[3]= opt;
if (strstr(hiddenflags, chkopt2))
chkerr= chkopt2;
}
}else if (key == 'Q' && isdigit(opt) && prevopt != 'b'
&& (prevopt == ' ' || islower(prevopt))) {
chkopt[2]= opt;
if (strstr(hiddenflags, chkopt))
chkerr= chkopt;
}else {
qh_strtod(s-1, &t);
if (s < t)
s= t;
}
prevopt= opt;
}
}
if (chkerr) {
*chkerr= '\'';
chkerr[strlen(chkerr)-1]= '\'';
qh_fprintf(qh, qh->ferr, 6029, "qhull error: option %s is not used with this program.\n It may be used with qhull.\n", chkerr);
waserr= True;
}
}
if (waserr)
qh_errexit(qh, qh_ERRinput, NULL, NULL);
} /* checkflags */
/*---------------------------------
qh_clear_outputflags(qh)
Clear output flags for QhullPoints
*/
void qh_clear_outputflags(qhT *qh) {
int i,k;
qh->ANNOTATEoutput= False;
qh->DOintersections= False;
qh->DROPdim= -1;
qh->FORCEoutput= False;
qh->GETarea= False;
qh->GOODpoint= 0;
qh->GOODpointp= NULL;
qh->GOODthreshold= False;
qh->GOODvertex= 0;
qh->GOODvertexp= NULL;
qh->IStracing= 0;
qh->KEEParea= False;
qh->KEEPmerge= False;
qh->KEEPminArea= REALmax;
qh->PRINTcentrums= False;
qh->PRINTcoplanar= False;
qh->PRINTdots= False;
qh->PRINTgood= False;
qh->PRINTinner= False;
qh->PRINTneighbors= False;
qh->PRINTnoplanes= False;
qh->PRINToptions1st= False;
qh->PRINTouter= False;
qh->PRINTprecision= True;
qh->PRINTridges= False;
qh->PRINTspheres= False;
qh->PRINTstatistics= False;
qh->PRINTsummary= False;
qh->PRINTtransparent= False;
qh->SPLITthresholds= False;
qh->TRACElevel= 0;
qh->TRInormals= False;
qh->USEstdout= False;
qh->VERIFYoutput= False;
- for (k=qh->input_dim+1; k--; ) { /* duplicated in qh_initqhull_buffers and qh_clear_ouputflags */
+ for (k=qh->input_dim+1; k--; ) { /* duplicated in qh_initqhull_buffers and qh_clear_outputflags */
qh->lower_threshold[k]= -REALmax;
qh->upper_threshold[k]= REALmax;
qh->lower_bound[k]= -REALmax;
qh->upper_bound[k]= REALmax;
}
for (i=0; i < qh_PRINTEND; i++) {
qh->PRINTout[i]= qh_PRINTnone;
}
if (!qh->qhull_commandsiz2)
qh->qhull_commandsiz2= (int)strlen(qh->qhull_command); /* WARN64 */
else {
qh->qhull_command[qh->qhull_commandsiz2]= '\0';
}
if (!qh->qhull_optionsiz2)
qh->qhull_optionsiz2= (int)strlen(qh->qhull_options); /* WARN64 */
else {
qh->qhull_options[qh->qhull_optionsiz2]= '\0';
qh->qhull_optionlen= qh_OPTIONline; /* start a new line */
}
} /* clear_outputflags */
/*---------------------------------
qh_clock()
return user CPU time in 100ths (qh_SECtick)
only defined for qh_CLOCKtype == 2
notes:
use first value to determine time 0
from Stevens '92 8.15
*/
unsigned long qh_clock(qhT *qh) {
#if (qh_CLOCKtype == 2)
struct tms time;
static long clktck; /* initialized first call and never updated */
double ratio, cpu;
unsigned long ticks;
if (!clktck) {
if ((clktck= sysconf(_SC_CLK_TCK)) < 0) {
qh_fprintf(qh, qh->ferr, 6030, "qhull internal error (qh_clock): sysconf() failed. Use qh_CLOCKtype 1 in user.h\n");
qh_errexit(qh, qh_ERRqhull, NULL, NULL);
}
}
if (times(&time) == -1) {
qh_fprintf(qh, qh->ferr, 6031, "qhull internal error (qh_clock): times() failed. Use qh_CLOCKtype 1 in user.h\n");
qh_errexit(qh, qh_ERRqhull, NULL, NULL);
}
ratio= qh_SECticks / (double)clktck;
ticks= time.tms_utime * ratio;
return ticks;
#else
qh_fprintf(qh, qh->ferr, 6032, "qhull internal error (qh_clock): use qh_CLOCKtype 2 in user.h\n");
qh_errexit(qh, qh_ERRqhull, NULL, NULL); /* never returns */
return 0;
#endif
} /* clock */
/*---------------------------------
qh_freebuffers()
free up global memory buffers
notes:
must match qh_initbuffers()
*/
void qh_freebuffers(qhT *qh) {
trace5((qh, qh->ferr, 5001, "qh_freebuffers: freeing up global memory buffers\n"));
/* allocated by qh_initqhull_buffers */
qh_memfree(qh, qh->NEARzero, qh->hull_dim * sizeof(realT));
qh_memfree(qh, qh->lower_threshold, (qh->input_dim+1) * sizeof(realT));
qh_memfree(qh, qh->upper_threshold, (qh->input_dim+1) * sizeof(realT));
qh_memfree(qh, qh->lower_bound, (qh->input_dim+1) * sizeof(realT));
qh_memfree(qh, qh->upper_bound, (qh->input_dim+1) * sizeof(realT));
qh_memfree(qh, qh->gm_matrix, (qh->hull_dim+1) * qh->hull_dim * sizeof(coordT));
qh_memfree(qh, qh->gm_row, (qh->hull_dim+1) * sizeof(coordT *));
qh->NEARzero= qh->lower_threshold= qh->upper_threshold= NULL;
qh->lower_bound= qh->upper_bound= NULL;
qh->gm_matrix= NULL;
qh->gm_row= NULL;
qh_setfree(qh, &qh->other_points);
qh_setfree(qh, &qh->del_vertices);
qh_setfree(qh, &qh->coplanarfacetset);
if (qh->line) /* allocated by qh_readinput, freed if no error */
qh_free(qh->line);
if (qh->half_space)
qh_free(qh->half_space);
if (qh->temp_malloc)
qh_free(qh->temp_malloc);
if (qh->feasible_point) /* allocated by qh_readfeasible */
qh_free(qh->feasible_point);
if (qh->feasible_string) /* allocated by qh_initflags */
qh_free(qh->feasible_string);
qh->line= qh->feasible_string= NULL;
qh->half_space= qh->feasible_point= qh->temp_malloc= NULL;
/* usually allocated by qh_readinput */
if (qh->first_point && qh->POINTSmalloc) {
qh_free(qh->first_point);
qh->first_point= NULL;
}
if (qh->input_points && qh->input_malloc) { /* set by qh_joggleinput */
qh_free(qh->input_points);
qh->input_points= NULL;
}
trace5((qh, qh->ferr, 5002, "qh_freebuffers: finished\n"));
} /* freebuffers */
/*---------------------------------
qh_freebuild(qh, allmem )
free global memory used by qh_initbuild and qh_buildhull
if !allmem,
does not free short memory (e.g., facetT, freed by qh_memfreeshort)
design:
free centrums
free each vertex
mark unattached ridges
for each facet
free ridges
free outside set, coplanar set, neighbor set, ridge set, vertex set
free facet
free hash table
free interior point
free merge set
free temporary sets
*/
void qh_freebuild(qhT *qh, boolT allmem) {
facetT *facet;
vertexT *vertex;
ridgeT *ridge, **ridgep;
mergeT *merge, **mergep;
trace1((qh, qh->ferr, 1005, "qh_freebuild: free memory from qh_inithull and qh_buildhull\n"));
if (qh->del_vertices)
qh_settruncate(qh, qh->del_vertices, 0);
if (allmem) {
while ((vertex= qh->vertex_list)) {
if (vertex->next)
qh_delvertex(qh, vertex);
else {
qh_memfree(qh, vertex, (int)sizeof(vertexT));
qh->newvertex_list= qh->vertex_list= NULL;
}
}
}else if (qh->VERTEXneighbors) {
FORALLvertices
qh_setfreelong(qh, &(vertex->neighbors));
}
qh->VERTEXneighbors= False;
qh->GOODclosest= NULL;
if (allmem) {
FORALLfacets {
FOREACHridge_(facet->ridges)
ridge->seen= False;
}
FORALLfacets {
if (facet->visible) {
FOREACHridge_(facet->ridges) {
if (!otherfacet_(ridge, facet)->visible)
ridge->seen= True; /* an unattached ridge */
}
}
}
while ((facet= qh->facet_list)) {
FOREACHridge_(facet->ridges) {
if (ridge->seen) {
qh_setfree(qh, &(ridge->vertices));
qh_memfree(qh, ridge, (int)sizeof(ridgeT));
}else
ridge->seen= True;
}
qh_setfree(qh, &(facet->outsideset));
qh_setfree(qh, &(facet->coplanarset));
qh_setfree(qh, &(facet->neighbors));
qh_setfree(qh, &(facet->ridges));
qh_setfree(qh, &(facet->vertices));
if (facet->next)
qh_delfacet(qh, facet);
else {
qh_memfree(qh, facet, (int)sizeof(facetT));
qh->visible_list= qh->newfacet_list= qh->facet_list= NULL;
}
}
}else {
FORALLfacets {
qh_setfreelong(qh, &(facet->outsideset));
qh_setfreelong(qh, &(facet->coplanarset));
if (!facet->simplicial) {
qh_setfreelong(qh, &(facet->neighbors));
qh_setfreelong(qh, &(facet->ridges));
qh_setfreelong(qh, &(facet->vertices));
}
}
}
qh_setfree(qh, &(qh->hash_table));
qh_memfree(qh, qh->interior_point, qh->normal_size);
qh->interior_point= NULL;
FOREACHmerge_(qh->facet_mergeset) /* usually empty */
qh_memfree(qh, merge, (int)sizeof(mergeT));
qh->facet_mergeset= NULL; /* temp set */
qh->degen_mergeset= NULL; /* temp set */
qh_settempfree_all(qh);
} /* freebuild */
/*---------------------------------
qh_freeqhull(qh, allmem )
free global memory
if !allmem,
does not free short memory (freed by qh_memfreeshort)
notes:
sets qh.NOerrexit in case caller forgets to
Does not throw errors
see:
see qh_initqhull_start2()
design:
free global and temporary memory from qh_initbuild and qh_buildhull
free buffers
free statistics
*/
void qh_freeqhull(qhT *qh, boolT allmem) {
qh->NOerrexit= True; /* no more setjmp since called at exit and ~QhullQh */
trace1((qh, qh->ferr, 1006, "qh_freeqhull: free global memory\n"));
qh_freebuild(qh, allmem);
qh_freebuffers(qh);
/* memset is the same in qh_freeqhull() and qh_initqhull_start2() */
memset((char *)qh, 0, sizeof(qhT)-sizeof(qhmemT)-sizeof(qhstatT));
qh->NOerrexit= True;
} /* freeqhull2 */
/*---------------------------------
qh_init_A(qh, infile, outfile, errfile, argc, argv )
initialize memory and stdio files
convert input options to option string (qh.qhull_command)
notes:
infile may be NULL if qh_readpoints() is not called
errfile should always be defined. It is used for reporting
errors. outfile is used for output and format options.
argc/argv may be 0/NULL
called before error handling initialized
qh_errexit() may not be used
*/
void qh_init_A(qhT *qh, FILE *infile, FILE *outfile, FILE *errfile, int argc, char *argv[]) {
qh_meminit(qh, errfile);
qh_initqhull_start(qh, infile, outfile, errfile);
qh_init_qhull_command(qh, argc, argv);
} /* init_A */
/*---------------------------------
qh_init_B(qh, points, numpoints, dim, ismalloc )
initialize globals for points array
points has numpoints dim-dimensional points
points[0] is the first coordinate of the first point
points[1] is the second coordinate of the first point
points[dim] is the first coordinate of the second point
ismalloc=True
Qhull will call qh_free(points) on exit or input transformation
ismalloc=False
Qhull will allocate a new point array if needed for input transformation
qh.qhull_command
is the option string.
It is defined by qh_init_B(), qh_qhull_command(), or qh_initflags
returns:
if qh.PROJECTinput or (qh.DELAUNAY and qh.PROJECTdelaunay)
projects the input to a new point array
if qh.DELAUNAY,
qh.hull_dim is increased by one
if qh.ATinfinity,
qh_projectinput adds point-at-infinity for Delaunay tri.
if qh.SCALEinput
changes the upper and lower bounds of the input, see qh_scaleinput(qh)
if qh.ROTATEinput
rotates the input by a random rotation, see qh_rotateinput()
if qh.DELAUNAY
rotates about the last coordinate
notes:
called after points are defined
qh_errexit() may be used
*/
void qh_init_B(qhT *qh, coordT *points, int numpoints, int dim, boolT ismalloc) {
qh_initqhull_globals(qh, points, numpoints, dim, ismalloc);
if (qh->qhmem.LASTsize == 0)
qh_initqhull_mem(qh);
/* mem_r.c and qset_r.c are initialized */
qh_initqhull_buffers(qh);
qh_initthresholds(qh, qh->qhull_command);
if (qh->PROJECTinput || (qh->DELAUNAY && qh->PROJECTdelaunay))
qh_projectinput(qh);
if (qh->SCALEinput)
qh_scaleinput(qh);
if (qh->ROTATErandom >= 0) {
qh_randommatrix(qh, qh->gm_matrix, qh->hull_dim, qh->gm_row);
if (qh->DELAUNAY) {
int k, lastk= qh->hull_dim-1;
for (k=0; k < lastk; k++) {
qh->gm_row[k][lastk]= 0.0;
qh->gm_row[lastk][k]= 0.0;
}
qh->gm_row[lastk][lastk]= 1.0;
}
qh_gram_schmidt(qh, qh->hull_dim, qh->gm_row);
qh_rotateinput(qh, qh->gm_row);
}
} /* init_B */
/*---------------------------------
qh_init_qhull_command(qh, argc, argv )
build qh.qhull_command from argc/argv
returns:
a space-delimited string of options (just as typed)
notes:
makes option string easy to input and output
argc/argv may be 0/NULL
*/
void qh_init_qhull_command(qhT *qh, int argc, char *argv[]) {
if (!qh_argv_to_command(argc, argv, qh->qhull_command, (int)sizeof(qh->qhull_command))){
/* Assumes qh.ferr is defined. */
qh_fprintf(qh, qh->ferr, 6033, "qhull input error: more than %d characters in command line\n",
(int)sizeof(qh->qhull_command));
qh_exit(qh_ERRinput); /* error reported, can not use qh_errexit */
}
} /* init_qhull_command */
/*---------------------------------
qh_initflags(qh, commandStr )
set flags and initialized constants from commandStr
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 error: qh.NOerrexit not cleared after setjmp() and before qh_initflags(). Exiting with error.");
qh_exit(6245);
}
if (command <= &qh->qhull_command[0] || command > &qh->qhull_command[0] + sizeof(qh->qhull_command)) {
if (command != &qh->qhull_command[0]) {
*qh->qhull_command= '\0';
strncat(qh->qhull_command, command, sizeof(qh->qhull_command)-strlen(qh->qhull_command)-1);
}
while (*s && !isspace(*s)) /* skip program name */
s++;
}
while (*s) {
while (*s && isspace(*s))
s++;
if (*s == '-')
s++;
if (!*s)
break;
prev_s= s;
switch (*s++) {
case 'd':
qh_option(qh, "delaunay", NULL, NULL);
qh->DELAUNAY= True;
break;
case 'f':
qh_option(qh, "facets", NULL, NULL);
qh_appendprint(qh, qh_PRINTfacets);
break;
case 'i':
qh_option(qh, "incidence", NULL, NULL);
qh_appendprint(qh, qh_PRINTincidences);
break;
case 'm':
qh_option(qh, "mathematica", NULL, NULL);
qh_appendprint(qh, qh_PRINTmathematica);
break;
case 'n':
qh_option(qh, "normals", NULL, NULL);
qh_appendprint(qh, qh_PRINTnormals);
break;
case 'o':
qh_option(qh, "offFile", NULL, NULL);
qh_appendprint(qh, qh_PRINToff);
break;
case 'p':
qh_option(qh, "points", NULL, NULL);
qh_appendprint(qh, qh_PRINTpoints);
break;
case 's':
qh_option(qh, "summary", NULL, NULL);
qh->PRINTsummary= True;
break;
case 'v':
qh_option(qh, "voronoi", NULL, NULL);
qh->VORONOI= True;
qh->DELAUNAY= True;
break;
case 'A':
if (!isdigit(*s) && *s != '.' && *s != '-')
qh_fprintf(qh, qh->ferr, 7002, "qhull warning: no maximum cosine angle given for option 'An'. Ignored.\n");
else {
if (*s == '-') {
qh->premerge_cos= -qh_strtod(s, &s);
qh_option(qh, "Angle-premerge-", NULL, &qh->premerge_cos);
qh->PREmerge= True;
}else {
qh->postmerge_cos= qh_strtod(s, &s);
qh_option(qh, "Angle-postmerge", NULL, &qh->postmerge_cos);
qh->POSTmerge= True;
}
qh->MERGING= True;
}
break;
case 'C':
if (!isdigit(*s) && *s != '.' && *s != '-')
qh_fprintf(qh, qh->ferr, 7003, "qhull warning: no centrum radius given for option 'Cn'. Ignored.\n");
else {
if (*s == '-') {
qh->premerge_centrum= -qh_strtod(s, &s);
qh_option(qh, "Centrum-premerge-", NULL, &qh->premerge_centrum);
qh->PREmerge= True;
}else {
qh->postmerge_centrum= qh_strtod(s, &s);
qh_option(qh, "Centrum-postmerge", NULL, &qh->postmerge_centrum);
qh->POSTmerge= True;
}
qh->MERGING= True;
}
break;
case 'E':
if (*s == '-')
qh_fprintf(qh, qh->ferr, 7004, "qhull warning: negative maximum roundoff given for option 'An'. Ignored.\n");
else if (!isdigit(*s))
qh_fprintf(qh, qh->ferr, 7005, "qhull warning: no maximum roundoff given for option 'En'. Ignored.\n");
else {
qh->DISTround= qh_strtod(s, &s);
qh_option(qh, "Distance-roundoff", NULL, &qh->DISTround);
qh->SETroundoff= True;
}
break;
case 'H':
start= s;
qh->HALFspace= True;
qh_strtod(s, &t);
while (t > s) {
if (*t && !isspace(*t)) {
if (*t == ',')
t++;
else
qh_fprintf(qh, qh->ferr, 7006, "qhull warning: origin for Halfspace intersection should be 'Hn,n,n,...'\n");
}
s= t;
qh_strtod(s, &t);
}
if (start < t) {
if (!(qh->feasible_string= (char*)calloc((size_t)(t-start+1), (size_t)1))) {
qh_fprintf(qh, qh->ferr, 6034, "qhull error: insufficient memory for 'Hn,n,n'\n");
qh_errexit(qh, qh_ERRmem, NULL, NULL);
}
strncpy(qh->feasible_string, start, (size_t)(t-start));
qh_option(qh, "Halfspace-about", NULL, NULL);
qh_option(qh, qh->feasible_string, NULL, NULL);
}else
qh_option(qh, "Halfspace", NULL, NULL);
break;
case 'R':
if (!isdigit(*s))
qh_fprintf(qh, qh->ferr, 7007, "qhull warning: missing random perturbation for option 'Rn'. Ignored\n");
else {
qh->RANDOMfactor= qh_strtod(s, &s);
qh_option(qh, "Random_perturb", NULL, &qh->RANDOMfactor);
qh->RANDOMdist= True;
}
break;
case 'V':
if (!isdigit(*s) && *s != '-')
qh_fprintf(qh, qh->ferr, 7008, "qhull warning: missing visible distance for option 'Vn'. Ignored\n");
else {
qh->MINvisible= qh_strtod(s, &s);
qh_option(qh, "Visible", NULL, &qh->MINvisible);
}
break;
case 'U':
if (!isdigit(*s) && *s != '-')
qh_fprintf(qh, qh->ferr, 7009, "qhull warning: missing coplanar distance for option 'Un'. Ignored\n");
else {
qh->MAXcoplanar= qh_strtod(s, &s);
qh_option(qh, "U-coplanar", NULL, &qh->MAXcoplanar);
}
break;
case 'W':
if (*s == '-')
qh_fprintf(qh, qh->ferr, 7010, "qhull warning: negative outside width for option 'Wn'. Ignored.\n");
else if (!isdigit(*s))
qh_fprintf(qh, qh->ferr, 7011, "qhull warning: missing outside width for option 'Wn'. Ignored\n");
else {
qh->MINoutside= qh_strtod(s, &s);
qh_option(qh, "W-outside", NULL, &qh->MINoutside);
qh->APPROXhull= True;
}
break;
/************ sub menus ***************/
case 'F':
while (*s && !isspace(*s)) {
switch (*s++) {
case 'a':
qh_option(qh, "Farea", NULL, NULL);
qh_appendprint(qh, qh_PRINTarea);
qh->GETarea= True;
break;
case 'A':
qh_option(qh, "FArea-total", NULL, NULL);
qh->GETarea= True;
break;
case 'c':
qh_option(qh, "Fcoplanars", NULL, NULL);
qh_appendprint(qh, qh_PRINTcoplanars);
break;
case 'C':
qh_option(qh, "FCentrums", NULL, NULL);
qh_appendprint(qh, qh_PRINTcentrums);
break;
case 'd':
qh_option(qh, "Fd-cdd-in", NULL, NULL);
qh->CDDinput= True;
break;
case 'D':
qh_option(qh, "FD-cdd-out", NULL, NULL);
qh->CDDoutput= True;
break;
case 'F':
qh_option(qh, "FFacets-xridge", NULL, NULL);
qh_appendprint(qh, qh_PRINTfacets_xridge);
break;
case 'i':
qh_option(qh, "Finner", NULL, NULL);
qh_appendprint(qh, qh_PRINTinner);
break;
case 'I':
qh_option(qh, "FIDs", NULL, NULL);
qh_appendprint(qh, qh_PRINTids);
break;
case 'm':
qh_option(qh, "Fmerges", NULL, NULL);
qh_appendprint(qh, qh_PRINTmerges);
break;
case 'M':
qh_option(qh, "FMaple", NULL, NULL);
qh_appendprint(qh, qh_PRINTmaple);
break;
case 'n':
qh_option(qh, "Fneighbors", NULL, NULL);
qh_appendprint(qh, qh_PRINTneighbors);
break;
case 'N':
qh_option(qh, "FNeighbors-vertex", NULL, NULL);
qh_appendprint(qh, qh_PRINTvneighbors);
break;
case 'o':
qh_option(qh, "Fouter", NULL, NULL);
qh_appendprint(qh, qh_PRINTouter);
break;
case 'O':
if (qh->PRINToptions1st) {
qh_option(qh, "FOptions", NULL, NULL);
qh_appendprint(qh, qh_PRINToptions);
}else
qh->PRINToptions1st= True;
break;
case 'p':
qh_option(qh, "Fpoint-intersect", NULL, NULL);
qh_appendprint(qh, qh_PRINTpointintersect);
break;
case 'P':
qh_option(qh, "FPoint-nearest", NULL, NULL);
qh_appendprint(qh, qh_PRINTpointnearest);
break;
case 'Q':
qh_option(qh, "FQhull", NULL, NULL);
qh_appendprint(qh, qh_PRINTqhull);
break;
case 's':
qh_option(qh, "Fsummary", NULL, NULL);
qh_appendprint(qh, qh_PRINTsummary);
break;
case 'S':
qh_option(qh, "FSize", NULL, NULL);
qh_appendprint(qh, qh_PRINTsize);
qh->GETarea= True;
break;
case 't':
qh_option(qh, "Ftriangles", NULL, NULL);
qh_appendprint(qh, qh_PRINTtriangles);
break;
case 'v':
/* option set in qh_initqhull_globals */
qh_appendprint(qh, qh_PRINTvertices);
break;
case 'V':
qh_option(qh, "FVertex-average", NULL, NULL);
qh_appendprint(qh, qh_PRINTaverage);
break;
case 'x':
qh_option(qh, "Fxtremes", NULL, NULL);
qh_appendprint(qh, qh_PRINTextremes);
break;
default:
s--;
qh_fprintf(qh, qh->ferr, 7012, "qhull warning: unknown 'F' output option %c, rest ignored\n", (int)s[0]);
while (*++s && !isspace(*s));
break;
}
}
break;
case 'G':
isgeom= True;
qh_appendprint(qh, qh_PRINTgeom);
while (*s && !isspace(*s)) {
switch (*s++) {
case 'a':
qh_option(qh, "Gall-points", NULL, NULL);
qh->PRINTdots= True;
break;
case 'c':
qh_option(qh, "Gcentrums", NULL, NULL);
qh->PRINTcentrums= True;
break;
case 'h':
qh_option(qh, "Gintersections", NULL, NULL);
qh->DOintersections= True;
break;
case 'i':
qh_option(qh, "Ginner", NULL, NULL);
qh->PRINTinner= True;
break;
case 'n':
qh_option(qh, "Gno-planes", NULL, NULL);
qh->PRINTnoplanes= True;
break;
case 'o':
qh_option(qh, "Gouter", NULL, NULL);
qh->PRINTouter= True;
break;
case 'p':
qh_option(qh, "Gpoints", NULL, NULL);
qh->PRINTcoplanar= True;
break;
case 'r':
qh_option(qh, "Gridges", NULL, NULL);
qh->PRINTridges= True;
break;
case 't':
qh_option(qh, "Gtransparent", NULL, NULL);
qh->PRINTtransparent= True;
break;
case 'v':
qh_option(qh, "Gvertices", NULL, NULL);
qh->PRINTspheres= True;
break;
case 'D':
if (!isdigit(*s))
qh_fprintf(qh, qh->ferr, 6035, "qhull input error: missing dimension for option 'GDn'\n");
else {
if (qh->DROPdim >= 0)
qh_fprintf(qh, qh->ferr, 7013, "qhull warning: can only drop one dimension. Previous 'GD%d' ignored\n",
qh->DROPdim);
qh->DROPdim= qh_strtol(s, &s);
qh_option(qh, "GDrop-dim", &qh->DROPdim, NULL);
}
break;
default:
s--;
qh_fprintf(qh, qh->ferr, 7014, "qhull warning: unknown 'G' print option %c, rest ignored\n", (int)s[0]);
while (*++s && !isspace(*s));
break;
}
}
break;
case 'P':
while (*s && !isspace(*s)) {
switch (*s++) {
case 'd': case 'D': /* see qh_initthresholds() */
key= s[-1];
i= qh_strtol(s, &s);
r= 0;
if (*s == ':') {
s++;
r= qh_strtod(s, &s);
}
if (key == 'd')
qh_option(qh, "Pdrop-facets-dim-less", &i, &r);
else
qh_option(qh, "PDrop-facets-dim-more", &i, &r);
break;
case 'g':
qh_option(qh, "Pgood-facets", NULL, NULL);
qh->PRINTgood= True;
break;
case 'G':
qh_option(qh, "PGood-facet-neighbors", NULL, NULL);
qh->PRINTneighbors= True;
break;
case 'o':
qh_option(qh, "Poutput-forced", NULL, NULL);
qh->FORCEoutput= True;
break;
case 'p':
qh_option(qh, "Pprecision-ignore", NULL, NULL);
qh->PRINTprecision= False;
break;
case 'A':
if (!isdigit(*s))
qh_fprintf(qh, qh->ferr, 6036, "qhull input error: missing facet count for keep area option 'PAn'\n");
else {
qh->KEEParea= qh_strtol(s, &s);
qh_option(qh, "PArea-keep", &qh->KEEParea, NULL);
qh->GETarea= True;
}
break;
case 'F':
if (!isdigit(*s))
qh_fprintf(qh, qh->ferr, 6037, "qhull input error: missing facet area for option 'PFn'\n");
else {
qh->KEEPminArea= qh_strtod(s, &s);
qh_option(qh, "PFacet-area-keep", NULL, &qh->KEEPminArea);
qh->GETarea= True;
}
break;
case 'M':
if (!isdigit(*s))
qh_fprintf(qh, qh->ferr, 6038, "qhull input error: missing merge count for option 'PMn'\n");
else {
qh->KEEPmerge= qh_strtol(s, &s);
qh_option(qh, "PMerge-keep", &qh->KEEPmerge, NULL);
}
break;
default:
s--;
qh_fprintf(qh, qh->ferr, 7015, "qhull warning: unknown 'P' print option %c, rest ignored\n", (int)s[0]);
while (*++s && !isspace(*s));
break;
}
}
break;
case 'Q':
lastproject= -1;
while (*s && !isspace(*s)) {
switch (*s++) {
case 'b': case 'B': /* handled by qh_initthresholds */
key= s[-1];
if (key == 'b' && *s == 'B') {
s++;
r= qh_DEFAULTbox;
qh->SCALEinput= True;
qh_option(qh, "QbBound-unit-box", NULL, &r);
break;
}
if (key == 'b' && *s == 'b') {
s++;
qh->SCALElast= True;
qh_option(qh, "Qbbound-last", NULL, NULL);
break;
}
k= qh_strtol(s, &s);
r= 0.0;
wasproject= False;
if (*s == ':') {
s++;
if ((r= qh_strtod(s, &s)) == 0.0) {
t= s; /* need true dimension for memory allocation */
while (*t && !isspace(*t)) {
if (toupper(*t++) == 'B'
&& k == qh_strtol(t, &t)
&& *t++ == ':'
&& qh_strtod(t, &t) == 0.0) {
qh->PROJECTinput++;
trace2((qh, qh->ferr, 2004, "qh_initflags: project dimension %d\n", k));
qh_option(qh, "Qb-project-dim", &k, NULL);
wasproject= True;
lastproject= k;
break;
}
}
}
}
if (!wasproject) {
if (lastproject == k && r == 0.0)
lastproject= -1; /* doesn't catch all possible sequences */
else if (key == 'b') {
qh->SCALEinput= True;
if (r == 0.0)
r= -qh_DEFAULTbox;
qh_option(qh, "Qbound-dim-low", &k, &r);
}else {
qh->SCALEinput= True;
if (r == 0.0)
r= qh_DEFAULTbox;
qh_option(qh, "QBound-dim-high", &k, &r);
}
}
break;
case 'c':
qh_option(qh, "Qcoplanar-keep", NULL, NULL);
qh->KEEPcoplanar= True;
break;
case 'f':
qh_option(qh, "Qfurthest-outside", NULL, NULL);
qh->BESToutside= True;
break;
case 'g':
qh_option(qh, "Qgood-facets-only", NULL, NULL);
qh->ONLYgood= True;
break;
case 'i':
qh_option(qh, "Qinterior-keep", NULL, NULL);
qh->KEEPinside= True;
break;
case 'm':
qh_option(qh, "Qmax-outside-only", NULL, NULL);
qh->ONLYmax= True;
break;
case 'r':
qh_option(qh, "Qrandom-outside", NULL, NULL);
qh->RANDOMoutside= True;
break;
case 's':
qh_option(qh, "Qsearch-initial-simplex", NULL, NULL);
qh->ALLpoints= True;
break;
case 't':
qh_option(qh, "Qtriangulate", NULL, NULL);
qh->TRIangulate= True;
break;
case 'T':
qh_option(qh, "QTestPoints", NULL, NULL);
if (!isdigit(*s))
qh_fprintf(qh, qh->ferr, 6039, "qhull input error: missing number of test points for option 'QTn'\n");
else {
qh->TESTpoints= qh_strtol(s, &s);
qh_option(qh, "QTestPoints", &qh->TESTpoints, NULL);
}
break;
case 'u':
qh_option(qh, "QupperDelaunay", NULL, NULL);
qh->UPPERdelaunay= True;
break;
case 'v':
qh_option(qh, "Qvertex-neighbors-convex", NULL, NULL);
qh->TESTvneighbors= True;
break;
case 'x':
qh_option(qh, "Qxact-merge", NULL, NULL);
qh->MERGEexact= True;
break;
case 'z':
qh_option(qh, "Qz-infinity-point", NULL, NULL);
qh->ATinfinity= True;
break;
case '0':
qh_option(qh, "Q0-no-premerge", NULL, NULL);
qh->NOpremerge= True;
break;
case '1':
if (!isdigit(*s)) {
qh_option(qh, "Q1-no-angle-sort", NULL, NULL);
qh->ANGLEmerge= False;
break;
}
switch (*s++) {
case '0':
qh_option(qh, "Q10-no-narrow", NULL, NULL);
qh->NOnarrow= True;
break;
case '1':
qh_option(qh, "Q11-trinormals Qtriangulate", NULL, NULL);
qh->TRInormals= True;
qh->TRIangulate= True;
break;
default:
s--;
qh_fprintf(qh, qh->ferr, 7016, "qhull warning: unknown 'Q' qhull option 1%c, rest ignored\n", (int)s[0]);
while (*++s && !isspace(*s));
break;
}
break;
case '2':
qh_option(qh, "Q2-no-merge-independent", NULL, NULL);
qh->MERGEindependent= False;
goto LABELcheckdigit;
break; /* no warnings */
case '3':
qh_option(qh, "Q3-no-merge-vertices", NULL, NULL);
qh->MERGEvertices= False;
LABELcheckdigit:
if (isdigit(*s))
qh_fprintf(qh, qh->ferr, 7017, "qhull warning: can not follow '1', '2', or '3' with a digit. '%c' skipped.\n",
*s++);
break;
case '4':
qh_option(qh, "Q4-avoid-old-into-new", NULL, NULL);
qh->AVOIDold= True;
break;
case '5':
qh_option(qh, "Q5-no-check-outer", NULL, NULL);
qh->SKIPcheckmax= True;
break;
case '6':
qh_option(qh, "Q6-no-concave-merge", NULL, NULL);
qh->SKIPconvex= True;
break;
case '7':
qh_option(qh, "Q7-no-breadth-first", NULL, NULL);
qh->VIRTUALmemory= True;
break;
case '8':
qh_option(qh, "Q8-no-near-inside", NULL, NULL);
qh->NOnearinside= True;
break;
case '9':
qh_option(qh, "Q9-pick-furthest", NULL, NULL);
qh->PICKfurthest= True;
break;
case 'G':
i= qh_strtol(s, &t);
if (qh->GOODpoint)
qh_fprintf(qh, qh->ferr, 7018, "qhull warning: good point already defined for option 'QGn'. Ignored\n");
else if (s == t)
qh_fprintf(qh, qh->ferr, 7019, "qhull warning: missing good point id for option 'QGn'. Ignored\n");
else if (i < 0 || *s == '-') {
qh->GOODpoint= i-1;
qh_option(qh, "QGood-if-dont-see-point", &i, NULL);
}else {
qh->GOODpoint= i+1;
qh_option(qh, "QGood-if-see-point", &i, NULL);
}
s= t;
break;
case 'J':
if (!isdigit(*s) && *s != '-')
qh->JOGGLEmax= 0.0;
else {
qh->JOGGLEmax= (realT) qh_strtod(s, &s);
qh_option(qh, "QJoggle", NULL, &qh->JOGGLEmax);
}
break;
case 'R':
if (!isdigit(*s) && *s != '-')
qh_fprintf(qh, qh->ferr, 7020, "qhull warning: missing random seed for option 'QRn'. Ignored\n");
else {
qh->ROTATErandom= i= qh_strtol(s, &s);
if (i > 0)
qh_option(qh, "QRotate-id", &i, NULL );
else if (i < -1)
qh_option(qh, "QRandom-seed", &i, NULL );
}
break;
case 'V':
i= qh_strtol(s, &t);
if (qh->GOODvertex)
qh_fprintf(qh, qh->ferr, 7021, "qhull warning: good vertex already defined for option 'QVn'. Ignored\n");
else if (s == t)
qh_fprintf(qh, qh->ferr, 7022, "qhull warning: no good point id given for option 'QVn'. Ignored\n");
else if (i < 0) {
qh->GOODvertex= i - 1;
qh_option(qh, "QV-good-facets-not-point", &i, NULL);
}else {
qh_option(qh, "QV-good-facets-point", &i, NULL);
qh->GOODvertex= i + 1;
}
s= t;
break;
default:
s--;
qh_fprintf(qh, qh->ferr, 7023, "qhull warning: unknown 'Q' qhull option %c, rest ignored\n", (int)s[0]);
while (*++s && !isspace(*s));
break;
}
}
break;
case 'T':
while (*s && !isspace(*s)) {
if (isdigit(*s) || *s == '-')
qh->IStracing= qh_strtol(s, &s);
else switch (*s++) {
case 'a':
qh_option(qh, "Tannotate-output", NULL, NULL);
qh->ANNOTATEoutput= True;
break;
case 'c':
qh_option(qh, "Tcheck-frequently", NULL, NULL);
qh->CHECKfrequently= True;
break;
case 's':
qh_option(qh, "Tstatistics", NULL, NULL);
qh->PRINTstatistics= True;
break;
case 'v':
qh_option(qh, "Tverify", NULL, NULL);
qh->VERIFYoutput= True;
break;
case 'z':
if (qh->ferr == qh_FILEstderr) {
/* The C++ interface captures the output in qh_fprint_qhull() */
qh_option(qh, "Tz-stdout", NULL, NULL);
qh->USEstdout= True;
}else if (!qh->fout)
qh_fprintf(qh, qh->ferr, 7024, "qhull warning: output file undefined(stdout). Option 'Tz' ignored.\n");
else {
qh_option(qh, "Tz-stdout", NULL, NULL);
qh->USEstdout= True;
qh->ferr= qh->fout;
qh->qhmem.ferr= qh->fout;
}
break;
case 'C':
if (!isdigit(*s))
qh_fprintf(qh, qh->ferr, 7025, "qhull warning: missing point id for cone for trace option 'TCn'. Ignored\n");
else {
i= qh_strtol(s, &s);
qh_option(qh, "TCone-stop", &i, NULL);
qh->STOPcone= i + 1;
}
break;
case 'F':
if (!isdigit(*s))
qh_fprintf(qh, qh->ferr, 7026, "qhull warning: missing frequency count for trace option 'TFn'. Ignored\n");
else {
qh->REPORTfreq= qh_strtol(s, &s);
qh_option(qh, "TFacet-log", &qh->REPORTfreq, NULL);
qh->REPORTfreq2= qh->REPORTfreq/2; /* for tracemerging() */
}
break;
case 'I':
if (!isspace(*s))
qh_fprintf(qh, qh->ferr, 7027, "qhull warning: missing space between 'TI' and filename, %s\n", s);
while (isspace(*s))
s++;
t= qh_skipfilename(qh, s);
{
char filename[qh_FILENAMElen];
qh_copyfilename(qh, filename, (int)sizeof(filename), s, (int)(t-s)); /* WARN64 */
s= t;
if (!freopen(filename, "r", stdin)) {
qh_fprintf(qh, qh->ferr, 6041, "qhull error: could not open file \"%s\".", filename);
qh_errexit(qh, qh_ERRinput, NULL, NULL);
}else {
qh_option(qh, "TInput-file", NULL, NULL);
qh_option(qh, filename, NULL, NULL);
}
}
break;
case 'O':
if (!isspace(*s))
qh_fprintf(qh, qh->ferr, 7028, "qhull warning: missing space between 'TO' and filename, %s\n", s);
while (isspace(*s))
s++;
t= qh_skipfilename(qh, s);
{
char filename[qh_FILENAMElen];
qh_copyfilename(qh, filename, (int)sizeof(filename), s, (int)(t-s)); /* WARN64 */
s= t;
if (!freopen(filename, "w", stdout)) {
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");
else {
qh->TRACEpoint= qh_strtol(s, &s);
qh_option(qh, "Trace-point", &qh->TRACEpoint, NULL);
}
break;
case 'M':
if (!isdigit(*s))
qh_fprintf(qh, qh->ferr, 7030, "qhull warning: missing merge id for trace option 'TMn'. Ignored\n");
else {
qh->TRACEmerge= qh_strtol(s, &s);
qh_option(qh, "Trace-merge", &qh->TRACEmerge, NULL);
}
break;
case 'R':
if (!isdigit(*s))
qh_fprintf(qh, qh->ferr, 7031, "qhull warning: missing rerun count for trace option 'TRn'. Ignored\n");
else {
qh->RERUN= qh_strtol(s, &s);
qh_option(qh, "TRerun", &qh->RERUN, NULL);
}
break;
case 'V':
i= qh_strtol(s, &t);
if (s == t)
qh_fprintf(qh, qh->ferr, 7032, "qhull warning: missing furthest point id for trace option 'TVn'. Ignored\n");
else if (i < 0) {
qh->STOPpoint= i - 1;
qh_option(qh, "TV-stop-before-point", &i, NULL);
}else {
qh->STOPpoint= i + 1;
qh_option(qh, "TV-stop-after-point", &i, NULL);
}
s= t;
break;
case 'W':
if (!isdigit(*s))
qh_fprintf(qh, qh->ferr, 7033, "qhull warning: missing max width for trace option 'TWn'. Ignored\n");
else {
qh->TRACEdist= (realT) qh_strtod(s, &s);
qh_option(qh, "TWide-trace", NULL, &qh->TRACEdist);
}
break;
default:
s--;
qh_fprintf(qh, qh->ferr, 7034, "qhull warning: unknown 'T' trace option %c, rest ignored\n", (int)s[0]);
while (*++s && !isspace(*s));
break;
}
}
break;
default:
qh_fprintf(qh, qh->ferr, 7035, "qhull warning: unknown flag %c(%x)\n", (int)s[-1],
(int)s[-1]);
break;
}
if (s-1 == prev_s && *s && !isspace(*s)) {
qh_fprintf(qh, qh->ferr, 7036, "qhull warning: missing space after flag %c(%x); reserved for menu. Skipped.\n",
(int)*prev_s, (int)*prev_s);
while (*s && !isspace(*s))
s++;
}
}
if (qh->STOPcone && qh->JOGGLEmax < REALmax/2)
qh_fprintf(qh, qh->ferr, 7078, "qhull warning: 'TCn' (stopCone) ignored when used with 'QJn' (joggle)\n");
if (isgeom && !qh->FORCEoutput && qh->PRINTout[1])
qh_fprintf(qh, qh->ferr, 7037, "qhull warning: additional output formats are not compatible with Geomview\n");
/* set derived values in qh_initqhull_globals */
} /* initflags */
/*---------------------------------
qh_initqhull_buffers(qh)
initialize global memory buffers
notes:
must match qh_freebuffers()
*/
void qh_initqhull_buffers(qhT *qh) {
int k;
qh->TEMPsize= (qh->qhmem.LASTsize - sizeof(setT))/SETelemsize;
if (qh->TEMPsize <= 0 || qh->TEMPsize > qh->qhmem.LASTsize)
qh->TEMPsize= 8; /* e.g., if qh_NOmem */
qh->other_points= qh_setnew(qh, qh->TEMPsize);
qh->del_vertices= qh_setnew(qh, qh->TEMPsize);
qh->coplanarfacetset= qh_setnew(qh, qh->TEMPsize);
qh->NEARzero= (realT *)qh_memalloc(qh, qh->hull_dim * sizeof(realT));
qh->lower_threshold= (realT *)qh_memalloc(qh, (qh->input_dim+1) * sizeof(realT));
qh->upper_threshold= (realT *)qh_memalloc(qh, (qh->input_dim+1) * sizeof(realT));
qh->lower_bound= (realT *)qh_memalloc(qh, (qh->input_dim+1) * sizeof(realT));
qh->upper_bound= (realT *)qh_memalloc(qh, (qh->input_dim+1) * sizeof(realT));
- for (k=qh->input_dim+1; k--; ) { /* duplicated in qh_initqhull_buffers and qh_clear_ouputflags */
+ for (k=qh->input_dim+1; k--; ) { /* duplicated in qh_initqhull_buffers and qh_clear_outputflags */
qh->lower_threshold[k]= -REALmax;
qh->upper_threshold[k]= REALmax;
qh->lower_bound[k]= -REALmax;
qh->upper_bound[k]= REALmax;
}
qh->gm_matrix= (coordT *)qh_memalloc(qh, (qh->hull_dim+1) * qh->hull_dim * sizeof(coordT));
qh->gm_row= (coordT **)qh_memalloc(qh, (qh->hull_dim+1) * sizeof(coordT *));
} /* initqhull_buffers */
/*---------------------------------
qh_initqhull_globals(qh, points, numpoints, dim, ismalloc )
initialize globals
if ismalloc
points were malloc'd and qhull should free at end
returns:
sets qh.first_point, num_points, input_dim, hull_dim and others
seeds random number generator (seed=1 if tracing)
modifies qh.hull_dim if ((qh.DELAUNAY and qh.PROJECTdelaunay) or qh.PROJECTinput)
adjust user flags as needed
also checks DIM3 dependencies and constants
notes:
do not use qh_point() since an input transformation may move them elsewhere
see:
qh_initqhull_start() sets default values for non-zero globals
design:
initialize points array from input arguments
test for qh.ZEROcentrum
(i.e., use opposite vertex instead of cetrum for convexity testing)
initialize qh.CENTERtype, qh.normal_size,
qh.center_size, qh.TRACEpoint/level,
initialize and test random numbers
qh_initqhull_outputflags() -- adjust and test output flags
*/
void qh_initqhull_globals(qhT *qh, coordT *points, int numpoints, int dim, boolT ismalloc) {
int seed, pointsneeded, extra= 0, i, randi, k;
realT randr;
realT factorial;
time_t timedata;
trace0((qh, qh->ferr, 13, "qh_initqhull_globals: for %s | %s\n", qh->rbox_command,
qh->qhull_command));
qh->POINTSmalloc= ismalloc;
qh->first_point= points;
qh->num_points= numpoints;
qh->hull_dim= qh->input_dim= dim;
if (!qh->NOpremerge && !qh->MERGEexact && !qh->PREmerge && qh->JOGGLEmax > REALmax/2) {
qh->MERGING= True;
if (qh->hull_dim <= 4) {
qh->PREmerge= True;
qh_option(qh, "_pre-merge", NULL, NULL);
}else {
qh->MERGEexact= True;
qh_option(qh, "Qxact_merge", NULL, NULL);
}
}else if (qh->MERGEexact)
qh->MERGING= True;
if (!qh->NOpremerge && qh->JOGGLEmax > REALmax/2) {
#ifdef qh_NOmerge
qh->JOGGLEmax= 0.0;
#endif
}
if (qh->TRIangulate && qh->JOGGLEmax < REALmax/2 && qh->PRINTprecision)
qh_fprintf(qh, qh->ferr, 7038, "qhull warning: joggle('QJ') always produces simplicial output. Triangulated output('Qt') does nothing.\n");
if (qh->JOGGLEmax < REALmax/2 && qh->DELAUNAY && !qh->SCALEinput && !qh->SCALElast) {
qh->SCALElast= True;
qh_option(qh, "Qbbound-last-qj", NULL, NULL);
}
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");
qh->DOcheckmax= (!qh->SKIPcheckmax && qh->MERGING );
qh->KEEPnearinside= (qh->DOcheckmax && !(qh->KEEPinside && qh->KEEPcoplanar)
&& !qh->NOnearinside);
if (qh->MERGING)
qh->CENTERtype= qh_AScentrum;
else if (qh->VORONOI)
qh->CENTERtype= qh_ASvoronoi;
if (qh->TESTvneighbors && !qh->MERGING) {
qh_fprintf(qh, qh->ferr, 6049, "qhull input error: test vertex neighbors('Qv') needs a merge option\n");
qh_errexit(qh, qh_ERRinput, NULL ,NULL);
}
if (qh->PROJECTinput || (qh->DELAUNAY && qh->PROJECTdelaunay)) {
qh->hull_dim -= qh->PROJECTinput;
if (qh->DELAUNAY) {
qh->hull_dim++;
if (qh->ATinfinity)
extra= 1;
}
}
if (qh->hull_dim <= 1) {
qh_fprintf(qh, qh->ferr, 6050, "qhull error: dimension %d must be > 1\n", qh->hull_dim);
qh_errexit(qh, qh_ERRinput, NULL, NULL);
}
for (k=2, factorial=1.0; k < qh->hull_dim; k++)
factorial *= k;
qh->AREAfactor= 1.0 / factorial;
trace2((qh, qh->ferr, 2005, "qh_initqhull_globals: initialize globals. dim %d numpoints %d malloc? %d projected %d to hull_dim %d\n",
dim, numpoints, ismalloc, qh->PROJECTinput, qh->hull_dim));
qh->normal_size= qh->hull_dim * sizeof(coordT);
qh->center_size= qh->normal_size - sizeof(coordT);
pointsneeded= qh->hull_dim+1;
if (qh->hull_dim > qh_DIMmergeVertex) {
qh->MERGEvertices= False;
qh_option(qh, "Q3-no-merge-vertices-dim-high", NULL, NULL);
}
if (qh->GOODpoint)
pointsneeded++;
#ifdef qh_NOtrace
if (qh->IStracing) {
qh_fprintf(qh, qh->ferr, 6051, "qhull input error: tracing is not installed(qh_NOtrace in user.h)");
qh_errexit(qh, qh_ERRqhull, NULL, NULL);
}
#endif
if (qh->RERUN > 1) {
qh->TRACElastrun= qh->IStracing; /* qh_build_withrestart duplicates next conditional */
if (qh->IStracing != -1)
qh->IStracing= 0;
}else if (qh->TRACEpoint != qh_IDunknown || qh->TRACEdist < REALmax/2 || qh->TRACEmerge) {
qh->TRACElevel= (qh->IStracing? qh->IStracing : 3);
qh->IStracing= 0;
}
if (qh->ROTATErandom == 0 || qh->ROTATErandom == -1) {
seed= (int)time(&timedata);
if (qh->ROTATErandom == -1) {
seed= -seed;
qh_option(qh, "QRandom-seed", &seed, NULL );
}else
qh_option(qh, "QRotate-random", &seed, NULL);
qh->ROTATErandom= seed;
}
seed= qh->ROTATErandom;
if (seed == INT_MIN) /* default value */
seed= 1;
else if (seed < 0)
seed= -seed;
qh_RANDOMseed_(qh, seed);
randr= 0.0;
for (i=1000; i--; ) {
randi= qh_RANDOMint;
randr += randi;
if (randi > qh_RANDOMmax) {
qh_fprintf(qh, qh->ferr, 8036, "\
qhull configuration error (qh_RANDOMmax in user.h):\n\
random integer %d > qh_RANDOMmax(qh, %.8g)\n",
randi, qh_RANDOMmax);
qh_errexit(qh, qh_ERRinput, NULL, NULL);
}
}
qh_RANDOMseed_(qh, seed);
randr = randr/1000;
if (randr < qh_RANDOMmax * 0.1
|| randr > qh_RANDOMmax * 0.9)
qh_fprintf(qh, qh->ferr, 8037, "\
qhull configuration warning (qh_RANDOMmax in user.h):\n\
average of 1000 random integers (%.2g) is much different than expected (%.2g).\n\
Is qh_RANDOMmax (%.2g) wrong?\n",
randr, qh_RANDOMmax * 0.5, qh_RANDOMmax);
qh->RANDOMa= 2.0 * qh->RANDOMfactor/qh_RANDOMmax;
qh->RANDOMb= 1.0 - qh->RANDOMfactor;
if (qh_HASHfactor < 1.1) {
qh_fprintf(qh, qh->ferr, 6052, "qhull internal error (qh_initqhull_globals): qh_HASHfactor %d must be at least 1.1. Qhull uses linear hash probing\n",
qh_HASHfactor);
qh_errexit(qh, qh_ERRqhull, NULL, NULL);
}
if (numpoints+extra < pointsneeded) {
qh_fprintf(qh, qh->ferr, 6214, "qhull input error: not enough points(%d) to construct initial simplex (need %d)\n",
numpoints, pointsneeded);
qh_errexit(qh, qh_ERRinput, NULL, NULL);
}
qh_initqhull_outputflags(qh);
} /* initqhull_globals */
/*---------------------------------
qh_initqhull_mem(qh, )
initialize mem_r.c for qhull
qh.hull_dim and qh.normal_size determine some of the allocation sizes
if qh.MERGING,
includes ridgeT
calls qh_user_memsizes(qh) to add up to 10 additional sizes for quick allocation
(see numsizes below)
returns:
mem_r.c already for qh_memalloc/qh_memfree (errors if called beforehand)
notes:
qh_produceoutput() prints memsizes
*/
void qh_initqhull_mem(qhT *qh) {
int numsizes;
int i;
numsizes= 8+10;
qh_meminitbuffers(qh, qh->IStracing, qh_MEMalign, numsizes,
qh_MEMbufsize, qh_MEMinitbuf);
qh_memsize(qh, (int)sizeof(vertexT));
if (qh->MERGING) {
qh_memsize(qh, (int)sizeof(ridgeT));
qh_memsize(qh, (int)sizeof(mergeT));
}
qh_memsize(qh, (int)sizeof(facetT));
i= sizeof(setT) + (qh->hull_dim - 1) * SETelemsize; /* ridge.vertices */
qh_memsize(qh, i);
qh_memsize(qh, qh->normal_size); /* normal */
i += SETelemsize; /* facet.vertices, .ridges, .neighbors */
qh_memsize(qh, i);
qh_user_memsizes(qh);
qh_memsetup(qh);
} /* initqhull_mem */
/*---------------------------------
qh_initqhull_outputflags
initialize flags concerned with output
returns:
adjust user flags as needed
see:
qh_clear_outputflags() resets the flags
design:
test for qh.PRINTgood (i.e., only print 'good' facets)
check for conflicting print output options
*/
void qh_initqhull_outputflags(qhT *qh) {
boolT printgeom= False, printmath= False, printcoplanar= False;
int i;
trace3((qh, qh->ferr, 3024, "qh_initqhull_outputflags: %s\n", qh->qhull_command));
if (!(qh->PRINTgood || qh->PRINTneighbors)) {
if (qh->KEEParea || qh->KEEPminArea < REALmax/2 || qh->KEEPmerge || qh->DELAUNAY
|| (!qh->ONLYgood && (qh->GOODvertex || qh->GOODpoint))) {
qh->PRINTgood= True;
qh_option(qh, "Pgood", NULL, NULL);
}
}
if (qh->PRINTtransparent) {
if (qh->hull_dim != 4 || !qh->DELAUNAY || qh->VORONOI || qh->DROPdim >= 0) {
qh_fprintf(qh, qh->ferr, 6215, "qhull input error: transparent Delaunay('Gt') needs 3-d Delaunay('d') w/o 'GDn'\n");
qh_errexit(qh, qh_ERRinput, NULL, NULL);
}
qh->DROPdim = 3;
qh->PRINTridges = True;
}
for (i=qh_PRINTEND; i--; ) {
if (qh->PRINTout[i] == qh_PRINTgeom)
printgeom= True;
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
+ qh->PRINTdots + qh->PRINTspheres + qh->DOintersections + qh->PRINTridges)) {
qh_fprintf(qh, qh->ferr, 6058, "qhull input error: no output specified for Geomview\n");
qh_errexit(qh, qh_ERRinput, NULL, NULL);
}
if (qh->VORONOI && (qh->hull_dim > 3 || qh->DROPdim >= 0)) {
qh_fprintf(qh, qh->ferr, 6059, "qhull input error: Geomview output for Voronoi diagrams only for 2-d\n");
qh_errexit(qh, qh_ERRinput, NULL, NULL);
}
/* can not warn about furthest-site Geomview output: no lower_threshold */
if (qh->hull_dim == 4 && qh->DROPdim == -1 &&
(qh->PRINTcoplanar || qh->PRINTspheres || qh->PRINTcentrums)) {
qh_fprintf(qh, qh->ferr, 7042, "qhull input warning: coplanars, vertices, and centrums output not\n\
available for 4-d output(ignored). Could use 'GDn' instead.\n");
qh->PRINTcoplanar= qh->PRINTspheres= qh->PRINTcentrums= False;
}
}
if (!qh->KEEPcoplanar && !qh->KEEPinside && !qh->ONLYgood) {
if ((qh->PRINTcoplanar && qh->PRINTspheres) || printcoplanar) {
if (qh->QHULLfinished) {
qh_fprintf(qh, qh->ferr, 7072, "qhull output warning: ignoring coplanar points, option 'Qc' was not set for the first run of qhull.\n");
}else {
qh->KEEPcoplanar = True;
qh_option(qh, "Qcoplanar", NULL, NULL);
}
}
}
qh->PRINTdim= qh->hull_dim;
if (qh->DROPdim >=0) { /* after Geomview checks */
if (qh->DROPdim < qh->hull_dim) {
qh->PRINTdim--;
if (!printgeom || qh->hull_dim < 3)
qh_fprintf(qh, qh->ferr, 7043, "qhull input warning: drop dimension 'GD%d' is only available for 3-d/4-d Geomview\n", qh->DROPdim);
}else
qh->DROPdim= -1;
}else if (qh->VORONOI) {
qh->DROPdim= qh->hull_dim-1;
qh->PRINTdim= qh->hull_dim-1;
}
} /* qh_initqhull_outputflags */
/*---------------------------------
qh_initqhull_start(qh, infile, outfile, errfile )
allocate memory if needed and call qh_initqhull_start2()
*/
void qh_initqhull_start(qhT *qh, FILE *infile, FILE *outfile, FILE *errfile) {
qh_initstatistics(qh);
qh_initqhull_start2(qh, infile, outfile, errfile);
} /* initqhull_start */
/*---------------------------------
qh_initqhull_start2(qh, infile, outfile, errfile )
start initialization of qhull
initialize statistics, stdio, default values for global variables
assumes qh is allocated
notes:
report errors elsewhere, error handling and g_qhull_output [Qhull.cpp, QhullQh()] not in initialized
see:
qh_maxmin() determines the precision constants
qh_freeqhull()
*/
void qh_initqhull_start2(qhT *qh, FILE *infile, FILE *outfile, FILE *errfile) {
time_t timedata;
int seed;
qh_CPUclock; /* start the clock(for qh_clock). One-shot. */
/* memset is the same in qh_freeqhull() and qh_initqhull_start2() */
memset((char *)qh, 0, sizeof(qhT)-sizeof(qhmemT)-sizeof(qhstatT)); /* every field is 0, FALSE, NULL */
qh->NOerrexit= True;
qh->ANGLEmerge= True;
qh->DROPdim= -1;
qh->ferr= errfile;
qh->fin= infile;
qh->fout= outfile;
qh->furthest_id= qh_IDunknown;
qh->JOGGLEmax= REALmax;
qh->KEEPminArea = REALmax;
qh->last_low= REALmax;
qh->last_high= REALmax;
qh->last_newhigh= REALmax;
qh->last_random= 1;
qh->max_outside= 0.0;
qh->max_vertex= 0.0;
qh->MAXabs_coord= 0.0;
qh->MAXsumcoord= 0.0;
qh->MAXwidth= -REALmax;
qh->MERGEindependent= True;
qh->MINdenom_1= fmax_(1.0/REALmax, REALmin); /* used by qh_scalepoints */
qh->MINoutside= 0.0;
qh->MINvisible= REALmax;
qh->MAXcoplanar= REALmax;
qh->outside_err= REALmax;
qh->premerge_centrum= 0.0;
qh->premerge_cos= REALmax;
qh->PRINTprecision= True;
qh->PRINTradius= 0.0;
qh->postmerge_cos= REALmax;
qh->postmerge_centrum= 0.0;
qh->ROTATErandom= INT_MIN;
qh->MERGEvertices= True;
qh->totarea= 0.0;
qh->totvol= 0.0;
qh->TRACEdist= REALmax;
qh->TRACEpoint= qh_IDunknown; /* recompile or use 'TPn' */
qh->tracefacet_id= UINT_MAX; /* recompile to trace a facet */
qh->tracevertex_id= UINT_MAX; /* recompile to trace a vertex */
seed= (int)time(&timedata);
qh_RANDOMseed_(qh, seed);
qh->run_id= qh_RANDOMint;
if(!qh->run_id)
qh->run_id++; /* guarantee non-zero */
qh_option(qh, "run-id", &qh->run_id, NULL);
strcat(qh->qhull, "qhull");
} /* initqhull_start2 */
/*---------------------------------
qh_initthresholds(qh, commandString )
set thresholds for printing and scaling from commandString
returns:
sets qh.GOODthreshold or qh.SPLITthreshold if 'Pd0D1' used
see:
qh_initflags(), 'Qbk' 'QBk' 'Pdk' and 'PDk'
qh_inthresholds()
design:
for each 'Pdn' or 'PDn' option
check syntax
set qh.lower_threshold or qh.upper_threshold
set qh.GOODthreshold if an unbounded threshold is used
set qh.SPLITthreshold if a bounded threshold is used
*/
void qh_initthresholds(qhT *qh, char *command) {
realT value;
int idx, maxdim, k;
char *s= command; /* non-const due to strtol */
char key;
maxdim= qh->input_dim;
if (qh->DELAUNAY && (qh->PROJECTdelaunay || qh->PROJECTinput))
maxdim++;
while (*s) {
if (*s == '-')
s++;
if (*s == 'P') {
s++;
while (*s && !isspace(key= *s++)) {
if (key == 'd' || key == 'D') {
if (!isdigit(*s)) {
qh_fprintf(qh, qh->ferr, 7044, "qhull warning: no dimension given for Print option '%c' at: %s. Ignored\n",
key, s-1);
continue;
}
idx= qh_strtol(s, &s);
if (idx >= qh->hull_dim) {
qh_fprintf(qh, qh->ferr, 7045, "qhull warning: dimension %d for Print option '%c' is >= %d. Ignored\n",
idx, key, qh->hull_dim);
continue;
}
if (*s == ':') {
s++;
value= qh_strtod(s, &s);
if (fabs((double)value) > 1.0) {
qh_fprintf(qh, qh->ferr, 7046, "qhull warning: value %2.4g for Print option %c is > +1 or < -1. Ignored\n",
value, key);
continue;
}
}else
value= 0.0;
if (key == 'd')
qh->lower_threshold[idx]= value;
else
qh->upper_threshold[idx]= value;
}
}
}else if (*s == 'Q') {
s++;
while (*s && !isspace(key= *s++)) {
if (key == 'b' && *s == 'B') {
s++;
for (k=maxdim; k--; ) {
qh->lower_bound[k]= -qh_DEFAULTbox;
qh->upper_bound[k]= qh_DEFAULTbox;
}
}else if (key == 'b' && *s == 'b')
s++;
else if (key == 'b' || key == 'B') {
if (!isdigit(*s)) {
qh_fprintf(qh, qh->ferr, 7047, "qhull warning: no dimension given for Qhull option %c. Ignored\n",
key);
continue;
}
idx= qh_strtol(s, &s);
if (idx >= maxdim) {
qh_fprintf(qh, qh->ferr, 7048, "qhull warning: dimension %d for Qhull option %c is >= %d. Ignored\n",
idx, key, maxdim);
continue;
}
if (*s == ':') {
s++;
value= qh_strtod(s, &s);
}else if (key == 'b')
value= -qh_DEFAULTbox;
else
value= qh_DEFAULTbox;
if (key == 'b')
qh->lower_bound[idx]= value;
else
qh->upper_bound[idx]= value;
}
}
}else {
while (*s && !isspace(*s))
s++;
}
while (isspace(*s))
s++;
}
for (k=qh->hull_dim; k--; ) {
if (qh->lower_threshold[k] > -REALmax/2) {
qh->GOODthreshold= True;
if (qh->upper_threshold[k] < REALmax/2) {
qh->SPLITthresholds= True;
qh->GOODthreshold= False;
break;
}
}else if (qh->upper_threshold[k] < REALmax/2)
qh->GOODthreshold= True;
}
} /* initthresholds */
/*---------------------------------
qh_lib_check( isQHpointer, qhTsize, vertexTsize, ridgeTsize, facetTsize, setTsize, qhmemTsize )
Report error if library does not agree with caller
notes:
NOerrors -- qh_lib_check can not call qh_errexit()
*/
void qh_lib_check(int libraryType, int qhTsize, int vertexTsize, int ridgeTsize, int facetTsize, int setTsize, int qhmemTsize) {
boolT iserror= False;
if (libraryType==0) {
qh_fprintf(NULL, 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 (libraryType==1) {
qh_fprintf(NULL, 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;
}
if (qhTsize != sizeof(qhT)) {
qh_fprintf(NULL, 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(NULL, 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(NULL, 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(NULL, 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(NULL, 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(NULL, 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) {
qh_fprintf(NULL, stderr, 6259, "qh_lib_check: Cannot continue. Library '%s' is reentrant (e.g., qhull_r.so)\n", qh_version);
qh_exit(qh_ERRqhull); /* can not use qh_errexit() */
}
} /* lib_check */
/*---------------------------------
qh_option(qh, option, intVal, realVal )
add an option description to qh.qhull_options
notes:
NOerrors -- qh_option can not call qh_errexit() [qh_initqhull_start2]
will be printed with statistics ('Ts') and errors
strlen(option) < 40
*/
void qh_option(qhT *qh, const char *option, int *i, realT *r) {
char buf[200];
int len, maxlen;
sprintf(buf, " %s", option);
if (i)
sprintf(buf+strlen(buf), " %d", *i);
if (r)
sprintf(buf+strlen(buf), " %2.2g", *r);
len= (int)strlen(buf); /* WARN64 */
qh->qhull_optionlen += len;
maxlen= sizeof(qh->qhull_options) - len -1;
maximize_(maxlen, 0);
if (qh->qhull_optionlen >= qh_OPTIONline && maxlen > 0) {
qh->qhull_optionlen= len;
strncat(qh->qhull_options, "\n", (size_t)(maxlen--));
}
strncat(qh->qhull_options, buf, (size_t)maxlen);
} /* option */
/*---------------------------------
qh_zero( qh, errfile )
Initialize and zero Qhull's memory for qh_new_qhull()
notes:
Not needed in global.c because static variables are initialized to zero
*/
void qh_zero(qhT *qh, FILE *errfile) {
memset((char *)qh, 0, sizeof(qhT)); /* every field is 0, FALSE, NULL */
qh->NOerrexit= True;
qh_meminit(qh, errfile);
} /* zero */