CGAL users discussion list

[Andreas Fabri <>]

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