Diffusion CADD_mesher (dev/incorporate-qhull) Browse

incorporate-qhull

qvoron_f.htm
View Options

This document is not UTF8. It was detected as Shift JIS and converted to UTF8 for display.

			<!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.geom.umn.edu/software/qhull">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><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.umn.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="qh-faq.htm#TOC">Qhull FAQ</a> - Delaunay and
			Voronoi diagram questions.</p>

			<p>Options '<a href="qh-optq.htm#Qt">Qt</a>' (triangulated output)
			and '<a href="qh-optq.htm#QJn">QJ</a>' (joggled input), may produce
			unexpected results. Cocircular and cospherical input sites will
			produce duplicate or nearly duplicate furthest-site Voronoi vertices. See also <a
			href="qh-impre.htm#joggle">Joggled input or merged facets</a>. </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-2002 The Geometry Center, Minneapolis MN</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#Qt">Qt</a></dt>
			<dd>triangulated output. If a furthest-site Voronoi vertex is defined by cospherical data, Qhull
			duplicates the vertex. For example, if 2-d data is contained in a square, the output
			will contain two, identical furthest-site Voronoi vertices.</dd>
			<dt><a href="qh-optq.htm#QJn">QJ</a></dt>
			<dd>joggle the input to avoid furthest-site Voronoi vertices defined by more
			than <i>dim+1</i> points.
			</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.geom.umn.edu/software/qhull">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><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.umn.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@geom.umn.edu>qhull@geom.umn.edu</a>
			</a><br>
			Created: Sept. 25, 1995 --- <!-- hhmts start --> Last modified: see top <!-- hhmts end --> </p>
			</body>
			</html>

rCADDMESH/html/qvoron_f.htmfb7d9109bc99dev/incorporate-qhull

qvoron_f.htmView Options

rCADDMESH/html/qvoron_f.htm
fb7d9109bc99dev/incorporate-qhull

qvoron_f.htm
View Options