--- Begin Message ---
Issha Kayo wrote:
> Dear all,
>
> I am now looking for a method to insert large number of points
> efficiently to a 3D Delaunay triangulation.
>
> "int dt.insert(InputIterator first, InputIterator last)" is the method
> but I want to insert points with info. Now I insert one by one by using
> "Vertex_handle dt.insert(Point)" and assigning the info to the returned
> Vertex_handle, but it is not efficient.
>
> Thank you,
> Issha Kayo
>
Hello,
You can simply copy-paste the insert(InputIterator first, InputIterator
last) function to benefit from the efficiency of the spatial sort.
Since the spatial sort requires your input data to be shuffled you
should be careful while assigning your info.
I joined to this email a working example where the info assigned to a
vertex is the original insertion order.
Best,
Sebastien.
--
You are currently subscribed to cgal-discuss.
To unsubscribe or access the archives, go to
https://lists-sop.inria.fr/wws/info/cgal-discuss
#include <CGAL/Exact_predicates_inexact_constructions_kernel.h>
#include <CGAL/Delaunay_triangulation_3.h>
#include <CGAL/Triangulation_vertex_base_with_info_3.h>
#include <iostream>
typedef CGAL::Exact_predicates_inexact_constructions_kernel K;
typedef CGAL::Triangulation_vertex_base_with_info_3<int, K> Vb;
typedef CGAL::Triangulation_data_structure_3<Vb> Tds;
typedef CGAL::Delaunay_triangulation_3<K, Tds> Delaunay;
typedef Delaunay::Point Point;
//spatial sort traits to use with a pair of point pointers and integer.
template<class Triangulation>
struct Traits_for_spatial_sort:public Triangulation::Geom_traits{
typedef typename Triangulation::Geom_traits Gt;
typedef std::pair<const typename Triangulation::Point*,int> Point_3;
struct Less_x_3{
bool operator()(const Point_3& p,const Point_3& q) const {
return typename Gt::Less_x_3()(*(p.first),*(q.first));
}
};
struct Less_y_3{
bool operator()(const Point_3& p,const Point_3& q) const {
return typename Gt::Less_y_3()(*(p.first),*(q.first));
}
};
struct Less_z_3{
bool operator()(const Point_3& p,const Point_3& q) const {
return typename Gt::Less_z_3()(*(p.first),*(q.first));
}
};
Less_x_3 less_x_3_object () const {return Less_x_3();}
Less_y_3 less_y_3_object () const {return Less_y_3();}
Less_z_3 less_z_3_object () const {return Less_z_3();}
};
//function inserting points into a triangulation
//and setting the info field to the order in the input list.
template <class Triangulation,class Point_iterator>
void
build_triangulation_with_indices(
Point_iterator begin,
Point_iterator end,
Triangulation& T)
{
std::vector<std::pair<const typename Triangulation::Point*,int> > points;
int index=-1;
for (Point_iterator it=begin;it!=end;++it){
points.push_back(std::make_pair(&(*it),++index));
}
std::random_shuffle (points.begin(), points.end());
spatial_sort (points.begin(),points.end(), Traits_for_spatial_sort<Triangulation>());
typename Triangulation::Cell_handle hint;
for (typename std::vector< std::pair<const typename Triangulation::Point*,int> >::const_iterator
p = points.begin();p != points.end(); ++p)
{
typename Triangulation::Locate_type lt;
typename Triangulation::Cell_handle c;
int li, lj;
c = T.locate (*(p->first), lt, li, lj, hint);
typename Triangulation::Vertex_handle v = T.insert (*(p->first), lt, c, li, lj);
if ( v==typename Triangulation::Vertex_handle() )
hint=c;
else{
v->info() = p->second ;
hint=v->cell();
}
}
}
int main()
{
std::list<Point> input;
input.push_back(Point(0,0,0));
input.push_back(Point(1,0,0));
input.push_back(Point(0,1,0));
input.push_back(Point(0,0,1));
input.push_back(Point(2,2,2));
input.push_back(Point(-1,0,1));
Delaunay T;
build_triangulation_with_indices(input.begin(),input.end(),T);
Delaunay::Finite_vertices_iterator vit;
for (vit = T.finite_vertices_begin(); vit != T.finite_vertices_end(); ++vit)
std::cout << vit->info() << "\n"; //prints the position in input
return 0;
}
--- End Message ---
