CGAL users discussion list

[Olivier Devillers <>]

Le 9/9/12 8:18 AM, Manu Kaul a écrit :
> Hi all,
> I used the "Triangle" library from 
> http://www.cs.cmu.edu/~quake/triangle.html 
> <http://www.cs.cmu.edu/%7Equake/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/ 
> <http://cs.smith.edu/%7Eorourke/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)
2 Triangulation of a terrain is what you need:
http://www.cgal.org/Manual/beta/doc_html/cgal_manual/Triangulation_2/Chapter_main.html#Subsection_37.5.2

4 The triangles intersected by the vertical projection of a line on the 
terrain are given by
http://www.cgal.org/Manual/beta/doc_html/cgal_manual/Triangulation_2_ref/Class_Triangulation_2.html#Nested_type_Line_face_circulator

5 use "dual" fonctions of vertices and faces

3 are just basic computations

1  you have to manage levels of details yourself. CGAL triangulation 
supports insertion and deletions.