diff options
Diffstat (limited to 'src/qhull/html/qvoron_f.htm')
| -rw-r--r-- | src/qhull/html/qvoron_f.htm | 396 |
1 files changed, 396 insertions, 0 deletions
diff --git a/src/qhull/html/qvoron_f.htm b/src/qhull/html/qvoron_f.htm new file mode 100644 index 000000000..db538b5ab --- /dev/null +++ b/src/qhull/html/qvoron_f.htm @@ -0,0 +1,396 @@ +<!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> |