CGAL users discussion list

[Manuel Holtgrewe <>]

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();
  }
}