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/qvoron_f.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/qvoron_f.htm')
| -rw-r--r-- | src/qhull/html/qvoron_f.htm | 396 |
1 files changed, 0 insertions, 396 deletions
diff --git a/src/qhull/html/qvoron_f.htm b/src/qhull/html/qvoron_f.htm deleted file mode 100644 index db538b5ab..000000000 --- a/src/qhull/html/qvoron_f.htm +++ /dev/null @@ -1,396 +0,0 @@ -<!DOCTYPE HTML PUBLIC "-//IETF//DTD HTML//EN"> -<html> - -<head> -<title>qvoronoi Qu -- furthest-site Voronoi diagram</title> -</head> - -<body> -<!-- Navigation links --> -<a name="TOP"><b>Up</b></a><b>:</b> -<a href="http://www.qhull.org">Home page</a> for Qhull<br> -<b>Up:</b> <a href="index.htm#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>To:</b> <a href="#synopsis">sy</a>nopsis -• <a href="#input">in</a>put • <a href="#outputs">ou</a>tputs -• <a href="#controls">co</a>ntrols • <a href="#graphics">gr</a>aphics -• <a href="#notes">no</a>tes • <a href="#conventions">co</a>nventions -• <a href="#options">op</a>tions - -<hr> -<!-- Main text of document --> -<h1><a -href="http://www.geom.uiuc.edu/graphics/pix/Special_Topics/Computational_Geometry/delaunay.html"><img -src="qh--dt.gif" alt="[delaunay]" align="middle" width="100" -height="100"></a>qvoronoi Qu -- furthest-site Voronoi diagram</h1> - -<p>The furthest-site Voronoi diagram is the furthest-neighbor map for a set of -points. Each region contains those points that are further -from one input site than any other input site. See the -survey article by Aurenhammer [<a href="index.htm#aure91">'91</a>] -and the brief introduction by O'Rourke [<a -href="index.htm#orou94">'94</a>]. The furthest-site Voronoi diagram is the dual of the <a -href="qdelau_f.htm">furthest-site Delaunay triangulation</a>. -</p> - -<blockquote> -<dl> - <dt><b>Example:</b> rbox 10 D2 | qvoronoi <a - href="qh-optq.htm#Qu">Qu</a> <a href="qh-opto.htm#s">s</a> - <a href="qh-opto.htm#o">o</a> <a href="qh-optt.htm#TO">TO - result</a></dt> - <dd>Compute the 2-d, furthest-site Voronoi diagram of 10 - random points. Write a summary to the console and the Voronoi - regions and vertices to 'result'. The first vertex of the - result indicates unbounded regions. Almost all regions - are unbounded.</dd> -</dl> - -<dl> - <dt><b>Example:</b> rbox r y c G1 D2 | qvoronoi <a - href="qh-optq.htm#Qu">Qu</a> - <a href="qh-opto.htm#s">s</a> - <a href="qh-optf.htm#Fn">Fn</a> <a href="qh-optt.htm#TO">TO - result</a></dt> - <dd>Compute the 2-d furthest-site Voronoi diagram of a square - and a small triangle. Write a summary to the console and the Voronoi - vertices for each input site to 'result'. - The origin is the only furthest-site Voronoi vertex. The - negative indices indicate vertices-at-infinity.</dd> -</dl> -</blockquote> - -<p> -Qhull computes the furthest-site Voronoi diagram via the <a href="qdelau_f.htm"> -furthest-site Delaunay triangulation</a>. -Each furthest-site Voronoi vertex is the circumcenter of an upper -facet of the Delaunay triangulation. Each furthest-site Voronoi -region corresponds to a vertex of the Delaunay triangulation -(i.e., an input site).</p> - -<p>See <a href="http://www.qhull.org/html/qh-faq.htm#TOC">Qhull FAQ</a> - Delaunay and -Voronoi diagram questions.</p> - -<p>The 'qvonoroi' program is equivalent to -'<a href=qhull.htm#outputs>qhull v</a> <a href=qh-optq.htm#Qbb>Qbb</a>' in 2-d to 3-d, and -'<a href=qhull.htm#outputs>qhull v</a> <a href=qh-optq.htm#Qbb>Qbb</a> <a href=qh-optq.htm#Qx>Qx</a>' -in 4-d and higher. It disables the following Qhull -<a href=qh-quick.htm#options>options</a>: <i>d n m v H U Qb -QB Qc Qf Qg Qi Qm Qr QR Qv Qx TR E V Fa FA FC Fp FS Ft FV Gt Q0,etc</i>. - - -<p><b>Copyright © 1995-2015 C.B. Barber</b></p> - -<hr> -<h3><a href="#TOP">»</a><a name="synopsis">furthest-site qvoronoi synopsis</a></h3> -<blockquote> - -See <a href="qvoronoi.htm#synopsis">qvoronoi synopsis</a>. The same -program is used for both constructions. Use option '<a href="qh-optq.htm#Qu">Qu</a>' -for furthest-site Voronoi diagrams. - - -</blockquote> -<h3><a href="#TOP">»</a><a name="input">furthest-site qvoronoi -input</a></h3> -<blockquote> -<p>The input data on <tt>stdin</tt> consists of:</p> -<ul> - <li>dimension - <li>number of points</li> - <li>point coordinates</li> -</ul> - -<p>Use I/O redirection (e.g., qvoronoi Qu < data.txt), a pipe (e.g., rbox 10 | qvoronoi Qu), -or the '<a href=qh-optt.htm#TI>TI</a>' option (e.g., qvoronoi TI data.txt Qu). - -<p>For example, this is a square containing four random points. -Its furthest-site Voronoi diagram has on vertex and four unbounded, -separating hyperplanes (i.e., the coordinate axes) -<p> -<blockquote> -<tt>rbox c 4 D2 > data</tt> -<blockquote><pre> -2 RBOX c 4 D2 -8 --0.4999921736307369 -0.3684622117955817 -0.2556053225468894 -0.0413498678629751 -0.0327672376602583 -0.2810408135699488 --0.452955383763607 0.17886471718444 - -0.5 -0.5 - -0.5 0.5 - 0.5 -0.5 - 0.5 0.5 -</pre></blockquote> - -<p><tt>qvoronoi Qu s Fo < data</tt> -<blockquote><pre> - -Furthest-site Voronoi vertices by the convex hull of 8 points in 3-d: - - Number of Voronoi regions: 8 - Number of Voronoi vertices: 1 - Number of non-simplicial Voronoi vertices: 1 - -Statistics for: RBOX c 4 D2 | QVORONOI Qu s Fo - - Number of points processed: 8 - Number of hyperplanes created: 20 - Number of facets in hull: 11 - Number of distance tests for qhull: 34 - Number of merged facets: 1 - Number of distance tests for merging: 107 - CPU seconds to compute hull (after input): 0 - -4 -5 4 5 0 1 0 -5 4 6 1 0 0 -5 5 7 1 0 0 -5 6 7 0 1 0 -</pre></blockquote> -</blockquote> - -</blockquote> -<h3><a href="#TOP">»</a> <a name="outputs">furthest-site qvoronoi -outputs</a></h3> -<blockquote> - -<p>These options control the output of furthest-site Voronoi diagrams.</p> -<blockquote> - -<dl compact> - <dt> </dt> - <dd><b>furthest-site Voronoi vertices</b></dd> - <dt><a href="qh-opto.htm#p">p</a></dt> - <dd>print the coordinates of the furthest-site Voronoi vertices. The first line - is the dimension. The second line is the number of vertices. Each - remaining line is a furthest-site Voronoi vertex. The points-in-square example - has one furthest-site Voronoi vertex at the origin.</dd> - <dt><a href="qh-optf.htm#Fn">Fn</a></dt> - <dd>list the neighboring furthest-site Voronoi vertices for each furthest-site Voronoi - vertex. The first line is the number of Voronoi vertices. Each - remaining line starts with the number of neighboring vertices. Negative indices (e.g., <em>-1</em>) indicate vertices - outside of the Voronoi diagram. In the points-in-square example, the - Voronoi vertex at the origin has four neighbors-at-infinity.</dd> - <dt><a href="qh-optf.htm#FN">FN</a></dt> - <dd>list the furthest-site Voronoi vertices for each furthest-site Voronoi region. The first line is - the number of Voronoi regions. Each remaining line starts with the - number of Voronoi vertices. Negative indices (e.g., <em>-1</em>) indicate vertices - outside of the Voronoi diagram. - In the points-in-square example, all regions share the Voronoi vertex - at the origin.</dd> - - <dt> </dt> - <dt> </dt> - <dd><b>furthest-site Voronoi regions</b></dd> - <dt><a href="qh-opto.htm#o">o</a></dt> - <dd>print the furthest-site Voronoi regions in OFF format. The first line is the - dimension. The second line is the number of vertices, the number - of input sites, and "1". The third line represents the vertex-at-infinity. - Its coordinates are "-10.101". The next lines are the coordinates - of the furthest-site Voronoi vertices. Each remaining line starts with the number - of Voronoi vertices in a Voronoi region. In 2-d, the vertices are -listed in adjacency order (unoriented). In 3-d and higher, the -vertices are listed in numeric order. In the points-in-square - example, each unbounded region includes the Voronoi vertex at - the origin. Lines consisting of <em>0</em> indicate - interior input sites. </dd> - <dt><a href="qh-optf.htm#Fi2">Fi</a></dt> - <dd>print separating hyperplanes for inner, bounded furthest-site Voronoi - regions. The first number is the number of separating - hyperplanes. Each remaining line starts with <i>3+dim</i>. The - next two numbers are adjacent input sites. The next <i>dim</i> - numbers are the coefficients of the separating hyperplane. The - last number is its offset. The are no bounded, separating hyperplanes - for the points-in-square example.</dd> - <dt><a href="qh-optf.htm#Fo2">Fo</a></dt> - <dd>print separating hyperplanes for outer, unbounded furthest-site Voronoi - regions. The first number is the number of separating - hyperplanes. Each remaining line starts with <i>3+dim</i>. The - next two numbers are adjacent input sites on the convex hull. The - next <i>dim</i> - numbers are the coefficients of the separating hyperplane. The - last number is its offset. The points-in-square example has four - unbounded, separating hyperplanes.</dd> - <dt> </dt> - <dt> </dt> - <dd><b>Input sites</b></dd> - <dt><a href="qh-optf.htm#Fv2">Fv</a></dt> - <dd>list ridges of furthest-site Voronoi vertices for pairs of input sites. The - first line is the number of ridges. Each remaining line starts with - two plus the number of Voronoi vertices in the ridge. The next - two numbers are two adjacent input sites. The remaining numbers list - the Voronoi vertices. As with option 'o', a <em>0</em> indicates - the vertex-at-infinity - and an unbounded, separating hyperplane. - The perpendicular bisector (separating hyperplane) - of the input sites is a flat through these vertices. - In the points-in-square example, the ridge for each edge of the square - is unbounded.</dd> - <dt> </dt> - <dt> </dt> - <dd><b>General</b></dd> - <dt><a href="qh-opto.htm#s">s</a></dt> - <dd>print summary of the furthest-site Voronoi diagram. Use '<a - href="qh-optf.htm#Fs">Fs</a>' for numeric data.</dd> - <dt><a href="qh-opto.htm#i">i</a></dt> - <dd>list input sites for each <a href=qdelau_f.htm>furthest-site Delaunay region</a>. Use option '<a href="qh-optp.htm#Pp">Pp</a>' - to avoid the warning. The first line is the number of regions. The - remaining lines list the input sites for each region. The regions are - oriented. In the points-in-square example, the square region has four - input sites. In 3-d and higher, report cospherical sites by adding extra points. - </dd> - <dt><a href="qh-optg.htm#G">G</a></dt> - <dd>Geomview output for 2-d furthest-site Voronoi diagrams.</dd> - </dl> -</blockquote> - -</blockquote> -<h3><a href="#TOP">»</a> <a name="controls">furthest-site qvoronoi -controls</a></h3> -<blockquote> - -<p>These options provide additional control:</p> -<blockquote> - -<dl compact> - <dt><a href="qh-optq.htm#Qu">Qu</a></dt> - <dd>must be used.</dd> - <dt><a href="qh-optq.htm#QVn">QVn</a></dt> - <dd>select furthest-site Voronoi vertices for input site <em>n</em> </dd> - <dt><a href="qh-optt.htm#Tv">Tv</a></dt> - <dd>verify result</dd> - <dt><a href="qh-optt.htm#TO">TI file</a></dt> - <dd>input data from file. The filename may not use spaces or quotes.</dd> - <dt><a href="qh-optt.htm#TO">TO file</a></dt> - <dd>output results to file. Use single quotes if the filename - contains spaces (e.g., <tt>TO 'file with spaces.txt'</tt></dd> - <dt><a href="qh-optt.htm#TFn">TFn</a></dt> - <dd>report progress after constructing <em>n</em> facets</dd> - <dt><a href="qh-optp.htm#PDk">PDk:1</a></dt> - <dd>include upper and lower facets in the output. Set <em>k</em> - to the last dimension (e.g., 'PD2:1' for 2-d inputs). </dd> - <dt><a href="qh-opto.htm#f">f </a></dt> - <dd>facet dump. Print the data structure for each facet (i.e., - furthest-site Voronoi vertex).</dd> -</dl> - -</blockquote> -</blockquote> -<h3><a href="#TOP">»</a> <a name="graphics">furthest-site qvoronoi -graphics</a></h3> -<blockquote> -<p>In 2-d, Geomview output ('<a href="qh-optg.htm#G">G</a>') -displays a furthest-site Voronoi diagram with extra edges to -close the unbounded furthest-site Voronoi regions. All regions -will be unbounded. Since the points-in-box example has only -one furthest-site Voronoi vertex, the Geomview output is one -point.</p> - -<p>See the <a href="qh-eg.htm#delaunay">Delaunay and Voronoi -examples</a> for a 2-d example. Turn off normalization (on -Geomview's 'obscure' menu) when comparing the furthest-site -Voronoi diagram with the corresponding Voronoi diagram. </p> - -</blockquote> -<h3><a href="#TOP">»</a><a name="notes">furthest-site qvoronoi -notes</a></h3> -<blockquote> - -<p>See <a href="qvoronoi.htm#notes">Voronoi notes</a>.</p> - -</blockquote> -<h3><a href="#TOP">»</a><a name="conventions">furthest-site qvoronoi conventions</a></h3> -<blockquote> - -<p>The following terminology is used for furthest-site Voronoi -diagrams in Qhull. The underlying structure is a furthest-site -Delaunay triangulation from a convex hull in one higher -dimension. Upper facets of the Delaunay triangulation correspond -to vertices of the furthest-site Voronoi diagram. Vertices of the -furthest-site Delaunay triangulation correspond to input sites. -They also define regions of the furthest-site Voronoi diagram. -All vertices are extreme points of the input sites. See <a -href="qconvex.htm#conventions">qconvex conventions</a>, <a -href="qdelau_f.htm#conventions">furthest-site delaunay -conventions</a>, and <a href="index.htm#structure">Qhull's data structures</a>.</p> - -<ul> - <li><em>input site</em> - a point in the input (one dimension - lower than a point on the convex hull)</li> - <li><em>point</em> - a point has <i>d+1</i> coordinates. The - last coordinate is the sum of the squares of the input - site's coordinates</li> - <li><em>vertex</em> - a point on the upper facets of the - paraboloid. It corresponds to a unique input site. </li> - <li><em>furthest-site Delaunay facet</em> - an upper facet of the - paraboloid. The last coefficient of its normal is - clearly positive.</li> - <li><em>furthest-site Voronoi vertex</em> - the circumcenter - of a furthest-site Delaunay facet</li> - <li><em>furthest-site Voronoi region</em> - the region of - Euclidean space further from an input site than any other - input site. Qhull lists the furthest-site Voronoi - vertices that define each furthest-site Voronoi region.</li> - <li><em>furthest-site Voronoi diagram</em> - the graph of the - furthest-site Voronoi regions with the ridges (edges) - between the regions.</li> - <li><em>infinity vertex</em> - the Voronoi vertex for - unbounded furthest-site Voronoi regions in '<a - href="qh-opto.htm#o">o</a>' output format. Its - coordinates are <em>-10.101</em>.</li> - <li><em>good facet</em> - an furthest-site Voronoi vertex with - optional restrictions by '<a href="qh-optq.htm#QVn">QVn</a>', - etc.</li> -</ul> - -</blockquote> -<h3><a href="#TOP">»</a><a name="options">furthest-site qvoronoi options</a></h3> -<blockquote> - -See <a href="qvoronoi.htm#options">qvoronoi options</a>. The same -program is used for both constructions. Use option '<a href="qh-optq.htm#Qu">Qu</a>' -for furthest-site Voronoi diagrams. -</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="index.htm#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>To:</b> <a href="#synopsis">sy</a>nopsis -• <a href="#input">in</a>put • <a href="#outputs">ou</a>tputs -• <a href="#controls">co</a>ntrols • <a href="#graphics">gr</a>aphics -• <a href="#notes">no</a>tes • <a href="#conventions">co</a>nventions -• <a href="#options">op</a>tions -<!-- 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> |