diff options
| author | tamasmeszaros <meszaros.q@gmail.com> | 2022-01-19 16:18:17 +0300 |
|---|---|---|
| committer | tamasmeszaros <meszaros.q@gmail.com> | 2022-04-04 13:43:25 +0300 |
| commit | 1070d71da66a60cc965293930006cb9c281b73bf (patch) | |
| tree | 13fb4894b96ca0ef5eff65dc35569061a02b46d6 /src/qhull/html/index.htm | |
| parent | 057232a2756dad131aba2b989e558bb1560eed93 (diff) | |
Use upstream Qhull, remove duplication in deps and src
REALfloat is not defined to 0 on all platforms.
Diffstat (limited to 'src/qhull/html/index.htm')
| -rw-r--r-- | src/qhull/html/index.htm | 935 |
1 files changed, 0 insertions, 935 deletions
diff --git a/src/qhull/html/index.htm b/src/qhull/html/index.htm deleted file mode 100644 index ca4789b47..000000000 --- a/src/qhull/html/index.htm +++ /dev/null @@ -1,935 +0,0 @@ -<!DOCTYPE HTML PUBLIC "-//IETF//DTD HTML//EN"> -<html> - -<head> -<meta http-equiv="Content-Type" -content="text/html; charset=iso-8859-1"> -<meta name="GENERATOR" content="Microsoft FrontPage 2.0"> -<title>Qhull manual</title> -<!-- Navigation links -NOTE -- verify all links by 'grep href=' 'grep name=' add # 'sort /+7' - index.htm ---> -</head> - -<body> - -<p><a name="TOP"><b>Up:</b></a> <a -href="http://www.qhull.org">Home page</a> for Qhull<br> -<b>Up:</b><a -href="http://www.qhull.org/news">News</a> about Qhull<br> -<b>Up:</b> <a href="http://www.qhull.org/html/qh-faq.htm">FAQ</a> about Qhull<br> -<b>To:</b> <a href="#TOC">Qhull manual: Table of Contents</a> -(please wait while loading) <br> -<b>To:</b> <a href="qh-quick.htm#programs">Programs</a> -• <a href="qh-quick.htm#options">Options</a> -• <a href="qh-opto.htm#output">Output</a> -• <a href="qh-optf.htm#format">Formats</a> -• <a href="qh-optg.htm#geomview">Geomview</a> -• <a href="qh-optp.htm#print">Print</a> -• <a href="qh-optq.htm#qhull">Qhull</a> -• <a href="qh-optc.htm#prec">Precision</a> -• <a href="qh-optt.htm#trace">Trace</a> -• <a href="../src/libqhull_r/index.htm">Functions</a><br> - -<hr> -<!-- Main text of document --> -<h1><a -href="http://www.geom.uiuc.edu/graphics/pix/Special_Topics/Computational_Geometry/fixed.html"><img -src="qh--rand.gif" alt="[random-fixed]" align="middle" -width="100" height="100"></a> Qhull manual </h1> - -<p>Qhull is a general dimension code for computing convex hulls, -Delaunay triangulations, halfspace intersections about a point, Voronoi -diagrams, furthest-site Delaunay triangulations, and -furthest-site Voronoi diagrams. These structures have -applications in science, engineering, statistics, and -mathematics. See <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. For a detailed -introduction, see O'Rourke [<a href="#orou94">'94</a>], <i>Computational -Geometry in C</i>. -</p> - -<p>There are six programs. Except for rbox, they use -the same code. Each program includes instructions and examples. -<blockquote> -<ul> -<li><a href="qconvex.htm">qconvex</a> -- convex hulls -<li><a href="qdelaun.htm">qdelaunay</a> -- Delaunay triangulations and - furthest-site Delaunay triangulations -<li><a href="qhalf.htm">qhalf</a> -- halfspace intersections about a point -<li><a href="qhull.htm">qhull</a> -- all structures with additional options -<li><a href="qvoronoi.htm">qvoronoi</a> -- Voronoi diagrams and - furthest-site Voronoi diagrams -<li><a href="rbox.htm">rbox</a> -- generate point distributions for qhull -</ul> -</blockquote> - -<p>Qhull implements the Quickhull algorithm for computing the -convex hull. Qhull includes options -for hull volume, facet area, multiple output formats, and -graphical output. It can approximate a convex hull. </p> - -<p>Qhull handles roundoff errors from floating point -arithmetic. It generates a convex hull with "thick" facets. -A facet's outer plane is clearly above all of the points; -its inner plane is clearly below the facet's vertices. Any -exact convex hull must lie between the inner and outer plane. - -<p>Qhull uses merged facets, triangulated output, or joggled -input. Triangulated output triangulates non-simplicial, merged -facets. Joggled input also -guarantees simplicial output, but it -is less accurate than merged facets. For merged facets, Qhull -reports the maximum outer and inner plane. - -<p><i>Brad Barber, Arlington, MA</i></p> - -<p><b>Copyright © 1995-2015 C.B. Barber</b></p> - -<hr> - -<h2><a href="#TOP">»</a><a name="TOC">Qhull manual: Table of -Contents </a></h2> - -<ul> - <li><a href="#when">When</a> to use Qhull - <ul> - <li><a href="http://www.qhull.org/news">News</a> for Qhull - with new features and reported bugs. - <li><a href="http://www.qhull.org">Home</a> for Qhull with additional URLs - (<a href=index.htm>local copy</a>) - <li><a href="http://www.qhull.org/html/qh-faq.htm">FAQ</a> for Qhull (<a href="qh-faq.htm">local copy</a>) - <li><a href="http://www.qhull.org/download">Download</a> Qhull (<a href=qh-get.htm>local copy</a>) - <li><a href="qh-quick.htm#programs">Quick</a> reference for Qhull and its <a href="qh-quick.htm#options">options</a> - <p> - <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="qhull.txt">qhull.txt</a> - Unix manual page - </ul> - <p> - <li><a href="#description">Description</a> of Qhull - <ul> - <li><a href="#definition">de</a>finition • <a - href="#input">in</a>put • <a href="#output">ou</a>tput - • <a href="#algorithm">al</a>gorithm • <a - href="#structure">da</a>ta structure </li> - <li><a href="qh-impre.htm">Imprecision</a> in Qhull</li> - <li><a href="qh-impre.htm#joggle">Merged facets</a> or joggled input - <li><a href="qh-eg.htm">Examples</a> of Qhull</li> - </ul> - <p> - <li><a href=qh-quick.htm#programs>Qhull programs</a>, with instructions and examples - <ul> - <li><a href="qconvex.htm">qconvex</a> -- convex hulls - <li><a href="qdelaun.htm">qdelaunay</a> -- Delaunay triangulations and - furthest-site Delaunay triangulations - <li><a href="qhalf.htm">qhalf</a> -- halfspace intersections about a point - <li><a href="qhull.htm">qhull</a> -- all structures with additional options - <li><a href="qvoronoi.htm">qvoronoi</a> -- Voronoi diagrams and - furthest-site Voronoi diagrams - <li><a href="rbox.htm">rbox</a> -- generate point distributions for qhull - </ul> - <p> - <li><a href="qh-quick.htm#options">Qhull options</a><ul> - <li><a href="qh-opto.htm#output">Output</a> formats</li> - <li><a href="qh-optf.htm#format">Additional</a> I/O - formats</li> - <li><a href="qh-optg.htm#geomview">Geomview</a> - output options</li> - <li><a href="qh-optp.htm#print">Print</a> options</li> - <li><a href="qh-optq.htm#qhull">Qhull</a> control - options</li> - <li><a href="qh-optc.htm#prec">Precision</a> options</li> - <li><a href="qh-optt.htm#trace">Trace</a> options</li> - </ul> - </li> - <p> - <li><a href="#geomview">Geomview</a>, Qhull's graphical viewer</li> - <ul> - <li><a href="#geomview-install">Installing Geomview</a></li> - <li><a href="#geomview-use">Using Geomview</a></li> - <li><a href="#geomview-win">Building Geomview for Windows</a></li> - </ul> - <p> - <li><a href="qh-code.htm">Qhull internals</a><ul> - <li><a href="qh-code.htm#reentrant">Reentrant</a> Qhull</li> - <li><a href="qh-code.htm#convert">How to convert</a> code to reentrant Qhull</li> - <li><a href="qh-code.htm#64bit">Qhull</a> on 64-bit computers</li> - <li><a href="qh-code.htm#cpp">Calling</a> Qhull - from C++ programs</li> - <li><a href="qh-code.htm#library">Calling</a> Qhull - from C programs</li> - <li><a href="qh-code.htm#performance">Performance</a> - of Qhull</li> - <li><a href="qh-code.htm#enhance">Enhancements</a> to - Qhull</li> - <li><a href="../src/libqhull_r/index.htm">Reentrant</a> Qhull functions, macros, and - data structures </li> - <li><a href="../src/libqhull/index.htm">Qhull</a> functions, macros, and - data structures </li> - </ul> - </li> - <p> - <li>Related URLs - <ul> - - <li><a href="news:comp.graphics.algorithms">Newsgroup</a>: - comp.graphics.algorithms - <li><a - href="http://www.faqs.org/faqs/graphics/algorithms-faq/">FAQ</a> for computer graphics algorithms and - Exaflop's <a href="http://exaflop.org/docs/cgafaq/cga6.html">geometric</a> structures. - <li>Amenta's <a href="http://www.geom.uiuc.edu/software/cglist">Directory - of Computational Geometry Software </a></li> - <li>Erickson's <a - href="http://compgeom.cs.uiuc.edu/~jeffe/compgeom/code.html">Computational - Geometry Software</a> </li> - <li>Fukuda's <a - href="http://www.cs.mcgill.ca/~fukuda/soft/polyfaq/polyfaq.html"> - introduction</a> to convex hulls, Delaunay triangulations, - Voronoi diagrams, and linear programming. - <li>Stony Brook's <a - href="http://www.cs.sunysb.edu/~algorith/major_section/1.6.shtml">Algorithm Repository</a> on computational geometry. - </li> - </ul> - <p> - <li><a href="#bugs">What to do</a> if something goes wrong</li> - <li><a href="#email">Email</a></li> - <li><a href="#authors">Authors</a></li> - <li><a href="#ref">References</a></li> - <li><a href="#acknowledge">Acknowledgments</a></li> -</ul> -<h2><a href="#TOC">»</a><a name="when">When to use Qhull</a></h2> -<blockquote> - -<p>Qhull constructs convex hulls, Delaunay triangulations, -halfspace intersections about a point, Voronoi diagrams, furthest-site Delaunay -triangulations, and furthest-site Voronoi diagrams.</p> - -<p>For convex hulls and halfspace intersections, Qhull may be used -for 2-d upto 8-d. For Voronoi diagrams and Delaunay triangulations, Qhull may be -used for 2-d upto 7-d. In higher dimensions, the size of the output -grows rapidly and Qhull does not work well with virtual memory. -If <i>n</i> is the size of -the input and <i>d</i> is the dimension (d>=3), the size of the output -and execution time -grows by <i>n^(floor(d/2)</i> -[see <a href=qh-code.htm#performance>Performance</a>]. For example, do -not try to build a 16-d convex hull of 1000 points. It will -have on the order of 1,000,000,000,000,000,000,000,000 facets. - -<p>On a 600 MHz Pentium 3, Qhull computes the 2-d convex hull of -300,000 cocircular points in 11 seconds. It computes the -2-d Delaunay triangulation and 3-d convex hull of 120,000 points -in 12 seconds. It computes the -3-d Delaunay triangulation and 4-d convex hull of 40,000 points -in 18 seconds. It computes the -4-d Delaunay triangulation and 5-d convex hull of 6,000 points -in 12 seconds. It computes the -5-d Delaunay triangulation and 6-d convex hull of 1,000 points -in 12 seconds. It computes the -6-d Delaunay triangulation and 7-d convex hull of 300 points -in 15 seconds. It computes the -7-d Delaunay triangulation and 8-d convex hull of 120 points -in 15 seconds. It computes the -8-d Delaunay triangulation and 9-d convex hull of 70 points -in 15 seconds. It computes the -9-d Delaunay triangulation and 10-d convex hull of 50 points -in 17 seconds. The 10-d convex hull of 50 points has about 90,000 facets. - -<!-- 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>This is a big package with many options. It is one of the -fastest available. It is the only 3-d code that handles precision -problems due to floating point arithmetic. For example, it -implements the identity function for extreme points (see <a -href="qh-impre.htm">Imprecision in Qhull</a>). </p> - -<p>[2016] A newly discovered, bad case for Qhull is multiple, nearly incident points within a 10^-13 ball of 3-d and higher -Delaunay triangulations (input sites in the unit cube). Nearly incident points within substantially -smaller or larger balls are OK. Error QH6271 is reported if a problem occurs. A future release of Qhull -will handle this case. For more information, see "Nearly coincident points on an edge" in <a href="../html/qh-impre.htm#limit">Limitations of merged facets</a> - -<p>If you need a short code for convex hull, Delaunay -triangulation, or Voronoi volumes consider Clarkson's <a -href="http://www.netlib.org/voronoi/hull.html">hull -program</a>. If you need 2-d Delaunay triangulations consider -Shewchuk's <a href="http://www.cs.cmu.edu/~quake/triangle.html">triangle -program</a>. It is much faster than Qhull and it allows -constraints. Both programs use exact arithmetic. They are in <a -href="http://www.netlib.org/voronoi/">http://www.netlib.org/voronoi/</a>. - -<p>If your input is in general position (i.e., no coplanar or colinear points), -<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/"documentation-ru</a/>) -or Qhull <a -href="http://www.qhull.org/download">version -1.0</a> may meet your needs. Both programs detect precision problems, -but do not handle them.</p> - -<p><a href=http://www.cgal.org>CGAL</a> is a library of efficient and reliable -geometric algorithms. It uses C++ templates and the Boost library to produce dimension-specific -code. This allows more efficient use of memory than Qhull's general-dimension -code. CGAL simulates arbitrary precision while Qhull handles round-off error -with thick facets. Compare the two approaches with <a href="http://doc.cgal.org/latest/Manual/devman_robustness.html">Robustness Issues in CGAL</a>, -and <a href+"qh-impre.htm">Imprecision in Qhull</a>. - - -<p><a href=http://www.algorithmic-solutions.com/enleda.htm>Leda</a> is a -library for writing computational -geometry programs and other combinatorial algorithms. It -includes routines for computing 3-d convex -hulls, 2-d Delaunay triangulations, and 3-d Delaunay triangulations. -It provides rational arithmetic and graphical output. It runs on most -platforms. - -<p>If your problem is in high dimensions with a few, -non-simplicial facets, try Fukuda's <a -href="http://www.cs.mcgill.ca/~fukuda/soft/cdd_home/cdd.html">cdd</a>. -It is much faster than Qhull for these distributions. </p> - -<p>Custom software for 2-d and 3-d convex hulls may be faster -than Qhull. Custom software should use less memory. Qhull uses -general-dimension data structures and code. The data structures -support non-simplicial facets.</p> - -<p>Qhull is not suitable for mesh generation or triangulation of -arbitrary surfaces. You may use Qhull if the surface is convex or -completely visible from an interior point (e.g., a star-shaped -polyhedron). First, project each site to a sphere that is -centered at the interior point. Then, compute the convex hull of -the projected sites. The facets of the convex hull correspond to -a triangulation of the surface. For mesh generation of arbitrary -surfaces, see <a -href="http://www.robertschneiders.de/meshgeneration/meshgeneration.html">Schneiders' -Finite Element Mesh Generation</a>.</p> - -<p>Qhull is not suitable for constrained Delaunay triangulations. -With a lot of work, you can write a program that uses Qhull to -add constraints by adding additional points to the triangulation.</p> - -<p>Qhull is not suitable for the subdivision of arbitrary -objects. Use <tt>qdelaunay</tt> to subdivide a convex object.</p> - -</blockquote> -<h2><a href="#TOC">»</a><a name="description">Description of -Qhull </a></h2> -<blockquote> - -<h3><a href="#TOC">»</a><a name="definition">definition</a></h3> -<blockquote> - -<p>The <i>convex hull</i> of a point set <i>P</i> is the smallest -convex set that contains <i>P</i>. If <i>P</i> is finite, the -convex hull defines a matrix <i>A</i> and a vector <i>b</i> such -that for all <i>x</i> in <i>P</i>, <i>Ax+b <= [0,...]</i>. </p> - -<p>Qhull computes the convex hull in 2-d, 3-d, 4-d, and higher -dimensions. Qhull represents a convex hull as a list of facets. -Each facet has a set of vertices, a set of neighboring facets, -and a halfspace. A halfspace is defined by a unit normal and an -offset (i.e., a row of <i>A</i> and an element of <i>b</i>). </p> - -<p>Qhull accounts for round-off error. It returns -"thick" facets defined by two parallel hyperplanes. The -outer planes contain all input points. The inner planes exclude -all output vertices. See <a href="qh-impre.htm#imprecise">Imprecise -convex hulls</a>.</p> - -<p>Qhull may be used for the Delaunay triangulation or the -Voronoi diagram of a set of points. It may be used for the -intersection of halfspaces. </p> - -</blockquote> -<h3><a href="#TOC">»</a><a name="input">input format</a></h3> -<blockquote> - -<p>The input data on <tt>stdin</tt> consists of:</p> - -<ul> - <li>first line contains the dimension</li> - <li>second line contains the number of input points</li> - <li>remaining lines contain point coordinates</li> -</ul> - -<p>For example: </p> - -<pre> - 3 #sample 3-d input - 5 - 0.4 -0.5 1.0 - 1000 -1e-5 -100 - 0.3 0.2 0.1 - 1.0 1.0 1.0 - 0 0 0 -</pre> - -<p>Input may be entered by hand. End the input with a control-D -(^D) character. </p> - -<p>To input data from a file, use I/O redirection or '<a -href="qh-optt.htm#TI">TI file</a>'. The filename may not -include spaces or quotes.</p> - -<p>A comment starts with a non-numeric character and continues to -the end of line. The first comment is reported in summaries and -statistics. With multiple <tt>qhull</tt> commands, use option '<a -href="qh-optf.htm#FQ">FQ</a>' to place a comment in the output.</p> - -<p>The dimension and number of points can be reversed. Comments -and line breaks are ignored. Error reporting is better if there -is one point per line.</p> - -</blockquote> -<h3><a href="#TOC">»</a><a name="option">option format</a></h3> -<blockquote> - -<p>Use options to specify the output formats and control -Qhull. The <tt>qhull</tt> program takes all options. The -other programs use a subset of the options. They disallow -experimental and inappropriate options. - -<blockquote> -<ul> -<li> -qconvex == qhull -<li> -qdelaunay == qhull d Qbb -<li> -qhalf == qhull H -<li> -qvoronoi == qhull v Qbb -</ul> -</blockquote> - -<p>Single letters are used for output formats and precision -constants. The other options are grouped into menus for formats -('<a href="qh-optf.htm#format">F</a>'), Geomview ('<a -href="qh-optg.htm#geomview">G </a>'), printing ('<a -href="qh-optp.htm#print">P</a>'), Qhull control ('<a -href="qh-optq.htm#qhull">Q </a>'), and tracing ('<a -href="qh-optt.htm#trace">T</a>'). The menu options may be listed -together (e.g., 'GrD3' for 'Gr' and 'GD3'). Options may be in any -order. Capitalized options take a numeric argument (except for '<a -href="qh-optp.htm#PG">PG</a>' and '<a href="qh-optf.htm#format">F</a>' -options). Use option '<a href="qh-optf.htm#FO">FO</a>' to print -the selected options.</p> - -<p>Qhull uses zero-relative indexing. If there are <i>n</i> -points, the index of the first point is <i>0</i> and the index of -the last point is <i>n-1</i>.</p> - -<p>The default options are:</p> - -<ul> - <li>summary output ('<a href="qh-opto.htm#s">s</a>') </li> - <li>merged facets ('<a href="qh-optc.htm#C0">C-0</a>' in 2-d, - 3-d, 4-d; '<a href="qh-optq.htm#Qx">Qx</a>' in 5-d and - up)</li> -</ul> - -<p>Except for bounding box -('<a href="qh-optq.htm#Qbk">Qbk:n</a>', etc.), drop facets -('<a href="qh-optp.htm#Pdk">Pdk:n</a>', etc.), and -Qhull command ('<a href="qh-optf.htm#FQ">FQ</a>'), only the last -occurence of an option counts. -Bounding box and drop facets may be repeated for each dimension. -Option 'FQ' may be repeated any number of times. - -<p>The Unix <tt>tcsh</tt> and <tt>ksh </tt>shells make it easy to -try out different options. In Windows 95, use a command window with <tt>doskey</tt> -and a window scroller (e.g., <tt>peruse</tt>). </p> - -</blockquote> -<h3><a href="#TOC">»</a><a name="output">output format</a></h3> -<blockquote> - -<p>To write the results to a file, use I/O redirection or '<a -href="qh-optt.htm#TO">TO file</a>'. Windows 95 users should use -'TO file' or the console. If a filename is surrounded by single quotes, -it may include spaces. -</p> - -<p>The default output option is a short summary ('<a -href="qh-opto.htm#s">s</a>') to <tt>stdout</tt>. There are many -others (see <a href="qh-opto.htm">output</a> and <a -href="qh-optf.htm">formats</a>). You can list vertex incidences, -vertices and facets, vertex coordinates, or facet normals. You -can view Qhull objects with Geomview, Mathematica, or Maple. You can -print the internal data structures. You can call Qhull from your -application (see <a href="qh-code.htm#library">Qhull library</a>).</p> - -<p>For example, 'qhull <a href="qh-opto.htm#o">o</a>' lists the -vertices and facets of the convex hull. </p> - -<p>Error messages and additional summaries ('<a -href="qh-opto.htm#s">s</a>') go to <tt>stderr</tt>. Unless -redirected, <tt>stderr</tt> is the console.</p> - -</blockquote> -<h3><a href="#TOC">»</a><a name="algorithm">algorithm</a></h3> -<blockquote> - -<p>Qhull implements the Quickhull algorithm for convex hull -[Barber et al. <a href="#bar-dob96">'96</a>]. This algorithm -combines the 2-d Quickhull algorithm with the <em>n</em>-d -beneath-beyond algorithm [c.f., Preparata & Shamos <a -href="#pre-sha85">'85</a>]. It is similar to the randomized -algorithms of Clarkson and others [Clarkson & Shor <a -href="#cla-sho89">'89</a>; Clarkson et al. <a href="#cla-meh93">'93</a>; -Mulmuley <a href="#mulm94">'94</a>]. For a demonstration, see <a -href="qh-eg.htm#how">How Qhull adds a point</a>. The main -advantages of Quickhull are output sensitive performance (in -terms of the number of extreme points), reduced space -requirements, and floating-point error handling. </p> - -</blockquote> -<h3><a href="#TOC">»</a><a name="structure">data structures</a></h3> -<blockquote> - -<p>Qhull produces the following data structures for dimension <i>d</i>: -</p> - -<ul> - <li>A <em>coordinate</em> is a real number in floating point - format. </li> - <li>A <em>point</em> is an array of <i>d</i> coordinates. - With option '<a href="qh-optq.htm#QJn">QJ</a>', the - coordinates are joggled by a small amount. </li> - <li>A <em>vertex</em> is an input point. </li> - <li>A <em>hyperplane</em> is <i>d</i> normal coefficients and - an offset. The length of the normal is one. The - hyperplane defines a halfspace. If <i>V</i> is a normal, <i>b</i> - is an offset, and <i>x</i> is a point inside the convex - hull, then <i>Vx+b <0</i>.</li> - <li>An <em>outer plane</em> is a positive - offset from a hyperplane. When Qhull is done, all points - will be below all outer planes.</li> - <li>An <em>inner plane</em> is a negative - offset from a hyperplane. When Qhull is done, all - vertices will be above the corresponding inner planes.</li> - <li>An <em>orientation</em> is either 'top' or 'bottom'. It is the - topological equivalent of a hyperplane's geometric - orientation. </li> - <li>A <em>simplicial facet</em> is a set of - <i>d</i> neighboring facets, a set of <i>d</i> vertices, a - hyperplane equation, an inner plane, an outer plane, and - an orientation. For example in 3-d, a simplicial facet is - a triangle. </li> - <li>A <em>centrum</em> is a point on a facet's hyperplane. A - centrum is the average of a facet's vertices. Neighboring - facets are <em>convex</em> if each centrum is below the - neighbor facet's hyperplane. </li> - <li>A <em>ridge</em> is a set of <i>d-1</i> vertices, two - neighboring facets, and an orientation. For example in - 3-d, a ridge is a line segment. </li> - <li>A <em>non-simplicial facet</em> is a set of ridges, a - hyperplane equation, a centrum, an outer plane, and an - inner plane. The ridges determine a set of neighboring - facets, a set of vertices, and an orientation. Qhull - produces a non-simplicial facet when it merges two facets - together. For example, a cube has six non-simplicial - facets. </li> -</ul> - -<p>For examples, use option '<a href="qh-opto.htm#f">f</a>'. See <a -href="../src/libqhull/qh-poly.htm">polyhedron operations</a> for further -design documentation. </p> - -</blockquote> -<h3><a href="#TOC">»</a>Imprecision in Qhull</h3> -<blockquote> - -<p>See <a href="qh-impre.htm">Imprecision in Qhull</a> and <a href="qh-impre.htm#joggle">Merged facets or joggled input</a></p> - -</blockquote> -<h3><a href="#TOC">»</a>Examples of Qhull</h3> -<blockquote> - -<p>See <a href="qh-eg.htm">Examples of Qhull</a>. Most of these examples require <a href="#geomview">Geomview</a>. -Some of the examples have <a -href="http://www.geom.uiuc.edu/graphics/pix/Special_Topics/Computational_Geometry/welcome.html">pictures -</a>.</p> - -</blockquote> -</blockquote> -<h2><a href="#TOC">»</a>Options for using Qhull </h2> -<blockquote> - -<p>See <a href="qh-quick.htm#options">Options</a>.</p> - -</blockquote> -<h2><a href="#TOC">»</a>Qhull internals </h2> -<blockquote> - -<p>See <a href="qh-code.htm">Internals</a>.</p> - -</blockquote> -<h2><a href="#TOC">»</a><a name="geomview">Geomview, Qhull's -graphical viewer</a></h2> -<blockquote> - -<p><a href="http://www.geomview.org">Geomview</a> -is an interactive geometry viewing program. -Geomview provides a good visualization of Qhull's 2-d and 3-d results. - -<p>Qhull includes <a href="qh-eg.htm">Examples of Qhull</a> that may be viewed with Geomview. - -<p>Geomview can help visulalize a 3-d Delaunay triangulation or the surface of a 4-d convex hull, -Use option '<a href="qh-optq.htm#QVn">QVn</a>' to select the 3-D facets adjacent to a vertex. - -<p>You may use Geomview to create movies that animate your objects (c.f., <a href="http://www.geomview.org/FAQ/answers.shtml#mpeg">How can I create a video animation?</a>). -Geomview helped create the <a href="http://www.geom.uiuc.edu/video/">mathematical videos</a> "Not Knot", "Outside In", and "The Shape of Space" from the Geometry Center. - - -<h3><a href="#TOC">»</a><a name="geomview-install">Installing Geomview</a></h3> -<blockquote> - -<p>Geomview is an <a href=http://sourceforge.net/projects/geomview>open source project</a> -under SourceForge. - -<p> -For build instructions see -<a href="http://www.geomview.org/download/">Downloading Geomview</a>. -Geomview builds under Linux, Unix, Macintosh OS X, and Windows. - -<p>Geomview has <a href="https://packages.debian.org/search?keywords=geomview">installable packages</a> for Debian and Ubuntu. -The OS X build needs Xcode, an X11 SDK, and Lesstif or Motif. -The Windows build uses Cygwin (see <a href="#geomview-win">Building Geomview</a> below for instructions). - -<p>If using Xforms (e.g., for Geomview's <a href="http://www.geomview.org/docs/html/Modules.html">External Modules</a>), install the 'libXpm-devel' package from cygwin and move the xforms directory into your geomview directory, e.g.,<br><tt>mv xforms-1.2.4 geomview-1.9.5/xforms</tt> - -<p>Geomview's <a href="http://www.geom.uiuc.edu/software/geomview/docs/NDview/manpagehelp.html">ndview<a/> provides multiple views into 4-d and higher objects. -This module is out-of-date (<a href="http://sourceforge.net/p/geomview/mailman/message/2004152/">geomview-users: 4dview</a>). -Download NDview-sgi.tar.Z at <a href="ftp://www.geom.uiuc.edu/pub/software/geomview/newpieces/sgi">newpieces</a> and 4dview at <a href="https://stuff.mit.edu/afs/sipb/project/3d/arch/sgi_62/lib/Geomview/modules/">Geomview/modules</a>. - -</blockquote> -<h3><a href="#TOC">»</a><a name="geomview-use">Using Geomview</a></h3> -<blockquote> - -<p>Use Geomview to view <a href="qh-eg.htm">Examples of Qhull</a>. You can spin the convex hull, fly a camera through its facets, -and see how Qhull produces thick facets in response to round-off error. - -<p>Follow these instructions to view 'eg,01.cube' from Examples of Qhull -<ol> -<li>Launch an XTerm command shell -<ul> -<li>If needed, start the X terminal server, Use 'xinit' or 'startx' in /usr/X11R6/bin<br><tt>xinit -- -multiwindow -clipboard</tt><br><tt>startx</tt> -<li>Start an XTerm command shell. In Windows, click the Cygwin/bash icon on your desktop. -<li>Set the DISPLAY variable, e.g.,<br><tt>export DISPLAY=:0</tt><br><tt>export DISPLAY=:0 >>~/.bashenv</tt> -</ul> -<li>Use Qhull's <a href="qh-optg.htm">Geomview options</a> to create a geomview object -<ul> -<li><tt>rbox c D3 | qconvex G >eg.01.cube</tt> -<li>On windows, convert the output to Unix text format with 'd2u'<br><tt>rbox c D3 | qconvex G | d2u >eg.01.cube</tt><br><tt>d2u eg.*</tt> -</ul> -<li>Run Geomview -<ul> -<li>Start Geomview with your example<br><tt>./geomview eg.01.cube</tt> -<li>Follow the instructions in <a href="http://www.geomview.org/docs/html/Tutorial.html">Gemoview Tutorial</a> -<li>Geomview creates the <i>Geomview control panel</i> with Targets and External Module, the <i>Geomview toolbar</i> with buttons for controlling Geomview, and the <i>Geomview camera window</i> showing a cube. -<li>Clear the camera window by selecting your object in the Targets list and 'Edit > Delete' or 'dd' -<li>Load the <i>Geomview files panel</i>. Select 'Open' in the 'File' menu. -<li>Set 'Filter' in the files panel to your example directory followed by '/*' (e.g., '/usr/local/qhull-2015.2/eg/*') -<li>Click 'Filter' in the files panel to view your examples in the 'Files' list. -<li>Load another example into the camera window by selecting it and clicking 'OK'. -<li>Review the instructions for <a href="http://www.geomview.org/docs/html/Interaction.html">Interacting with Geomview</a> -<li>When viewing multiple objects at once, you may want to turn off normalization. In the 'Inspect > Apperance' control panel, set 'Normalize' to 'None'. -</ul> -</ol> - -<p>Geomview defines GCL (a textual API for controlling Geomview) and OOGL (a textual file format for defining objects). -<ul> -<li>To control Geomview, you may use any program that reads and writes from stdin and stdout. For example, it could report Qhull's information about a vertex identified by a double-click 'pick' event. -<li><a href="http://www.geomview.org/docs/html/GCL.html">GCL</a> command language for controlling Geomview -<li><a href="http://www.geomview.org/docs/html/OOGL-File-Formats.html">OOGL</a> file format for defining objects (<a href="http://www.geomview.org/docs/oogltour.html">tutorial</a>). -<li><a href="http://www.geomview.org/docs/html/Modules.html">External Modules</a> for interacting with Geomview via GCL -<li>Interact with your objects via <a href="http://www.geomview.org/docs/html/pick.html">pick</a> commands in response to right-mouse double clicks. Enable pick events with the <a href="http://www.geomview.org/docs/html/interest.html">interest</a> command. -</ul> - -</blockquote> -<h3><a href="#TOC">»</a><a name="geomview-win">Building Geomview for Windows</a></h3> -<blockquote> - -<p>Compile Geomview under Cygwin. For detailed instructions, see -<a href="http://www.ee.surrey.ac.uk/Personal/L.Wood/software/SaVi/building-under-Windows/" ->Building Savi and Geomview under Windows</a>. These instructions are somewhat out-of-date. Updated -instructions follow. - -<p>How to compile Geomview under 32-bit Cygwin (October 2015)</p> -<ol> -<li><b>Note:</b> L. Wood has run into multiple issues with Geomview on Cygwin. He recommends Virtualbox/Ubuntu -and a one-click install of geomview via the Ubuntu package. See his Savi/Geomview link above. -<li>Install 32-bit <a href="http://cygwin.com/">Cygwin</a> as follows. -For additional guidance, see Cygwin's <a href="https://cygwin.com/install.html">Installing and Updating Cygwin Packages</a> -and <a href="http://www.qhull.org/road/road-faq/xml/cmdline.xml#setup-cygwin">Setup cygwin</a>. -<ul> -<li>Launch the cygwin installer. -<li>Select a mirror from <a href="http://cygwin.com/mirrors.html">Cygwin mirrors</a> (e.g., http://mirrors.kernel.org/sourceware/cygwin/ in California). -<li>Select the packages to install. Besides the cygwin packages listed in the Savi/Windows instructions consider adding -<ul> -<li><b>Default</b> -- libXm-devel (required for /usr/include/Xm/Xm.h) -<li><b>Devel</b> -- bashdb, gcc-core (in place of gcc), gdb -<li><b>Lib</b> -- libGL-devel, libGLU1 (required, obsolete), libGLU-devel (required, obsolete), libjpeg-devel(XForms), libXext-devel (required), libXpm-devel (Xforms) -libGL and lib -<li><b>Math</b> -- bc -<li><b>Net</b> -- autossh, inetutils, openssh -<li><b>System</b> -- chere -<li><b>Utils</b> -- dos2unix (required for qhull), keychain -<li>If installing perl, ActiveState Perl may be a better choice than cygwin's perl. Perl is not used by Geomview or Qhull. -<li><a href="https://cygwin.com/cgi-bin2/package-grep.cgi">Cygwin Package Search</a> -- Search for cygwin programs and packages -</ul> -<li>Click 'Next' to download and install the packages. -<li>If the download is incomplete, try again. -<li>If you try again after a successful install, cygwin will uninstall and reinstall all modules.. -<li>Click on the 'Cywin Terminal' icon on the Desktop. It sets up a user directory in /home from /etc/skel/... -<li>Mount your disk drives<br>mount c: /c # Ignore the warning /c does not exist -</ul> -<li>Consider installing the <a href="http://www.qhull.org/bash/doc/road-bash.html">Road Bash</a> scripts (/etc/road-*) from <a href="http://www.qhull.org/road/">Road</a>. -They define aliases and functions for Unix command shells (Unix, Linux, Mac OS X, Windows), -<ul> -<li>Download Road Bash and unzip the downloaded file -<li>Copy .../bash/etc/road-* to the Cywin /etc directory (by default, C:\cygwin\etc). -<li>Using the cygwin terminal, convert the road scripts to Unix format<br>d2u /etc/road-* -<li>Try it<br>source /etc/road-home.bashrc -<li>Install it<br>cp /etc/road-home.bashrc ~/.bashrc -</ul> -<li>Launch the X terminal server from '<tt>Start > All programs > Cygwin-X > Xwin Server</tt>'. Alternatively, run 'startx' -<li>Launch an XTerm shell -<ul> -<li>Right click the Cywin icon on the system tray in the Windows taskbar. -<li>Select '<tt>System Tools > XTerm</tt>' -</ul> -<li>Download and extract Geomview -- <a href="http://www.geomview.org/download/">Downloading Geomview</a> -<li>Compile Geomview -<ul> -<li>./configure -<li>make -</ul> -<li>If './configure' fails, check 'config.log' at the failing step. Look carefully for missing libraries, etc. The <a href="http://www.geomview.org/FAQ/answers.shtml">Geomview FAQ</a> contains suggestions (e.g., "configure claims it can't find OpenGl"). -<li>If 'make' fails, read the output carefully for error messages. Usually it is a missing include file or package. Locate and install the missing cygwin packages -(<a href="https://cygwin.com/cgi-bin2/package-grep.cgi">Cygwin Package Search</a>). -</ol> - -</blockquote> -</blockquote> -<h2><a href="#TOC">»</a><a name="bugs">What to do if something -goes wrong</a></h2> -<blockquote> - -<p>Please report bugs to <a href=mailto:qhull_bug@qhull.org>qhull_bug@qhull.org</a> -</a>. Please report if Qhull crashes. Please report if Qhull -generates an "internal error". Please report if Qhull -produces a poor approximate hull in 2-d, 3-d or 4-d. Please -report documentation errors. Please report missing or incorrect -links.</p> - -<p>If you do not understand something, try a small example. The <a -href="rbox.htm">rbox</a> program is an easy way to generate -test cases. The <a href="#geomview">Geomview</a> program helps to -visualize the output from Qhull.</p> - -<p>If Qhull does not compile, it is due to an incompatibility -between your system and ours. The first thing to check is that -your compiler is ANSI standard. Qhull produces a compiler error -if __STDC__ is not defined. You may need to set a flag (e.g., -'-A' or '-ansi').</p> - -<p>If Qhull compiles but crashes on the test case (rbox D4), -there's still incompatibility between your system and ours. -Sometimes it is due to memory management. This can be turned off -with qh_NOmem in mem.h. Please let us know if you figure out how -to fix these problems. </p> - -<p>If you doubt the output from Qhull, add option '<a -href="qh-optt.htm#Tv">Tv</a>'. It checks that every point is -inside the outer planes of the convex hull. It checks that every -facet is convex with its neighbors. It checks the topology of the -convex hull.</p> - -<p>Qhull should work on all inputs. It may report precision -errors if you turn off merged facets with option '<a -href="qh-optq.htm#Q0">Q0</a>'. This can get as bad as facets with -flipped orientation or two facets with the same vertices. You'll -get a long help message if you run into such a case. They are -easy to generate with <tt>rbox</tt>.</p> - -<p>If you do find a problem, try to simplify it before reporting -the error. Try different size inputs to locate the smallest one -that causes an error. You're welcome to hunt through the code -using the execution trace ('<a href="qh-optt.htm#Tn">T4</a>') as -a guide. This is especially true if you're incorporating Qhull -into your own program. </p> - -<p>When you report an error, please attach a data set to the end -of your message. Include the options that you used with Qhull, -the results of option '<a href="qh-optf.htm#FO">FO</a>', and any -messages generated by Qhull. This allows me to see the error for -myself. Qhull is maintained part-time. </p> - -</blockquote> -<h2><a href="#TOC">»</a><a name="email">Email</a></h2> -<blockquote> - -<p>Please send correspondence to Brad Barber at <a href=mailto:qhull@qhull.org>qhull@qhull.org</a> -and report bugs to <a href=mailto:qhull_bug@qhull.org>qhull_bug@qhull.org</a> -</a>. Let me know how you use Qhull. If you mention it in a -paper, please send a reference and abstract.</p> - -<p>If you would like to get Qhull announcements (e.g., a new -version) and news (any bugs that get fixed, etc.), let us know -and we will add you to our mailing list. For Internet news about geometric algorithms -and convex hulls, look at comp.graphics.algorithms and -sci.math.num-analysis. For Qhull news look at <a -href="http://www.qhull.org/news">qhull-news.html</a>.</p> - -</blockquote> -<h2><a href="#TOC">»</a><a name="authors">Authors</a></h2> -<blockquote> - -<pre> - C. Bradford Barber Hannu Huhdanpaa - bradb@shore.net hannu@qhull.org -</pre> - -</blockquote> -<h2><a href="#TOC">»</a><a name="acknowledge">Acknowledgments</a></h2> -<blockquote> - -<p>A special thanks to David Dobkin for his guidance. A special -thanks to Albert Marden, Victor Milenkovic, the Geometry Center, -and Harvard University for supporting this work.</p> - -<p>A special thanks to Mark Phillips, Robert Miner, and Stuart Levy for running the Geometry - Center web site long after the Geometry Center closed. - Stuart moved the web site to the University of Illinois at Champaign-Urbana. -Mark and Robert are founders of <a href=http://www.geomtech.com>Geometry Technologies</a>. -Mark, Stuart, and Tamara Munzner are the original authors of <a href=http://www.geomview.org>Geomview</a>. - -<p>A special thanks to <a href="http://www.endocardial.com/">Endocardial -Solutions, Inc.</a> of St. Paul, Minnesota for their support of the -internal documentation (<a href=../src/libqhull/index.htm>src/libqhull/index.htm</a>). They use Qhull to build 3-d models of -heart chambers.</p> - -<p>Qhull 1.0 and 2.0 were developed under National Science Foundation -grants NSF/DMS-8920161 and NSF-CCR-91-15793 750-7504. If you find -it useful, please let us know.</p> - -<p>The Geometry Center was supported by grant DMS-8920161 from the -National Science Foundation, by grant DOE/DE-FG02-92ER25137 from -the Department of Energy, by the University of Minnesota, and by -Minnesota Technology, Inc.</p> - -</blockquote> -<h2><a href="#TOC">»</a><a name="ref">References</a></h2> -<blockquote> - -<p><a name="aure91">Aurenhammer</a>, F., "Voronoi diagrams --- A survey of a fundamental geometric data structure," <i>ACM -Computing Surveys</i>, 1991, 23:345-405. </p> - -<p><a name="bar-dob96">Barber</a>, C. B., D.P. Dobkin, and H.T. -Huhdanpaa, "The Quickhull Algorithm for Convex Hulls," <i>ACM -Transactions on Mathematical Software</i>, 22(4):469-483, Dec 1996, www.qhull.org -[<a -href="http://portal.acm.org/citation.cfm?doid=235815.235821">http://portal.acm.org</a>; -<a href="http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.117.405">http://citeseerx.ist.psu.edu</a>]. -</p> - -<p><a name="cla-sho89">Clarkson</a>, K.L. and P.W. Shor, -"Applications of random sampling in computational geometry, -II", <i>Discrete Computational Geometry</i>, 4:387-421, 1989</p> - -<p><a name="cla-meh93">Clarkson</a>, K.L., K. Mehlhorn, and R. -Seidel, "Four results on randomized incremental -construction," <em>Computational Geometry: Theory and -Applications</em>, vol. 3, p. 185-211, 1993.</p> - -<p><a name="devi01">Devillers</a>, et. al., -"Walking in a triangulation," <i>ACM Symposium on -Computational Geometry</i>, June 3-5,2001, Medford MA. - -<p><a name="dob-kir90">Dobkin</a>, D.P. and D.G. Kirkpatrick, -"Determining the separation of preprocessed polyhedra--a -unified approach," in <i>Proc. 17th Inter. Colloq. Automata -Lang. Program.</i>, in <i>Lecture Notes in Computer Science</i>, -Springer-Verlag, 443:400-413, 1990. </p> - -<p><a name="edel01">Edelsbrunner</a>, H, <i>Geometry and Topology for Mesh Generation</i>, -Cambridge University Press, 2001. - -<p><a name=gart99>Gartner, B.</a>, "Fast and robust smallest enclosing balls", <i>Algorithms - ESA '99</i>, LNCS 1643. - -<p><a name=golub83>Golub, G.H. and van Loan, C.F.</a>, <i>Matric Computations</i>, Baltimore, Maryland, USA: John Hopkins Press, 1983 - -<p><a name="fort93">Fortune, S.</a>, "Computational -geometry," in R. Martin, editor, <i>Directions in Geometric -Computation</i>, Information Geometers, 47 Stockers Avenue, -Winchester, SO22 5LB, UK, ISBN 1-874728-02-X, 1993.</p> - -<p><a name="mile93">Milenkovic, V.</a>, "Robust polygon -modeling," Computer-Aided Design, vol. 25, p. 546-566, -September 1993. </p> - -<p><a name="muck96">Mucke</a>, E.P., I. Saias, B. Zhu, <i>Fast -randomized point location without preprocessing in Two- and -Three-dimensional Delaunay Triangulations</i>, ACM Symposium on -Computational Geometry, p. 274-283, 1996 [<a -href="http://www.geom.uiuc.edu/software/cglist/GeomDir/">GeomDir</a>]. -</p> - -<p><a name="mulm94">Mulmuley</a>, K., <i>Computational Geometry, -An Introduction Through Randomized Algorithms</i>, Prentice-Hall, -NJ, 1994.</p> - -<p><a name="orou94">O'Rourke</a>, J., <i>Computational Geometry -in C</i>, Cambridge University Press, 1994.</p> - -<p><a name="pre-sha85">Preparata</a>, F. and M. Shamos, <i>Computational -Geometry</i>, Springer-Verlag, New York, 1985.</p> - -</blockquote> -<!-- Navigation links --> -<hr> - -<p><b>Up:</b> <a -href="http://www.qhull.org">Home page</a> for Qhull<br> -<b>Up:</b><a -href="http://www.qhull.org/news">News</a> about Qhull<br> -<b>Up:</b> <a href="http://www.qhull.org/html/qh-faq.htm">FAQ</a> about Qhull<br> -<b>To:</b> <a href="#TOC">Qhull manual</a>: Table of Contents<br> -<b>To:</b> <a href="qh-quick.htm#programs">Programs</a> -• <a href="qh-quick.htm#options">Options</a> -• <a href="qh-opto.htm#output">Output</a> -• <a href="qh-optf.htm#format">Formats</a> -• <a href="qh-optg.htm#geomview">Geomview</a> -• <a href="qh-optp.htm#print">Print</a> -• <a href="qh-optq.htm#qhull">Qhull</a> -• <a href="qh-optc.htm#prec">Precision</a> -• <a href="qh-optt.htm#trace">Trace</a> -• <a href="../src/libqhull_r/index.htm">Functions</a><br> -<b>Dn:</b> <a href="qh-impre.htm">Imprecision in Qhull</a><br> -<b>Dn:</b> <a href="qh-eg.htm">Description of Qhull examples</a><br> -<b>Dn:</b> <a href="qh-code.htm">Qhull internals</a><br> -<b>Dn:</b> <a href="../src/libqhull/index.htm">Qhull functions, macros, and data -structures</a> -<!-- GC common information --> -<hr> - -<p><a href="http://www.geom.uiuc.edu/"><img src="qh--geom.gif" -align="middle" width="40" height="40"></a><i>The Geometry Center -Home Page </i></p> - -<p>Comments to: <a href=mailto:qhull@qhull.org>qhull@qhull.org</a> -</a><br> -Created: Sept. 25, 1995 --- <!-- hhmts start --> Last modified: see top <!-- hhmts end --> </p> -</body> -</html> |