CGAL users discussion list

[Tom Kazimiers <>]

Mariette,

thanks for your further explanations. Indeed, I was wrong and did not
see this issue.
The demomstration through the voronoi diagram makes everyting clear.

The hint of using get_boundary_of_conflicts(Point q, .......) works
pretty well and yes,
I was looking for the nearest visible neighbor.

Thanks and regards,
Tom

Mariette Yvinec schrieb:
> Sorry to disturb,
> but this is wrong.
> Even within  a Delaunay triangulation (without any constraint)
> you may find query points whose nearest site is not a vertex
> of the triangle in which they lie.
> In the joint the example, the blue lines draw the Delaunay triangulation
> while the red line draw the Voronoi diagram (showing for each site,
> its set of closest points).
> Every query point in the grey area has for nearest neighbor
> a site which is not a vertex in its cell.
>
> Furthermore,
> it seems that what you are looking for is not
> the nearest neighbor but the nearest visible
> neighbor...
> What is true is that if you were inserting your query point
> in the constrained Delaunay,
> the new triangulation would have an edge
> between your query point and its nearest visible vertex.
> So what you can do, is to use the member function
> get_boundary_of_conflicts(Point q, .......),
> where q is your query point,
> look at all vertices on the output boundary
> and get the closest to q :
> this is the nearest visible vertex from q.
>
>
>
>
> Tom Kazimiers wrote:
>> Damien,
>>
>> thanks for your intrusion and clarification :)
>> Now, the problem is clear and I am happy that it is not a problem for me
>> since I needed not the geometrically absolute next vertex, but the
>> geometrically next vertex respecting constrains. So in your example I
>> would be lucky if NY is the result of the query. It seems that I made
>> myself not very clear in the first place, infact, what should one think
>> else by reading "nearest vertex" :) So thanks for the explanation and
>> the patience, I will surely need this at another place in my application.
>>
>> Thanks and regards,
>> Tom
>>
>>
>> Damian Sheehy schrieb:
>>   
>>> 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 
>>> <
>>> <mailto:>>
>>>  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
>>>
>>>
>>>
>>> ------------------------------------------------------------------------
>>>
>>>     
>>
>>   
>
> -- 
> Mariette Yvinec
> Geometrica project team
> INRIA  Sophia-Antipolis  
>
>
>