CGAL users discussion list

["Sebastien Loriot (GeometryFactory)" <>]

Frankie Li wrote:
> Hi all,
>
> I'm trying to traverse all neighbors of each vertex in a regular 
> triangulation, and naively, I've done something like this:
>
> // pseudo-code
>
> for( Finite_vertex_iterator it = tr.finite_vertices_begin();
>       it != tr.finite_vertices_end(); ++ it )
> {
>
>   vector<Vertex_handle> Ngb_vertices;
>   tr.finite_adjacent_vertices( it, std::back_inserter( Ngb_vertices ));
> }
>
> However, I found it to be surprisingly slow.  I have approximately 15000 
> vertices, and I'm using Exact_predicates_inexact_constructions_kernel. 
> (It takes about 3000 seconds to go through the loop above for 15000 
> vertices.  I'm running on a Core 2 Quad machine.)
>
>
> Any advice is welcomed!  Thanks!
>
> Frankie
Hello,

what you report is quite strange, because this is a combinatoric 
operation usually fast. I just make a quick test with 4500 weighted 
points and without any optimisation the timing is less 0.03s.

Can you test the program joint (it expects a file with line x y z radius 
as first argument) and tell us about the running time.


S.
#include <CGAL/Exact_predicates_inexact_constructions_kernel.h>
#include <CGAL/Regular_triangulation_euclidean_traits_3.h>
#include <CGAL/Regular_triangulation_3.h>
#include <CGAL/Timer.h>
#include <fstream>
#include <iostream>

typedef CGAL::Exact_predicates_inexact_constructions_kernel Kernel;
typedef CGAL::Regular_triangulation_euclidean_traits_3<Kernel> Traits;
typedef CGAL::Regular_triangulation_3<Traits> T3;

template <class Object>
void fill_wp_lists(const char* file_path,std::list<Object>& Ls,double rw=0){
  double x,y,z,r;
  std::ifstream input(file_path);
 
  while(input){
    input >> x;
    if (!input) break;
    input >> y >> z >> r;
    Ls.push_back(Object(Kernel::Point_3(x,y,z),(r+rw)*(r+rw)));
  }
}


int main(int argc,char** argv){
  CGAL::Timer time;
  
  std::list<CGAL::Weighted_point<Kernel::Point_3,Kernel::FT> > lst;
  fill_wp_lists(argv[1],lst);
  
  T3 t(lst.begin(),lst.end());
  
  time.start();
  int i=0;
  for( T3::Finite_vertices_iterator it = t.finite_vertices_begin();
      it != t.finite_vertices_end(); ++ it )
  {

    std::vector<T3::Vertex_handle> Ngb_vertices;
    t.finite_adjacent_vertices( it, std::back_inserter( Ngb_vertices ));
    i+=Ngb_vertices.size();
  }
  time.stop();
  std::cout << time.time()<< "s. " << i << std::endl;
}