CGAL users discussion list

[Tom Kazimiers <>]

Hi,

sorry to come back on this, but my question why my solution to get the
nearest vertex to a given position
in a constrained delaunay triangulation is oversimplified is not clear
to me.
Mariette said that the is not said that the nearest vertex to a given
position has not to be a vertex of the face
I get by using "locate(position)". How can this be if it is a 2D
triangulation?

Thanks in advance and regards,
Tom

Tom Kazimiers schrieb:
> 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
>