Path: utzoo!attcan!uunet!husc6!mailrus!ulowell!apollo!aramini
From: aramini@apollo.COM (Michael Aramini)
Newsgroups: comp.graphics
Subject: Re: Contour to grid algorithm
Message-ID: <3f730d14.c463@apollo.COM>
Date: 3 Nov 88 18:52:00 GMT
References: <661@prlhp1.prl.philips.co.uk>
Organization: Apollo Computer, Chelmsford, Mass.
Lines: 38

If the contours were generated from a grid by a standard algorithm, it may be
possible to partially invert the algorithm to at least partially reconstruct
the original grid.

If you don't know the positions of the initial grid points, you might be able to
infer at least some of them, and thus the grid spacing.  Note that if the
standard contour algorithm had been used, all of the contour verticies will fall
grid edges.  Thus a given contour vertex will either have the x coordiate of a
column of grid points or the y coordinate of a row of grid points.  You can't
tell from an individual contour vertex which of its coordinates matches that of
grid points.  However, you can construct a histogram of x coordinates of contour
verticies and a histogram of y coordinate of contour verticies.  Peaks in each
histogram will correspond to coordinate values of grid points.  There won't
necessarily be a peak at every grid point coordinate value, but you can at least
infer the spacing for the peak positions.

Once you know where the grid points are, you can derive what some of the grid
point heights must be.  Note that:

    1. Whenever two or more contour verticies fall on the grid segment between 2
       adjacent grid points, you can compute the height of both ofthose grid
       points by linear extrapolation.  

    2. If only one contour vertex falls between 2 adjacent grid points, and you
       know the height of the one of those grid points, you can compute the
       height of the other by linear extrapolation.

By first applying rule 1 wherever possible, and then by repeatedly applying rule
2 wherever possible, you should be able to compute the heights of a large number
of grid points.

For the rest of the grid points, you can determine their approximate heights by
looking at the heights of the contour lines between which each grid point falls.
Note that in regions of the grid where you must resort to this must be fairly
level (since they are regions where contour lines are fairly sparse), so I would
expect that low order curve fitting methods will probably give good results.

-Michael