CGAL users discussion list

[Damian Sheehy <>]

Hi Manuel,

Based on visual inspection, your code looks correct. You do not have
to special case the first nearest_vertex search; just pass a default
Face_handle in the first iteration of the loop and start the loop from
zero.

Regards,

Damian

On 4/17/09, Manuel Holtgrewe 
<>
 wrote:
> Hi,
>
> I am trying to perform finger search with the delaunay hierarchy code
> from CGAL. That is, I have a random point set which is added as the
> points of a delaunay hierarchy / triangulation. Then, I have a list of
> query points which lie along a line through this point set. I want to
> query for the nearest neighbours of the points on the line.
>
> This sequence of queries should offer good locality, i.e. if I know
> the nearest neighbour x of point i on the line, the nearest neighbour
> y of point i+1 should be very close to x. Thus, I am trying to use the
> second parameter to Delaunay_triangulation_2::nearest_vertex(const
> Point& p, Face_handle f= Face_handle()) const.
>
> Will the following code do this, i.e. when calling x->face() (where x
> is the nearest neighbour of the i-th query point i), will this return
> a face adjacent to x and this helps to speed up the queries?
>
> Thanks,
> Manuel
>
> // typedefs/aliases
> struct K : CGAL::Exact_predicates_inexact_constructions_kernel {};
>
> typedef CGAL::Triangulation_vertex_base_2<K>              Vbb;
> typedef CGAL::Triangulation_hierarchy_vertex_base_2<Vbb>  Vb;
> typedef CGAL::Triangulation_face_base_2<K>                Fb;
> typedef CGAL::Triangulation_data_structure_2<Vb,Fb>       Tds;
>
> typedef CGAL::Delaunay_triangulation_2<K, Tds>            Dt;
> typedef CGAL::Triangulation_hierarchy_2<Dt>
> Triangulation_hierarchy;
> typedef Triangulation_hierarchy::Vertex_circulator
> Vertex_circulator_hierarchy;
> typedef Triangulation_hierarchy::Point                    Point_hierarchy;
> typedef Triangulation_hierarchy::Vertex                   Vertex_hierarchy;
> typedef Triangulation_hierarchy::Vertex_handle
> Vertex_hierarchy_handle;
> typedef Triangulation_hierarchy::Face_handle
> Face_hierarchy_handle;
>
> void foo(const std::vector<Point_hierarchy> &points, const
> std::vector<Point_hierarchy> &queries) {
>  Triangulation_hierarchy dh;
>   dh.insert(points.begin(), points.end());
>   Vertex_hierarchy_handle v = dh.nearest_vertex(queries[0]);
>   Face_hierarchy_handle f = v->face();
>   for (int j = 1, jend = queries.size(); j < jend; ++j) {
>     v = dh.nearest_vertex(queries[j], f);
>     f = v->face();
>   }
> }
> --
> You are currently subscribed to cgal-discuss.
> To unsubscribe or access the archives, go to
> https://lists-sop.inria.fr/wws/info/cgal-discuss
>