#include <kdtree_d.h>

Collaboration diagram for Kdtree_d< Traits >:

Classes
class	Box

class	ExtPoint

class	Node

Public Types
typedef Traits::Point	Point

typedef std::vector< Point >	List_points

typedef std::vector< Point >	list_points

Public Member Functions
	Kdtree_d (int k=2)

	~Kdtree_d ()

bool	is_valid (bool verbose=false, int level=0) const

void	dump ()

void	delete_all ()

void	search (std::back_insert_iterator< list_points > result, Box &rect)

void	build (std::vector< Point > &v)

Private Types
typedef Point *	Point_ptr

Private Member Functions
Node *	malloc_node (void)

Node *	build_r (Point_ptr *arr, int left, int right, int d)

Static Private Member Functions
static int	comp (const Point &a, const Point &b, int dim)

static int	partition (Point_ptr arr, int left, int right, Point p_pivot, int dim)

static void	split_arr (Point_ptr *arr, int left, int right, int pos_mid, int dim)

static Point_ptr	get_max_element (Point_ptr *arr, int left, int right, int d)

Private Attributes
int	size

Point *	p_arr_pt

Node *	root

int	dim

Node *	p_node_arr

int	node_count

Detailed Description

template<class Traits>
class Kdtree_d< Traits >

Definition at line 138 of file kdtree_d.h.

Member Typedef Documentation

typedef std::vector<Point> List_points

Definition at line 143 of file kdtree_d.h.

typedef std::vector<Point> list_points

Definition at line 933 of file kdtree_d.h.

typedef Traits::Point Point

Definition at line 142 of file kdtree_d.h.

typedef Point* Point_ptr

private

Definition at line 782 of file kdtree_d.h.

Constructor & Destructor Documentation

Kdtree_d ( int k = 2 )

inlineexplicit

Definition at line 935 of file kdtree_d.h.

References Kdtree_d< Traits >::dim, k, Kdtree_d< Traits >::p_arr_pt, Kdtree_d< Traits >::p_node_arr, and Kdtree_d< Traits >::root.

   { 
     dim = k;
     root = NULL; 
     p_arr_pt = NULL;
     p_node_arr = NULL;
   }

~Kdtree_d ( )

inline

Definition at line 943 of file kdtree_d.h.

References Kdtree_d< Traits >::delete_all().

   {
     delete_all();
   }

Here is the call graph for this function:

Member Function Documentation

void build ( std::vector< Point > & v )

inline

Definition at line 989 of file kdtree_d.h.

References Kdtree_d< Traits >::build_r(), i, j, Kdtree_d< Traits >::node_count, Kdtree_d< Traits >::p_arr_pt, Kdtree_d< Traits >::p_node_arr, Kdtree_d< Traits >::root, and Kdtree_d< Traits >::size.

Referenced by buildversionstring().

   {
     int  i;
     Point_ptr  * p_arr;
 
     size = v.size();
     p_arr_pt = new  Point[ size ];
     assert( p_arr_pt != NULL ); 
 
     p_arr = new  Point_ptr[ size ];
     assert( p_arr != NULL ); 
     
     p_node_arr = new Node[ 2 * size ];
     assert( p_node_arr != NULL );
 
     node_count = 0;
 
     /* fill the array */
     i = 0;
     for ( typename std::vector<Point>::iterator j = v.begin(); 
           j != v.end(); 
           j++ ) 
     {
       p_arr_pt[ i ] = (*j);
       p_arr[ i ] = p_arr_pt + i;
       i++;
     }
 
     // recursively build the tree from the sorted list
     // starting to divide it in coordinate 0
     root = build_r( p_arr, 0, size - 1, 0 );
     
     //printf( "b\n" );
     delete[]  p_arr;
   }

Here is the call graph for this function:

Here is the caller graph for this function:

Node* build_r	(	Point_ptr *	arr,
		int	left,
		int	right,
		int	d
	)

inlineprivate

Definition at line 883 of file kdtree_d.h.

References Kdtree_d< Traits >::dim, Kdtree_d< Traits >::get_max_element(), Kdtree_d< Traits >::Node::left, Kdtree_d< Traits >::malloc_node(), n, Kdtree_d< Traits >::Node::plane, Kdtree_d< Traits >::Node::pnt, Kdtree_d< Traits >::Node::right, and Kdtree_d< Traits >::split_arr().

Referenced by Kdtree_d< Traits >::build().

   {
     int  num, pos, next_d;
     Node  * n;
 
     num = right - left + 1;
 
     if ( num < 1)
       return NULL;
                 
     // if the list contains only one point, 
     // construct a leaf for this node
     if  ( num == 1) {
       //n = new node;
       n = malloc_node();
       n->pnt = arr[ left ];
             
       return  n;
     }
         
     // else divide space into two regions in 
     // dim-dim and cotinue recursively
     pos = (left + right) / 2;
     split_arr( arr, left, right, pos, d ); 
 
     Point  * p_median = get_max_element( arr, left, pos, d );
                 
     // create division plane;
     typename Node::Plane  plane( d, *p_median );
     //n = new node;
     // assert( n != NULL );
     n = malloc_node();
 
     n->plane = plane;
 
     next_d = d + 1;
     if  ( next_d >= dim )
       next_d = 0;
 
     // build left sub-tree
     n->left = build_r( arr, left, pos, next_d );
         
     // build right sub-tree
     n->right = build_r( arr, pos + 1, right, next_d );
                 
     return n;
   }

