From: chickles@rintintin.Colorado.EDU (CHICKLES DEREK JASON)
Subject: Responses from Contouring Non-gridded Data
Keywords: responses, non-gridded data
Organization: University of Colorado, Boulder
Date: Fri, 6 Nov 1992 20:42:41 GMT

Here are the responses I got from posting the following:

>Hello,
>
>I am looking for any free source out there that will make contours of
>non-gridded data. I would prefer to have source in C or C++, but other
>languages are usable. The data I am using contains a coordinate (x,y)
>and a value associated with each coordinate.
>
>I haven't found any algorithms yet that do contours without the data being in
>a grid. Does the data need to be mapped into a grid then contoured? -- Or
>is there some slick method for doing this?

Mail these people for more information.

	DEREK	chickles@rintintin.colorado.edu

---------------------------------------------------------------------------
From dave@stereo.mitre.org Wed Oct 28 14:59:36 1992
Subject: Re: Contouring non-gridded data

One approach would be to triangulate the data using a Delaunay
triangulation, then for each triangle draw a line segment where
the triangle intersects any contour threshold, which defines a plane.

Petroleum engineers, cartographers, and geographers do this type of
thing all the time, and there are many more advanced methods than
the one I suggest.

I can supply you with a few specific references if you are interested.



---------------------------------------------------------------------------
From spl@szechuan.UCSD.EDU Wed Oct 28 16:16:37 1992
Subject: Re: Contouring non-gridded data

I've got a subroutine called CONISD (CONtour Irregularly Spaced Data)
that's written in FORTRAN.  Drop me a note if you want it.

							spl
