Homec4science
Diffusion CADD_mesher (dev/incorporate-qhull) Browse

rCADDMESH/html/qh-home.htm
dff2d0e64a79dev/incorporate-qhull

Last Change
Raw File

qh-home.htm
View Options

<!DOCTYPE HTML PUBLIC "-//IETF//DTD HTML//EN">
<html>
<head>
<title>Home page for Qhull</title>
</head>
<body>
<!-- Navigation links -->
<p><b>Up:</b> <a href="../past-projects.html"><i>Past Software
Projects of the Geometry Center</i></a> <br>
<b>URL:</b> <a href="http://www.geom.umn.edu/locate/qhull">http://www.geom.umn.edu/locate/qhull</a>
</p>
<hr>
<!-- Main text of document -->
<h1><a
href="/graphics/pix/Special_Topics/Computational_Geometry/cone.html"><img
src="html/qh--cone.gif" alt="[CONE]" align="middle" width="100"
height="100"></a> Home page for Qhull</h1>
<p>Qhull computes convex hulls, Delaunay triangulations,
halfspace intersections about a point, Voronoi diagrams, furthest-site Delaunay
triangulations, and furthest-site Voronoi diagrams. 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 computes volumes,
surface areas, and approximations to the convex hull.</p>
<p>Qhull does <i>not</i> support constrained Delaunay
triangulations, triangulation of non-convex surfaces, mesh
generation of non-convex objects, or medium-sized inputs in 9-D
and higher. </p>
<hr>
<ul>
<li><a href="/~bradb/qhull-news.html">News</a> about Qhull </li>
<li><a href="/~bradb/qhull-news.html#use">How</a> is Qhull used?</li>
<li><a href="/software/download/qhull.html">Download</a>
Qhull</li>
<li><a
href="/graphics/pix/Special_Topics/Computational_Geometry/welcome.html">Examples
</a>of Qhull output </li>
<li><a href="html/index.htm">Manual</a> for Qhull and rbox
<ul>
<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>
<li><a href="html/qh-faq.htm">Frequently</a> asked
questions about Qhull</li>
<li>MATLAB's qhull functions: <a href=http://www.mathworks.com/access/helpdesk/jhelp/techdoc/ref/convhulln.shtml>convhulln</a>
<a href=http://www.mathworks.com/access/helpdesk/jhelp/techdoc/ref/delaunayn.shtml>delaunayn</a>
<a href=http://www.mathworks.com/access/helpdesk/jhelp/techdoc/ref/griddata3.shtml>griddata3</a>
<a href=http://www.mathworks.com/access/helpdesk/jhelp/techdoc/ref/griddatan.shtml>griddatan</a>
<a href=http://www.mathworks.com/access/helpdesk/jhelp/techdoc/ref/tsearch.shtml>tsearch</a>
<a href=http://www.mathworks.com/access/helpdesk/jhelp/techdoc/ref/tsearchn.shtml>tsearchn</a>
<a href=http://www.mathworks.com/access/helpdesk/jhelp/techdoc/ref/voronoin.shtml>voronoin</a>
</li>
<li>Mathematica's Delaunay interface: <a href=http://www.mathsource.com/Content/Enhancements/Geometry/0211-251>qh-math</a>
<li><a href="qhull-mail.html">Send e-mail</a> to
qhull@geom.umn.edu </li>
<li><a href="qhull-bug-mail.html">Report bugs</a> to <a
href="mailto:qhull_bug@geom.umn.edu">qhull_bug@geom.umn.edu</a>
</ul>
<ul>
<li><a
href="http://www.ifor.math.ethz.ch/ifor/staff/fukuda/polyfaq/polyfaq.html">Fukuda's
introduction</a> to convex hulls, Delaunay
triangulations, Voronoi diagrams, and linear programming</li>
<li><a
href="http://www.cse.unsw.edu.au/~lambert/java/3d/hull.html">Lambert's
Java</a> visualization of convex hull algorithms </li>
<li><a
href="http://www.cs.sunysb.edu/~algorith/major_section/1.6.shtml">Stony
Brook</a> Algorithm Repository, computational geometry</li>
</ul>
<ul>
<li><a
href="http://netlib.bell-labs.com/netlib/voronoi/hull.html">Clarkson's
hull </a>program with exact arithmetic </li>
<li><a
href="http://www.ifor.math.ethz.ch/ifor/staff/fukuda/cdd_home/cdd.html">Fukuda's
cdd</a> program for halfspace intersection and convex hulls</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.algorithmic-solutions.com/as_html/research/research.html>Leda</a>
and CGAL libraries for writing computational
geometry programs and other combinatorial algorithms
<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,
</ul>
<ul>
<li><a href="http://www.geom.umn.edu/locate/cglist">Amenta's directory</a> of
computational geometry software </li>
<li><a
href="http://www.inria.fr/prisme/personnel/bronnimann/cgt/WWW.html">Bronnimann's
Computational</a> Geometry Tribune</li>
<li><a href="http://compgeom.cs.uiuc.edu/~jeffe/compgeom/compgeom.html">Erickson's
Computational</a> Geometry Pages and
<a href="http://compgeom.cs.uiuc.edu/~jeffe/compgeom/code.html">Software</a>
<li><a href="http://www.andrew.cmu.edu/user/sowen/mesh.html">Owen's Meshing</a> Research Corner
<li><a
href="http://www-users.informatik.rwth-aachen.de/~roberts/meshgeneration.html">Schneiders'
Finite Element</a> Mesh Generation page</li>
</ul>
<ul>
<li><a
href="http://exaflop.org/docs/cgafaq/">FAQ</a>
for computer graphics algorithms
(<a href="http://exaflop.org/docs/cgafaq/cga6.html">geometric</a> structures)
</li>
<li><a
href="http://www-unix.mcs.anl.gov/otc/Guide/faq/linear-programming-faq.html">FAQ
</a>for linear programming </li>
<li><a href="news:comp.graphics.algorithms">Newsgroup</a>:
comp.graphics.algorithms </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>
<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>. </p>
<p>For an article about Qhull, download <a
href="ftp://geom.umn.edu/pub/software/qhull-96.ps.Z">qhull-96.ps.Z</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>, Dec 1996. <a
href="http://www.acm.org/pubs/citations/journals/toms/1996-22-4/p469-barber/">http://www.acm.org</a>;
</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="../past-projects.html"><i>Past Software
Projects of the Geometry Center</i></a> <br>
<b>URL:</b> <a href="http://www.geom.umn.edu/locate/qhull">http://www.geom.umn.edu/locate/qhull</a>
<!-- GC common information --></p>
<hr>
<p><a href="/"><img src="/pix/home.gif" alt="[HOME]"
align="middle"></a> <i>The Geometry Center Home Page</i> </p>
<p>Comments to: <a href="/admin/mail/webmaster.html">webmaster@geom.umn.edu</a>
<br>
Created: May 17 1995 --- <!-- hhmts start --> Last modified: December 30, 1998<!-- hhmts end --> </p>
</body>
</html>
c4science · Help