Here is the call graph for this function:

Here is the caller graph for this function:

static int comp	(	const Point &	a,
		const Point &	b,
		int	dim
	)

inlinestaticprivate

Definition at line 807 of file kdtree_d.h.

References CGAL::compare().

Referenced by Kdtree_d< Traits >::get_max_element(), and Kdtree_d< Traits >::partition().

   {
     return  Traits::compare( dim, a, b );
   }

Here is the call graph for this function:

Here is the caller graph for this function:

void delete_all ( )

inline

Definition at line 966 of file kdtree_d.h.

References Kdtree_d< Traits >::p_arr_pt, Kdtree_d< Traits >::p_node_arr, and Kdtree_d< Traits >::root.

Referenced by Kdtree_d< Traits >::~Kdtree_d().

   {
     root = NULL;
 
     if  ( p_arr_pt != NULL )
       delete[] p_arr_pt;
     p_arr_pt = NULL;
     if  ( p_node_arr != NULL )
       delete[]  p_node_arr;
     p_node_arr = NULL;
   }

Here is the caller graph for this function:

void dump ( )

inline

Definition at line 961 of file kdtree_d.h.

References Kdtree_d< Traits >::Node::dump(), and Kdtree_d< Traits >::root.

   {
     root->dump( 0);
   }

Here is the call graph for this function:

static Point_ptr get_max_element	(	Point_ptr *	arr,
		int	left,
		int	right,
		int	d
	)

inlinestaticprivate

Definition at line 868 of file kdtree_d.h.

References Kdtree_d< Traits >::comp().

Referenced by Kdtree_d< Traits >::build_r().

   {
     int  max_pos = left;
     Point  mx = *(arr[ max_pos ]);
 
     for  ( int  ind = left + 1; ind <= right; ind++ ) 
       if  ( comp( mx, *(arr[ ind ]), d ) < 0 ) {
         mx = *(arr[ ind ]);
         max_pos = ind;
       }
           
     return  arr[ max_pos ];
   }

Here is the call graph for this function:

Here is the caller graph for this function:

bool is_valid	(	bool	verbose = `false`,
		int	level = `0`
	)		const

inline

Definition at line 949 of file kdtree_d.h.

References Kdtree_d< Traits >::Node::is_valid(), and Kdtree_d< Traits >::root.

   {
     (void)verbose;
     (void)level;
 
     if  ( root == NULL )
       return  true;
 
     return  root->is_valid();
   }

Here is the call graph for this function:

Node* malloc_node ( void )

inlineprivate

Definition at line 792 of file kdtree_d.h.

References n, Kdtree_d< Traits >::node_count, Kdtree_d< Traits >::p_node_arr, and Kdtree_d< Traits >::size.

Referenced by Kdtree_d< Traits >::build_r().

   {
     Node  * p_ret;
 
     p_ret = &(p_node_arr[ node_count ]);
     node_count++;
     
     assert( node_count <= ( 2 * size ));
 
     Node n;
     *p_ret = n;
 
     return  p_ret;
   }

Here is the caller graph for this function:

static int partition	(	Point_ptr *	arr,
		int	left,
		int	right,
		Point *	p_pivot,
		int	dim
	)

inlinestaticprivate

Definition at line 812 of file kdtree_d.h.

References Kdtree_d< Traits >::comp(), i, and j.

Referenced by Kdtree_d< Traits >::split_arr().

   {
     int  i, j;
     Point_ptr  tmp;
 
     if  ( left >= right )
       return  left;
 
     i = left;
     j = right;
     
     while  ( i < j )  {
       if  ( comp( *(arr[ i ]), *(arr[ j ]), dim ) > 0 ) {
         tmp = arr[ i ];
         arr[ i ] = arr[ j ];
         arr[ j ] = tmp;
       }
       if  ( comp( *(arr[ i ]), *p_pivot, dim ) < 0 ) {
         i++;
       } else
         if  ( comp( *p_pivot, *(arr[ j ]), dim ) <= 0 ) 
           j--;
     }
 
     return  (i > left)? i - 1 : left;
   }

Here is the call graph for this function:

Here is the caller graph for this function:

void search	(	std::back_insert_iterator< list_points >	result,
		Box &	rect
	)

inline

Definition at line 978 of file kdtree_d.h.

References Kdtree_d< Traits >::dim, Kdtree_d< Traits >::root, and Kdtree_d< Traits >::Node::search().

   {
     if (root == NULL)
       return; // it is an empty tree - nothing to search in
 
     Box region = Box( dim );
                 
     root->search( result, rect, region );
   }

Here is the call graph for this function:

static void split_arr	(	Point_ptr *	arr,
		int	left,
		int	right,
		int	pos_mid,
		int	dim
	)

inlinestaticprivate

Definition at line 845 of file kdtree_d.h.

References Kdtree_d< Traits >::partition().

Referenced by Kdtree_d< Traits >::build_r().

   {
     int  pos;
             
     if  ( left >= right )
       return;
  
     pos = partition( arr, left, right, arr[ (left + right ) / 2 ],
                      dim );
     if  ( pos == pos_mid )
       return;
             
     if  ( pos < pos_mid ) 
       split_arr( arr, pos+1, right, pos_mid, dim );
     else
       split_arr( arr, left, pos, pos_mid, dim );
   }