CGAL users discussion list

[Tom Kazimiers <>]

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