Diffusion CADD_mesher (dev/incorporate-qhull) Browse

incorporate-qhull

index.htm
View Options

			<!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>
			<a href="http://www.qhull.org/download">Download</a>
			<a href="http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.117.405">CiteSeer</a>
			<a href=http://images.google.com/images?q=qhull&num=100>Images</a>
			<a href="html/index.htm#TOC">Manual</a>
			<a href="http://www.qhull.org/html/qh-faq.htm">FAQ</a>
			<a href="html/qh-quick.htm#programs">Programs</a>
			<a href="html/qh-quick.htm#options">Options</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 constrained Delaunay
			triangulations, triangulation of non-convex surfaces, mesh
			generation of non-convex objects, or medium-sized inputs in 9-D
			and higher. </p>

			<p>A serious bug was found in Qhull 2003.1. Please upgrade to 2010.1 or apply <a href="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 2010.1 2010/01/14</li>
			<li><a href="http://www.qhull.org/download">Download</a> Qhull</li>
			<li><a
			href="http://www.geom.uiuc.edu/graphics/pix/Special_Topics/Computational_Geometry/welcome.html">Examples
			</a>of Qhull output </li>
			<li><a href=http://gitorious.org/qhull/>Gitorious</a> C++ interface to Qhull
			(<a href="http://gitorious.org/qhull/pages/Home">wiki</a>, <a href="http://www.qhull.org/src/Changes.txt">changes</a>)
			<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://citeseerx.ist.psu.edu/showciting?doi=10.1.1.117.405&sort=cite">CiteSeer</a>
			and <a href="http://scholar.google.com/scholar?cites=6731193060570243661&hl=en&as_sdt=40000000">Google Scholar</a> references to Qhull
			</p>
			<li>
			<a href=http://www.google.com/search?as_q=qhull+-debian+-cvs+-gentoo+-pool+-mirrors&num=100>Google</a> Qhull,
			Qhull <a href="http://images.google.com/images?q=qhull&num=100">Images</a>,
			Qvoronoi <a href="http://home.scarlet.be/zoetrope/voronoi3d/index.htm">Models</a>,
			Qhull in <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 computational geometry functions: <a href=http://www.mathworks.com/access/helpdesk/help/techdoc/ref/convhulln.shtml>convhulln</a>
			<a href=http://www.mathworks.com/access/helpdesk/help/techdoc/ref/delaunayn.shtml>delaunayn</a>
			<a href=http://www.mathworks.com/access/helpdesk/help/techdoc/ref/griddata3.shtml>griddata3</a>
			<a href=http://www.mathworks.com/access/helpdesk/help/techdoc/ref/griddatan.shtml>griddatan</a>
			<a href=http://www.mathworks.com/access/helpdesk/help/techdoc/ref/tsearch.shtml>tsearch</a>
			<a href=http://www.mathworks.com/access/helpdesk/help/techdoc/ref/tsearchn.shtml>tsearchn</a>
			<a href=http://www.mathworks.com/access/helpdesk/help/techdoc/ref/voronoin.shtml>voronoin</a>. MATLAB R14 upgraded
			to Qhull 2002.1 and triangulated output ('Qt').
			</li>
			<li>The <a href="http://packages.debian.org/sid/octave3.2">Debian build</a> of
			<a href=http://www.octave.org/>GNU Octave</a> includes Qhull for computational geometry.
			<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>
			and <a href="http://www.imtek.uni-freiburg.de/simulation/mathematica/IMSweb/imsTOC/Interfaces/QHullInterfaceDocu.html">QHullInterface</a>
			<li><a href=http://www.geomview.org>Geomview</a> for 3-D and 4-D visualization of Qhull output
			</ul>
			</form>

			<p><b>Introduction</b>
			<ul>
			<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.cse.unsw.edu.au/~lambert/java/3d/hull.html"
			>Lambert's Java</a> visualization of convex hull algorithms </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/qh-quick.htm#programs">Programs</a> and <a href="html/qh-quick.htm#options">Options</a>
			<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/index.htm#description">Description</a> of 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="src/index.htm">Qhull functions</a>, macros, and data structures with source
			</ul>
			</td></tr></table>
			<li><a href="http://www.qhull.org/html/qh-faq.htm">Frequently</a> asked
			questions about Qhull</li>
			<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.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://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.cs.mcgill.ca/~fukuda/soft/cdd_home/cdd.html">Fukuda's
			cdd</a> program for halfspace intersection and convex hulls</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://directory.google.com/Top/Science/Math/Geometry/Computational_Geometry/Software/>Google's directory</a> for
			Science > Math > Geometry > Computational Geometry > Software
			<li><a href=http://www.algorithmic-solutions.com/enleda.htm>Leda</a>
			and <a href=http://www.cgal.org/>CGAL</a> libraries for writing computational
			geometry programs and other combinatorial algorithms
			<li><a href=http://www.mathtools.net/>Mathtools.net</a> of scientific and engineering
			software
			<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>
			<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.nnov.ru/~zny/skeleton/">Zolotykh's Skeleton</a> generates all extreme rays of a polyhedral cone using the Double Description Method</li>
			</ul>

			<p><b>FAQs and Newsgroups</b>
			<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: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="http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.117.405">CiteSeer</a> or <a
			href="http://portal.acm.org/citation.cfm?doid=235815.235821">www.acm.org</a>:
			</p>

			<blockquote>
			<p>Barber, C.B., Dobkin, D.P., and Huhdanpaa, H.T., "The
			Quickhull algorithm for convex hulls," <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>
			<a href="http://www.qhull.org/download">Download</a>
			<a href="http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.117.405">CiteSeer</a>
			<a href=http://images.google.com/images?q=qhull&num=100>Images</a>
			<a href="html/index.htm#TOC">Manual</a>
			<a href="http://www.qhull.org/html/qh-faq.htm">FAQ</a>
			<a href="html/qh-quick.htm#programs">Programs</a>
			<a href="html/qh-quick.htm#options">Options</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>

rCADDMESH/index.htm6b407609818fdev/incorporate-qhull

index.htmView Options

rCADDMESH/index.htm
6b407609818fdev/incorporate-qhull

index.htm
View Options