[GRASS-user] TIN algorithm

GRASS GRASS user
1

I was just reading an interesting paper about the DEST algorithm to
poduce TINS, and I was wondering how are TIN-related stuff in GRASS? I
never needed, but.. it is possible? to generate a real TIN?

cheers

@article{favalli2004dem,
  title={{Digital elevation model construction from structured
topographic data: The DEST algorithm}},
  author={Favalli, M. and Pareschi, M.T.},
  journal={Journal of Geophysical Research},
  volume={109},
  number={F4},
  year={2004}
}

--
+-----------------------------------------------------------+
              Carlos Henrique Grohmann - Guano
  Visiting Researcher at Kingston University London - UK
  Geologist M.Sc - Doctorate Student at IGc-USP - Brazil
Linux User #89721 - carlos dot grohmann at gmail dot com
+-----------------------------------------------------------+
_________________
"Good morning, doctors. I have taken the liberty of removing Windows
95 from my hard drive."
--The winning entry in a "What were HAL's first words" contest judged
by 2001: A SPACE ODYSSEY creator Arthur C. Clarke

2

Forwarding a msg sent to me instead of the list by
Agustin Diez Castillo <Agustin.Diez@uv.es>

where there is >200 points I see nothing. I've tried v.build and
v.digit with no success. In the dbf there are the point I either
v.in.db or v.in.ascii
coor files of vector 'ACas20070519@adiez2' is larger than it should be
(14 bytes excess).
Building topology ...
Registering lines:
0 primitives registered
Building areas:
0 areas built
0 isles built
Attaching islands:
Attaching centroids: Topology was built.
Number of nodes : 0
Number of primitives: 0
Number of points : 0
Number of lines : 0
Number of boundaries: 0
Number of centroids : 0
Number of areas : 0
Number of isles : 0
Building topology ...
Registering lines:
0 primitives registered
Building areas:
0 areas built
0 isles built
Attaching islands:
Attaching centroids: Topology was built.
Number of nodes : 0
Number of primitives: 0
Number of points : 0
Number of lines : 0
Number of boundaries: 0
Number of centroids : 0
Number of areas : 0
Number of isles : 0

+-----------------------------------------------------------+
              Carlos Henrique Grohmann - Guano
  Visiting Researcher at Kingston University London - UK
  Geologist M.Sc - Doctorate Student at IGc-USP - Brazil
Linux User #89721 - carlos dot grohmann at gmail dot com
+-----------------------------------------------------------+
_________________
"Good morning, doctors. I have taken the liberty of removing Windows
95 from my hard drive."
--The winning entry in a "What were HAL's first words" contest judged
by 2001: A SPACE ODYSSEY creator Arthur C. Clarke

3

Carlos wrote:

I was just reading an interesting paper about the DEST algorithm to
poduce TINS, and I was wondering how are TIN-related stuff in GRASS? I
never needed, but.. it is possible? to generate a real TIN?

TINs are just xyz points joined together, e.g. with v.delaunay.
http://www.ian-ko.com/resources/triangulated_irregular_network.htm

I had thought there was a script on the wiki add-ons page, but I don't
see it there now. (to do v.delaunay + v.distance to apply elevation
value to triangle centroid?) Maybe google could find it.

r.refine, again from Laura Toma's group:
  http://www.bowdoin.edu/~ltoma/research.html

TINs + GDAL:
http://lists.maptools.org/pipermail/gdal-dev/2007-January/011633.html

also, in the GRASS 6 vector lib there is lib/vector/Vlib/tin.c. I don't
really know what it does, but d.what.vect calls it.

Hamish

4

Hamish wrote:

Carlos wrote:

I was just reading an interesting paper about the DEST algorithm to
poduce TINS, and I was wondering how are TIN-related stuff in GRASS? I
never needed, but.. it is possible? to generate a real TIN?

TINs are just xyz points joined together, e.g. with v.delaunay.
http://www.ian-ko.com/resources/triangulated_irregular_network.htm

I had thought there was a script on the wiki add-ons page, but I don't
see it there now. (to do v.delaunay + v.distance to apply elevation
value to triangle centroid?) Maybe google could find it.

r.refine, again from Laura Toma's group:
  http://www.bowdoin.edu/~ltoma/research.html

Just regarding TIN refinement, there's Shewchuk approach which I
suspect may represent a state-of-the-art in the field [1].

[1] http://www.cs.cmu.edu/~jrs/jrspapers.html#dtstreamn

Maciek

5

Just regarding TIN refinement, there's Shewchuk approach which I
suspect may represent a state-of-the-art in the field [1].

[1] http://www.cs.cmu.edu/~jrs/jrspapers.html#dtstreamn

Maciek

So, the DEST algorithm (Favalli and Pareschi, 2004) claims to be
better than Constrained Delaunay Triangulation (CDT), which is what
Shewchuk uses.

Carlos

--
+-----------------------------------------------------------+
              Carlos Henrique Grohmann - Guano
  Visiting Researcher at Kingston University London - UK
  Geologist M.Sc - Doctorate Student at IGc-USP - Brazil
Linux User #89721 - carlos dot grohmann at gmail dot com
+-----------------------------------------------------------+
_________________
"Good morning, doctors. I have taken the liberty of removing Windows
95 from my hard drive."
--The winning entry in a "What were HAL's first words" contest judged
by 2001: A SPACE ODYSSEY creator Arthur C. Clarke

6

So, the DEST algorithm (Favalli and Pareschi, 2004) claims to be
better than Constrained Delaunay Triangulation (CDT), which is what
Shewchuk uses.

One of the achievements of Shewchuk’s Delaunay procedure, besides the constrained
triangulation, is the exact arithmetic for floating point operations. Which is of great
importance in the context of finite element simulations.

Before his release of the pyramid algorithm, there is also tetgen, that claims to be
a “A Quality Tetrahedral Mesh Generator and Three-Dimensional Delaunay Triangulator”.

http://tetgen.berlios.de/

Regards.
Patricio