File: index.htm

package info (click to toggle)
qhull 2019.1-5
  • links: PTS, VCS
  • area: main
  • in suites: sid
  • size: 8,524 kB
  • sloc: ansic: 45,753; cpp: 10,541; sh: 2,295; makefile: 802; xml: 203
file content (281 lines) | stat: -rw-r--r-- 14,712 bytes parent folder | download
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
<!DOCTYPE HTML PUBLIC "-//IETF//DTD HTML//EN">
<html>

<head>
<title>Qhull code for Convex Hull, Delaunay Triangulation, Voronoi Diagram, and Halfspace Intersection about a Point</title>
</head>

<body>
<!-- Navigation links -->
<b>URL:</b> <a href="http://www.qhull.org">http://www.qhull.org</a>
<br><b>To:</b>
<a href="http://www.qhull.org/news">News</a>
&#149; <a href="http://scholar.google.com/scholar?cites=13151392091060773178&as_sdt=40000005">Scholar</a>
&#149; <a href=http://images.google.com/images?q=qhull&num=100>Images</a>
&#149; <a href="https://github.com/qhull/qhull/wiki">GitHub</a>
&#149; <a href="http://www.qhull.org/download">Download</a>
&#149; <a href="html/index.htm">Manual</a>
&#149; <a href="html/qh-quick.htm#programs">Programs</a>
&#149; <a href="html/qh-quick.htm#options">Options</a>
&#149; <a href="html/qh-code.htm">Code</a>
&#149; <a href="src/libqhull_r/index.htm">Functions</a>
&#149; <a href="html/qh-faq.htm">FAQ</a>
</p>

<hr>
<!-- Main text of document -->
<table>
<tr><td valign=top>
        <h1>Qhull</h1>
        <a
        href="http://www.geom.uiuc.edu/graphics/pix/Special_Topics/Computational_Geometry/cone.html"><img
        src="html/qh--cone.gif" alt="[CONE]" align="middle" width="100"
        height="100"></a>
</td><td>
Qhull computes the convex hull, Delaunay triangulation, Voronoi diagram,
halfspace intersection about a point, furthest-site Delaunay
triangulation, and furthest-site Voronoi diagram. The source code runs in
2-d, 3-d, 4-d, and higher dimensions. Qhull implements the Quickhull
algorithm for computing the convex hull. It handles roundoff
errors from floating point arithmetic. It computes volumes,
surface areas, and approximations to the convex hull.</p>

<!-- duplicated in index.htm and html/index.htm -->
<p>Qhull does <i>not</i> support triangulation of non-convex surfaces, mesh
generation of non-convex objects, medium-sized inputs in 9-D
and higher, alpha shapes, weighted Voronoi diagrams, Voronoi volumes, or
constrained Delaunay triangulations,  </p>

<p>If you call Qhull from your program, please use reentrant Qhull (libqhull_r) or static Qhull (libqhull).
If you use Qhull 2003.1, please upgrade or apply <a href="http://www.qhull.org/download/poly.c-qh_gethash.patch">poly.c-qh_gethash.patch</a>.
</p>
</td></tr></table>

