Collaboration diagram for Kdtree_d< Traits >::Node:

Classes
class	Plane

Public Types
enum	{ LEFT, RIGHT }

typedef std::back_insert_iterator < List_points >	back_iter

Public Member Functions
const Plane &	get_hs (int side) const

bool	is_points_in_hs (const Plane &pl) const

bool	is_valid () const

void	dump (int depth)

bool	is_point () const

	Node ()

	~Node ()

void	copy_subtree_points (back_iter &result, const Box &rect)

void	search (std::back_insert_iterator< List_points > result, const Box &rect, Box &region)

Static Public Member Functions
static void	search_recursive (back_iter &result, Node *node, const Box &rect, Box &_region, Plane &plane, bool f_split_plus)

Public Attributes
Plane	plane

Point *	pnt

Node *	left

Node *	right

Detailed Description

template<class Traits>
class Kdtree_d< Traits >::Node

Definition at line 558 of file kdtree_d.h.

Member Typedef Documentation

typedef std::back_insert_iterator<List_points> back_iter

Definition at line 697 of file kdtree_d.h.

Member Enumeration Documentation

anonymous enum

Enumerator
LEFT
RIGHT

Definition at line 629 of file kdtree_d.h.

629 { LEFT, RIGHT };

Kdtree_d::Node::RIGHT

Definition: kdtree_d.h:629

Kdtree_d::Node::LEFT

Definition: kdtree_d.h:629

Constructor & Destructor Documentation

Node ( )

inline

Definition at line 699 of file kdtree_d.h.

699 : plane(), pnt(NULL), left(NULL), right(NULL)

700 {}

Kdtree_d::Node::pnt

Point * pnt

Definition: kdtree_d.h:625

Kdtree_d::Node::right

Node * right

Definition: kdtree_d.h:627

Kdtree_d::Node::left

Node * left

Definition: kdtree_d.h:627

Kdtree_d::Node::plane

Plane plane

Definition: kdtree_d.h:624

~Node ( )

inline

Definition at line 702 of file kdtree_d.h.

703 {}

Member Function Documentation

void copy_subtree_points	(	back_iter &	result,
		const Box &	rect
	)

inline

Definition at line 705 of file kdtree_d.h.

References Kdtree_d< Traits >::Node::copy_subtree_points(), Kdtree_d< Traits >::Box::is_in(), Kdtree_d< Traits >::Node::is_point(), Kdtree_d< Traits >::Node::left, Kdtree_d< Traits >::Node::pnt, and Kdtree_d< Traits >::Node::right.

Referenced by Kdtree_d< Traits >::Node::copy_subtree_points(), and Kdtree_d< Traits >::Node::search_recursive().

     {
       if  ( is_point() ) {
         if  ( rect.is_in( *pnt ) )
           (*result++) = *pnt;
         return;
       }
       if  ( left != NULL ) 
         left->copy_subtree_points( result, rect );
       if  ( right != NULL ) 
         right->copy_subtree_points( result, rect );
     }

Here is the call graph for this function:

Here is the caller graph for this function:

void dump ( int depth )

inline

Definition at line 670 of file kdtree_d.h.

References Kdtree_d< Traits >::Node::Plane::dump(), Kdtree_d< Traits >::Node::dump(), Kdtree_d< Traits >::Node::is_point(), Kdtree_d< Traits >::Node::left, Kdtree_d< Traits >::Node::plane, and Kdtree_d< Traits >::Node::right.

Referenced by Kdtree_d< Traits >::Node::dump(), and Kdtree_d< Traits >::dump().

     {
       int  ind;
           
       for  ( ind = 0; ind < depth; ind++ )
         std::cout << " ";
 
       if  ( is_point() ) {
         std::cout << *pnt << "\n";
         return;
       }
           
       plane.dump(); 
       std::cout << "\n";
       left->dump( depth + 1 );
       for  ( ind = 0; ind < depth; ind++ )
         std::cout << " ";
 
       std::cout << "!!!!!!!!!!!!\n";
       right->dump( depth + 1 );          
     }

Here is the call graph for this function:

Here is the caller graph for this function:

const Plane& get_hs ( int side ) const

inline

Definition at line 631 of file kdtree_d.h.

References Kdtree_d< Traits >::Node::LEFT, Kdtree_d< Traits >::Node::Plane::orient_half_space(), and Kdtree_d< Traits >::Node::plane.

Referenced by Kdtree_d< Traits >::Node::is_valid().

     {
     
       ((Plane *)&plane)->orient_half_space( side == LEFT );
 
       return   plane;
     }

Here is the call graph for this function:

Here is the caller graph for this function:

bool is_point ( ) const

inline

Definition at line 692 of file kdtree_d.h.

References Kdtree_d< Traits >::Node::left, and Kdtree_d< Traits >::Node::right.

