CGAL users discussion list

[Tom Kazimiers <>]

Mariette Yvinec schrieb:
>
> 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,

thank you for your answer. Why does the nearest vertex not need to be a
vertex of the face?
If the (2D-) point is included in a face the nearest vertex can only be
part of it, could't it? If not, where could the nearest vertex be?
(to clarify, I ment 2D space with a non-intersecting mesh - sorry, I did
not say this before)

I also found the the traits class you mentioned (it was used in the
terrain example), but I see no way
to insert it as a parameter for a constrained delaunay triangulation.

Thanks and regards,
Tom