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:

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

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.


  Interpolation and Multidimensional Arrays Tessellation and Interpolation of Scattered Data in Higher Dimensions