<html lang="en"> <head> <title>Identifying points in Triangulation - Untitled</title> <meta http-equiv="Content-Type" content="text/html"> <meta name="description" content="Untitled"> <meta name="generator" content="makeinfo 4.13"> <link title="Top" rel="start" href="index.html#Top"> <link rel="up" href="Delaunay-Triangulation.html#Delaunay-Triangulation" title="Delaunay Triangulation"> <link rel="prev" href="Plotting-the-Triangulation.html#Plotting-the-Triangulation" title="Plotting the Triangulation"> <link href="http://www.gnu.org/software/texinfo/" rel="generator-home" title="Texinfo Homepage"> <meta http-equiv="Content-Style-Type" content="text/css"> <style type="text/css"><!-- pre.display { font-family:inherit } pre.format { font-family:inherit } pre.smalldisplay { font-family:inherit; font-size:smaller } pre.smallformat { font-family:inherit; font-size:smaller } pre.smallexample { font-size:smaller } pre.smalllisp { font-size:smaller } span.sc { font-variant:small-caps } span.roman { font-family:serif; font-weight:normal; } span.sansserif { font-family:sans-serif; font-weight:normal; } --></style> </head> <body> <div class="node"> <a name="Identifying-points-in-Triangulation"></a> <p> Previous: <a rel="previous" accesskey="p" href="Plotting-the-Triangulation.html#Plotting-the-Triangulation">Plotting the Triangulation</a>, Up: <a rel="up" accesskey="u" href="Delaunay-Triangulation.html#Delaunay-Triangulation">Delaunay Triangulation</a> <hr> </div> <h4 class="subsection">29.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>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><code> + 1</code> vectors <var>t</var>(<var>i</var>,:), then the Barycentric coordinates defining the point <var>p</var> are given by <pre class="example"> <var>p</var> = sum (<var>beta</var>(1:<var>N</var>+1) * <var>t</var>(1:<var>N</var>+1),:) </pre> <p class="noindent">where there are <var>N</var><code> + 1</code> values <var>beta</var><code>(</code><var>i</var><code>)</code> 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><code>(</code><var>i</var><code>)</code> an additional criteria of <pre class="example"> sum (<var>beta</var>(1:<var>N</var>+1)) == 1 </pre> <p class="noindent">is imposed, and we can therefore write the above as <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> <p class="noindent">Solving for <var>beta</var> we can then write <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> <p class="noindent">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 <pre class="example"> 0 <= <var>beta</var>(<var>i</var>) <= 1 </pre> <p class="noindent">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. <!-- ./DLD-FUNCTIONS/tsearch.cc --> <p><a name="doc_002dtsearch"></a> <div class="defun"> — Loadable Function: <var>idx</var> = <b>tsearch</b> (<var>x, y, t, xi, yi</var>)<var><a name="index-tsearch-2095"></a></var><br> <blockquote><p>Searches for the enclosing Delaunay convex hull. For <var>t</var><code> = delaunay (</code><var>x</var><code>, </code><var>y</var><code>)</code>, finds the index in <var>t</var> containing the points <code>(</code><var>xi</var><code>, </code><var>yi</var><code>)</code>. For points outside the convex hull, <var>idx</var> is NaN. <!-- Texinfo @sp should work but in practice produces ugly results for HTML. --> <!-- A simple blank line produces the correct behavior. --> <!-- @sp 1 --> <p class="noindent"><strong>See also:</strong> <a href="doc_002ddelaunay.html#doc_002ddelaunay">delaunay</a>, <a href="doc_002ddelaunayn.html#doc_002ddelaunayn">delaunayn</a>. </p></blockquote></div> <!-- ./geometry/tsearchn.m --> <p><a name="doc_002dtsearchn"></a> <div class="defun"> — Function File: [<var>idx</var>, <var>p</var>] = <b>tsearchn</b> (<var>x, t, xi</var>)<var><a name="index-tsearchn-2096"></a></var><br> <blockquote><p>Searches for the enclosing Delaunay convex hull. For <var>t</var><code> = delaunayn (</code><var>x</var><code>)</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. If requested <code>tsearchn</code> also returns the Barycentric coordinates <var>p</var> of the enclosing triangles. <!-- Texinfo @sp should work but in practice produces ugly results for HTML. --> <!-- A simple blank line produces the correct behavior. --> <!-- @sp 1 --> <p class="noindent"><strong>See also:</strong> <a href="doc_002ddelaunay.html#doc_002ddelaunay">delaunay</a>, <a href="doc_002ddelaunayn.html#doc_002ddelaunayn">delaunayn</a>. </p></blockquote></div> <p>An example of the use of <code>tsearch</code> can be seen with the simple triangulation <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, 1]; </pre> <p class="noindent">consisting of two triangles defined by <var>tri</var>. We can then identify which triangle a point falls in like <pre class="example"> tsearch (<var>x</var>, <var>y</var>, <var>tri</var>, -0.5, -0.5) ⇒ 1 tsearch (<var>x</var>, <var>y</var>, <var>tri</var>, 0.5, 0.5) ⇒ 2 </pre> <p class="noindent">and we can confirm that a point doesn't lie within one of the triangles like <pre class="example"> tsearch (<var>x</var>, <var>y</var>, <var>tri</var>, 2, 2) ⇒ NaN </pre> <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. <!-- ./geometry/dsearch.m --> <p><a name="doc_002ddsearch"></a> <div class="defun"> — Function File: <var>idx</var> = <b>dsearch</b> (<var>x, y, tri, xi, yi</var>)<var><a name="index-dsearch-2097"></a></var><br> — Function File: <var>idx</var> = <b>dsearch</b> (<var>x, y, tri, xi, yi, s</var>)<var><a name="index-dsearch-2098"></a></var><br> <blockquote><p>Returns the index <var>idx</var> or the closest point in <var>x</var><code>, </code><var>y</var> to the elements <code>[</code><var>xi</var><code>(:), </code><var>yi</var><code>(:)]</code>. The variable <var>s</var> is accepted but ignored for compatibility. <!-- Texinfo @sp should work but in practice produces ugly results for HTML. --> <!-- A simple blank line produces the correct behavior. --> <!-- @sp 1 --> <p class="noindent"><strong>See also:</strong> <a href="doc_002ddsearchn.html#doc_002ddsearchn">dsearchn</a>, <a href="doc_002dtsearch.html#doc_002dtsearch">tsearch</a>. </p></blockquote></div> <!-- ./geometry/dsearchn.m --> <p><a name="doc_002ddsearchn"></a> <div class="defun"> — Function File: <var>idx</var> = <b>dsearchn</b> (<var>x, tri, xi</var>)<var><a name="index-dsearchn-2099"></a></var><br> — Function File: <var>idx</var> = <b>dsearchn</b> (<var>x, tri, xi, outval</var>)<var><a name="index-dsearchn-2100"></a></var><br> — Function File: <var>idx</var> = <b>dsearchn</b> (<var>x, xi</var>)<var><a name="index-dsearchn-2101"></a></var><br> — Function File: [<var>idx</var>, <var>d</var>] = <b>dsearchn</b> (<var><small class="dots">...</small></var>)<var><a name="index-dsearchn-2102"></a></var><br> <blockquote><p>Returns the index <var>idx</var> or the closest point in <var>x</var> to the elements <var>xi</var>. If <var>outval</var> is supplied, then the values of <var>xi</var> that are not contained within one of the simplicies <var>tri</var> are set to <var>outval</var>. Generally, <var>tri</var> is returned from <code>delaunayn (</code><var>x</var><code>)</code>. <!-- Texinfo @sp should work but in practice produces ugly results for HTML. --> <!-- A simple blank line produces the correct behavior. --> <!-- @sp 1 --> <p class="noindent"><strong>See also:</strong> <a href="doc_002ddsearch.html#doc_002ddsearch">dsearch</a>, <a href="doc_002dtsearch.html#doc_002dtsearch">tsearch</a>. </p></blockquote></div> <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 <pre class="example"> dsearch (<var>x</var>, <var>y</var>, <var>tri</var>, -2, -2) ⇒ 1 </pre> <p>If you wish the points that are outside the tessellation to be flagged, then <code>dsearchn</code> can be used as <pre class="example"> dsearchn ([<var>x</var>, <var>y</var>], <var>tri</var>, [-2, -2], NaN) ⇒ NaN dsearchn ([<var>x</var>, <var>y</var>], <var>tri</var>, [-0.5, -0.5], NaN) ⇒ 1 </pre> <p class="noindent">where the point outside the tessellation are then flagged with <code>NaN</code>. </body></html>