CGAL users discussion list

[Johannes Otepka <>]

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;

}

-- 
-----------------------------------------------------------------------
Dr Johannes Otepka       Institute of Photogrammetry and Remote Sensing
                                       Vienna University of  Technology
                                                  Gusshausstrasse 27-29
                                                            A-1040 Wien
                                             Tel Linz   ++43/732/716460
                                             Tel Linz ++43/59966/612213
email:                    Tel     ++43/1/58801 12213
www:   http://www.ipf.tuwien.ac.at/jo        Fax     ++43/1/58801 12299
-----------------------------------------------------------------------