Page Menu
Home
c4science
Search
Configure Global Search
Log In
Files
F104523825
qh-in.htm
No One
Temporary
Actions
Download File
Edit File
Delete File
View Transforms
Subscribe
Mute Notifications
Award Token
Subscribers
None
File Metadata
Details
File Info
Storage
Attached
Created
Mon, Mar 10, 03:56
Size
23 KB
Mime Type
text/html
Expires
Wed, Mar 12, 03:56 (1 d, 18 h)
Engine
blob
Format
Raw Data
Handle
24804777
Attached To
rCADDMESH CADD_mesher
qh-in.htm
View Options
This document is not UTF8. It was detected as Shift JIS and converted to UTF8 for display.
<!DOCTYPE HTML PUBLIC "-//IETF//DTD HTML//EN">
<html>
<head>
<title>
Qhull internals
</title>
<!-- Navigation links -->
</head>
<body>
<p><a
name=
"TOP"
><b>
Up:
</b></a>
<a
href=
"http://www.geom.umn.edu/locate/qhull"
>
Home page for Qhull
</a>
<br>
<b>
Up:
</b>
<a
href=
"index.htm#TOC"
>
Qhull manual: Table of
Contents
</a><br>
<b>
To:
</b>
<a
href=
"qh-quick.htm#programs"
>
Programs
</a>
•
</a>
<a
href=
"qh-quick.htm#options"
>
Options
</a>
•
<a
href=
"qh-opto.htm#output"
>
Output
</a>
•
<a
href=
"qh-optf.htm#format"
>
Formats
</a>
•
<a
href=
"qh-optg.htm#geomview"
>
Geomview
</a>
•
<a
href=
"qh-optp.htm#print"
>
Print
</a>
•
<a
href=
"qh-optq.htm#qhull"
>
Qhull
</a>
•
<a
href=
"qh-optc.htm#prec"
>
Precision
</a>
•
<a
href=
"qh-optt.htm#trace"
>
Trace
</a><br>
<b>
To:
</b>
<a
href=
"#TOC"
>
Qhull internals: Table of Contents
</a>
(please wait while loading)
<br>
<b>
Dn:
</b>
<a
href=
"../src/index.htm"
>
Qhull functions, macros, and data
structures
</a>
</p>
<hr>
<!-- Main text of document -->
<h1><a
href=
"http://www.geom.umn.edu/graphics/pix/Special_Topics/Computational_Geometry/4dcube.html"
><img
src=
"qh--4d.gif"
alt=
"[4-d cube]"
align=
"middle"
width=
"100"
height=
"100"
></a>
Qhull internals
</h1>
<p>
This section discusses the internals of Qhull.
</p>
<p><b>
Copyright ｩ 1995-2001 The Geometry Center, Minneapolis MN
</b></p>
<hr>
<h2><a
href=
"#TOP"
>
ｻ
</a><a
name=
"TOC"
>
Qhull internals: Table of
Contents
</a></h2>
<ul>
<li><a
href=
"#performance"
>
Performance of Qhull
</a></li>
<li><a
href=
"#library"
>
Calling Qhull from your program
</a></li>
<ul>
<li><a
href=
"#mem"
>
sets and quick memory allocation
</a></li>
<li><a
href=
"#dids"
>
print point indices for Delaunay
triangles
</a></li>
<li><a
href=
"#findfacet"
>
locate a facet with
qh_findbestfacet()
</a></li>
<li><a
href=
"#inc"
>
on-line construction with
qh_addpoint()
</a></li>
<li><a
href=
"#constrained"
>
Constrained Delaunay
triangulation
</a></li>
<li><a
href=
"#vertices"
>
Voronoi vertices of a region
</a></li>
<li><a
href=
"#ridge"
>
Voronoi vertices of a ridge
</a></li>
<li><a
href=
"#vneighbor"
>
vertex neighbors of a vertex
</a></li>
</ul>
</li>
<li><a
href=
"#enhance"
>
Enhancements to Qhull
</a></li>
<li><a
href=
"../src/index.htm"
>
Qhull functions, macros, and data
structures
</a>
</li>
</ul>
<hr>
<h2><a
href=
"#TOC"
>
ｻ
</a><a
name=
"performance"
>
Performance of
Qhull
</a></h2>
<p>
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
<i>
O(log n)
</i>
bits. Empirically, the maximum number of vertices occurs at the
end of constructing the hull.
</p>
<p>
Let
<i>
n
</i>
be the number of input points,
<i>
v
</i>
be the
number of output vertices, and
<i>
f_v
</i>
be the maximum number
of facets for a convex hull of
<i>
v
</i>
vertices. If both
conditions hold, Qhull runs in
<i>
O(n log v)
</i>
in 2-d and 3-d
and
<i>
O(n f_v/v)
</i>
otherwise. The function
<i>
f_v
</i>
increases rapidly with dimension. It is
<em>
O(v^floor(d/2) /
floor(d/2)!)
</em>
.
</p>
<p>
The time complexity for merging is unknown. Options '
<a
href=
"qh-optc.htm#C0"
>
C-0
</a>
' and '
<a
href=
"qh-optq.htm#Qx"
>
Qx
</a>
'
(defaults) handle precision problems due to floating-point
arithmetic. They are optimized for simplicial outputs.
</p>
<p>
When running large data sets, you should monitor Qhull's
performance with the '
<a
href=
"qh-optt.htm#TFn"
>
TFn
</a>
' 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 simplicies contains 18 facets and
500,000 ridges. This will increase the time needed per facet.
</p>
<p>
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.
</p>
<p>
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.
</p>
<p>
When building hulls in 20-d and higher, you can follow the
progress of Qhull with option '
<a
href=
"qh-optt.htm#Tn"
>
T1
</a>
'.
It reports each major event in processing a point.
</p>
<p>
To reduce memory requirements, recompile Qhull for
single-precision reals (REALfloat in
<tt>
user.h
</tt>
).
Single-precision does not work with joggle ('
<a
href=
"qh-optq.htm#QJn"
>
QJ
</a>
'). Check qh_MEMalign in
<tt>
user.h
</tt>
and the match between free list sizes and data structure sizes
(see the end of the statistics report from '
<a
href=
"qh-optt.htm#Ts"
>
Ts
</a>
'). 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
<tt>
user.h
</tt>
).
</p>
<p>
To reduce the size of the Qhull executable, consider
qh_NOtrace and qh_KEEPstatistics 0 in
<tt>
user.h
</tt>
. By
changing
<tt>
user.c
</tt>
you can also remove the input/output
code in
<tt>
io.c
</tt>
. 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.
</p>
<p>
The precision options, '
<a
href=
"qh-optc.htm#Vn"
>
Vn
</a>
', '
<a
href=
"qh-optc.htm#Wn"
>
Wn
</a>
', '
<a
href=
"qh-optc.htm#Un"
>
Un
</a>
'.
'
<a
href=
"qh-optc.htm#An"
>
A-n
</a>
', '
<a
href=
"qh-optc.htm#Cn"
>
C-n
</a>
',
'
<a
href=
"qh-optc.htm#An2"
>
An
</a>
', '
<a
href=
"qh-optc.htm#Cn2"
>
Cn
</a>
',
and '
<a
href=
"qh-optq.htm#Qx"
>
Qx
</a>
', may have large effects on
Qhull performance. You will need to experiment to find the best
combination for your application.
</p>
<p>
The verify option ('
<a
href=
"qh-optt.htm#Tv"
>
Tv
</a>
') 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.
</p>
<p>
The check-frequently option ('
<a
href=
"qh-optt.htm#Tc"
>
Tc
</a>
')
becomes expensive as the dimension increases. The verify option
('
<a
href=
"qh-optt.htm#Tv"
>
Tv
</a>
') performs many of the same
checks before outputting the results.
</p>
<p>
Options '
<a
href=
"qh-optq.htm#Q0"
>
Q0
</a>
' (no pre-merging), '
<a
href=
"qh-optq.htm#Q3"
>
Q3
</a>
' (no checks for redundant vertices),
'
<a
href=
"qh-optq.htm#Q5"
>
Q5
</a>
' (no updates for outer planes),
and '
<a
href=
"qh-optq.htm#Q8"
>
Q8
</a>
' (no near-interior points)
increase Qhull's speed. The corresponding operations may not be
needed in your application.
</p>
<p>
In 2-d and 3-d, a partial hull may be faster to produce.
Option '
<a
href=
"qh-optq.htm#QGn"
>
QgGn
</a>
' only builds facets
visible to point n. Option '
<a
href=
"qh-optq.htm#QVn"
>
QgVn
</a>
'
only builds facets that contain point n. In higher-dimensions,
this does not reduce the number of facets.
</p>
<p><tt>
User.h
</tt>
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.
</p>
<h2><a
href=
"#TOC"
>
ｻ
</a><a
name=
"library"
>
Calling Qhull from
your program
</a></h2>
<p>
The
<tt>
Makefile
</tt>
produces a library,
<tt>
libqhull.a
</tt>
,
for inclusion in your programs. First review
<tt>
qhull.h
</tt>
.
This defines the data structures used by Qhull and provides
prototypes for the top-level functions.
</p>
<p>
Most users will only need qhull.h in their programs. For
example, the Qhull program is defined with
<tt>
qhull.h
</tt>
and
<tt>
unix.c
</tt>
.
To access all functions, use
<tt>
qhull_a.h
</tt>
. Include the file
with
"
<tt>
#include
<
qhull/qhull_a.h
>"
.
</tt>
This
avoids potential name conflicts.
</p>
<p>
See
<a
href=
"../src/index.htm"
>
Qhull functions, macros, and data
structures
</a>
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.
</p>
<p>
When you read the code, be aware of the macros
"
qh
"
and
"
qhstat
"
, e.g.,
"
qh hull_dim
"
. They are
defined in
<tt>
qhull.h
</tt>
. They allow the global data
structures to be pre-allocated (faster access) or dynamically
allocated (allows multiple copies).
</p>
<p><tt>
User.c
</tt>
and
<tt>
qhull_interface.cpp
</tt>
include
an application template. You can use
<tt>
user_eg.c
</tt>
as an example. It also shows how to reduce memory requirements by
not loading
<tt>
io.o
</tt>
. If you use joggled input ('
<a
href=
"qh-optq.htm#QJn"
>
QJ
</a>
'), you may also remove
<tt>
merge.o
</tt>
with
<a
href=
"user.h#NOmerge"
>
qh_NOmerge
</a>
'.
</p>
<p>
The
<a
href=
http://www.boost.org/libs/graph/doc/table_of_contents.html
>
BGL
</a>
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
<a
href=
"mailto:bradb@geom.umn.edu"
>
bradb@geom.umn.edu
</a>
.
<p>
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
'
<a
href=
"qh-optt.htm#Tc"
>
Tc
</a>
' option will catch many problems
as they occur. When an error occurs, use '
<a
href=
"qh-optt.htm#Tn"
>
T4
</a>
<a
href=
"qh-optt.htm#TPn"
>
TPn
</a>
'
to trace from the last point added to the hull. Compare your
trace with the trace output from the Qhull program.
</p>
<p>
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.
</p>
<h3><a
href=
"#TOC"
>
ｻ
</a><a
name=
"mem"
>
sets and quick memory
allocation
</a></h3>
<p>
You can use
<tt>
mem.c
</tt>
and
<tt>
qset.c
</tt>
individually.
<tt>
Mem.c
</tt>
implements quick-fit memory allocation. It is faster than
malloc/free in applications that allocate and deallocate lots of
memory.
</p>
<p><tt>
Qset.c
</tt>
implements sets and related collections. It's
the inner loop of Qhull, so speed is more important than
abstraction. Set iteration is particularly fast.
<tt>
qset.c
</tt>
just includes the functions needed for Qhull.
</p>
<h3><a
href=
"#TOC"
>
ｻ
</a><a
name=
"dids"
>
print point indices for
Delaunay triangles
</a></h3>
<p>
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.
</p>
<blockquote>
<pre>
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
"
);
}
}
</pre>
</blockquote>
<h3><a
href=
"#TOC"
>
ｻ
</a><a
name=
"findfacet"
>
locate a facet with
qh_findbestfacet()
</a></h3>
<p>
The routine qh_findbestfacet in
<tt>
poly2.c
</tt>
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.
</p>
<p>
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.
</p>
<p>
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
<a
href=
"index.htm#dob-kir90"
>
'90
</a>
].
</p>
<p>
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.c). Do not scale the input with
options 'Qbk', 'QBk', 'QbB' or 'Qbb'. See Mucke, et al [
<a
href=
"index.htm#muck96"
>
'96
</a>
] for a good point location
algorithm.
</p>
<p>
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.
</p>
<h3><a
href=
"#TOC"
>
ｻ
</a><a
name=
"inc"
>
on-line construction with
qh_addpoint()
</a></h3>
<p>
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
<a
href=
"http://netlib.bell-labs.com/netlib/voronoi/hull.html"
>
hull
program
</a>
). 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).
</p>
<p>
You may use qh_addpoint in
<tt>
qhull.c
</tt>
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 (
<a
href=
"#findfacet"
>
qh_findbestfacet
</a>
).
</p>
<p>
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).
</p>
<p>
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.
</p>
<p>
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]
</p>
<p>
See user_eg.c for examples of the on-line construction of
convex hulls, Delaunay triangulations, and halfspace
intersections. The outline is:
</p>
<blockquote>
<pre>
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
</pre>
</blockquote>
<h3><a
href=
"#TOC"
>
ｻ
</a><a
name=
"constrained"
>
Constrained
Delaunay triangulation
</a></h3>
<p>
With a fair amount of work, Qhull is suitable for constrained
Delaunay triangulation. See Shewchuk, ACM Symposium on
Computational Geometry, Minneapolis 1998.
</p>
<p>
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]
</p>
<h3><a
href=
"#TOC"
>
ｻ
</a><a
name=
"vertices"
>
Voronoi vertices of a
region
</a></h3>
<p>
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
<tt>
io.c
</tt>
for '
<a
href=
qvoronoi.htm
>
qvoronoi
</a>
<a
href=
"qh-opto.htm#o"
>
o'
</a>
</p>
<blockquote>
<pre>
/* 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 ...
}
}
}
</pre>
</blockquote>
<h3><a
href=
"#TOC"
>
ｻ
</a><a
name=
"ridge"
>
Voronoi vertices of a
ridge
</a></h3>
<p>
Qhull uses qh_printvdiagram() in io.c to print the ridges of a
Voronoi diagram for option '
<a
href=
"qh-optf.htm#Fv2"
>
Fv
</a>
'.
The helper function qh_eachvoronoi() does the real work. It calls
the callback 'printvridge' for each ridge of the Voronoi diagram.
</p>
<p>
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.
</p>
<h3><a
href=
"#TOC"
>
ｻ
</a><a
name=
"vneighbor"
>
vertex neighbors of
a vertex
</a></h3>
<p>
To visit all of the vertices that share an edge with a vertex:
</p>
<ul>
<li>
Generate neighbors for each vertex with
qh_vertexneighbors in
<tt>
poly2.c
</tt>
.
</li>
<li>
For simplicial facets, visit the vertices of each
neighbor
</li>
<li>
For non-simplicial facets,
<ul>
<li>
Generate ridges for neighbors with qh_makeridges
in
<tt>
merge.c
</tt>
.
</li>
<li>
Generate ridges for a vertex with qh_vertexridges
in
<tt>
merge.c
</tt>
.
</li>
<li>
Visit the vertices of these ridges.
</li>
</ul>
</li>
</ul>
<p>
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.
</p>
<h2><a
href=
"#TOC"
>
ｻ
</a><a
name=
"enhance"
>
Enhancements to Qhull
</a></h2>
<p>
There are many ways in which Qhull can be improved.
</p>
<pre>
Here is a partial list:
- write a BGL interface to Qhull
http://www.boost.org/libs/graph/doc/table_of_contents.html
- rewrite Qhull in C++ to make it easier to use Qhull in a program
- change qh_save_qhull to swap the qhT structure instead of using pointers
- change error handling and tracing to be independent of 'qh ferr'
- produce a custom version and documentation for Delaunay triangulations
The convex hull code/documentation is confusing for Delaunay triangulations
- determine the maximum width for a given set of parameters
- prove that directed search locates all coplanar facets
- improve and speed up directed search (qh_findbest)
- for Delaunay triangulations, remove potential exhaustive search in qh_findbestfacet()
- 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 ('
<a
href=
"qh-optc.htm#Vn"
>
Vn
</a>
')
- determine the limitations of '
<a
href=
"qh-optq.htm#Qg"
>
Qg
</a>
'
Precision improvements:
- 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 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]
- compute volume of Voronoi regions [see Clarkson's hull program]
- 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:
- 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 '
<a
href=
"qh-optg.htm#GDn"
>
GDn
</a>
' 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 '
<a
href=
"qh-optf.htm#Fv"
>
Fv
</a>
' 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
<a
href=
"index.htm#orou94"
>
'94
</a>
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
</pre>
<p>
Please let us know about your applications and improvements.
</p>
<!-- Navigation links -->
<hr>
<p><b>
Up:
</b>
<a
href=
"http://www.geom.umn.edu/locate/qhull"
>
Home
page for Qhull
</a>
<br>
<b>
Up:
</b>
<a
href=
"index.htm#TOC"
>
Qhull manual: Table of
Contents
</a><br>
<b>
To:
</b>
<a
href=
"qh-quick.htm#programs"
>
Programs
</a>
•
</a>
<a
href=
"qh-quick.htm#options"
>
Options
</a>
•
<a
href=
"qh-opto.htm#output"
>
Output
</a>
•
<a
href=
"qh-optf.htm#format"
>
Formats
</a>
•
<a
href=
"qh-optg.htm#geomview"
>
Geomview
</a>
•
<a
href=
"qh-optp.htm#print"
>
Print
</a>
•
<a
href=
"qh-optq.htm#qhull"
>
Qhull
</a>
•
<a
href=
"qh-optc.htm#prec"
>
Precision
</a>
•
<a
href=
"qh-optt.htm#trace"
>
Trace
</a><br>
<b>
To:
</b>
<a
href=
"#TOC"
>
Qhull internals: Table of Contents
</a>
<br>
<b>
Dn:
</b>
<a
href=
"../src/index.htm"
>
Qhull functions, macros, and data
structures
</a>
<!-- GC common information -->
</p>
<hr>
<p><a
href=
"http://www.geom.umn.edu/"
><img
src=
"qh--geom.gif"
align=
"middle"
width=
"40"
height=
"40"
></a><i>
The Geometry Center
Home Page
</i></p>
<p>
Comments to:
<a
href=
"http://www.geom.umn.edu/software/qhull/qhull-mail.html"
>
qhull@geom.umn.edu
</a><br>
Created: Sept. 25, 1995 ---
<!-- hhmts start -->
Last modified: see changes.txt
<!-- hhmts end -->
</p>
</body>
</html>
Event Timeline
Log In to Comment