CGAL users discussion list

[Andreas Fabri <>]

 wrote:
> Hi Andreas,
> that seems to be an appropriate solution. However I don't get it to work. Does
> locate only works for Triangulation_2 or also for Delaunay_Triangulation_2 ? I
> get an error "no matching function" when trying this:
>
> Point2 p_c(2.0,3.2);
> Face_handle fh = Delaunay.locate(p_c);

Hi Matthias,

Well, if you use the traits class that allows you to insert 3D points,
and only their x and y coordinate is taken into account, you should also use

DT::Point p(2.0, 3.2, 0);


When it works, you should next have a look at
http://www.cgal.org/Manual/3.4/doc_html/cgal_manual/Triangulation_2/Chapter_main.html#Section_29.10

The thing is that with the locate function you get it down from linear
time (looking at all triangles) to sqrt(n) time (the average diameter of
a triangulation with n vertices and random points in a square).

The Triangulation_hierarchy_2 brings it down to log(n).

andreas