<hr>
<form method=get action=http://www.google.com/search>
<input type=hidden name=sitesearch value=www.qhull.org>
<input type=hidden name=num value=100>
<ul>
    <li><a href="http://www.qhull.org/news">News</a> and
        <a href="http://www.qhull.org/news/qhull-news.html#bugs">Bugs</a>
        about Qhull 2019.1  2019/06/21 (7.3.2)</li>
	<li><a href="http://www.qhull.org/download">Download</a> Qhull (<a href="http://www.qhull.org/src/Changes.txt">changes</a>)</li>
	<li><a href="https://github.com/qhull/qhull/wiki">GitHub</a> C++ interface to Qhull
	<li><a href="html/index.htm">Introduction and manual</a> for Qhull and rbox with a <a href="html/qh-faq.htm">FAQ</a>
	<li><a href="html/index.htm#geomview">Geomview</a> for 3-D and 4-D visualization of Qhull output
	<li><input name=as_q size=10 value="">
                <input type="submit" value="Search">
                www.qhull.org
        <p>
    <li><a href="http://www.qhull.org/news/qhull-news.html#users">How</a> is Qhull used?</li>
        <li><a href="http://scholar.google.com/scholar?cites=13151392091060773178&as_sdt=40000005">Google Scholar</a>,
        and <a href="http://citeseerx.ist.psu.edu/showciting?doi=10.1.1.117.405&sort=cite">CiteSeer</a>
        references to Qhull
    <li>
    <a href=http://www.google.com/search?as_q=qhull+-debian+-cvs+-gentoo+-pool+-mirrors&num=100>Google</a> Qhull,
         <a href="http://images.google.com/images?q=qhull&num=100">Images</a>,
         <a href="http://www.google.com/#q=qhull&tbm=bks">Books</a>,
         <a href="http://www.google.com/search?q=qhull&tbm=pts">Patents</a>,
         <a href="http://groups.google.com/groups?as_q=qhull&num=100&as_scoring=d">Newsgroups</a>,
        and <a href=http://www.googlism.com/who_is/q/qhull/>Who is</a> Qhull?


        <p>
        <li><a href=http://www.mathworks.com/>MATLAB</a> uses Qhull for their n-d computational geometry functions:
        <a href=http://www.mathworks.com/help/matlab/ref/convhulln.html>convhulln</a>
        <a href=http://www.mathworks.com/help/matlab/ref/delaunayn.html>delaunayn</a>
        <a href=http://www.mathworks.com/help/matlab/ref/griddatan.html>griddatan</a>
        <a href=http://www.mathworks.com/help/matlab/ref/voronoin.html>voronoin</a>.
    </li>
        <li>The <a href="http://cran.r-project.org/web/packages/geometry/geometry.pdf">geometry</a> package of <a href="http://www.r-project.org/">R</a> provides <a href="http://geometry.r-forge.r-project.org/">Qhull in R</a>.
        <li><a href=http://www.octave.org/>GNU Octave</a> includes Qhull for <a href="http://www.gnu.org/software/octave/doc/interpreter/Geometry.html">computational geometry<a>.
        <li><a href=http://www.wolfram.com/products/mathematica/>Mathematica</a>'s Delaunay interface <a href=http://library.wolfram.com/infocenter/MathSource/1160/>qh-math</a>.
     <li>The <a href="http://docs.scipy.org/doc/scipy/reference/tutorial/spatial.html">scipy.spatial</a> of <a href="http://scipy.org/">SciPy</a> is implemented with Qhull.  It includes
     support for Delaunay triangulations.
</ul>
</form>

<p><b>Introduction</b>
<ul>
    <li><a
        href="http://box2d.org/files/GDC2014/DirkGregorius_ImplementingQuickHull.pdf">Gregorius' talk</a> on implementing Quickhull,
        Lloyd's <a href="https://www.cs.ubc.ca/~lloyd/java/quickhull3d.html">QuickHull3D</a> in Java,
        and Newbold's <a href="http://dogfeathers.com/java/ccppoly.html">Waterman polyhedra</a>
    <li><a
        href="http://www.cs.mcgill.ca/~fukuda/soft/polyfaq/polyfaq.html"
                >Fukuda's introduction</a> to convex hulls, Delaunay
        triangulations, Voronoi diagrams, and linear programming</li>
        <li><a
        href="http://www.algorithmic-solutions.info/leda_guide/geometryalgorithms.html"
                >LEDA Guide</a> to geometry algorithms
        <li><a
            href="http://mathworld.wolfram.com/ComputationalGeometry.html"
                >MathWorld's</a> Computational Geometry from Wolfram Research
        <li><a
                href="http://www.cs.sunysb.edu/~algorith/major_section/1.6.shtml"
                >Skiena's</a> Computational Geometry from his <i>Algorithm Design Manual</i>.
    <li><a
        href="http://www.cs.sunysb.edu/~algorith/major_section/1.6.shtml"
                >Stony Brook</a> Algorithm Repository, computational geometry</li>
