1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
|
<!DOCTYPE html>
<html>
<!-- Created by GNU Texinfo 7.1.1, https://www.gnu.org/software/texinfo/ -->
<head>
<meta http-equiv="Content-Type" content="text/html; charset=utf-8">
<title>Identifying Points in Triangulation (GNU Octave (version 10.3.0))</title>
<meta name="description" content="Identifying Points in Triangulation (GNU Octave (version 10.3.0))">
<meta name="keywords" content="Identifying Points in Triangulation (GNU Octave (version 10.3.0))">
<meta name="resource-type" content="document">
<meta name="distribution" content="global">
<meta name="Generator" content="makeinfo">
<meta name="viewport" content="width=device-width,initial-scale=1">
<link href="index.html" rel="start" title="Top">
<link href="Concept-Index.html" rel="index" title="Concept Index">
<link href="index.html#SEC_Contents" rel="contents" title="Table of Contents">
<link href="Delaunay-Triangulation.html" rel="up" title="Delaunay Triangulation">
<link href="Plotting-the-Triangulation.html" rel="prev" title="Plotting the Triangulation">
<style type="text/css">
<!--
a.copiable-link {visibility: hidden; text-decoration: none; line-height: 0em}
div.example {margin-left: 3.2em}
span:hover a.copiable-link {visibility: visible}
strong.def-name {font-family: monospace; font-weight: bold; font-size: larger}
-->
</style>
<link rel="stylesheet" type="text/css" href="octave.css">
</head>
<body lang="en">
<div class="subsection-level-extent" id="Identifying-Points-in-Triangulation">
<div class="nav-panel">
<p>
Previous: <a href="Plotting-the-Triangulation.html" accesskey="p" rel="prev">Plotting the Triangulation</a>, Up: <a href="Delaunay-Triangulation.html" accesskey="u" rel="up">Delaunay Triangulation</a> [<a href="index.html#SEC_Contents" title="Table of contents" rel="contents">Contents</a>][<a href="Concept-Index.html" title="Index" rel="index">Index</a>]</p>
</div>
<hr>
<h4 class="subsection" id="Identifying-Points-in-Triangulation-1"><span>30.1.2 Identifying Points in Triangulation<a class="copiable-link" href="#Identifying-Points-in-Triangulation-1"> ¶</a></span></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 function <code class="code">tsearch</code> performs this function in a triangulation,
and the functions <code class="code">tsearchn</code> and <code class="code">dsearchn</code> in an N-dimensional
tessellation.
</p>
<p>To identify whether a particular point represented by a vector <var class="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 class="var">N</var> + 1 vectors <code class="code"><var class="var">t</var>(<var class="var">i</var>,:)</code>, then the Barycentric
coordinates defining the point <var class="var">p</var> are given by
</p>
<div class="example">
<pre class="example-preformatted"><var class="var">p</var> = <var class="var">beta</var> * <var class="var">t</var>
</pre></div>
<p>where <var class="var">beta</var> contains <var class="var">N</var> + 1 values that together as a vector
represent the Barycentric coordinates of the point <var class="var">p</var>. To ensure a unique
solution for the values of <var class="var">beta</var> an additional criteria of
</p>
<div class="example">
<pre class="example-preformatted">sum (<var class="var">beta</var>) == 1
</pre></div>
<p>is imposed, and we can therefore write the above as
</p>
<div class="example">
<div class="group"><pre class="example-preformatted"><var class="var">p</var> - <var class="var">t</var>(end, :) = <var class="var">beta</var>(1:end-1) * (<var class="var">t</var>(1:end-1, :)
- ones (<var class="var">N</var>, 1) * <var class="var">t</var>(end, :)
</pre></div></div>
<p>Solving for <var class="var">beta</var> we can then write
</p>
<div class="example">
<div class="group"><pre class="example-preformatted"><var class="var">beta</var>(1:end-1) = (<var class="var">p</var> - <var class="var">t</var>(end, :)) /
(<var class="var">t</var>(1:end-1, :) - ones (<var class="var">N</var>, 1) * <var class="var">t</var>(end, :))
<var class="var">beta</var>(end) = sum (<var class="var">beta</var>(1:end-1))
</pre></div></div>
<p>which gives the formula for the conversion of the Cartesian coordinates
of the point <var class="var">p</var> to the Barycentric coordinates <var class="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-preformatted">0 <= <var class="var">beta</var>(<var class="var">i</var>) <= 1
</pre></div>
<p>Therefore, the test in <code class="code">tsearch</code> and <code class="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 class="var">beta</var>. This is exactly the implementation used in
<code class="code">tsearchn</code>. <code class="code">tsearch</code> is optimized for 2-dimensions and the
Barycentric coordinates are not explicitly formed.
</p>
<a class="anchor" id="XREFtsearch"></a><span style="display:block; margin-top:-4.5ex;"> </span>
<dl class="first-deftypefn">
<dt class="deftypefn" id="index-tsearch"><span><code class="def-type"><var class="var">idx</var> =</code> <strong class="def-name">tsearch</strong> <code class="def-code-arguments">(<var class="var">x</var>, <var class="var">y</var>, <var class="var">t</var>, <var class="var">xi</var>, <var class="var">yi</var>)</code><a class="copiable-link" href="#index-tsearch"> ¶</a></span></dt>
<dd><p>Search for the enclosing Delaunay convex hull.
</p>
<p>For <code class="code"><var class="var">t</var> = delaunay (<var class="var">x</var>, <var class="var">y</var>)</code>, finds the index in <var class="var">t</var>
containing the points <code class="code">(<var class="var">xi</var>, <var class="var">yi</var>)</code>. For points outside the
convex hull, <var class="var">idx</var> is NaN.
</p>
<p>Programming Note: The algorithm is <code class="code">O</code>(<var class="var">M</var>*<var class="var">N</var>) for locating
<var class="var">M</var> points in <var class="var">N</var> triangles. Performance is typically much faster if
the points to be located are in a single continuous path; a point is first
checked against the region its predecessor was found in, speeding up lookups
for points along a continuous path.
</p>
<p><strong class="strong">See also:</strong> <a class="ref" href="Delaunay-Triangulation.html#XREFdelaunay">delaunay</a>, <a class="ref" href="Delaunay-Triangulation.html#XREFdelaunayn">delaunayn</a>.
</p></dd></dl>
<a class="anchor" id="XREFtsearchn"></a><span style="display:block; margin-top:-4.5ex;"> </span>
<dl class="first-deftypefn">
<dt class="deftypefn" id="index-tsearchn"><span><code class="def-type"><var class="var">idx</var> =</code> <strong class="def-name">tsearchn</strong> <code class="def-code-arguments">(<var class="var">x</var>, <var class="var">t</var>, <var class="var">xi</var>)</code><a class="copiable-link" href="#index-tsearchn"> ¶</a></span></dt>
<dt class="deftypefnx def-cmd-deftypefn" id="index-tsearchn-1"><span><code class="def-type">[<var class="var">idx</var>, <var class="var">p</var>] =</code> <strong class="def-name">tsearchn</strong> <code class="def-code-arguments">(<var class="var">x</var>, <var class="var">t</var>, <var class="var">xi</var>)</code><a class="copiable-link" href="#index-tsearchn-1"> ¶</a></span></dt>
<dd><p>Find the simplexes enclosing the given points.
</p>
<p><code class="code">tsearchn</code> is typically used with <code class="code">delaunayn</code>:
<code class="code"><var class="var">t</var> = delaunayn (<var class="var">x</var>)</code> returns a set of simplexes <code class="code">t</code>,
then <code class="code">tsearchn</code> returns the row index of <var class="var">t</var> containing each point
of <var class="var">xi</var>. For points outside the convex hull, <var class="var">idx</var> is NaN.
</p>
<p>If requested, <code class="code">tsearchn</code> also returns the barycentric coordinates
<var class="var">p</var> of the enclosing simplexes.
</p>
<p><strong class="strong">See also:</strong> <a class="ref" href="#XREFtsearch">tsearch</a>, <a class="ref" href="#XREFdsearchn">dsearchn</a>, <a class="ref" href="Delaunay-Triangulation.html#XREFdelaunayn">delaunayn</a>.
</p></dd></dl>
<p>An example of the use of <code class="code">tsearch</code> can be seen with the simple
triangulation
</p>
<div class="example">
<div class="group"><pre class="example-preformatted"><var class="var">x</var> = [-1; -1; 1; 1];
<var class="var">y</var> = [-1; 1; -1; 1];
<var class="var">tri</var> = [1, 2, 3; 2, 3, 4];
</pre></div></div>
<p>consisting of two triangles defined by <var class="var">tri</var>. We can then identify
which triangle a point falls in like
</p>
<div class="example">
<div class="group"><pre class="example-preformatted">tsearch (<var class="var">x</var>, <var class="var">y</var>, <var class="var">tri</var>, -0.5, -0.5)
⇒ 1
tsearch (<var class="var">x</var>, <var class="var">y</var>, <var class="var">tri</var>, 0.5, 0.5)
⇒ 2
</pre></div></div>
<p>and we can confirm that a point doesn’t lie within one of the triangles like
</p>
<div class="example">
<div class="group"><pre class="example-preformatted">tsearch (<var class="var">x</var>, <var class="var">y</var>, <var class="var">tri</var>, 2, 2)
⇒ NaN
</pre></div></div>
<p>The <code class="code">dsearchn</code> function finds 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 vertices of the N-simplex within which the desired point
is found.
</p>
<a class="anchor" id="XREFdsearchn"></a><span style="display:block; margin-top:-4.5ex;"> </span>
<dl class="first-deftypefn">
<dt class="deftypefn" id="index-dsearchn"><span><code class="def-type"><var class="var">idx</var> =</code> <strong class="def-name">dsearchn</strong> <code class="def-code-arguments">(<var class="var">x</var>, <var class="var">tri</var>, <var class="var">xi</var>)</code><a class="copiable-link" href="#index-dsearchn"> ¶</a></span></dt>
<dt class="deftypefnx def-cmd-deftypefn" id="index-dsearchn-1"><span><code class="def-type"><var class="var">idx</var> =</code> <strong class="def-name">dsearchn</strong> <code class="def-code-arguments">(<var class="var">x</var>, <var class="var">tri</var>, <var class="var">xi</var>, <var class="var">outval</var>)</code><a class="copiable-link" href="#index-dsearchn-1"> ¶</a></span></dt>
<dt class="deftypefnx def-cmd-deftypefn" id="index-dsearchn-2"><span><code class="def-type"><var class="var">idx</var> =</code> <strong class="def-name">dsearchn</strong> <code class="def-code-arguments">(<var class="var">x</var>, <var class="var">xi</var>)</code><a class="copiable-link" href="#index-dsearchn-2"> ¶</a></span></dt>
<dt class="deftypefnx def-cmd-deftypefn" id="index-dsearchn-3"><span><code class="def-type">[<var class="var">idx</var>, <var class="var">d</var>] =</code> <strong class="def-name">dsearchn</strong> <code class="def-code-arguments">(…)</code><a class="copiable-link" href="#index-dsearchn-3"> ¶</a></span></dt>
<dd><p>Return the index <var class="var">idx</var> of the closest point in <var class="var">x</var> to the elements
<var class="var">xi</var>.
</p>
<p>If <var class="var">outval</var> is supplied, then the values of <var class="var">xi</var> that are not
contained within one of the simplices <var class="var">tri</var> are set to <var class="var">outval</var>.
Generally, <var class="var">tri</var> is returned from <code class="code">delaunayn (<var class="var">x</var>)</code>.
</p>
<p>The optional output <var class="var">d</var> contains a column vector of distances between
the query points <var class="var">xi</var> and the nearest simplex points <var class="var">x</var>.
</p>
<p>Compatibility note: The <code class="code">dsearchn</code> algorithm only uses the input
<var class="var">tri</var> when <var class="var">outdim</var> is specified to determine if any points lie
outside of the triangulation region. For compatibility, <var class="var">tri</var> is
accepted as an input even when <var class="var">outdim</var> is not specified, but it is not
used or checked to be a valid triangulation, and providing it will not
affect either the output <var class="var">idx</var> or the calculation efficiency.
</p>
<p><strong class="strong">See also:</strong> <a class="ref" href="#XREFtsearchn">tsearchn</a>, <a class="ref" href="Delaunay-Triangulation.html#XREFdelaunayn">delaunayn</a>.
</p></dd></dl>
<p>An example of the use of <code class="code">dsearchn</code>, using the above values of <var class="var">x</var>,
<var class="var">y</var> and <var class="var">tri</var> is
</p>
<div class="example">
<div class="group"><pre class="example-preformatted">dsearchn ([<var class="var">x</var>, <var class="var">y</var>], <var class="var">tri</var>, [-2, -2])
⇒ 1
</pre></div></div>
<p>If you wish the points that are outside the tessellation to be flagged,
then <code class="code">dsearchn</code> can be used as
</p>
<div class="example">
<div class="group"><pre class="example-preformatted">dsearchn ([<var class="var">x</var>, <var class="var">y</var>], <var class="var">tri</var>, [-2, -2], NaN)
⇒ NaN
dsearchn ([<var class="var">x</var>, <var class="var">y</var>], <var class="var">tri</var>, [-0.5, -0.5], NaN)
⇒ 1
</pre></div></div>
<p>where the point outside the tessellation are then flagged with <code class="code">NaN</code>.
</p>
</div>
<hr>
<div class="nav-panel">
<p>
Previous: <a href="Plotting-the-Triangulation.html">Plotting the Triangulation</a>, Up: <a href="Delaunay-Triangulation.html">Delaunay Triangulation</a> [<a href="index.html#SEC_Contents" title="Table of contents" rel="contents">Contents</a>][<a href="Concept-Index.html" title="Index" rel="index">Index</a>]</p>
</div>
</body>
</html>
|
