Path: utzoo!utgpu!watmath!clyde!att!osu-cis!tut.cis.ohio-state.edu!mailrus!ames!amdcad!sun!pitstop!sundc!seismo!uunet!mcvax!ukc!stc!idec!prlhp1!yuleat
From: yuleat@prlhp1.prl.philips.co.uk (yuleat)
Newsgroups: comp.graphics
Subject: Re: Contour to grid algorithm
Message-ID: <699@prlhp1.prl.philips.co.uk>
Date: 9 Nov 88 14:14:40 GMT
References: <661@prlhp1.prl.philips.co.uk>
Reply-To: yuleat@prlhp1.UUCP ()
Organization: Philips Research Laboratories, Redhill, UK
Lines: 66

About a fortnight ago I posted the following problem:

> I have data for a relief map in terms of height contours.
> The data stored for each contour is :
>     1. A height above sea-level
>     2. A linked list of points, which are joined by
>        straight line segments to make up the contour.
> 
> The area mapped by this data is rectangular and all component
> points of the contour must be within this area.  As a result,
> some contours do not join up, as they start/finish off the map.
> All the contour line segments are guarenteed not to touch/cross.
> 
> The problem I have is that I wish to convert this relief data
> stored in contour form into a form where a uniform rectangular
> grid is used.  Each point of the grid will have a spot height.

As I've now had quite a lot of mail on this subject
(for which thanks to those concerned), I shall give
a quick summary.

The proposed solutions fell into two main categories:
    i)  Line based. Interpolation (anything from linear
        to use of splines) along the grid lines.
    ii) Fitting a surface to the contours and 
        determining the point values from that.
The problem in all cases cocerns not knowing the edge
of the map values (and as you can see, below, I have
cheated a bit!)

What I didn't mention in my original posting was the fact
that I really have two goals. 
    i)    To get a prototype system working a.s.a.p.
    ii)   A long term view to get the "best" solution.
As a result I have implemented a simple system that seems
to work and will be investigating improvements/new methods
in the future.

I will briefly describe the algorithm I have used for 
your interest/comments:
    i)    Determine/Get user to supply the spot height of
            the four corners of the "map".
    ii)   Determine any intersections of contour lines with
            the edges of the map.
    iii)  Use the above data to determine values for all the
            edge values. This is done by interpolating using
            the "know" points (i.e. corners + contour
            intersections from i & ii).
With this I can guarantee that every row & column has two
known values, one at each end. In addition, I then :
    iv)   Determine all intersections between contour lines
            and individual mesh columns & rows. This data I
            store in ordered linked lists; one list for each
            row & each column, containing all the "fixed"
            points along that line (including the edge
            values determined by step iii).
    v)    Calculate the values at each mesh point by averaging
            the values obtained by interpolating along both
            the relevant column & row lists.

I hope this makes some kind of sense (it's a bit difficult to
explain without a diagram!).  At present I am using simple 
linear interpolation for steps iii & v but obviously more
sophisticated methods could be used.

Andy Yule (yuleat@prl.philips.co.uk)