Mathematics

Triangulation and Interpolation of Scattered Data

MATLAB provides routines that aid in the analysis of closest-point problems and geometric analysis.

Functions for Analysis of Closest-Point Problems and Geometric Analysis  

Function	Description
convhull	Convex hull.
delaunay	Delaunay triangulation.
delaunay3	3-D Delaunay tessellation.
dsearch	Nearest point search of Delaunay triangulation.
inpolygon	True for points inside polygonal region.
polyarea	Area of polygon.
rectint	Area of intersection for two or more rectangles.
tsearch	Closest triangle search.
voronoi	Voronoi diagram.

This section applies the following techniques to the seamount data set supplied with MATLAB:

• Convex hulls
• Delaunay triangulation
• Voronoi diagrams

See also Tessellation and Interpolation of Scattered Data in Higher Dimensions.

Convex Hulls

The convhull function returns the indices of the points in a data set that comprise the convex hull for the set. For example, to view the convex hull for the seamount data.

load seamount
plot(x,y,'.','markersize',10)
k = convhull(x,y);
hold on, plot(x(k),y(k)), hold off
grid on

Delaunay Triangulation

The delaunay function returns a set of triangles such that no data points are contained in any triangle's circumcircle. To try delaunay, load the seamount data set and view the data as a simple scatter plot.

load seamount
plot(x,y,'.','markersize',12)
xlabel('Longitude'), ylabel('Latitude')
grid on

Apply Delaunay triangulation and overplot the resulting triangles on the scatter plot.

tri = delaunay(x,y);
hold on, trimesh(tri,x,y,z), hold off
hidden off; grid on
xlabel('Longitude'); ylabel('Latitude')

Here's a contour plot.

[xi,yi] = meshgrid(210.8:.01:211.8,-48.5:.01:-47.9);
zi = griddata(x,y,z,xi,yi,'cubic');
[c,h] = contour(xi,yi,zi,'c-'); clabel(c,h)

The arguments for meshgrid encompass the largest and smallest x and y values in the original seamount data. To obtain these values, use

min(min(x))
max(max(x))

and

min(min(y))
max(max(y))

Closest-Point Searches.   You can search through the Delaunay triangulation data with two functions:

• dsearch finds the point closest to a point you specify.
• tsearch, given a point (xi,yi), returns an index into the delaunay output that specifies the enclosing triangle for the point.

Voronoi Diagrams

Voronoi diagrams are a closest-point plotting technique related to Delaunay triangulation. Use the voronoi function to produce the Voronoi diagram for the seamount data.

load seamount
voronoi(x,y)
grid on

Interpolation and Multidimensional Arrays

Tessellation and Interpolation of Scattered Data in Higher Dimensions