/usr/share/doc/octave/octave.html/Identifying-Points-in-Triangulation.html

<!DOCTYPE html PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN" "http://www.w3.org/TR/html4/loose.dtd">
<html>
<!-- Created by GNU Texinfo 6.5, http://www.gnu.org/software/texinfo/ -->
<head>
<meta http-equiv="Content-Type" content="text/html; charset=utf-8">
<title>Identifying Points in Triangulation (GNU Octave)</title>

<meta name="description" content="Identifying Points in Triangulation (GNU Octave)">
<meta name="keywords" content="Identifying Points in Triangulation (GNU Octave)">
<meta name="resource-type" content="document">
<meta name="distribution" content="global">
<meta name="Generator" content="makeinfo">
<link href="index.html#Top" rel="start" title="Top">
<link href="Concept-Index.html#Concept-Index" rel="index" title="Concept Index">
<link href="index.html#SEC_Contents" rel="contents" title="Table of Contents">
<link href="Delaunay-Triangulation.html#Delaunay-Triangulation" rel="up" title="Delaunay Triangulation">
<link href="Voronoi-Diagrams.html#Voronoi-Diagrams" rel="next" title="Voronoi Diagrams">
<link href="Plotting-the-Triangulation.html#Plotting-the-Triangulation" rel="prev" title="Plotting the Triangulation">
<style type="text/css">
<!--
a.summary-letter {text-decoration: none}
blockquote.indentedblock {margin-right: 0em}
blockquote.smallindentedblock {margin-right: 0em; font-size: smaller}
blockquote.smallquotation {font-size: smaller}
div.display {margin-left: 3.2em}
div.example {margin-left: 3.2em}
div.lisp {margin-left: 3.2em}
div.smalldisplay {margin-left: 3.2em}
div.smallexample {margin-left: 3.2em}
div.smalllisp {margin-left: 3.2em}
kbd {font-style: oblique}
pre.display {font-family: inherit}
pre.format {font-family: inherit}
pre.menu-comment {font-family: serif}
pre.menu-preformatted {font-family: serif}
pre.smalldisplay {font-family: inherit; font-size: smaller}
pre.smallexample {font-size: smaller}
pre.smallformat {font-family: inherit; font-size: smaller}
pre.smalllisp {font-size: smaller}
span.nolinebreak {white-space: nowrap}
span.roman {font-family: initial; font-weight: normal}
span.sansserif {font-family: sans-serif; font-weight: normal}
ul.no-bullet {list-style: none}
-->
</style>
<link rel="stylesheet" type="text/css" href="octave.css">


</head>

<body lang="en">
<a name="Identifying-Points-in-Triangulation"></a>
<div class="header">
<p>
Previous: <a href="Plotting-the-Triangulation.html#Plotting-the-Triangulation" accesskey="p" rel="prev">Plotting the Triangulation</a>, Up: <a href="Delaunay-Triangulation.html#Delaunay-Triangulation" accesskey="u" rel="up">Delaunay Triangulation</a> &nbsp; [<a href="index.html#SEC_Contents" title="Table of contents" rel="contents">Contents</a>][<a href="Concept-Index.html#Concept-Index" title="Index" rel="index">Index</a>]</p>
</div>
<hr>
<a name="Identifying-Points-in-Triangulation-1"></a>
<h4 class="subsection">30.1.2 Identifying Points in Triangulation</h4>

<p>It is often necessary to identify whether a particular point in the
N-dimensional space is within the Delaunay tessellation of a set of
points in this N-dimensional space, and if so which N-simplex contains
the point and which point in the tessellation is closest to the desired
point.  The functions <code>tsearch</code> and <code>dsearch</code> perform this
function in a triangulation, and <code>tsearchn</code> and <code>dsearchn</code> in
an N-dimensional tessellation.
</p>
<p>To identify whether a particular point represented by a vector <var>p</var>
falls within one of the simplices of an N-simplex, we can write the
Cartesian coordinates of the point in a parametric form with respect to
the N-simplex.  This parametric form is called the Barycentric
Coordinates of the point.  If the points defining the N-simplex are given
by <var>N</var> + 1 vectors <code><var>t</var>(<var>i</var>,:)</code>, then the Barycentric
coordinates defining the point <var>p</var> are given by
</p>
<div class="example">
<pre class="example"><var>p</var> = <var>beta</var> * <var>t</var>
</pre></div>