Referenced by Kdtree_d< Traits >::Node::copy_subtree_points(), Kdtree_d< Traits >::Node::dump(), Kdtree_d< Traits >::Node::is_points_in_hs(), Kdtree_d< Traits >::Node::is_valid(), and Kdtree_d< Traits >::Node::search().

     { 
       return   ((left == NULL)  &&  (right == NULL)); 
     }

Here is the caller graph for this function:

bool is_points_in_hs ( const Plane & pl ) const

inline

Definition at line 640 of file kdtree_d.h.

References Kdtree_d< Traits >::Node::Plane::is_in(), Kdtree_d< Traits >::Node::is_point(), Kdtree_d< Traits >::Node::is_points_in_hs(), Kdtree_d< Traits >::Node::left, and Kdtree_d< Traits >::Node::right.

Referenced by Kdtree_d< Traits >::Node::is_points_in_hs(), and Kdtree_d< Traits >::Node::is_valid().

     {
       if  ( is_point() ) 
         return  pl.is_in( *pnt );
 
       if  ( left != NULL  &&  ( ! left->is_points_in_hs( pl ) ) )
         return  false;
       if  ( right != NULL  &&  ( ! right->is_points_in_hs( pl ) ) )
         return  false;
 
       return  true;
     }

Here is the call graph for this function:

Here is the caller graph for this function:

bool is_valid ( ) const

inline

Definition at line 654 of file kdtree_d.h.

References Kdtree_d< Traits >::Node::get_hs(), Kdtree_d< Traits >::Node::is_point(), Kdtree_d< Traits >::Node::is_points_in_hs(), Kdtree_d< Traits >::Node::left, Kdtree_d< Traits >::Node::LEFT, Kdtree_d< Traits >::Node::right, and Kdtree_d< Traits >::Node::RIGHT.

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

     {
       if  ( is_point() )
         return  true;
 
       if  ( left != NULL ) 
         if  ( ! left->is_points_in_hs( get_hs( LEFT ) ) )
           return  false;
       if  ( right != NULL ) 
         if  ( ! right->is_points_in_hs( get_hs( RIGHT ) ) )
           return  false;
 
       return  true;
     }

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,
		const Box &	rect,
		Box &	region
	)

inline

Definition at line 762 of file kdtree_d.h.

References Kdtree_d< Traits >::Box::is_in(), Kdtree_d< Traits >::Node::is_point(), Kdtree_d< Traits >::Node::left, Kdtree_d< Traits >::Node::plane, Kdtree_d< Traits >::Node::pnt, Kdtree_d< Traits >::Node::right, and Kdtree_d< Traits >::Node::search_recursive().

Referenced by Kdtree_d< Traits >::search(), and Kdtree_d< Traits >::Node::search_recursive().

     {
       if (is_point()) {
         if  ( rect.is_in( *pnt ) )
           (*result++) = *pnt;
         return;
       }
         
       //this is not a point so it is a hypeplane
       if  ( left != NULL )
         search_recursive( result, left, rect,
                           region, plane, true );
       if  ( right != NULL )
         search_recursive( result, right, rect, 
                           region, plane, false );
     }

Here is the call graph for this function:

Here is the caller graph for this function:

static void search_recursive	(	back_iter &	result,
		Node *	node,
		const Box &	rect,
		Box &	_region,
		Plane &	plane,
		bool	f_split_plus
	)

inlinestatic

Definition at line 719 of file kdtree_d.h.

References Kdtree_d< Traits >::Node::copy_subtree_points(), Kdtree_d< Traits >::Node::Plane::get_coord(), Kdtree_d< Traits >::Box::is_in(), Kdtree_d< Traits >::Box::is_intersect_in_dim_closed(), Kdtree_d< Traits >::Node::search(), and Kdtree_d< Traits >::Node::Plane::split().

Referenced by Kdtree_d< Traits >::Node::search().

     {
       //printf( "search_recusrive\n" );
       Box  * p_r = new Box( _region );
 
       //printf( "z" );
       //fflush( stdout );
 
       plane.split( *p_r, f_split_plus );
 
       //printf( "c" );
       //fflush( stdout );
       assert( node != NULL );
  
       //printf( "b" );
       //fflush( stdout );
       if  ( rect.is_in( *p_r ) ) 
       {
         //printf( "5" );
         //fflush( stdout );
         node->copy_subtree_points( result, rect );
         //printf( "\tsearch_recursive done...\n" );
         //printf( "6" );
         //fflush( stdout );
         delete p_r;
         return;
       } 
                 
       //printf( "v" );
       //fflush( stdout );
 
       if  ( rect.is_intersect_in_dim_closed( plane.get_coord(), *p_r ) )
         node->search( result, rect, *p_r );
       //printf( "x" );
       //fflush( stdout );
       delete p_r;
     }