Mercurial > hg > octave-nkf

comparison doc/interpreter/geometry.txi @ 9070:e9dc2ed2ec0f

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Cleanup documentation for poly.texi, interp.texi, geometry.texi Grammarcheck input .txi files Spellcheck .texi files
author Rik <rdrider0-list@yahoo.com>
date Sun, 29 Mar 2009 10:22:56 -0700
parents eb63fbe60fab
children 77e71f3da3d6
comparison
equal deleted inserted replaced
9069:634274aaa183 9070:e9dc2ed2ec0f
17 @c <http://www.gnu.org/licenses/>. 17 @c <http://www.gnu.org/licenses/>.
18 18
19 @node Geometry 19 @node Geometry
20 @chapter Geometry 20 @chapter Geometry
21 21
22 Much of geometry code in Octave is based on the QHull library@footnote{Barber, 22 Much of the geometry code in Octave is based on the Qhull
23 C.B., Dobkin, D.P., and Huhdanpaa, H.T., "The Quickhull algorithm for 23 library@footnote{Barber, C.B., Dobkin, D.P., and Huhdanpaa, H.T.,
24 convex hulls," ACM Trans. on Mathematical Software, 22(4):469-483, Dec 24 "The Quickhull algorithm for convex hulls," ACM Trans. on Mathematical
25 1996, @url{http://www.qhull.org}}. Some of the documentation for Qhull, 25 Software, 22(4):469--483, Dec 1996, @url{http://www.qhull.org}}.
26 particularly for the options that can be passed to @code{delaunay}, 26 Some of the documentation for Qhull, particularly for the options that
27 @code{voronoi} and @code{convhull}, etc, is relevant to Octave users. 27 can be passed to @code{delaunay}, @code{voronoi} and @code{convhull},
28 etc., is relevant to Octave users.
28 29
29 @menu 30 @menu
30 * Delaunay Triangulation:: 31 * Delaunay Triangulation::
31 * Voronoi Diagrams:: 32 * Voronoi Diagrams::
32 * Convex Hull:: 33 * Convex Hull::
35 36
36 @node Delaunay Triangulation 37 @node Delaunay Triangulation
37 @section Delaunay Triangulation 38 @section Delaunay Triangulation
38 39
39 The Delaunay triangulation is constructed from a set of 40 The Delaunay triangulation is constructed from a set of
40 circum-circles. These circum-circles are chosen so that there are at 41 circum-circles. These circum-circles are chosen so that there are at
41 least three of the points in the set to triangulation on the 42 least three of the points in the set to triangulation on the
42 circumference of the circum-circle. None of the points in the set of 43 circumference of the circum-circle. None of the points in the set of
43 points falls within any of the circum-circles. 44 points falls within any of the circum-circles.
44 45
45 In general there are only three points on the circumference of any 46 In general there are only three points on the circumference of any
46 circum-circle. However, in some cases, and in particular for the 47 circum-circle. However, in some cases, and in particular for the
47 case of a regular grid, 4 or more points can be on a single 48 case of a regular grid, 4 or more points can be on a single
48 circum-circle. In this case the Delaunay triangulation is not unique. 49 circum-circle. In this case the Delaunay triangulation is not unique.
49 50
50 @DOCSTRING(delaunay) 51 @DOCSTRING(delaunay)
51 52
52 The 3- and N-dimensional extension of the Delaunay triangulation are 53 The 3- and N-dimensional extension of the Delaunay triangulation are
53 given by @code{delaunay3} and @code{delaunayn} respectively. 54 given by @code{delaunay3} and @code{delaunayn} respectively.
163 164
164 @noindent 165 @noindent
165 is imposed, and we can therefore write the above as 166 is imposed, and we can therefore write the above as
166 167
167 @example 168 @example
169 @group
168 @var{p} - @var{t}(end, :) = @var{beta}(1:end-1) * (@var{t}(1:end-1, :) 170 @var{p} - @var{t}(end, :) = @var{beta}(1:end-1) * (@var{t}(1:end-1, :)
169 - ones(@var{N}, 1) * @var{t}(end, :) 171 - ones(@var{N}, 1) * @var{t}(end, :)
172 @end group
170 @end example 173 @end example
171 174
172 @noindent 175 @noindent
173 Solving for @var{beta} we can then write 176 Solving for @var{beta} we can then write
174 177
175 @example 178 @example
179 @group
176 @var{beta}(1:end-1) = (@var{p} - @var{t}(end, :)) / (@var{t}(1:end-1, :) 180 @var{beta}(1:end-1) = (@var{p} - @var{t}(end, :)) / (@var{t}(1:end-1, :)
177 - ones(@var{N}, 1) * @var{t}(end, :)) 181 - ones(@var{N}, 1) * @var{t}(end, :))
178 @var{beta}(end) = sum(@var{beta}(1:end-1)) 182 @var{beta}(end) = sum(@var{beta}(1:end-1))
183 @end group
179 @end example 184 @end example
180 185
181 @noindent 186 @noindent
182 which gives the formula for the conversion of the Cartesian coordinates 187 which gives the formula for the conversion of the Cartesian coordinates
183 of the point @var{p} to the Barycentric coordinates @var{beta}. An 188 of the point @var{p} to the Barycentric coordinates @var{beta}. An
190 195
191 @noindent 196 @noindent
192 Therefore, the test in @code{tsearch} and @code{tsearchn} essentially 197 Therefore, the test in @code{tsearch} and @code{tsearchn} essentially
193 only needs to express each point in terms of the Barycentric coordinates 198 only needs to express each point in terms of the Barycentric coordinates
194 of each of the simplices of the N-simplex and test the values of 199 of each of the simplices of the N-simplex and test the values of
195 @var{beta}. This is exactly the implementation used in 200 @var{beta}. This is exactly the implementation used in
196 @code{tsearchn}. @code{tsearch} is optimized for 2-dimensions and the 201 @code{tsearchn}. @code{tsearch} is optimized for 2-dimensions and the
197 Barycentric coordinates are not explicitly formed. 202 Barycentric coordinates are not explicitly formed.
198 203
199 @DOCSTRING(tsearch) 204 @DOCSTRING(tsearch)
200 205
201 @DOCSTRING(tsearchn) 206 @DOCSTRING(tsearchn)
210 @var{tri} = [1, 2, 3; 2, 3, 1]; 215 @var{tri} = [1, 2, 3; 2, 3, 1];
211 @end group 216 @end group
212 @end example 217 @end example
213 218
214 @noindent 219 @noindent
215 consisting of two triangles defined by @var{tri}. We can then identify 220 consisting of two triangles defined by @var{tri}. We can then identify
216 which triangle a point falls in like 221 which triangle a point falls in like
217 222
218 @example 223 @example
219 @group 224 @group
220 tsearch (@var{x}, @var{y}, @var{tri}, -0.5, -0.5) 225 tsearch (@var{x}, @var{y}, @var{tri}, -0.5, -0.5)
233 @result{} NaN 238 @result{} NaN
234 @end group 239 @end group
235 @end example 240 @end example
236 241
237 The @code{dsearch} and @code{dsearchn} find the closest point in a 242 The @code{dsearch} and @code{dsearchn} find the closest point in a
238 tessellation to the desired point. The desired point does not 243 tessellation to the desired point. The desired point does not
239 necessarily have to be in the tessellation, and even if it the returned 244 necessarily have to be in the tessellation, and even if it the returned
240 point of the tessellation does not have to be one of the vertexes of the 245 point of the tessellation does not have to be one of the vertexes of the
241 N-simplex within which the desired point is found. 246 N-simplex within which the desired point is found.
242 247
243 @DOCSTRING(dsearch) 248 @DOCSTRING(dsearch)
276 an N-dimensional space, is the tessellation of the N-dimensional space 281 an N-dimensional space, is the tessellation of the N-dimensional space
277 such that all points in @code{@var{v}(@var{p})}, a partitions of the 282 such that all points in @code{@var{v}(@var{p})}, a partitions of the
278 tessellation where @var{p} is a member of @var{s}, are closer to @var{p} 283 tessellation where @var{p} is a member of @var{s}, are closer to @var{p}
279 than any other point in @var{s}. The Voronoi diagram is related to the 284 than any other point in @var{s}. The Voronoi diagram is related to the
280 Delaunay triangulation of a set of points, in that the vertexes of the 285 Delaunay triangulation of a set of points, in that the vertexes of the
281 Voronoi tessellation are the centers of the circum-circles of the 286 Voronoi tessellation are the centers of the circum-circles of the
282 simplicies of the Delaunay tessellation. 287 simplicies of the Delaunay tessellation.
283 288
284 @DOCSTRING(voronoi) 289 @DOCSTRING(voronoi)
285 290
286 @DOCSTRING(voronoin) 291 @DOCSTRING(voronoin)
301 @end example 306 @end example
302 307
303 @ifset HAVE_QHULL 308 @ifset HAVE_QHULL
304 @ifnotinfo 309 @ifnotinfo
305 @noindent 310 @noindent
306 The result of which can be seen in @ref{fig:voronoi}. Note that the 311 The result of which can be seen in @ref{fig:voronoi}. Note that the
307 circum-circle of one of the triangles has been added to this figure, to 312 circum-circle of one of the triangles has been added to this figure, to
308 make the relationship between the Delaunay tessellation and the Voronoi 313 make the relationship between the Delaunay tessellation and the Voronoi
309 diagram clearer. 314 diagram clearer.
310 315
311 @float Figure,fig:voronoi 316 @float Figure,fig:voronoi
335 endfor 340 endfor
336 @end group 341 @end group
337 @end example 342 @end example
338 343
339 Facets of the Voronoi diagram with a vertex at infinity have infinity 344 Facets of the Voronoi diagram with a vertex at infinity have infinity
340 area. A simplified version of @code{polyarea} for rectangles is 345 area. A simplified version of @code{polyarea} for rectangles is
341 available with @code{rectint} 346 available with @code{rectint}
342 347
343 @DOCSTRING(rectint) 348 @DOCSTRING(rectint)
344 349
345 @DOCSTRING(inpolygon) 350 @DOCSTRING(inpolygon)
372 377
373 @node Convex Hull 378 @node Convex Hull
374 @section Convex Hull 379 @section Convex Hull
375 380
376 The convex hull of a set of points is the minimum convex envelope 381 The convex hull of a set of points is the minimum convex envelope
377 containing all of the points. Octave has the functions @code{convhull} 382 containing all of the points. Octave has the functions @code{convhull}
378 and @code{convhulln} to calculate the convex hull of 2-dimensional and 383 and @code{convhulln} to calculate the convex hull of 2-dimensional and
379 N-dimensional sets of points. 384 N-dimensional sets of points.
380 385
381 @DOCSTRING(convhull) 386 @DOCSTRING(convhull)
382 387
408 413
409 @node Interpolation on Scattered Data 414 @node Interpolation on Scattered Data
410 @section Interpolation on Scattered Data 415 @section Interpolation on Scattered Data
411 416
412 An important use of the Delaunay tessellation is that it can be used to 417 An important use of the Delaunay tessellation is that it can be used to
413 interpolate from scattered data to an arbitrary set of points. To do 418 interpolate from scattered data to an arbitrary set of points. To do
414 this the N-simplex of the known set of points is calculated with 419 this the N-simplex of the known set of points is calculated with
415 @code{delaunay}, @code{delaunay3} or @code{delaunayn}. Then the 420 @code{delaunay}, @code{delaunay3} or @code{delaunayn}. Then the
416 simplicies in to which the desired points are found are 421 simplicies in to which the desired points are found are
417 identified. Finally the vertices of the simplicies are used to 422 identified. Finally the vertices of the simplicies are used to
418 interpolate to the desired points. The functions that perform this 423 interpolate to the desired points. The functions that perform this
419 interpolation are @code{griddata}, @code{griddata3} and 424 interpolation are @code{griddata}, @code{griddata3} and
420 @code{griddatan}. 425 @code{griddatan}.
421 426
422 @DOCSTRING(griddata) 427 @DOCSTRING(griddata)
423 428