Path: utzoo!attcan!uunet!lll-winken!lll-tis!ames!haven!mimsy!tank!uxc!uxc.cso.uiuc.edu!uxg.cso.uiuc.edu!uicsrd.csrd.uiuc.edu!petersen
From: petersen@uicsrd.csrd.uiuc.edu
Newsgroups: comp.graphics
Subject: Re: Contour to grid algorithm
Message-ID: <44100006@uicsrd.csrd.uiuc.edu>
Date: 31 Oct 88 23:16:00 GMT
References: <661@prlhp1.prl.philips.co.uk>
Lines: 39
Nf-ID: #R:prlhp1.prl.philips.co.uk:661:uicsrd.csrd.uiuc.edu:44100006:000:2052
Nf-From: uicsrd.csrd.uiuc.edu!petersen    Oct 31 17:16:00 1988


In general I know of no "simple" algorithms that will do a good job,
the basic method is to compute a surface to approximate the contours
and then sample that surface at the desired grid spacing.

The system I worked with used a DTM (digital triangulation model)
to represent the surface, so we never went the final step of re-sampling
the surface at grid points.  However since we already had the routines
to create the DTM from random points, the problem was half solved.

To create a reasonable DTM from a contour map you need to worry about
the flat artifacts that can occur when the triangulation procedure
connects 3 adjacent points on a contour line.  In general this is the
wrong thing to do (maxima, and minima excepted).  Most methods for DTM
construction have a property that we refered to as the "Great Circle
Test", this being that for any three points in the plane fit a circle
to those 3 points, and if any other point lies within that circle then
those 3 point will NOT be connected into a triangle.  Thus the crux of
the method we used was to scan each contour line in sequence and to
compute the circle for each 3 adjacent points, and find the point on
another contour line that was closest to the circle.  If that point
was inside the circle then we are ok.  Otherwise do a linear
interpolation from the new point to the middle of the three points.

This should give a flavor for what is needed to use this method.  It is
resonably accurate, we were able to get 95%-99% volume comparisions,
buy creating a contour map from a DTM, creating a new DTM from the
contour map, and then comparing the two surfaces (depending on the
spacing of the contour lines).  If anyone knows of a simpler of more
elegant method, I would like to know about it.

-Paul Petersen

University of Illinois, Urbana-Champaign
Center for Supercomputing Research and Development

    UUCP:    {uunet,convex}!uiucuxc!uicsrd!petersen
    ARPANET: petersen%uicsrd@uxc.cso.uiuc.edu
    CSNET:   petersen%uicsrd@uiuc.csnet
    BITNET:  petersen@uicsrd.csrd.uiuc.edu