-- 
Steve Lamont, SciViGuy -- (619) 534-7968 -- spl@szechuan.ucsd.edu
UCSD Microscopy and Imaging Resource/UCSD Med School/La Jolla, CA 92093-0608
Let the people who own the country govern the country.
Vote Perot in `92.

---------------------------------------------------------------------------
From ruprecht@corse.informatik.uni-freiburg.de Thu Oct 29 04:33:40 1992
Subject: Re: Contouring non-gridded data
Organization: 	Institut fuer Informatik der Universitaet Freiburg
Address: 	Rheinstrasse 10-12, D-7800 Freiburg i. Br., Germany
Phone: 		+49-761-203 3884, fax: +49-761-203 3889

If you are willing to write your own code, here are some references
that might be of use for you:

@InCollection{Alfeld89,
  author =	{P. Alfeld},
  title =	{Scattered Data Interpolation in Three or More Variables},
  booktitle =	{Mathematical Methods in CAGD},
  publisher =	{Academic Press},
  year =	{1989},
  editor =	{T. Lyche and L.L. Schumaker},
  pages =	{1-33}
}
Abstract = {This is a survey of techniques for the interpolation of
scattered data in three or more independent variables. It covers
schemes that can be used for any number of variables as well as
schemes specifically designed for three variables. Emphasis is on
breadth rather than depth, but there are explicit illustrations of
different techniques used in the solution of multivariate
interpolation problems.}

@Article{Hardy71,
  author =	{R.L. Hardy},
  OPTfullname =	{Rolland L. Hardy},
  title = 	{Multiquadric Equations of Topography and other
		 Irregular Surfaces},
  journal = 	{J. Geophys. Res.},
  year = 	{1971},
  volume = 	{76},
  OPTnumber = 	{},
  pages = 	{1905-1915},
  OPTmonth = 	{}
}

@Article{Hardy90,
  author =	{R.L. Hardy},
  title =	{Theory and Applications of the multiquadric--biharmonic
		 Method},
  journal =	{Computers and Mathematics with Applications},
  year =	1990,
  volume =	19,
  pages =	{163-208}
}

@Article{Carlson91,
  author =	{R.E. Carlson and T.A. Foley},
  title =	{The parameter ${R}^2$ in multiquadric interpolation},
  journal =	{Computers and Mathematics with Applications},
  year =	1991,
  volume =	21,
  pages =	{29-42}
}

@InCollection{Sibson81,
  author = 	{R. Sibson},
  title = 	{A Brief Description of Natural Neighbour Interpolation},
  booktitle = 	{Interpreting Multivariate Data},
  publisher = 	{Wiley},
  year = 	{1981},
  editor = 	{D.V. Barnett},
  pages = 	{21-36},
  address = 	{New York}
}

@Article{Watson87,
  author =	{D. Watson},
  title =	{Neighborhood-based Interpolation},
  journal =	{Geobyte},
  volume =	2,
  number =	2,
  pages =	{12-16},
  year =	1987
}

@Article{Farin90,
  author =	{G. Farin},
  title =	{Surfaces over Dirichlet Tesselations},
  journal =	{Computer Aided Geometric Design},
  volume =	7,
  year =	1990,
  pages =	{281-292}
}

@Article{Franke82,
  author =	{R. Franke},
  title =	{Scattered Data Interpolation: Tests of Some
	   	Methods},
  journal =	{Mathematics of Computation},
  year =	{1982},
  volume =	{38},
  number =	{157},
  pages =	{181-200},
  month =	{Jan.},
  note =	{}
}
Abstract = {This paper is concerned with the evaluation of methods
for scattered data interpolation and some of the results of the
tests when applied to a number of different methods. The process
involves evaluation of the methods in terms of timing, storage,
accuracy, visual pleasantness of the surface, and ease of
implementation. To indicate the flavor of the type of results
obtained, we give a summary table and representative perspective
plots of several surfaces.}

@InCollection{Franke87,
  author =	{R. Franke},
  title =	{Recent advances in the approximation of surfaces from
		 scattered data},
  booktitle =	{Topics in Multivariate Approximation},
  publisher =	{Academic Press},
  address =	{New York},
  year =	1987,
  editor =	{L.L. Schumaker and C.C. Chui and F.Utreras et al.},
  pages =	{175-184}
}

-- 

Nick Ruprecht
Institut fuer Informatik der Universitaet Freiburg

---------------------------------------------------------------------------
From dave@stereo.mitre.org Thu Oct 29 07:15:49 1992
Subject: Re: Contouring non-gridded data

Here are some references on the triangulation method I suggested:

CL Lawson (1977), Software for C1 surface interpolation, In: JR Rice (ed)
Mathematical Software III, Academic Press, New York, pp. 161-194.

RF Fowler & JJ Little (1979), Automatic extraction of irregular digital 
terrain models, Computer Graphics 13(3) 199-207.  (discusses contour
map generation from triangulation)

SW Sloan (1987), A fast algorithm for constructing Delaunay triangulations
in the plane, Advances in Engineering Software 9(1) 34-55.

The method I suggest is probably the simplest & fastest way.  This is
a piecewise linear interpolation of the sample points.

Geologists often use a more sophisticated method called 'kriging' to
interpolate the data, and then fit smooth curves to the interpolated
data for the contour maps.  If you do a library search on kriging and
contour mapping, you should come up with a _lot_ of references.

David A. Southard                     tel: (617)271-7425
The MITRE Corporation E073            fax: (617)271-2964
Bedford MA 01730-1420 USA             net: southard@mitre.org (internet)



---------------------------------------------------------------------------
From ma@informatik.uni-kiel.dbp.de Thu Oct 29 08:23:35 1992
Subject: Re: Contouring non-gridded data

There are a number of methods for contouring non-gridded data,
most of them involving triangulation.
David Watson (somewhere in Australia) is writing or has written a book on that
subject; he'll probably reply to your query as well.
I don't know of any freely available program, but I guess I could dig out
a couple of papers.

If, however, you have access to GRASS (free GIS distributed by CERL) - they
include one or two functions for interpolating scattered data using
thin-plate splines. If interested, ask me for details.

Martin
--
Martin Ameskamp, Kiel University, Germany
Fax: ++49 431 8804054, Voice: ++49 431 8804474, 
email: ma@informatik.uni-kiel.dbp.de

---------------------------------------------------------------------------
From orgk2-a.sundin@macpost.lu.se Thu Oct 29 13:17:45 1992

Check out

A Method of Bivariate Interpolation and Smooth Surface Fitting for Irregularly 
Distributed Data Points., Akima, Hiroshi, ACM-Transactions of  Mathematical 
Software, Vol. 4, No 2, 1978, pp 148-159 

An improved (?) method was described in the same journal:
Vol.10, NO. 4, December 1984, pp. 473-.

The source code is available from netlib:
==========================================================
Do:
        mail netlib@nac.no
        send index

If ftp is more convenient for you than email, you may connect to
"research.att.com"; log in as "netlib".
==========================================================

The source code is in FORTRAN and is in the TOMS directory.

--
 Anders Sundin                e-mail: Anders.Sundin@orgk2.lth.se
 Organic Chemistry 2                  sundinKC@dna.lth.se
 Lund University                      ok2aps@seldc52.bitnet
 P.O. Box 124                 voice:  +46 46 104139
 S-22100 Lund, Sweden         fax:    +46 46 108209

---------------------------------------------------------------------------
From pbuttuls@seymour.ucs.ualberta.ca Tue Nov  3 10:37:21 1992
Subject: Re: Contouring non-gridded data

I have a program written in FORTRAN '66 that has been running on our
mainframe successfully for over 10 years. You'd have to convert it to
call the graphics routines you want. Right now it uses the CalComp 
routines PLOTS, PLOT, SYMBOL,...