CGAL users discussion list

[Mariette Yvinec <>]

Tom Kazimiers wrote:
> Hello,
>
> as I am relatively new to CGAL I am not very familiar with some concepts
> or design decisions taken.
> For example have I currently the problem (or wish :P ) to make fast
> "nearest vertex queries" on constrained delaunay triangulations.
> In the manual I found a "nearest_vertex ( Point p, Face_handle
> f=Face_handle())" method only for
> CGAL::Delaunay_triangulation_2<Traits,Tds> and this is what I would need
> in a constrained delaunay triangulation. Since I did not find it I
> implemented it in the following way:
>
>                 // Typedefs CGAL
>                 struct K :
> CGAL::Exact_predicates_inexact_constructions_kernel {};
>                 typedef
> CGAL::Constrained_triangulation_face_base_2<K>                    Fb;
>                 typedef CGAL::Exact_predicates_tag                   
>                     Itag;
>        
>                 typedef CGAL::Triangulation_data_structure_2 <
> CGALLaunchSite<>, Fb >    Tds;
>                typedef CGAL::Constrained_Delaunay_triangulation_2<K,
> Tds, Itag>        CDT;
>        
>                 typedef CDT::Vertex_handle        Vertex_handle;
>                 typedef CDT::Face_handle           Face_handle;
>                 typedef CDT::Point                       PointCDT;
>                 typedef K::Vector_2                    VectorCGAL;
>
>                 ...
>
>                 // Nearest vertex query
>                 PointCDT cgal_pos(position.x(), position.z());
>                
>                 Face_handle handle = m_cdt.locate(cgal_pos);
>                     
>                 Vertex_handle v0 = handle->vertex(0);
>                 Vertex_handle v1 = handle->vertex(1);
>                 Vertex_handle v2 = handle->vertex(2);
>                
>                 VectorCGAL vec0(v0->point(), cgal_pos);
>                 VectorCGAL vec1(v1->point(), cgal_pos);
>                 VectorCGAL vec2(v2->point(), cgal_pos);
>                
>                 PrecisionType distance0 = vec0.squared_length();
>                 PrecisionType distance1 = vec1.squared_length();
>                 PrecisionType distance2 = vec2.squared_length();
>                
>                 if (distance0 < distance1) {
>                     if (distance0 < distance2) {
>                         return &*v0;
>                     } else {
>                         return &*v2;
>                     }
>                 } else {
>                     if (distance1 < distance2) {
>                         return &*v1;
>                     } else {
>                         return &*v2;
>                     }
>                 }
>
>
> Is there any more easy or "convenient" way to do this? I ask since a
> similar method exists for the triangulation without constrains.
>
> Thanks again and in advance,
> I hope that I did not miss anything in the manual :),
> Tom
>
> P. s.: Is there a way to make a constrained delaunay "terrain" (e. g. a
> CDT with elevation, but that is only in XY space delaunay)?
>   

your solution is oversimplified because the nearest vertex need not
be a vertex of the face including the query location.

The CGAL traits class Triangulation_euclidean_traits_xy_2
is designed to compute  the elevation of
the Delaunay triangulation in xy space  of 3d points.
It will lack of intersection test to compute a constrained Delaunay
triangulation in xy space.

--
Mariette Yvinec
Geometrica project team
INRIA  Sophia-Antipolis