NetNews Usenet Archive 1992 #26/NN_1992_26.iso/spool/comp/graphics/11589

Text File | 1992-11-08 | 9.4 KB | 277 lines

Newsgroups: comp.graphics
Path: sparky!uunet!cis.ohio-state.edu!magnus.acs.ohio-state.edu!usenet.ins.cwru.edu!agate!boulder!ucsu!rintintin.Colorado.EDU!chickles
From: [e-mail] (CHICKLES DEREK JASON)
Subject: Responses from Contouring Non-gridded Data
Message-ID: <[e-mail]>
Keywords: responses, non-gridded data
Sender: [e-mail] (USENET News System)
Nntp-Posting-Host: rintintin.colorado.edu
Organization: University of Colorado, Boulder
Date: Fri, 6 Nov 1992 20:42:41 GMT
Lines: 264

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    [e-mail]

---------------------------------------------------------------------------
From [e-mail] 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 [e-mail] 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 -- [phone] -- [e-mail]
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 [e-mail] 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:         [phone], fax: [phone]

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 [e-mail] 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: [phone]
The MITRE Corporation E073            fax: [phone]
Bedford MA 01730-1420 USA             net: [e-mail] (internet)



---------------------------------------------------------------------------
From [e-mail] 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: [e-mail]

---------------------------------------------------------------------------
From [e-mail] 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 [e-mail]
        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: [e-mail]
 Organic Chemistry 2                  [e-mail]
 Lund University                      [e-mail]
 P.O. Box 124                 voice:  [phone]
 S-22100 Lund, Sweden         fax:    [phone]

---------------------------------------------------------------------------
From [e-mail] 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,...