CGAL users discussion list

[Johannes Otepka <>]

Thetis,
Simply call the function build(). Considering your code:

[...]

      Distance tr_dist;

// want to compute query time
      tree.build();  //builds the tree!!!

      DWORD   dwStart    =   GetTickCount();

      Neighbor_search N1( tree, query, K, 0.0, false); // eps=10.0, 
nearest=false

      DWORD   dwEnd    =   GetTickCount();  

[...]


Cheers,
Johannes



thetis guan wrote:

>  Hi  Johannes
> thank you for your answer..but i do not know how to build the kd tree 
> manually. please explain it clearly or give me a sample!
> thank you very much!
>
>  
>
> Cheers,
> thetis
>
>
>
>  
> On 4/20/07, *Johannes Otepka* < 
> <mailto:>> wrote:
>
>     Thetis,
>     If you really want to measure the "true" search time, you have to
>     build the kd tree manually. otherwise it's done automatically
>     during the first spatial (search) operation which is why all your
>     different tests result in more or less to the same computation time.
>
>     I have no experince with CGAL::Cartesian*_d *Kernel, the Manhattan
>     distance and furtherst neigbour searching. However the building
>     time of 30s for 200000 Points seems to me quite slow. I use the
>     'normal' CGAL::Cartesian for 2D and 3D kd tree's. On my 2 years
>     old notebook a kd tree of about 2 Mio Pts takes ca..10 sec to build.
>
>     Cheers,
>        Johannes
>
>     thetis guan wrote:
>
> >     Dear all:
> >
> >     I have a question about efficiency of dD Spatial Searching. that
> >     is, give a query item /q / the points of* P *set can not browsed
> >     efficiently.
> >
> >     My operating system is MS XP; compiler is MS Visual8.0(.NET2005),
> >     toolkit of CGAL is Release3.2;
> >      
> >
> >     For example:
> >
> >     I set a set* P* of data points including 200000 points. I want to
> >     find a query point */q/ *in set* P . *
> >
> >     Both Neighbor searching and Range searching which I had a try to
> >     test. Searching time is about 30s. In Neighbor searching, I
> >     respectively use four classes to test:
> >     CGAL::Orthogonal_k_neighbor_search,
> >     CGAL::Orthogonal_incremental_neighbor_search, CGAL::
> >     k_neighbor_search, CGAL:: Incremental _neighbor_search. Among the
> >     tests, I give different splitting rules and bucket size, such as
> >     Sliding_midpoint, Fair, Sliding_fair, ect.
> >
> >     Although time of these test are different, these differences are
> >     little. Searching time always  about 30s.
> >
> >     I think the searching time is too long, but I do not know how to
> >     improve searching efficiency and reduce searching time.
> >
> >     Could you please shed some light on this?
> >
> >     Thanks in advance and best regards!
> >
> >      
> >
> >      
> >
> >     I execute all of examples of General neighbor searching described
> >     in cgal-manual. And one of examples Codes as below:
> >
> >      
> >
> >     #include <CGAL/basic.h>
> >
> >     #include <CGAL/Cartesian_d.h>
> >
> >     #include <CGAL/point_generators_2.h>
> >
> >     #include <CGAL/Manhattan_distance_iso_box_point.h>
> >
> >     #include <CGAL/K_neighbor_search.h>
> >
> >     #include <CGAL/Search_traits_2.h>
> >
> >     #include  <Windows.h >
> >
> >     #include  <time.h >
> >
> >     using namespace std ;
> >
> >      
> >
> >     typedef CGAL:: Cartesian_d <double> K;
> >
> >     typedef K:: Point_d Point_d;
> >
> >     typedef CGAL:: Random_points_in_square_2 <Point_d>
> >     Random_points_iterator;
> >
> >     typedef K:: Iso_box_d Iso_box_d;
> >
> >     typedef K TreeTraits ;
> >
> >     typedef CGAL:: Manhattan_distance_iso_box_point <TreeTraits>
> >     Distance;
> >
> >     typedef CGAL:: K_neighbor_search <TreeTraits, Distance>
> >     Neighbor_search;
> >
> >     typedef Neighbor_search:: Tree Tree;
> >
> >      
> >
> >     int _tmain( int argc, _TCHAR* argv[])
> >
> >     {
> >
> >            const int N = 200000; //set P including N points
> >
> >            const int K = 10; //search K points
> >
> >            Tree tree;
> >
> >            Random_points_iterator   rpg;   //generator random N points
> >
> >            for(int i = 0; i < N; i++)
> >
> >            {
> >
> >                   tree.insert(* rpg++); //add  point to kd-tree
> >
> >            }
> >
> >      
> >          //define query item
> >
> >            Point_d pp(0.1,0.1);
> >
> >            Point_d qq(0.2,0.2);
> >
> >            Iso_box_d query( pp, qq);
> >
> >      
> >
> >            Distance tr_dist;
> >
> >     // want to compute query time
> >
> >            DWORD   dwStart    =   GetTickCount();
> >
> >            Neighbor_search N1( tree, query, K, 0.0, false); //
> >     eps=10.0, nearest=false
> >
> >            DWORD   dwEnd    =   GetTickCount();  
> >
> >            DWORD   dwTimeTaken    =   dwEnd   -   dwStart; //this is
> >     query time result
> >
> >      
> >
> >            std::cout << "For query rectange = [0.1, 0.2]ˆ2 " << std::endl
> >
> >                   << "The " << K << " approximate furthest neighbors
> >     are: " << std::endl;
> >
> >            for (Neighbor_search:: iterator it = N1.begin();it != N1.
> >     end(); it++)
> >
> >            {
> >
> >                          std:: cout << " Point " << it->first << " at
> >     distance = " << tr_dist.
> >     inverse_of_transformed_distance(it->second) << std:: endl;
> >
> >            }
> >
> >      
> >
> >            return 0;
> >
> >     }