Triangulate the Domain where 0 <= F(X,Y)

SHORELINE is a MATLAB library which tries to identify and triangulate the 2D domain over which some function F(X,Y) is nonnegative.

It does this by starting with a set of sample points, where the function is evaluated. Triangles are dropped from the triangulation if all 3 vertices have negative functions. Triangles with 3 positive vertices are assumed (to within the requested resolution) to be part of the region. Therefore, a more accurate answer can be sought by refining those triangles whose vertices include both positive and negative values.

This results in a refined "shoreline" around the positive triangles. The function is evaluated at the new nodes, and again the negative triangles are dropped, the positive ones kept, and the intermediate triangles can be further refined, if desired.

It is also possible to estimate the integral of some function g(x,y) over the region implicitly defined by 0 <= f(x,y).


The computer code and data files described and made available on this web page are distributed under the GNU LGPL license.


SHORELINE is available in a MATLAB version.

Related Data and Programs:

CONTOUR_GRADIENT, a MATLAB program which displays contours and gradient vectors for a function f(x,y).

EDGE, a MATLAB library which defines some test functions in 1D, 2D and 3D for the detection of edges.

HYPERSPHERE_SURFACE, a MATLAB library which illustrates a procedure for estimating the location of a hypersurface defined by a characteristic function or a signed function.

LEVELS, a MATLAB library which makes a contour plot, choosing the contour levels using random sampling.

MATLAB_SURF, a MATLAB library which demonstrates the MATLAB surf() function for displaying a 3D surface of the form Z=F(X,Y).

SHORELINE2, a MATLAB program which tries to identify and triangulate the 2D domain over which some function f(x,y) is roughly zero.

TOMS626, a FORTRAN77 library which creates a contour plot of data associated with a triangulated set of points;
this is ACM TOMS algorithm 626.

TRIANGULATION_ORDER3_CONTOUR, a MATLAB program which makes contour plot of scattered data, or of data defined on an order 3 triangulation.

TWOD_PLOTC, a MATLAB program which makes a color contour plot of scalar data defined on a 2D finite element mesh, by Jeff Borggaard.

Source Code:

Examples and Tests:

A number of functions are available to define the F(X,Y):

SHORELINE_TEST simply uses shoreline with 1, 2, 3, and 4 refinement steps, comparing the estimates of the area of the region for a centered circle, an off-center circle, a centered ellipse, and a slanted ellipse.

SHORELINE_INTEGRAL_TEST uses shoreline with 1, 2, 3, and 4 refinement steps to triangulate a region implicitly defined by 0 < F(X,Y), and then uses the resulting triangulation to estimate the integral over that region of a circular Gaussian function, for a centered circle and an off-center circle, with initial uniform grids of 11x11 and 21x21 points.

You can go up one level to the MATLAB source codes.

Last modified on 06 January 2012.