@c DO NOT EDIT!  Generated automatically by munge-texi.

@c Copyright (C) 2007, 2008, 2009 John W. Eaton and David Bateman
@c
@c This file is part of Octave.
@c
@c Octave is free software; you can redistribute it and/or modify it
@c under the terms of the GNU General Public License as published by the
@c Free Software Foundation; either version 3 of the License, or (at
@c your option) any later version.
@c 
@c Octave is distributed in the hope that it will be useful, but WITHOUT
@c ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
@c FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
@c for more details.
@c 
@c You should have received a copy of the GNU General Public License
@c along with Octave; see the file COPYING.  If not, see
@c <http://www.gnu.org/licenses/>.

@node Geometry
@chapter Geometry

Much of the geometry code in Octave is based on the Qhull 
library@footnote{Barber, C.B., Dobkin, D.P., and Huhdanpaa, H.T., 
"The Quickhull algorithm for convex hulls," ACM Trans. on Mathematical 
Software, 22(4):469--483, Dec 1996, @url{http://www.qhull.org}}.  
Some of the documentation for Qhull, particularly for the options that 
can be passed to @code{delaunay}, @code{voronoi} and @code{convhull}, 
etc., is relevant to Octave users.

@menu
* Delaunay Triangulation::
* Voronoi Diagrams::
* Convex Hull::
* Interpolation on Scattered Data::
@end menu

@node Delaunay Triangulation
@section Delaunay Triangulation

The Delaunay triangulation is constructed from a set of
circum-circles.  These circum-circles are chosen so that there are at
least three of the points in the set to triangulation on the
circumference of the circum-circle.  None of the points in the set of
points falls within any of the circum-circles.

In general there are only three points on the circumference of any
circum-circle.  However, in some cases, and in particular for the
case of a regular grid, 4 or more points can be on a single
circum-circle.  In this case the Delaunay triangulation is not unique. 

@c ./geometry/delaunay.m
@anchor{doc-delaunay}
@deftypefn {Function File} {@var{tri} =} delaunay (@var{x}, @var{y})
@deftypefnx {Function File} {@var{tri} =} delaunay (@var{x}, @var{y}, @var{opt})
The return matrix of size [n, 3] contains a set triangles which are
described by the indices to the data point x and y vector.
The triangulation satisfies the Delaunay circum-circle criterion.
No other data point is in the circum-circle of the defining triangle.

A third optional argument, which must be a string, contains extra options
passed to the underlying qhull command.  See the documentation for the 
Qhull library for details.

@example
@group
x = rand (1, 10);
y = rand (size (x));
T = delaunay (x, y);
X = [x(T(:,1)); x(T(:,2)); x(T(:,3)); x(T(:,1))];
Y = [y(T(:,1)); y(T(:,2)); y(T(:,3)); y(T(:,1))];
axis ([0,1,0,1]);
plot (X, Y, "b", x, y, "r*");
@end group
@end example
@seealso{@ref{doc-voronoi,,voronoi}, @ref{doc-delaunay3,,delaunay3}, @ref{doc-delaunayn,,delaunayn}}
@end deftypefn


The 3- and N-dimensional extension of the Delaunay triangulation are
given by @code{delaunay3} and @code{delaunayn} respectively.  
@code{delaunay3} returns a set of tetrahedra that satisfy the
Delaunay circum-circle criteria.  Similarly, @code{delaunayn} returns the
N-dimensional simplex satisfying the Delaunay circum-circle criteria.  
The N-dimensional extension of a triangulation is called a tessellation.

@c ./geometry/delaunay3.m
@anchor{doc-delaunay3}
@deftypefn {Function File} {@var{T} =} delaunay3 (@var{x}, @var{y}, @var{z})
@deftypefnx {Function File} {@var{T} =} delaunay3 (@var{x}, @var{y}, @var{z}, @var{opt})
A matrix of size [n, 4] is returned.  Each row contains a 
set of tetrahedron which are
described by the indices to the data point vectors (x,y,z).

A fourth optional argument, which must be a string or cell array of strings,
contains extra options passed to the underlying qhull command.  See the 
documentation for the Qhull library for details.
@seealso{@ref{doc-delaunay,,delaunay}, @ref{doc-delaunayn,,delaunayn}}
@end deftypefn


@c ./geometry/delaunayn.m
@anchor{doc-delaunayn}
@deftypefn {Function File} {@var{T} =} delaunayn (@var{P})
@deftypefnx {Function File} {@var{T} =} delaunayn (@var{P}, @var{opt})
Form the Delaunay triangulation for a set of points.
The Delaunay triangulation is a tessellation of the convex hull of the
points such that no n-sphere defined by the n-triangles contains
any other points from the set.
The input matrix @var{P} of size @code{[n, dim]} contains @var{n}
points in a space of dimension dim.  The return matrix @var{T} has the
size @code{[m, dim+1]}.  It contains for each row a set of indices to
the points, which describes a simplex of dimension dim.  For example,
a 2d simplex is a triangle and 3d simplex is a tetrahedron.

Extra options for the underlying Qhull command can be specified by the
second argument.  This argument is a cell array of strings.  The default
options depend on the dimension of the input: 

@itemize 
@item 2D and 3D: @var{opt} = @code{@{"Qt", "Qbb", "Qc"@}}
@item 4D and higher: @var{opt} = @code{@{"Qt", "Qbb", "Qc", "Qz"@}} 
@end itemize

If @var{opt} is [], then the default arguments are used.  If @var{opt}
is @code{@{"@w{}"@}}, then none of the default arguments are used by Qhull. 
See the Qhull documentation for the available options. 

All options can also be specified as single string, for example
@code{"Qt Qbb Qc Qz"}.

@end deftypefn


An example of a Delaunay triangulation of a set of points is

@example
@group
rand ("state", 2);
x = rand (10, 1);
y = rand (10, 1);
T = delaunay (x, y);
X = [ x(T(:,1)); x(T(:,2)); x(T(:,3)); x(T(:,1)) ];
Y = [ y(T(:,1)); y(T(:,2)); y(T(:,3)); y(T(:,1)) ];
axis ([0, 1, 0, 1]);
plot(X, Y, "b", x, y, "r*");
@end group
@end example

@ifset HAVE_QHULL
@ifnotinfo
@noindent
The result of which can be seen in @ref{fig:delaunay}.

@float Figure,fig:delaunay
@center @image{delaunay,4in}
@caption{Delaunay triangulation of a random set of points}
@end float
@end ifnotinfo
@end ifset

@menu
* Plotting the Triangulation::
* Identifying points in Triangulation::
@end menu

@node Plotting the Triangulation
@subsection Plotting the Triangulation

Octave has the functions @code{triplot} and @code{trimesh} to plot the
Delaunay triangulation of a 2-dimensional set of points.

@c ./geometry/triplot.m
@anchor{doc-triplot}
@deftypefn {Function File} {} triplot (@var{tri}, @var{x}, @var{y})
@deftypefnx {Function File} {} triplot (@var{tri}, @var{x}, @var{y}, @var{linespec})
@deftypefnx {Function File} {@var{h} =} triplot (@dots{})
Plot a triangular mesh in 2D.  The variable @var{tri} is the triangular
meshing of the points @code{(@var{x}, @var{y})} which is returned from
@code{delaunay}.  If given, the @var{linespec} determines the properties
to use for the lines.  The output argument @var{h} is the graphic handle
to the plot.
@seealso{@ref{doc-plot,,plot}, @ref{doc-trimesh,,trimesh}, @ref{doc-delaunay,,delaunay}}
@end deftypefn


@c ./geometry/trimesh.m
@anchor{doc-trimesh}
@deftypefn {Function File} {} trimesh (@var{tri}, @var{x}, @var{y}, @var{z})
@deftypefnx {Function File} {@var{h} =} trimesh (@dots{})
Plot a triangular mesh in 3D.  The variable @var{tri} is the triangular
meshing of the points @code{(@var{x}, @var{y})} which is returned 
from @code{delaunay}.  The variable @var{z} is value at the point 
@code{(@var{x}, @var{y})}.  The output argument @var{h} is the graphic 
handle to the plot.
@seealso{@ref{doc-triplot,,triplot}, @ref{doc-delaunay3,,delaunay3}}
@end deftypefn


The difference between @code{triplot} and @code{trimesh} is that the
former only plots the 2-dimensional triangulation itself, whereas the
second plots the value of some function @code{f (@var{x}, @var{y})}.
An example of the use of the @code{triplot} function is

@example
@group
rand ("state", 2)
x = rand (20, 1);
y = rand (20, 1);
tri = delaunay (x, y);
triplot (tri, x, y);
@end group
@end example

that plot the Delaunay triangulation of a set of random points in
2-dimensions.
@ifnotinfo
The output of the above can be seen in @ref{fig:triplot}.

@float Figure,fig:triplot
@center @image{triplot,4in}
@caption{Delaunay triangulation of a random set of points}
@end float
@end ifnotinfo

@node Identifying points in Triangulation
@subsection Identifying points in Triangulation

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} and @code{dsearch} perform this
function in a triangulation, and @code{tsearchn} and @code{dsearchn} in
an N-dimensional tessellation.

To identify whether a particular point represented by a vector @var{p}
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 @code{@var{N} + 1} vectors @var{t}(@var{i},:), then the Barycentric
coordinates defining the point @var{p} are given by

@example
@var{p} = sum (@var{beta}(1:@var{N}+1) * @var{t}(1:@var{N}+1),:)
@end example

@noindent
where there are @code{@var{N} + 1} values @code{@var{beta}(@var{i})}
that together as a vector represent the Barycentric coordinates of the
point @var{p}.  To ensure a unique solution for the values of
@code{@var{beta}(@var{i})} an additional criteria of

@example
sum (@var{beta}(1:@var{N}+1)) == 1
@end example

@noindent
is imposed, and we can therefore write the above as

@example
@group
@var{p} - @var{t}(end, :) = @var{beta}(1:end-1) * (@var{t}(1:end-1, :)
      - ones(@var{N}, 1) * @var{t}(end, :)
@end group
@end example

@noindent
Solving for @var{beta} we can then write

@example
@group
@var{beta}(1:end-1) = (@var{p} - @var{t}(end, :)) / (@var{t}(1:end-1, :)
      - ones(@var{N}, 1) * @var{t}(end, :))
@var{beta}(end) = sum(@var{beta}(1:end-1))
@end group
@end example

@noindent
which gives the formula for the conversion of the Cartesian coordinates
of the point @var{p} to the Barycentric coordinates @var{beta}.  An
important property of the Barycentric coordinates is that for all points
in the N-simplex

@example
0 <= @var{beta}(@var{i}) <= 1
@end example

@noindent
Therefore, the test in @code{tsearch} and @code{tsearchn} 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}.  This is exactly the implementation used in
@code{tsearchn}.  @code{tsearch} is optimized for 2-dimensions and the
Barycentric coordinates are not explicitly formed.

@c ./DLD-FUNCTIONS/tsearch.cc
@anchor{doc-tsearch}
@deftypefn {Loadable Function} {@var{idx} =} tsearch (@var{x}, @var{y}, @var{t}, @var{xi}, @var{yi})
Searches for the enclosing Delaunay convex hull.  For @code{@var{t} =
delaunay (@var{x}, @var{y})}, finds the index in @var{t} containing the
points @code{(@var{xi}, @var{yi})}.  For points outside the convex hull,
@var{idx} is NaN.
@seealso{@ref{doc-delaunay,,delaunay}, @ref{doc-delaunayn,,delaunayn}}
@end deftypefn


@c ./geometry/tsearchn.m
@anchor{doc-tsearchn}
@deftypefn {Function File} {[@var{idx}, @var{p}] =} tsearchn (@var{x}, @var{t}, @var{xi})
Searches for the enclosing Delaunay convex hull.  For @code{@var{t} =
delaunayn (@var{x})}, finds the index in @var{t} containing the
points @var{xi}.  For points outside the convex hull, @var{idx} is NaN.
If requested @code{tsearchn} also returns the Barycentric coordinates @var{p}
of the enclosing triangles.
@seealso{@ref{doc-delaunay,,delaunay}, @ref{doc-delaunayn,,delaunayn}}
@end deftypefn


An example of the use of @code{tsearch} can be seen with the simple
triangulation

@example
@group
@var{x} = [-1; -1; 1; 1];
@var{y} = [-1; 1; -1; 1];
@var{tri} = [1, 2, 3; 2, 3, 1];
@end group
@end example

@noindent
consisting of two triangles defined by @var{tri}.  We can then identify
which triangle a point falls in like

@example
@group
tsearch (@var{x}, @var{y}, @var{tri}, -0.5, -0.5)
@result{} 1
tsearch (@var{x}, @var{y}, @var{tri}, 0.5, 0.5)
@result{} 2
@end group
@end example

@noindent
and we can confirm that a point doesn't lie within one of the triangles like

@example
@group
tsearch (@var{x}, @var{y}, @var{tri}, 2, 2)
@result{} NaN
@end group
@end example

The @code{dsearch} and @code{dsearchn} 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.

@c ./geometry/dsearch.m
@anchor{doc-dsearch}
@deftypefn {Function File} {@var{idx} =} dsearch (@var{x}, @var{y}, @var{tri}, @var{xi}, @var{yi})
@deftypefnx {Function File} {@var{idx} =} dsearch (@var{x}, @var{y}, @var{tri}, @var{xi}, @var{yi}, @var{s})
Returns the index @var{idx} or the closest point in @code{@var{x}, @var{y}}
to the elements @code{[@var{xi}(:), @var{yi}(:)]}.  The variable @var{s} is
accepted but ignored for compatibility.
@seealso{@ref{doc-dsearchn,,dsearchn}, @ref{doc-tsearch,,tsearch}}
@end deftypefn


@c ./geometry/dsearchn.m
@anchor{doc-dsearchn}
@deftypefn {Function File} {@var{idx} =} dsearchn (@var{x}, @var{tri}, @var{xi})
@deftypefnx {Function File} {@var{idx} =} dsearchn (@var{x}, @var{tri}, @var{xi}, @var{outval})
@deftypefnx {Function File} {@var{idx} =} dsearchn (@var{x}, @var{xi})
@deftypefnx {Function File} {[@var{idx}, @var{d}] =} dsearchn (@dots{})
Returns the index @var{idx} or the closest point in @var{x} to the elements
@var{xi}.  If @var{outval} is supplied, then the values of @var{xi} that are
not contained within one of the simplicies @var{tri} are set to 
@var{outval}.  Generally, @var{tri} is returned from @code{delaunayn 
(@var{x})}.
@seealso{@ref{doc-dsearch,,dsearch}, @ref{doc-tsearch,,tsearch}}
@end deftypefn


An example of the use of @code{dsearch}, using the above values of
@var{x}, @var{y} and @var{tri} is

@example
@group
dsearch (@var{x}, @var{y}, @var{tri}, -2, -2)
@result{} 1
@end group
@end example

If you wish the points that are outside the tessellation to be flagged,
then @code{dsearchn} can be used as

@example
@group
dsearchn ([@var{x}, @var{y}], @var{tri}, [-2, -2], NaN)
@result{} NaN
dsearchn ([@var{x}, @var{y}], @var{tri}, [-0.5, -0.5], NaN)
@result{} 1
@end group
@end example

@noindent
where the point outside the tessellation are then flagged with @code{NaN}.

@node Voronoi Diagrams
@section Voronoi Diagrams

A Voronoi diagram or Voronoi tessellation of a set of points @var{s} in
an N-dimensional space, is the tessellation of the N-dimensional space
such that all points in @code{@var{v}(@var{p})}, a partitions of the
tessellation where @var{p} is a member of @var{s}, are closer to @var{p}
than any other point in @var{s}.  The Voronoi diagram is related to the
Delaunay triangulation of a set of points, in that the vertexes of the
Voronoi tessellation are the centers of the circum-circles of the
simplicies of the Delaunay tessellation. 

@c ./geometry/voronoi.m
@anchor{doc-voronoi}
@deftypefn {Function File} {} voronoi (@var{x}, @var{y})
@deftypefnx {Function File} {} voronoi (@var{x}, @var{y}, "plotstyle")
@deftypefnx {Function File} {} voronoi (@var{x}, @var{y}, "plotstyle", @var{options})
@deftypefnx {Function File} {[@var{vx}, @var{vy}] =} voronoi (@dots{})
plots voronoi diagram of points @code{(@var{x}, @var{y})}.
The voronoi facets with points at infinity are not drawn.
[@var{vx}, @var{vy}] = voronoi(@dots{}) returns the vertices instead of plotting the
diagram. plot (@var{vx}, @var{vy}) shows the voronoi diagram.

A fourth optional argument, which must be a string, contains extra options
passed to the underlying qhull command.  See the documentation for the
Qhull library for details.

@example
@group
  x = rand (10, 1);
  y = rand (size (x));
  h = convhull (x, y);
  [vx, vy] = voronoi (x, y);
  plot (vx, vy, "-b", x, y, "o", x(h), y(h), "-g")
  legend ("", "points", "hull");
@end group
@end example

@seealso{@ref{doc-voronoin,,voronoin}, @ref{doc-delaunay,,delaunay}, @ref{doc-convhull,,convhull}}
@end deftypefn


@c ./geometry/voronoin.m
@anchor{doc-voronoin}
@deftypefn {Function File} {[@var{C}, @var{F}] =} voronoin (@var{pts})
@deftypefnx {Function File} {[@var{C}, @var{F}] =} voronoin (@var{pts}, @var{options})
computes n- dimensional voronoi facets.  The input matrix @var{pts}
of size [n, dim] contains n points of dimension dim.
@var{C} contains the points of the voronoi facets.  The list @var{F}
contains for each facet the indices of the voronoi points.

A second optional argument, which must be a string, contains extra options
passed to the underlying qhull command.  See the documentation for the
Qhull library for details.
@seealso{@ref{doc-voronoin,,voronoin}, @ref{doc-delaunay,,delaunay}, @ref{doc-convhull,,convhull}}
@end deftypefn


An example of the use of @code{voronoi} is

@example
@group
rand("state",9);
x = rand(10,1);
y = rand(10,1);
tri = delaunay (x, y);
[vx, vy] = voronoi (x, y, tri);
triplot (tri, x, y, "b");
hold on;
plot (vx, vy, "r");
@end group
@end example

@ifset HAVE_QHULL
@ifnotinfo
@noindent
The result of which can be seen in @ref{fig:voronoi}.  Note that the
circum-circle of one of the triangles has been added to this figure, to
make the relationship between the Delaunay tessellation and the Voronoi
diagram clearer.

@float Figure,fig:voronoi
@center @image{voronoi,4in}
@caption{Delaunay triangulation and Voronoi diagram of a random set of points}
@end float
@end ifnotinfo
@end ifset

Additional information about the size of the facets of a Voronoi
diagram, and which points of a set of points is in a polygon can be had
with the @code{polyarea} and @code{inpolygon} functions respectively.

@c ./general/polyarea.m
@anchor{doc-polyarea}
@deftypefn {Function File} {} polyarea (@var{x}, @var{y})
@deftypefnx {Function File} {} polyarea (@var{x}, @var{y}, @var{dim})

Determines area of a polygon by triangle method.  The variables
@var{x} and @var{y} define the vertex pairs, and must therefore have
the same shape.  They can be either vectors or arrays.  If they are
arrays then the columns of @var{x} and @var{y} are treated separately
and an area returned for each.

If the optional @var{dim} argument is given, then @code{polyarea}
works along this dimension of the arrays @var{x} and @var{y}.

@end deftypefn


An example of the use of @code{polyarea} might be 

@example
@group
rand ("state", 2);
x = rand (10, 1);
y = rand (10, 1);
[c, f] = voronoin ([x, y]);
af = zeros (size(f));
for i = 1 : length (f)
  af(i) = polyarea (c (f @{i, :@}, 1), c (f @{i, :@}, 2));
endfor
@end group
@end example

Facets of the Voronoi diagram with a vertex at infinity have infinity
area.  A simplified version of @code{polyarea} for rectangles is
available with @code{rectint}

@c ./geometry/rectint.m
@anchor{doc-rectint}
@deftypefn {Function File} {@var{area} =} rectint (@var{a}, @var{b})

Compute the area of intersection of rectangles in @var{a} and
rectangles in @var{b}.  Rectangles are defined as [x y width height]
where x and y are the minimum values of the two orthogonal
dimensions.

If @var{a} or @var{b} are matrices, then the output, @var{area}, is a
matrix where the i-th row corresponds to the i-th row of a and the j-th
column corresponds to the j-th row of b.

@seealso{@ref{doc-polyarea,,polyarea}}
@end deftypefn


@c ./geometry/inpolygon.m
@anchor{doc-inpolygon}
@deftypefn {Function File} {[@var{in}, @var{on}] =} inpolygon (@var{x}, @var{y}, @var{xv}, @var{xy})

For a polygon defined by @code{(@var{xv}, @var{yv})} points, determine
if the points @code{(@var{x}, @var{y})} are inside or outside the polygon.
The variables @var{x}, @var{y}, must have the same dimension.  The optional
output @var{on} gives the points that are on the polygon.

@end deftypefn


An example of the use of @code{inpolygon} might be

@example
@group
randn ("state", 2);
x = randn (100, 1);
y = randn (100, 1);
vx = cos (pi * [-1 : 0.1: 1]);
vy = sin (pi * [-1 : 0.1 : 1]);
in = inpolygon (x, y, vx, vy);
plot(vx, vy, x(in), y(in), "r+", x(!in), y(!in), "bo");
axis ([-2, 2, -2, 2]);
@end group
@end example

@ifnotinfo
@noindent
The result of which can be seen in @ref{fig:inpolygon}.

@float Figure,fig:inpolygon
@center @image{inpolygon,4in}
@caption{Demonstration of the @code{inpolygon} function to determine the
points inside a polygon}
@end float
@end ifnotinfo

@node Convex Hull
@section Convex Hull

The convex hull of a set of points is the minimum convex envelope
containing all of the points.  Octave has the functions @code{convhull}
and @code{convhulln} to calculate the convex hull of 2-dimensional and
N-dimensional sets of points.

@c ./geometry/convhull.m
@anchor{doc-convhull}
@deftypefn {Function File} {@var{H} =} convhull (@var{x}, @var{y})
@deftypefnx {Function File} {@var{H} =} convhull (@var{x}, @var{y}, @var{opt})
Returns the index vector to the points of the enclosing convex hull.  The
data points are defined by the x and y vectors.

A third optional argument, which must be a string, contains extra options
passed to the underlying qhull command.  See the documentation for the 
Qhull library for details.

@seealso{@ref{doc-delaunay,,delaunay}, @ref{doc-convhulln,,convhulln}}
@end deftypefn


@c ./DLD-FUNCTIONS/convhulln.cc
@anchor{doc-convhulln}
@deftypefn {Loadable Function} {@var{h} =} convhulln (@var{p})
@deftypefnx {Loadable Function} {@var{h} =} convhulln (@var{p}, @var{opt})
@deftypefnx {Loadable Function} {[@var{h}, @var{v}] =} convhulln (@dots{})
Return an index vector to the points of the enclosing convex hull.
The input matrix of size [n, dim] contains n points of dimension dim.

If a second optional argument is given, it must be a string or cell array
of strings containing options for the underlying qhull command.  (See
the Qhull documentation for the available options.)  The default options
are "s Qci Tcv".
If the second output @var{V} is requested the volume of the convex hull is
calculated.

@seealso{@ref{doc-convhull,,convhull}, @ref{doc-delaunayn,,delaunayn}}
@end deftypefn


An example of the use of @code{convhull} is

@example
@group
x = -3:0.05:3;
y = abs (sin (x));
k = convhull (x, y);
plot (x(k), y(k), "r-", x, y, "b+");
axis ([-3.05, 3.05, -0.05, 1.05]);
@end group
@end example

@ifset HAVE_QHULL
@ifnotinfo
@noindent
The output of the above can be seen in @ref{fig:convhull}.

@float Figure,fig:convhull
@center @image{convhull,4in}
@caption{The convex hull of a simple set of points}
@end float
@end ifnotinfo
@end ifset

@node Interpolation on Scattered Data
@section Interpolation on Scattered Data

An important use of the Delaunay tessellation is that it can be used to
interpolate from scattered data to an arbitrary set of points.  To do
this the N-simplex of the known set of points is calculated with
@code{delaunay}, @code{delaunay3} or @code{delaunayn}.  Then the
simplicies in to which the desired points are found are
identified.  Finally the vertices of the simplicies are used to
interpolate to the desired points.  The functions that perform this
interpolation are @code{griddata}, @code{griddata3} and
@code{griddatan}.

@c ./geometry/griddata.m
@anchor{doc-griddata}
@deftypefn {Function File} {@var{zi} =} griddata (@var{x}, @var{y}, @var{z}, @var{xi}, @var{yi}, @var{method})
@deftypefnx {Function File} {[@var{xi}, @var{yi}, @var{zi}] =} griddata (@var{x}, @var{y}, @var{z}, @var{xi}, @var{yi}, @var{method})

Generate a regular mesh from irregular data using interpolation.
The function is defined by @code{@var{z} = f (@var{x}, @var{y})}.
The interpolation points are all @code{(@var{xi}, @var{yi})}.  If
@var{xi}, @var{yi} are vectors then they are made into a 2D mesh.

The interpolation method can be @code{"nearest"}, @code{"cubic"} or
@code{"linear"}.  If method is omitted it defaults to @code{"linear"}.
@seealso{@ref{doc-delaunay,,delaunay}}
@end deftypefn


@c ./geometry/griddata3.m
@anchor{doc-griddata3}
@deftypefn {Function File} {@var{vi} =} griddata3 (@var{x}, @var{y}, @var{z}, @var{v} @var{xi}, @var{yi}, @var{zi}, @var{method}, @var{options})

Generate a regular mesh from irregular data using interpolation.
The function is defined by @code{@var{y} = f (@var{x},@var{y},@var{z})}.
The interpolation points are all @var{xi}.  

The interpolation method can be @code{"nearest"} or @code{"linear"}.
If method is omitted it defaults to @code{"linear"}.
@seealso{@ref{doc-griddata,,griddata}, @ref{doc-delaunayn,,delaunayn}}
@end deftypefn


@c ./geometry/griddatan.m
@anchor{doc-griddatan}
@deftypefn {Function File} {@var{yi} =} griddatan (@var{x}, @var{y}, @var{xi}, @var{method}, @var{options})

Generate a regular mesh from irregular data using interpolation.
The function is defined by @code{@var{y} = f (@var{x})}.
The interpolation points are all @var{xi}.  

The interpolation method can be @code{"nearest"} or @code{"linear"}.
If method is omitted it defaults to @code{"linear"}.
@seealso{@ref{doc-griddata,,griddata}, @ref{doc-delaunayn,,delaunayn}}
@end deftypefn


An example of the use of the @code{griddata} function is

@example
@group
rand("state",1);
x=2*rand(1000,1)-1;
y=2*rand(size(x))-1;
z=sin(2*(x.^2+y.^2));
[xx,yy]=meshgrid(linspace(-1,1,32));
griddata(x,y,z,xx,yy);
@end group
@end example

@ifset HAVE_QHULL
@noindent
that interpolates from a random scattering of points, to a uniform
grid. 
@ifnotinfo
The output of the above can be seen in @ref{fig:griddata}.

@float Figure,fig:griddata
@center @image{griddata,4in}
@caption{Interpolation from a scattered data to a regular grid}
@end float
@end ifnotinfo
@end ifset