From: Alexandre L Cunha Newsgroups: sci.math.num-analysis Subject: Re: Surface map Date: Tue, 28 Jan 1997 19:14:15 -0500 Excerpts from netnews.sci.math.num-analysis: 28-Jan-97 Surface map Gary Cousins@gecm.com (694*) > Hello, > I have a set of data points on a non uniform grid (i.e x and y data > with height z) and i need to produce an expression for the surface they > form so that i can put an x and y value in and get z out. > Any suggestions welcome, an E-mail reply would be prefered if possible. > Thanks. > -- > Gary Cousins Getting a continuous function out of a discrete set of points and their values is almost always impractical for medium to large sets. The best bet is to construct a piecewise approximation of your data through a surface fitting scheme. There are lots of work in this area. Check the netlib web page, www.netlib.org, for a public software list. I would suggest a reading on "Fast polygonal approximation of terrain and height fields", by Garland and Heckbert available at www.cs.cmu.edu/~garland/scape/scape.ps.gz. They also have a companion software you can download. A simple strategy would be: 1. construct a Delaunay triangulation of your (x,y) point set; try Triangle (www.cs.cmu.edu/~quake/triangle.html) to construct the Delaunay mesh. 2. for any query point p = (x,y) find the triangle it lies in and do a linear interpolation on the z values of the triangle vertices, z = linear_interpolate(z1, z2, z3); you can use your Delaunay mesh to efficiently solve the point location problem. - Alex.