</ul>

<p><b>Qhull Documentation and Support</b>
<ul>
   <li><a href="html/index.htm">Manual</a> for Qhull and rbox
   <table><tr><td>
        <ul>
          <li><a href="html/index.htm#description">Description</a> of Qhull
                <li><a href="html/qh-impre.htm">Imprecision</a> in Qhull
                <li><a href="html/qh-quick.htm#programs">Programs</a> and <a href="html/qh-quick.htm#options">Options</a>
                    quick reference
                <li><a href="html/qconvex.htm">qconvex</a> -- convex hull
                <li><a href="html/qdelaun.htm">qdelaunay</a> -- Delaunay triangulation
                <li><a href="html/qvoronoi.htm">qvoronoi</a> -- Voronoi diagram
                <li><a href="html/qhalf.htm">qhalf</a> -- halfspace intersection about a point
                <li><a href="html/rbox.htm">rbox</a> -- generate point distributions
        </ul></td><td><ul>
            <li><a href="html/qh-faq.htm">FAQ</a> - frequently asked
                questions about Qhull</li>
            <li><a href="html/index.htm#geomview">Geomview</a> for visualizing Qhull
            <li><a href="COPYING.txt">COPYING.txt</a> - copyright notice<br>
            <li><a href="REGISTER.txt">REGISTER.txt</a> - registration<br>
            <li><a href="README.txt">README.txt</a> - installation
            instructions<br>
            <li><a href="src/Changes.txt">Changes.txt</a> - change history <br>
            <li><a href="html/qh-code.htm">Qhull code</a>
            <li><a href="src/libqhull_r/index.htm">Function</a> index to Qhull
            </ul>
        </td></tr></table>
    <li>Send e-mail to <a href=mailto:qhull@qhull.org>qhull@qhull.org</a> </li>
    <li>Report bugs to <a
        href="mailto:qhull_bug@qhull.org">qhull_bug@qhull.org</a>
</ul>

<p><b>Related URLs</b>
<ul>
    <li><a href="http://www.geom.uiuc.edu/software/cglist">Amenta's directory</a> of
        computational geometry software </li>

        <li><a href=http://www.boost.org/libs/graph/doc/table_of_contents.html>BGL</a>
        Boost Graph Library provides C++ classes for graph data structures
and algorithms,
    <li><a href=http://www.cgal.org/>CGAL</a> and <a href=http://www.algorithmic-solutions.com/index.php/products/leda-for-c>Leda</a>
libraries for writing computational
geometry programs and other combinatorial algorithms
    <li><a
        href="http://www.netlib.org/voronoi/hull.html">Clarkson's hull</a> program
        with exact arithmetic for convex hulls, Delaunay triangulations,
                Voronoi volumes, and alpha shapes. </li>
        <li><a href="http://jeffe.cs.illinois.edu/compgeom/">Erickson's
            Computational</a> Geometry Pages and
                <a href="http://jeffe.cs.illinois.edu/compgeom/code.html">Software</a>
    <li><a
        href="http://www.cs.mcgill.ca/~fukuda/soft/cdd_home/cdd.html">Fukuda's
        cdd</a> program for halfspace intersection and convex hulls (<a
        href="http://www.csb.ethz.ch/tools/polco">Polco/Java</a>)</li>
        <li><a href="http://www.inf.ethz.ch/personal/gaertner/miniball.html">Gartner's
        Miniball</a> for fast and robust smallest enclosing balls (up to 20-d)

        <li><a href=http://www.mathtools.net/>Mathtools.net</a> of scientific and engineering
        software
    <li><a href="http://www.imr.sandia.gov/papers/topics.html">Owen's International Meshing</a> Roundtable
    <li><a
        href="http://www.robertschneiders.de/meshgeneration/meshgeneration.html">Schneiders'
        Finite Element</a> Mesh Generation page</li>
     <li><a href="http://www.cs.cmu.edu/~quake/triangle.html">Shewchuk's triangle</a> program for 2-d Delaunay</li>
        <li><a href=http://www.voronoi.com>Voronoi Web Site</a> for all things Voronoi
        <li>Young's <a href="http://homepage.usask.ca/~ijm451/finite/fe_resources/">Internet Finite Element Resources</a>
        <li><a href="http://www.uic.unn.ru/~zny/skeleton/">Zolotykh's Skeleton</a> generates all extreme rays of a polyhedral cone using the Double Description Method</li>
        <li><a href="https://github.com/tomilov/quickhull/blob/master/include/quickhull.hpp">Tomilov's quickhull.hpp</a> (<a href="http://habrahabr.ru/post/245221/">doc-ru</a>) implements the Quickhull algorithm for points in general position.
