CGAL users discussion list

[Monique Teillaud <>]

Le 09/09/12 08:18, Manu Kaul a écrit :
> Hi all,
> I used the "Triangle" library from
> http://www.cs.cmu.edu/~quake/triangle.html by Jonathan Shewchuck to
> generate a Delaunay triangulation
> of my raw x,y,z points. I am trying to create an indexing structure and
> some distance bounds that make the shortest path calculation on a
> terrain faster + some other queries like range queries, and k-nearest
> neighbour queries as well.
>
> I noticed that in order to do some of these things I might need CGAL,
> but I understand that the learning curve can be quite steep.
> The things I need to do are :
> 1. Generate TINs at multiple levels of details by introducing Steiner
> points.
> 2. Being able to access the triangles and its adjacent triangles in raw
> form (like 0 1 2 vertices of triangle in counter-clockwise format)
> so that I can feed it to a "Chen and Han" shortest path implementation
> by O'Rourke (http://cs.smith.edu/~orourke/ShortestPaths/)
> 3. Have the ability to compute the slope of each triangle and also all
> its interior angles.
> 4. Need to be able to *project* onto the terrain the 3D euclidean line
> between any two points of the terrain.
> 5. Generate a Voronoi diagram from the Delaunay (Triangle generates this
> too)

Hi,

An email will certainly not be able to summarize everything you can do 
with CGAL triangulations... the CGAL manual does it much better.
The user manual presents an overview, together with examples 
http://www.cgal.org/Manual/latest/doc_html/cgal_manual/Triangulation_2/Chapter_main.html
Then the reference manual gives all details.

In a nutshell, the 2D triangulation package allows to compute Delaunay 
triangulations and gives dual functions to get Voronoi features.
It has many functionalities.
There is a specific traits class Projection_traits_xy_3 for the case of 
a terrain.
There are functions computing angles in the CGAL Kernel.
There is a Voronoi diagram package.
There is also an interface to the BGL that should help for shortest 
paths 
http://www.cgal.org/Manual/latest/doc_html/cgal_manual/BGL/Chapter_main.html 


> Someone who used CGAL mentioned that traversing over faces of a
> triangulation in CGAL can be quite cumbersome

strange... the package provides several iterators and circulators to 
easily traverse triangulations in various ways.

Best,
        Monique Teillaud

> and that I should
> instead convert it to a polyhedron and use the iterator there. So I just
> want to understand if CGAL will be able to help me with all the
> things I need to do and if I might get stuck halfway? Hopefully CGAL
> will not be overkill for what I am trying to do? I found another C++
> library that used the DECL (http://www.holmes3d.net/graphics/dcel/),
> would this be easier to use than CGAL for what I am trying to achieve?
> I ask since I am not going to do very complicated computational geometry
> related work on the surface, if CGAL would be too much to work with?
>
> Thanks,
> Manu
>
> --
>
> The greater danger for most of us lies not in setting our aim too high
> and falling short; but in setting our aim too low, and achieving our mark.
> - Michelangelo


--
Monique Teillaud
INRIA Sophia Antipolis - Méditerranée
http://www.inria.fr/sophia/members/Monique.Teillaud/