hnevanlinna@opmvax.kpo.fi (01/24/89)
Someone asked a few days ago for 3D-tringulation.
I would be more than happy for an efficient algorithm for
2D-triangulation.
I am familiar with algorithm, which sorts data with distance to the
middle point of two closest points ( actually did it with object pascal
in Mac ), but triangles made were not satisfactory. I know, there
exist an algorith starting with poine, and searching more ching more points
inside this circle, but how it's done in Nlog(n), is beyond my imagination.
So do you know source for this algorith or other.
Jouni Rynv, Finish Meteorological Institute, Dep. of Geophysics
(doing graduate work on macnetic maps with irregular
measument points)
kerlick@prandtl.nas.nasa.gov (G David Kerlick) (01/27/89)
Newsgroups: comp.graphics
Subject: Re: 2D-triangulation
Summary:
Expires:
SReferences: <11@opmvax.kpo.fi>
Sender:
Reply-To: kerlick@prandtl.nas.nasa.gov (G David Kerlick)
Followup-To:
Distribution:
Organization: NASA Ames Research Center
Keywords:
In article <11@opmvax.kpo.fi> hnevanlinna@opmvax.kpo.fi writes:
.Someone asked a few days ago for 3D-triangulation.
.I would be more than happy for an efficient algorithm for
.2D-triangulation.
What you are looking for is a Delaunay Triangulation
(with boundary it is called a Dirichlet Tesselation,
and its dual is a Voronoi Tesselation).
There is a method due to D.F. Watson which is of order
O(N**(1 + 2/d)) where N is the number of points and d
is the spatial dimension.
There is a faster O(NlogN) algorithm of Guibas and
Stolfi which is, however, conceptually more complicated
and only works in the plane (d=2).
The subject of triangulations and data structures for them
is reviewed in:
Leila De Floriani
"Surface representations based on triangular grids"
The Visual Computer (1987) No.3 pp 27-50.
(published by Springer-Verlag)
which also has an extensive bibliography.
By the way, if anybody has working, public-domain
code for these, I'd like to see it as well!
The opinions expressed by NASA or the U.S. Government
are not necessarily those of the Author.
David Kerlick _ (415)-694-4779 _ kerlick@prandtl.nas.nasa.gov