</ul>

<p><b>FAQs and Newsgroups</b>
<ul>
    <li><a
        href="http://www.faqs.org/faqs/graphics/algorithms-faq/">FAQ</a>
        for computer graphics algorithms
    </li>
    <li><a
        href="http://lpsolve.sourceforge.net/4.0/LinearProgrammingFAQ.htm">FAQ</a> for linear programming </li>
    <li><a href="news:comp.graphics.algorithms">Newsgroup</a>:
        comp.graphics.algorithms </li>
        <li><a href="news:comp.soft-sys.matlab">Newsgroup</a>:
            comp.soft-sys.matlab</li>
    <li><a href="news:sci.math.num-analysis">Newsgroup</a>:
        sci.math.num-analysis </li>
    <li><a href="news:sci.op-research">Newsgroup</a>:
        sci.op-research </li>
</ul>
</blockquote>
<hr>

<p>The program includes options for input transformations,
randomization, tracing, multiple output formats, and execution
statistics. The program can be called from within your
application. </p>

<p>You can view the results in 2-d, 3-d and 4-d with <a
href="http://www.geomview.org">Geomview</a>.   An alternative
is <a href=http://www.vtk.org/>VTK</a>.</p>

<p>For an article about Qhull, download from
  <a href="https://dl.acm.org/authorize?N685077">ACM</a> or <a
    href="http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.117.405">CiteSeer</a>:
</p>

<blockquote>
    <p>Barber, C.B., Dobkin, D.P., and Huhdanpaa, H.T., &quot;The
    Quickhull algorithm for convex hulls,&quot; <i>ACM Trans. on
    Mathematical Software</i>, 22(4):469-483, Dec 1996, http://www.qhull.org</p>
</blockquote>

<p>Abstract: </p>

<blockquote>
    <p>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. </p>
    <p>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. </p>
</blockquote>
<!-- Navigation links -->
<hr>

<p><b>Up:</b> <a href="http://www.geom.uiuc.edu/software/past-projects.html"><i>Past Software
Projects of the Geometry Center</i></a> <br>
<b>URL:</b> <a href="http://www.qhull.org">http://www.qhull.org</a>
<br><b>To:</b>
<a href="http://www.qhull.org/news">News</a>
&#149; <a href="http://www.qhull.org/download">Download</a>
&#149; <a href="http://scholar.google.com/scholar?cites=13151392091060773178&as_sdt=40000005">Scholar</a>
&#149; <a href=http://images.google.com/images?q=qhull&num=100>Images</a>
&#149; <a href="html/index.htm#TOC">Manual</a>
&#149; <a href="http://www.qhull.org/html/qh-faq.htm">FAQ</a>
&#149; <a href="html/qh-quick.htm#programs">Programs</a>
&#149; <a href="html/qh-quick.htm#options">Options</a>
&#149; <a href="src/libqhull_r/index.htm">Functions</a>
<!-- GC common information --></p>

<hr>

<p><a href="http://www.geom.uiuc.edu/"><img src="html/qh--geom.gif" alt="[HOME]"
align="middle"></a> <i>The Geometry Center Home Page</i> </p>

<p>Comments to: <a href="mailto:qhull@qhull.org">qhull@qhull.org</a>
<br>
Created: May 17 1995 --- <!-- hhmts start -->
</body>
</html>