corkum@csri.toronto.edu (Brent Thomas Corkum) (06/15/90)
I'm looking for some references or comments concerning the conversion of scattered data in two dimensions to data on a regular grid. I would alos like to be able to handle holes in the data, meaning areas in which no interpolation or extrapolation will occur or cross. But this last requirement is not mandatory. Brent corkum@csri.toronto.edu
xanthian@zorch.SF-Bay.ORG (Kent Paul Dolan) (06/16/90)
In article <1990Jun15.122858.1197@jarvis.csri.toronto.edu> corkum@csri.toronto.edu (Brent Thomas Corkum) writes: >I'm looking for some references or comments concerning the conversion >of scattered data in two dimensions to data on a regular grid. I would >alos like to be able to handle holes in the data, meaning areas in which >no interpolation or extrapolation will occur or cross. But this last >requirement is not mandatory. > > >Brent >corkum@csri.toronto.edu This problem is regularly encountered in the digital cartography field, where it is a preprocessing step to several contouring packages. Make sure that it is the only way to solve your problem before you select this approach, however, as it is fraught with special cases, numerical instabilities, and numerical artifacts. A superior method for many uses is to triangulate the data points with a method that replaces the edge between two skinny triangles with a common long border with the edge connecting the two uninvolved points of the two triangles (where this edge is internal to the quadrilateral formed by the two triangles) to make them more nearly equilateral, until no further such cases exist, and then either doing linear interpolation from the corner values to get interior values for whatever your problem needs, or doing a higher order interpolation using points from surrounding triangles to get second order continuity at the edges. Kent, the man from xanth. <xanthian@Zorch.SF-Bay.ORG> <xanthian@well.sf.ca.us>
xanthian@zorch.SF-Bay.ORG (Kent Paul Dolan) (06/16/90)
In article <1990Jun16.004234.17224@zorch.SF-Bay.ORG> xanthian@zorch.SF-Bay.ORG (Kent Paul Dolan) writes: >In article <1990Jun15.122858.1197@jarvis.csri.toronto.edu> corkum@csri.toronto.edu (Brent Thomas Corkum) writes: >>I'm looking for some references or comments concerning the conversion >>of scattered data in two dimensions to data on a regular grid. I would >>alos like to be able to handle holes in the data, meaning areas in which >>no interpolation or extrapolation will occur or cross. But this last >>requirement is not mandatory. Sorry about following up my own posting, I'm not usually this lazy. The triangulation described in the following, if accomplished by first enclosing the whole data set in a very large triangle whose points have the average value of the data set, (or perhaps lie on a plane which is a least squares fit to the data) allows reasonable assignment of points to a regular grid covering the same area, and stable extrapolation within the area covered by the circumscribing triangle. Automated Contour Mapping Using Triangular Element Data Structures and An Interpolant Over Each Irregular Triangular Domain by C. M. Gold, University of Alberta, T. D. Charters, Alberta Environment, and J. Ramsden, Alberta Research Page 170-175 in: Computer Graphics, A Quarterly Report of SIGGRAPH-ACM, Volume 11, Number 2, Summer 1977, a.k.a. SIGGRAPH '77 Proceedings. This is a very approachable paper, though I'd like to see where Chris has gone with this material since 1977. Kent, the man from xanth. <xanthian@Zorch.SF-Bay.ORG> <xanthian@well.sf.ca.us>