CGAL users discussion list

[Tom Kazimiers <>]

Hi Andreas,

thank you for your reply. If I sit on a vertex close to the constraint
isn't it the case that I get
a face that is on the constraints side the vertex is in? Actually, I
wonder if one face can be "crossed"
by a constraint so that some vertices are on one constraint side and
some on the other. I guess not,
since all faces are delaunay triangles. So if I get a face lieing to the
"left" of the constraint through a
vertex lieing to the "left" of the contraint, all vertices of the face
should lie on the "left" side of the
constraint, don't they?
The solution I currently use relies at least on this assumption -if this
is not true, it will not safely work, true.
A function called "closesst_vertex" does not exist for constrained
delaunay triangulations, so I go through
the face to the vertices.
But, maybe I understood something wrong :)

bye, and thanks,
Tom



Andreas Fabri schrieb:
> Hi Tom,
>
> If you have a constraint running from San Francisco to New York City,
> and you sit on a vertex close to the constraint somewhere in the middle
> of the US and the geometrically closest vertex is on the other side of
> this constaint, then the function closest_vertex gives you either a
> vertex on your side or even the vertex of SF or NYC, but not what you
> are looking for.
>
> andreas
>
>
> Tom Kazimiers wrote:
>> 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
>>>   
>>
>