<p>where <var>beta</var> contains <var>N</var> + 1 values that together as a vector
represent the Barycentric coordinates of the point <var>p</var>.  To ensure a unique
solution for the values of <var>beta</var> an additional criteria of
</p>
<div class="example">
<pre class="example">sum (<var>beta</var>) == 1
</pre></div>

<p>is imposed, and we can therefore write the above as
</p>
<div class="example">
<pre class="example"><var>p</var> - <var>t</var>(end, :) = <var>beta</var>(1:end-1) * (<var>t</var>(1:end-1, :)
                - ones (<var>N</var>, 1) * <var>t</var>(end, :)
</pre></div>

<p>Solving for <var>beta</var> we can then write
</p>
<div class="example">
<pre class="example"><var>beta</var>(1:end-1) = (<var>p</var> - <var>t</var>(end, :)) / 
                (<var>t</var>(1:end-1, :) - ones (<var>N</var>, 1) * <var>t</var>(end, :))
<var>beta</var>(end) = sum (<var>beta</var>(1:end-1))
</pre></div>

<p>which gives the formula for the conversion of the Cartesian coordinates
of the point <var>p</var> to the Barycentric coordinates <var>beta</var>.  An
important property of the Barycentric coordinates is that for all points
in the N-simplex
</p>
<div class="example">
<pre class="example">0 &lt;= <var>beta</var>(<var>i</var>) &lt;= 1
</pre></div>

<p>Therefore, the test in <code>tsearch</code> and <code>tsearchn</code> essentially
only needs to express each point in terms of the Barycentric coordinates
of each of the simplices of the N-simplex and test the values of
<var>beta</var>.  This is exactly the implementation used in
<code>tsearchn</code>.  <code>tsearch</code> is optimized for 2-dimensions and the
Barycentric coordinates are not explicitly formed.
</p>
<a name="XREFtsearch"></a><dl>
<dt><a name="index-tsearch"></a>: <em><var>idx</var> =</em> <strong>tsearch</strong> <em>(<var>x</var>, <var>y</var>, <var>t</var>, <var>xi</var>, <var>yi</var>)</em></dt>
<dd><p>Search for the enclosing Delaunay convex hull.
</p>
<p>For <code><var>t</var> = delaunay (<var>x</var>, <var>y</var>)</code>, finds the index in <var>t</var>
containing the points <code>(<var>xi</var>, <var>yi</var>)</code>.  For points outside the
convex hull, <var>idx</var> is NaN.
</p>
<p><strong>See also:</strong> <a href="Delaunay-Triangulation.html#XREFdelaunay">delaunay</a>, <a href="Delaunay-Triangulation.html#XREFdelaunayn">delaunayn</a>.
</p></dd></dl>


<a name="XREFtsearchn"></a><dl>
<dt><a name="index-tsearchn"></a>: <em><var>idx</var> =</em> <strong>tsearchn</strong> <em>(<var>x</var>, <var>t</var>, <var>xi</var>)</em></dt>
<dt><a name="index-tsearchn-1"></a>: <em>[<var>idx</var>, <var>p</var>] =</em> <strong>tsearchn</strong> <em>(<var>x</var>, <var>t</var>, <var>xi</var>)</em></dt>
<dd><p>Search for the enclosing Delaunay convex hull.
</p>
<p>For <code><var>t</var> = delaunayn (<var>x</var>)</code>, finds the index in <var>t</var>
containing the points <var>xi</var>.  For points outside the convex hull,
<var>idx</var> is NaN.
</p>
<p>If requested <code>tsearchn</code> also returns the Barycentric coordinates
<var>p</var> of the enclosing triangles.
</p>
<p><strong>See also:</strong> <a href="Delaunay-Triangulation.html#XREFdelaunay">delaunay</a>, <a href="Delaunay-Triangulation.html#XREFdelaunayn">delaunayn</a>.
</p></dd></dl>


<p>An example of the use of <code>tsearch</code> can be seen with the simple
triangulation
</p>
<div class="example">
<pre class="example"><var>x</var> = [-1; -1; 1; 1];
<var>y</var> = [-1; 1; -1; 1];
<var>tri</var> = [1, 2, 3; 2, 3, 4];
</pre></div>

<p>consisting of two triangles defined by <var>tri</var>.  We can then identify
which triangle a point falls in like
</p>
<div class="example">
<pre class="example">tsearch (<var>x</var>, <var>y</var>, <var>tri</var>, -0.5, -0.5)
&rArr; 1
tsearch (<var>x</var>, <var>y</var>, <var>tri</var>, 0.5, 0.5)
&rArr; 2
</pre></div>

<p>and we can confirm that a point doesn&rsquo;t lie within one of the triangles like
</p>
<div class="example">
<pre class="example">tsearch (<var>x</var>, <var>y</var>, <var>tri</var>, 2, 2)
&rArr; NaN
</pre></div>

<p>The <code>dsearch</code> and <code>dsearchn</code> find the closest point in a
tessellation to the desired point.  The desired point does not
necessarily have to be in the tessellation, and even if it the returned
point of the tessellation does not have to be one of the vertexes of the
N-simplex within which the desired point is found.
</p>
<a name="XREFdsearch"></a><dl>
<dt><a name="index-dsearch"></a>: <em><var>idx</var> =</em> <strong>dsearch</strong> <em>(<var>x</var>, <var>y</var>, <var>tri</var>, <var>xi</var>, <var>yi</var>)</em></dt>
<dt><a name="index-dsearch-1"></a>: <em><var>idx</var> =</em> <strong>dsearch</strong> <em>(<var>x</var>, <var>y</var>, <var>tri</var>, <var>xi</var>, <var>yi</var>, <var>s</var>)</em></dt>
<dd><p>Return the index <var>idx</var> of the closest point in <code><var>x</var>, <var>y</var></code>
to the elements <code>[<var>xi</var>(:), <var>yi</var>(:)]</code>.
</p>
<p>The variable <var>s</var> is accepted for compatibility but is ignored.
</p>
<p><strong>See also:</strong> <a href="#XREFdsearchn">dsearchn</a>, <a href="#XREFtsearch">tsearch</a>.
</p></dd></dl>


<a name="XREFdsearchn"></a><dl>
<dt><a name="index-dsearchn"></a>: <em><var>idx</var> =</em> <strong>dsearchn</strong> <em>(<var>x</var>, <var>tri</var>, <var>xi</var>)</em></dt>
<dt><a name="index-dsearchn-1"></a>: <em><var>idx</var> =</em> <strong>dsearchn</strong> <em>(<var>x</var>, <var>tri</var>, <var>xi</var>, <var>outval</var>)</em></dt>
<dt><a name="index-dsearchn-2"></a>: <em><var>idx</var> =</em> <strong>dsearchn</strong> <em>(<var>x</var>, <var>xi</var>)</em></dt>
<dt><a name="index-dsearchn-3"></a>: <em>[<var>idx</var>, <var>d</var>] =</em> <strong>dsearchn</strong> <em>(&hellip;)</em></dt>
<dd><p>Return the index <var>idx</var> of the closest point in <var>x</var> to the elements
<var>xi</var>.
</p>
<p>If <var>outval</var> is supplied, then the values of <var>xi</var> that are not
contained within one of the simplices <var>tri</var> are set to <var>outval</var>.
Generally, <var>tri</var> is returned from <code>delaunayn (<var>x</var>)</code>.
</p>
<p><strong>See also:</strong> <a href="#XREFdsearch">dsearch</a>, <a href="#XREFtsearch">tsearch</a>.
</p></dd></dl>


<p>An example of the use of <code>dsearch</code>, using the above values of
<var>x</var>, <var>y</var> and <var>tri</var> is
</p>
<div class="example">
<pre class="example">dsearch (<var>x</var>, <var>y</var>, <var>tri</var>, -2, -2)
&rArr; 1
</pre></div>

<p>If you wish the points that are outside the tessellation to be flagged,
then <code>dsearchn</code> can be used as
</p>
<div class="example">
<pre class="example">dsearchn ([<var>x</var>, <var>y</var>], <var>tri</var>, [-2, -2], NaN)
&rArr; NaN
dsearchn ([<var>x</var>, <var>y</var>], <var>tri</var>, [-0.5, -0.5], NaN)
&rArr; 1
</pre></div>

<p>where the point outside the tessellation are then flagged with <code>NaN</code>.
</p>
<hr>
<div class="header">
<p>
Previous: <a href="Plotting-the-Triangulation.html#Plotting-the-Triangulation" accesskey="p" rel="prev">Plotting the Triangulation</a>, Up: <a href="Delaunay-Triangulation.html#Delaunay-Triangulation" accesskey="u" rel="up">Delaunay Triangulation</a> &nbsp; [<a href="index.html#SEC_Contents" title="Table of contents" rel="contents">Contents</a>][<a href="Concept-Index.html#Concept-Index" title="Index" rel="index">Index</a>]</p>
</div>



</body>
</html>
octave-doc 4.2.2-1ubuntu1 / usr / share / doc / octave / octave.html / Identifying-Points-in-Triangulation.html
