| 1 |
<!DOCTYPE HTML PUBLIC "-//IETF//DTD HTML//EN"> |
| 2 |
<html> |
| 3 |
|
| 4 |
<head> |
| 5 |
<title>Qhull code for Convex Hull, Delaunay Triangulation, Voronoi Diagram, and Halfspace Intersection about a Point</title> |
| 6 |
</head> |
| 7 |
|
| 8 |
<body> |
| 9 |
<!-- Navigation links --> |
| 10 |
<b>URL:</b> <a href="http://www.qhull.org">http://www.qhull.org</a> |
| 11 |
<br><b>To:</b> |
| 12 |
<a href="http://www.qhull.org/news">News</a> |
| 13 |
• <a href="http://www.qhull.org/download">Download</a> |
| 14 |
• <a href="http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.117.405">CiteSeer</a> |
| 15 |
• <a href=http://images.google.com/images?q=qhull&num=100>Images</a> |
| 16 |
• <a href="html/index.htm#TOC">Manual</a> |
| 17 |
• <a href="http://www.qhull.org/html/qh-faq.htm">FAQ</a> |
| 18 |
• <a href="html/qh-quick.htm#programs">Programs</a> |
| 19 |
• <a href="html/qh-quick.htm#options">Options</a> |
| 20 |
</p> |
| 21 |
|
| 22 |
<hr> |
| 23 |
<!-- Main text of document --> |
| 24 |
<table> |
| 25 |
<tr><td valign=top> |
| 26 |
<h1>Qhull</h1> |
| 27 |
<a |
| 28 |
href="http://www.geom.uiuc.edu/graphics/pix/Special_Topics/Computational_Geometry/cone.html"><img |
| 29 |
src="html/qh--cone.gif" alt="[CONE]" align="middle" width="100" |
| 30 |
height="100"></a> |
| 31 |
</td><td> |
| 32 |
Qhull computes the convex hull, Delaunay triangulation, Voronoi diagram, |
| 33 |
halfspace intersection about a point, furthest-site Delaunay |
| 34 |
triangulation, and furthest-site Voronoi diagram. The source code runs in |
| 35 |
2-d, 3-d, 4-d, and higher dimensions. Qhull implements the Quickhull |
| 36 |
algorithm for computing the convex hull. It handles roundoff |
| 37 |
errors from floating point arithmetic. It computes volumes, |
| 38 |
surface areas, and approximations to the convex hull.</p> |
| 39 |
|
| 40 |
<!-- duplicated in index.htm and html/index.htm --> |
| 41 |
<p>Qhull does <i>not</i> support triangulation of non-convex surfaces, mesh |
| 42 |
generation of non-convex objects, medium-sized inputs in 9-D |
| 43 |
and higher, alpha shapes, weighted Voronoi diagrams, Voronoi volumes, or |
| 44 |
constrained Delaunay triangulations, </p> |
| 45 |
|
| 46 |
<p>Qhull 2012.1 fixes qhull-go for Windows 64-bit. If you use Qhull 2003.1. please upgrade to 2012.1 or apply <a href="http://www.qhull.org/download/poly.c-qh_gethash.patch">poly.c-qh_gethash.patch</a>.</p> |
| 47 |
</td></tr></table> |
| 48 |
|
| 49 |
<hr> |
| 50 |
<form method=get action=http://www.google.com/search> |
| 51 |
<input type=hidden name=sitesearch value=www.qhull.org> |
| 52 |
<input type=hidden name=num value=100> |
| 53 |
<ul> |
| 54 |
<li><a href="http://www.qhull.org/news">News</a> and |
| 55 |
<a href="http://www.qhull.org/news/qhull-news.html#bugs">Bugs</a> |
| 56 |
about Qhull 2012.1 2012/02/18</li> |
| 57 |
<li><a href="http://www.qhull.org/download">Download</a> Qhull</li> |
| 58 |
<li><a |
| 59 |
href="http://www.geom.uiuc.edu/graphics/pix/Special_Topics/Computational_Geometry/welcome.html">Examples |
| 60 |
</a>of Qhull output </li> |
| 61 |
<li><a href=http://gitorious.org/qhull/>Gitorious</a> C++ interface to Qhull |
| 62 |
(<a href="http://gitorious.org/qhull/pages/Home">wiki</a>, <a href="http://www.qhull.org/src/Changes.txt">changes</a>) |
| 63 |
<li><input name=as_q size=10 value=""> |
| 64 |
<input type="submit" value="Search"> |
| 65 |
www.qhull.org |
| 66 |
<p> |
| 67 |
<li><a href="http://www.qhull.org/news/qhull-news.html#users">How</a> is Qhull used?</li> |
| 68 |
<li><a href="http://scholar.google.com/scholar?cites=13151392091060773178&as_sdt=40000005">Google Scholar</a> |
| 69 |
and <a href="http://citeseerx.ist.psu.edu/showciting?doi=10.1.1.117.405&sort=cite">CiteSeer</a> |
| 70 |
references to Qhull |
| 71 |
</p> |
| 72 |
<li> |
| 73 |
<a href=http://www.google.com/search?as_q=qhull+-debian+-cvs+-gentoo+-pool+-mirrors&num=100>Google</a> Qhull, |
| 74 |
<a href="http://images.google.com/images?q=qhull&num=100">Images</a>, |
| 75 |
<a href="http://www.google.com/#q=qhull&tbm=bks">Books</a>, |
| 76 |
<a href="http://www.google.com/search?q=qhull&tbm=pts">Patents</a>, |
| 77 |
<a href="http://groups.google.com/groups?as_q=qhull&num=100&as_scoring=d">Newsgroups</a>, |
| 78 |
<a href="http://www.google.com/search?q=qhull&tbm=blg">Blogs</a>, |
| 79 |
and <a href=http://www.googlism.com/who_is/q/qhull/>Who is</a> Qhull? |
| 80 |
|
| 81 |
|
| 82 |
<p> |
| 83 |
<li><a href=http://www.mathworks.com/>MATLAB</a> uses Qhull for their n-d computational geometry functions: |
| 84 |
<a href=http://www.mathworks.com/help/techdoc/ref/convhulln.html>convhulln</a> |
| 85 |
<a href=http://www.mathworks.com/help/techdoc/ref/delaunayn.html>delaunayn</a> |
| 86 |
<a href=http://www.mathworks.com/help/techdoc/ref/griddatan.html>griddatan</a> |
| 87 |
<a href=http://www.mathworks.com/help/techdoc/ref/voronoin.html>voronoin</a>. |
| 88 |
</li> |
| 89 |
<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>. |
| 90 |
<li>The <a href="http://packages.debian.org/sid/octave3.2">Debian build</a> of |
| 91 |
<a href=http://www.octave.org/>GNU Octave</a> includes Qhull for computational geometry. |
| 92 |
<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> |
| 93 |
and <a href="http://portal.uni-freiburg.de/imteksimulation/downloads/ims">QHullInterface</a> |
| 94 |
<li><a href=http://www.geomview.org>Geomview</a> for 3-D and 4-D visualization of Qhull output |
| 95 |
</ul> |
| 96 |
</form> |
| 97 |
|
| 98 |
<p><b>Introduction</b> |
| 99 |
<ul> |
| 100 |
<li><a |
| 101 |
href="http://www.cs.mcgill.ca/~fukuda/soft/polyfaq/polyfaq.html" |
| 102 |
>Fukuda's introduction</a> to convex hulls, Delaunay |
| 103 |
triangulations, Voronoi diagrams, and linear programming</li> |
| 104 |
<li><a |
| 105 |
href="http://www.cse.unsw.edu.au/~lambert/java/3d/hull.html" |
| 106 |
>Lambert's Java</a> visualization of convex hull algorithms </li> |
| 107 |
<li><a |
| 108 |
href="http://www.algorithmic-solutions.info/leda_guide/geometryalgorithms.html" |
| 109 |
>LEDA Guide</a> to geometry algorithms |
| 110 |
<li><a |
| 111 |
href="http://mathworld.wolfram.com/ComputationalGeometry.html" |
| 112 |
>MathWorld's</a> Computational Geometry from Wolfram Research |
| 113 |
<li><a |
| 114 |
href="http://www.cs.sunysb.edu/~algorith/major_section/1.6.shtml" |
| 115 |
>Skiena's</a> Computational Geometry from his <i>Algorithm Design Manual</i>. |
| 116 |
<li><a |
| 117 |
href="http://www.cs.sunysb.edu/~algorith/major_section/1.6.shtml" |
| 118 |
>Stony Brook</a> Algorithm Repository, computational geometry</li> |
| 119 |
</ul> |
| 120 |
|
| 121 |
<p><b>Qhull Documentation and Support</b> |
| 122 |
<ul> |
| 123 |
<li><a href="html/index.htm">Manual</a> for Qhull and rbox |
| 124 |
<table><tr><td> |
| 125 |
<ul> |
| 126 |
<li><a href="html/index.htm#description">Description</a> of Qhull |
| 127 |
<li><a href="html/qh-quick.htm#programs">Programs</a> and <a href="html/qh-quick.htm#options">Options</a> |
| 128 |
quick reference |
| 129 |
<li><a href="html/qconvex.htm">qconvex</a> -- convex hull |
| 130 |
<li><a href="html/qdelaun.htm">qdelaunay</a> -- Delaunay triangulation |
| 131 |
<li><a href="html/qvoronoi.htm">qvoronoi</a> -- Voronoi diagram |
| 132 |
<li><a href="html/qhalf.htm">qhalf</a> -- halfspace intersection about a point |
| 133 |
<li><a href="html/rbox.htm">rbox</a> -- generate point distributions |
| 134 |
</ul></td><td><ul> |
| 135 |
<li><a href="http://www.qhull.org/html/qh-faq.htm">Frequently</a> asked |
| 136 |
questions about Qhull</li> |
| 137 |
<li><a href="COPYING.txt">COPYING.txt</a> - copyright notice<br> |
| 138 |
<li><a href="REGISTER.txt">REGISTER.txt</a> - registration<br> |
| 139 |
<li><a href="README.txt">README.txt</a> - installation |
| 140 |
instructions<br> |
| 141 |
<li><a href="src/Changes.txt">Changes.txt</a> - change history <br> |
| 142 |
<li><a href="html/qh-code.htm">Calling Qhull</a> from your program |
| 143 |
<li><a href="src/libqhull/index.htm">Qhull functions</a>, macros, and data structures with source |
| 144 |
</ul> |
| 145 |
</td></tr></table> |
| 146 |
<li>Send e-mail to <a href=mailto:qhull@qhull.org>qhull@qhull.org</a> </li> |
| 147 |
<li>Report bugs to <a |
| 148 |
href="mailto:qhull_bug@qhull.org">qhull_bug@qhull.org</a> |
| 149 |
</ul> |
| 150 |
|
| 151 |
<p><b>Related URLs</b> |
| 152 |
<ul> |
| 153 |
<li><a href="http://www.geom.uiuc.edu/software/cglist">Amenta's directory</a> of |
| 154 |
computational geometry software </li> |
| 155 |
|
| 156 |
<li><a href=http://www.boost.org/libs/graph/doc/table_of_contents.html>BGL</a> |
| 157 |
Boost Graph Library provides C++ classes for graph data structures |
| 158 |
and algorithms, |
| 159 |
<li><a |
| 160 |
href="http://www.netlib.org/voronoi/hull.html">Clarkson's |
| 161 |
hull </a>program with exact arithmetic for convex hulls, Delaunay triangulations, |
| 162 |
Voronoi volumes, and alpha shapes. </li> |
| 163 |
<li><a href="http://compgeom.cs.uiuc.edu/~jeffe/compgeom/compgeom.html">Erickson's |
| 164 |
Computational</a> Geometry Pages and |
| 165 |
<a href="http://compgeom.cs.uiuc.edu/~jeffe/compgeom/code.html">Software</a> |
| 166 |
<li><a |
| 167 |
href="http://www.cs.mcgill.ca/~fukuda/soft/cdd_home/cdd.html">Fukuda's |
| 168 |
cdd</a> program for halfspace intersection and convex hulls</li> |
| 169 |
<li><a href="http://www.inf.ethz.ch/personal/gaertner/miniball.html">Gartner's |
| 170 |
Miniball</a> for fast and robust smallest enclosing balls (up to 20-d) |
| 171 |
|
| 172 |
<li><a href=http://www.algorithmic-solutions.com/enleda.htm>Leda</a> |
| 173 |
and <a href=http://www.cgal.org/>CGAL</a> libraries for writing computational |
| 174 |
geometry programs and other combinatorial algorithms |
| 175 |
<li><a href=http://www.mathtools.net/>Mathtools.net</a> of scientific and engineering |
| 176 |
software |
| 177 |
<li><a href="http://morden.csee.usf.edu/dragon/kpalbrec/mesh.html">Owen's Meshing</a> Research Corner |
| 178 |
<li><a |
| 179 |
href="http://www-users.informatik.rwth-aachen.de/~roberts/meshgeneration.html">Schneiders' |
| 180 |
Finite Element</a> Mesh Generation page</li> |
| 181 |
<li><a href="http://www.cs.cmu.edu/~quake/triangle.html">Shewchuk's |
| 182 |
triangle </a>program for 2-d Delaunay</li> |
| 183 |
<li><a href=http://www.voronoi.com>Voronoi Web Site</a> for all things Voronoi |
| 184 |
<li>Young's <a href="http://homepage.usask.ca/~ijm451/finite/fe_resources/">Internet Finite Element Resources</a> |
| 185 |
<li><a href="http://www.uic.nnov.ru/~zny/skeleton/">Zolotykh's Skeleton</a> generates all extreme rays of a polyhedral cone using the Double Description Method</li> |
| 186 |
</ul> |
| 187 |
|
| 188 |
<p><b>FAQs and Newsgroups</b> |
| 189 |
<ul> |
| 190 |
<li><a |
| 191 |
href="http://exaflop.org/docs/cgafaq/">FAQ</a> |
| 192 |
for computer graphics algorithms |
| 193 |
(<a href="http://exaflop.org/docs/cgafaq/cga6.html">geometric</a> structures) |
| 194 |
</li> |
| 195 |
<li><a |
| 196 |
href="http://www-unix.mcs.anl.gov/otc/Guide/faq/linear-programming-faq.html">FAQ |
| 197 |
</a>for linear programming </li> |
| 198 |
<li><a href="news:comp.graphics.algorithms">Newsgroup</a>: |
| 199 |
comp.graphics.algorithms </li> |
| 200 |
<li><a href="news:comp.soft-sys.matlab">Newsgroup</a>: |
| 201 |
comp.soft-sys.matlab</li> |
| 202 |
<li><a href="news:sci.math.num-analysis">Newsgroup</a>: |
| 203 |
sci.math.num-analysis </li> |
| 204 |
<li><a href="news:sci.op-research">Newsgroup</a>: |
| 205 |
sci.op-research </li> |
| 206 |
</ul> |
| 207 |
</blockquote> |
| 208 |
<hr> |
| 209 |
|
| 210 |
<p>The program includes options for input transformations, |
| 211 |
randomization, tracing, multiple output formats, and execution |
| 212 |
statistics. The program can be called from within your |
| 213 |
application. </p> |
| 214 |
|
| 215 |
<p>You can view the results in 2-d, 3-d and 4-d with <a |
| 216 |
href="http://www.geomview.org">Geomview</a>. An alternative |
| 217 |
is <a href=http://www.vtk.org/>VTK</a>.</p> |
| 218 |
|
| 219 |
<p>For an article about Qhull, download from |
| 220 |
<a href="http://dl.acm.org/authorize?89250">ACM</a> or <a |
| 221 |
href="http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.117.405">CiteSeer</a>: |
| 222 |
</p> |
| 223 |
|
| 224 |
<blockquote> |
| 225 |
<p>Barber, C.B., Dobkin, D.P., and Huhdanpaa, H.T., "The |
| 226 |
Quickhull algorithm for convex hulls," <i>ACM Trans. on |
| 227 |
Mathematical Software</i>, 22(4):469-483, Dec 1996, http://www.qhull.org</p> |
| 228 |
</blockquote> |
| 229 |
|
| 230 |
<p>Abstract: </p> |
| 231 |
|
| 232 |
<blockquote> |
| 233 |
<p>The convex hull of a set of points is the smallest convex |
| 234 |
set that contains the points. This article presents a |
| 235 |
practical convex hull algorithm that combines the |
| 236 |
two-dimensional Quickhull Algorithm with the general |
| 237 |
dimension Beneath-Beyond Algorithm. It is similar to the |
| 238 |
randomized, incremental algorithms for convex hull and |
| 239 |
Delaunay triangulation. We provide empirical evidence that |
| 240 |
the algorithm runs faster when the input contains non-extreme |
| 241 |
points, and that it uses less memory. </p> |
| 242 |
<p>Computational geometry algorithms have traditionally |
| 243 |
assumed that input sets are well behaved. When an algorithm |
| 244 |
is implemented with floating point arithmetic, this |
| 245 |
assumption can lead to serious errors. We briefly describe a |
| 246 |
solution to this problem when computing the convex hull in |
| 247 |
two, three, or four dimensions. The output is a set of |
| 248 |
"thick" facets that contain all possible exact convex hulls |
| 249 |
of the input. A variation is effective in five or more |
| 250 |
dimensions. </p> |
| 251 |
</blockquote> |
| 252 |
<!-- Navigation links --> |
| 253 |
<hr> |
| 254 |
|
| 255 |
<p><b>Up:</b> <a href="http://www.geom.uiuc.edu/software/past-projects.html"><i>Past Software |
| 256 |
Projects of the Geometry Center</i></a> <br> |
| 257 |
<b>URL:</b> <a href="http://www.qhull.org">http://www.qhull.org</a> |
| 258 |
<br><b>To:</b> |
| 259 |
<a href="http://www.qhull.org/news">News</a> |
| 260 |
• <a href="http://www.qhull.org/download">Download</a> |
| 261 |
• <a href="http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.117.405">CiteSeer</a> |
| 262 |
• <a href=http://images.google.com/images?q=qhull&num=100>Images</a> |
| 263 |
• <a href="html/index.htm#TOC">Manual</a> |
| 264 |
• <a href="http://www.qhull.org/html/qh-faq.htm">FAQ</a> |
| 265 |
• <a href="html/qh-quick.htm#programs">Programs</a> |
| 266 |
• <a href="html/qh-quick.htm#options">Options</a> |
| 267 |
<!-- GC common information --></p> |
| 268 |
|
| 269 |
<hr> |
| 270 |
|
| 271 |
<p><a href="http://www.geom.uiuc.edu/"><img src="html/qh--geom.gif" alt="[HOME]" |
| 272 |
align="middle"></a> <i>The Geometry Center Home Page</i> </p> |
| 273 |
|
| 274 |
<p>Comments to: <a href="mailto:qhull@qhull.org">qhull@qhull.org</a> |
| 275 |
<br> |
| 276 |
Created: May 17 1995 --- <!-- hhmts start --> |
| 277 |
</body> |
| 278 |
</html> |
