CGAL users discussion list

[Damian Sheehy <>]

Hi Tom,

Pardon my intrusion - I think the attached image will help clarify what Andreas is saying.
The thing to bear in mind here is the fact that a constrained Delaunay triangulation is not fully Delaunay.
In other words, some (or all!) triangles in the triangulation may not respect the Delaunay (empty circumcircle) property.
This is the case in the attached image; Denver is within the circumcircle of the larger triangle.
You can clearly see that Denver is the nearest vertex to the query point, however if you were to base your solution on the nearest vertex of the enclosing triangle the result would be New York, which is wrong.

To get around this problem you can do the following; make a copy of your constrained triangulation. Remove the constraints from the copy, and then you can use it to perform nearest vertex queries.

I hope this helps.

Damian

On Tue, Feb 17, 2009 at 1:29 PM, Tom Kazimiers <> wrote:

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
>>>
>>
>

--
You are currently subscribed to cgal-discuss.
To unsubscribe or access the archives, go to
https://lists-sop.inria.fr/wws/info/cgal-discuss

Attachment: NotNearestVertex.jpg
Description: JPEG image