diff options
Diffstat (limited to 'src/qhull/index.htm')
| -rw-r--r-- | src/qhull/index.htm | 284 |
1 files changed, 284 insertions, 0 deletions
diff --git a/src/qhull/index.htm b/src/qhull/index.htm new file mode 100644 index 000000000..4ea7806c9 --- /dev/null +++ b/src/qhull/index.htm @@ -0,0 +1,284 @@ +<!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 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>Qhull 2015.2 introduces reentrant Qhull. It allows concurrent Qhull runs and simplifies the C++ interface to Qhull. +If you call Qhull from your program, you should use reentrant Qhull (libqhull_r) instead of qh_QHpointer (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 2015.2 2016/01/18</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=http://github.com/qhull/qhull/wiki>GitHub</a> C++ interface to Qhull + <li><a href="html/index.htm">Manual</a> for Qhull and rbox + <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>, + <a href="http://libra.msra.cn/Publication/232063/the-quickhull-algorithm-for-convex-hulls">Microsoft Academic</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>, + <a href="http://www.google.com/search?q=qhull&tbm=blg">Blogs</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/techdoc/ref/convhulln.html>convhulln</a> + <a href=http://www.mathworks.com/help/techdoc/ref/delaunayn.html>delaunayn</a> + <a href=http://www.mathworks.com/help/techdoc/ref/griddatan.html>griddatan</a> + <a href=http://www.mathworks.com/help/techdoc/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>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 <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> + and <a href="http://portal.uni-freiburg.de/imteksimulation/downloads/ims">QHullInterface</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://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/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="http://www.qhull.org/html/qh-faq.htm">Frequently</a> 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">Calling Qhull</a> from your program + <li><a href="src/libqhull_r/index.htm">Reentrant</a> Qhull functions, macros, and data structures with source + </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.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 (<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.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.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.nnov.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 + (Exaflop.org: <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://dl.acm.org/authorize?89250">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., "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> |