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.

Note    Examples in this section use the MATLAB seamount data set. Seamounts are underwater mountains. They are valuable sources of information about marine geology. The seamount data set represents the surface, in 1984, of the seamount designated LR148.8W located at 48.2°S, 148.8°W on the Louisville Ridge in the South Pacific. For more information about the data and its use, see Parker [2]. The seamount data set provides longitude (x), latitude (y) and depth-in-feet (z) data for 294 points on the seamount LR148.8W.

Convex Hulls

The convhull function returns the indices of the points in a data set that comprise the convex hull for the set. Use the plot function to plot the output of convhull.

This example loads the seamount data and plots the longitudinal (x) and latitudinal (y) data as a scatter plot. It then generates the convex hull and uses plot to plot the convex hull.

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

Delaunay Triangulation

Given a set of coplanar data points, Delaunay triangulation is a set of lines connecting each point to its natural neighbors. The delaunay function returns a Delaunay triangulation as a set of triangles such that no data points are contained in any triangle's circumcircle.

You can use triplot to print the resulting triangles in two-dimensional space. You can also add data for a third dimension to the output of delaunay and plot the result as a surface with trisurf, or as a mesh with trimesh.

Plotting a Delaunay Triangulation.   To try delaunay, load the seamount data set and view the longitude (x) and latitude (y) data as a scatter plot.

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

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

• tri = delaunay(x,y);
  hold on, triplot(tri,x,y), hold off
  
  
  

Mesh and Surface Plots.   Add the depth data (z) from seamount, to the Delaunay triangulation, and use trimesh to produce a mesh in three-dimensional space. Similarly, you can use trisurf to produce a surface.

• figure
  hidden on
  trimesh(tri,x,y,z)
  grid on
  xlabel('Longitude'); ylabel('Latitude'); zlabel('Depth in Feet')
  
  
  

Contour Plots.   This code uses meshgrid, griddata, and contour to produce a contour plot of the seamount data.

• figure
  [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,'b-'); 
  clabel(c,h)
  xlabel('Longitude'), ylabel('Latitude')
  
  
  

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

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

• dsearch finds the indices of the (x,y) points in a Delaunay triangulation closest to the points you specify. This code searches for the point closest to (211.32, -48.35) in the triangulation of the seamount data.

• xi = 211.32; yi = -48.35;
  p = dsearch(x,y,tri,xi,yi);
  [x(p), y(p)]
  
  ans =
      211.3400  -48.3700
  

• tsearch, finds the indices into the delaunay output that specify the enclosing triangles of the points you specify. This example uses the index of the enclosing triangle for the point (211.32, -48.35) to obtain the coordinates of the vertices of the triangle.

• xi = 211.32; yi = -48.35;
  t = tsearch(x,y,tri,xi,yi);
  r = tri(t,:);
  A = [x(r) y(r)]
  
  A =
    211.3000  -48.3000
    211.3400  -48.3700
    211.2800  -48.3200
  

Voronoi Diagrams

Voronoi diagrams are a closest-point plotting technique related to Delaunay triangulation.

For each point in a set of coplanar points, you can draw a polygon that encloses all the intermediate points that are closer to that point than to any other point in the set. Such a polygon is called a Voronoi polygon, and the set of all Voronoi polygons for a given point set is called a Voronoi diagram.

The voronoi function can plot the cells of the Voronoi diagram, or return the vertices of the edges of the diagram. This example loads the seamount data, then uses the voronoi function to produce the Voronoi diagram for the longitudinal (x) and latitudinal (y) dimensions. Note that voronoi plots only the bounded cells of the Voronoi diagram.

• load seamount
  voronoi(x,y)
  grid on
  xlabel('Longitude'), ylabel('Latitude')
  
  
  

Note    See the voronoi function for an example that uses the vertices of the edges to plot a Voronoi diagram.

Interpolation and Multidimensional Arrays

Tessellation and Interpolation of Scattered Data in Higher Dimensions