CGAL users discussion list

["thetis guan" <>]

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;

}