TIN / Thiessen / Voronoi / Delaunay
eastsea
Thiessen polygon method
Voronoi diagram
Delaunay triangulation
Please explain the difference of these concepts.
These words are confused in meaning..
Bob Chamberlain
the net and reading what you find.
Bob (Robert G.) Chamberlain | I have yet to see any problem, however
r...@jpl.nasa.gov | complicated, which, when looked at in
Opinions & quips are mine | the right way, did not become still more
- or public - not JPL's | complicated. - Poul Anderson
In article <khgK8.19859$nP6.2...@news.bora.net>
eastsea
i'm a gis application programmer, but have poor knowledge in gis theories.
for example, i don't know wether thiessen and voronoi is the same or
different.
"Bob Chamberlain" <Robert.G.C...@jpl.nasa.gov> wrote in message
news:ae39vo$erf$1...@nntp1.jpl.nasa.gov...
Peter Halls
> Bob, i'm not a school student.
> i'm a gis application programmer, but have poor knowledge in gis theories.
> for example, i don't know wether thiessen and voronoi is the same or
> different.
>
In that case, may I recommend a couple of books, or so, to help you with
these fundamentals?
GIS Basics, Stephen Wise, Taylor & Francis, London, ISBN 0-415-24651-2
ppbk ~US$20ish. This is based on a series of articals Steve wrote for
GeoEurope and explains both terms and the geometry that underpins the GIS
algorithms in very approachable terms. Just published.
An Introdurction to the Theory of Spatial Object Modelling for GIS,
Martien Molenaar, Taylor & Francis, London, ISBN 0-7484-0774-X ppbk,
around US$25?, published 1998. This goes into considerably more detail
than Steve Wise's book and is useful reference material when programming
up spatial algorithms ... as is
Computational Geometry in C, Joseph O'Rourke, Cambridge University Press,
Cambridge (UK), ISBN 0-521-64976-5 ppbk 2nd Edn published 1998. US$30?
This is extremely valuable, complete as it is with code snippets. There
is a very similar volume by O'Reilly ... I just happen to prefer this one!
Lastly, as a guide into the very extensive literature on GIS Theory, the
NCGIA website and Core Curriculum in GIS may be helpful:
http://www.ncgia.ucsb.edu/ (homesite) and
http://www.ncgia.ucsb.edu:80/education/curricula/giscc/cc_outline.html
(Core Curriculum)
There are a lot of other books one could recommend, the first two and the
Core Curriculum have good bibliographies which should lead you further in
your reading. There are also quite a lot of GIS teaching materials on the
web, so a GOOGLE search (www.google.com) for, for example, Thiessen is
likely to lead you to somebody's lecture notes explaining the answer to
the very question you've posed! (And part of the answer is that a Voronoi
diagram is / can be three dimensional whilst Thiessen merely applied the
European mathematician Dirichlet's neighbourhood in a plane, a technique
already some 50 years established by the time von Thiessen applied it in
the US. Also a warning: some writers, incorrectly, use the terms
Thiessen and Voronoi interchangeably: they are wrong but this may help
lead to your confusion.)
Hope that helps,
Peter
>
> "Bob Chamberlain" <Robert.G.C...@jpl.nasa.gov> wrote in message
> news:ae39vo$erf$1...@nntp1.jpl.nasa.gov...
> > This looks like a homework assignment. Try searching
> > the net and reading what you find.
> >
> > Bob (Robert G.) Chamberlain | I have yet to see any problem, however
> > r...@jpl.nasa.gov | complicated, which, when looked at in
> > Opinions & quips are mine | the right way, did not become still more
> > - or public - not JPL's | complicated. - Poul Anderson
> >
> >
> > In article <khgK8.19859$nP6.2...@news.bora.net>
> > "eastsea" <hdc...@uniboss.com> writes:
> >
> > > Triangulaed Irregular Network
> > > Thiessen polygon method
> > > Voronoi diagram
> > > Delaunay triangulation
> > >
> > > Please explain the difference of these concepts.
> > > These words are confused in meaning..
> > >
> > >
> > >
>
>
>
>
--------------------------------------------------------------------------
PPPPPH H | Peter Halls - University of York Computing Service -
P P H | GIS Advisor
P P H | Email: P.H...@YORK.AC.UK
PPPPPJHHHHHH | Telephone: 01904 433806 FAX: 01904 433740
P J H | Smail: Computing Service,
P J H | University of York,
P J H | Heslington.
J | YORK YO10 5DD
J J | England.
JJJ This message has the status of a private & personal communication
--------------------------------------------------------------------------
Bob Chamberlain
A TRIANGULATED IRREGULAR NETWORK, also known as a TIN, is a way
of modeling the shape of a surface. (In GIS, the surface of
interest is generally the Earth's topography.) It is the
two-dimensional equivalent of a piecewise linear function. That
is, it consists of a collection of triangles that tile the
surface. The interesting question if you are a researcher is
how to select the locations and elevations for the TIN vertices
(that is, the points at which the corners of the triangles
meet) and how to connect those vertices with TIN edges. Other
interesting questions might include what data structures are
best in a particular context, how to judge how well the TIN
fits the terrain, and so on.
Given a set of points (call it S), a VORONOI POLYGON consists
of the lines that mark the boundaries of the regions that are
closest to the points in S. One way to visualize it is to
think of the points in S as tiny round cells (usually we deal
only in two dimensions, not three) that all grow at the same
rate in all directions until they are stopped by other cells'
walls. The lines between the cell boundaries are the Voronoi
polygon, and are pieces of the perpendicular bisectors of the
lines connecting the points in S whose "cell walls" touch.
Some of those lines extend to infinity. A Voronoi polygon is
less often known as a THIESSEN POLYGON - I'm a user of these
concepts, not a historian, so I don't recall whether Voronoi or
Thiessen has precedence and should get the credit. These
objects have been rediscovered several times; I think other
names have been attached to them, too.
The DELAUNAY TRIANGULATION is the collection of the lines between
the points that create lines in the Voronoi polygon. That is why
the Delaunay triangulation and the Voronoi polygon are considered
to be "duals" of each other. The Delaunay triangulation, which
is, incidentally, unique (with trivial exceptions) has a number of
nice properties, among which is that the triangles have shapes that
are as "nice" as possible. The Delaunay triangulation connects
each of the points in S to its nearest neighbors - where "nearest"
is best understood by thinking about the dual Voronoi polygon,
which is obviously unique.
Delaunay triangulations are often used in the creation of TINs
after the locations of the vertices have been found by some
criteria. The resultant TINs suffer from the fact that only
two-dimensional geometry, and no elevation data, is used in the
triangulation. Thus, the "nicely" shaped triangles may fit the
terrain less well than triangles chosen to optimize some quality
metrics.
There is a LOT more that can be said about these very interesting
objects, but saying it requires the writing of a textbook!
Do I get an "A"? :^)
Bob
Bob (Robert G.) Chamberlain | Among mathematicians, IÕm a scientist.
r...@jpl.nasa.gov | Among scientists, IÕm an engineer.
Opinions & quips are mine | Among engineers, IÕm a mathematician.
- or public - not JPL's | At heart, IÕm a systems analyst.
In article <AOeO8.40896$nP6.5...@news.bora.net>
Bob Chamberlain
> a Voronoi
> diagram is / can be three dimensional whilst Thiessen merely applied the
> European mathematician Dirichlet's neighbourhood in a plane, a technique
> already some 50 years established by the time von Thiessen applied it in
> the US. Also a warning: some writers, incorrectly, use the terms
> Thiessen and Voronoi interchangeably: they are wrong but this may help
> lead to your confusion.)
Oops. Well, I _did_ say I wasn't a historian!
Bob
Bob (Robert G.) Chamberlain | I recall making a misteak oneÕs before
r...@jpl.nasa.gov | - but that thyme it was in thinking I
Opinions & quips are mine | had maid won the weak before that.
- or public - not JPL's | ;-)
Art
comunication/help in a group.
As a distant reader with limited access to books, thanks.
Art
just an argentinian surveyor.
:)