CGAL users discussion list

["Laurent Rineau (GeometryFactory)" <>]

On Sunday 22 February 2009 05:46:28 Cai Zhenning wrote:
> Hi,
>
> I'm new to CGAL and now I'm using Triangulation_2 to generate a
> triangulation.
>
> I wonder that if there is an efficient way to access to the points
> before I insert them into triangulation. For example, if I write
>
> Triangulation_2 t;
> std::vector<Point_2> p;
> // ...
> t.insert(p.begin(), p.end());
>
> How can I get the vertex in t that holds p.front()? I know t.locate will
> do that, but I think it is an inefficient way if I want to locate all
> points in p.

You need to insert the points one by one. Something like that:

std::vector<Triangulation_2::Vertex_handle> handles;
Triangulation_2::Face_handle f;
typedef std::vector<Point_2>::const_iterator iterator;
for(iterator it = p.begin(); it != p.end(); ++it)
{
  Triangulation_2::Vertex_handle v = t.insert(*it, f);
  handles.push_back(v);
  f = v->face();
}

The variable f is a possible optimization, if your points are sorted. You can 
even sort them *before* the insertion, using the spatial sort:

#include <CGAL/spatial_sort.h>
CGAL::spatial_sort(p.begin, p.end());

but not that this will modify your vector of points.

-- 
Laurent Rineau, PhD
Engineer at GeometryFactory
http://www.geometryfactory.com/