Mathematics Previous page   Next Page

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  
Convex hull.
Delaunay triangulation.
3-D Delaunay tessellation.
Nearest point search of Delaunay triangulation.
True for points inside polygonal region.
Area of polygon.
Area of intersection for two or more rectangles.
Closest triangle search.
Voronoi diagram.

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

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. 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.

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 having the property that, for each triangle, the unique circle circumscribed about the triangle contains no data points.

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.

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

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.

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

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:

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.

Previous page  Interpolation and Multidimensional Arrays Tessellation and Interpolation of Scattered Data in Higher Dimensions Next page

© 1994-2005 The MathWorks, Inc.