#include <RTree.hpp>

Inheritance diagram for RTree< Z >:

Classes
class	LessThan
Public Types
typedef double(*	DistSqFunc )(CubitVector &a, Z &b)
Public Member Functions
	RTree (double tol=GEOMETRY_RESABS)
	RTree (double tol, int max_c, int min_c)
	~RTree ()
CubitStatus	add (Z data)
CubitStatus	find (const CubitBox &range_box, DLIList< Z > &range_members)
CubitStatus	find (const CubitVector &ray_origin, const CubitVector &ray_direction, DLIList< Z > &range_members)
CubitBoolean	remove (Z data)
CubitStatus	k_nearest_neighbor (CubitVector &q, int k, double &closest_dist, DLIList< Z > &nearest_neighbors, DistSqFunc dist_sq_point_data)
void	set_tol (double tol)
double	get_tol ()
Static Public Member Functions
static bool	less_than_func (RTreeNode< Z > &node_a, RTreeNode< Z > &node_b)
Private Member Functions
CubitStatus	recursive_find (RTreeNode< Z > *rect_tree, const CubitBox &range_box, DLIList< Z > &range_members)
CubitStatus	recursive_find (RTreeNode< Z > *rect_tree, const CubitVector &ray_origin, const CubitVector &ray_direction, DLIList< Z > &range_members)
void	to_list (DLIList< RTreeNode< Z > * > &member_list, RTreeNode< Z > *top)
double	min_dist_sq (CubitVector &q, CubitBox &b_box)
Private Attributes
double	myTolerance
int	maxChildren
int	minChildren
RTreeNode< Z > *	myRoot

Detailed Description

template<class Z>
class RTree< Z >

Definition at line 24 of file RTree.hpp.

Member Typedef Documentation

template<class Z>

typedef double(* RTree< Z >::DistSqFunc)(CubitVector &a, Z &b)

Reimplemented from AbstractTree< Z >.

Definition at line 89 of file RTree.hpp.

Constructor & Destructor Documentation

template<class Z >

MY_INLINE RTree< Z >::RTree ( double tol = GEOMETRY_RESABS )

Definition at line 31 of file RTree.cpp.

{
  myRoot = NULL;
  myTolerance = tol;
  maxChildren = 8;
  minChildren = 2;
}

template<class Z >

MY_INLINE RTree< Z >::RTree	(	double	tol,
		int	max_c,
		int	min_c
	)

Definition at line 38 of file RTree.cpp.

{
  myRoot = NULL;
  myTolerance = tol;
  maxChildren = max_c;
  minChildren = min_c;
}

template<class Z >

MY_INLINE RTree< Z >::~RTree ( )

Definition at line 45 of file RTree.cpp.

{
  if ( myRoot != NULL )
  {
      //Go through and get all the children in a list.
    DLIList <RTreeNode<Z>*> to_delete;
    to_list(to_delete, myRoot);
    int ii;
    for(ii = to_delete.size(); ii > 0; ii-- )
      delete to_delete.pop();
    delete myRoot;
  }
}

Member Function Documentation

template<class Z>

MY_INLINE CubitStatus RTree< Z >::add ( Z data ) [virtual]

Implements AbstractTree< Z >.

Definition at line 76 of file RTree.cpp.

{
  CubitStatus stat;
  RTreeNode<Z> *new_root;
  RTreeNode<Z> *new_node = new RTreeNode<Z> (data, myTolerance, maxChildren,
                                             minChildren);
  if ( myRoot == NULL )
  {
    CubitBox b_box = data->bounding_box();
    myRoot = new RTreeNode <Z> (b_box, maxChildren, minChildren);
    myRoot->set_leaf_level(LEAF_RNODE);
    stat = myRoot->insert(new_node, new_root);
      //this shouldn't change the root, or fail!
    if ( stat != CUBIT_SUCCESS || new_root != NULL )
    {
      PRINT_ERROR("Insertion into RTree failed.\n");
      return CUBIT_FAILURE;
    }
    return CUBIT_SUCCESS;
  }
  
  stat = myRoot->insert(new_node, new_root);
  if ( stat != CUBIT_SUCCESS )
  {
    PRINT_ERROR("Insertion into RTree failed.\n");
    return CUBIT_FAILURE;
  }
  if ( new_root != NULL )
  {
      //this is fine, it just means we are adding more
      //so the root had to be split...
    myRoot = new_root;
  }
  return CUBIT_SUCCESS;
}

template<class Z>

MY_INLINE CubitStatus RTree< Z >::find	(	const CubitBox &	range_box,
		DLIList< Z > &	range_members
	)		`[virtual]`

Implements AbstractTree< Z >.

Definition at line 111 of file RTree.cpp.

{
    //Find all of the members of the RTree that intersect this range_box.
  if ( myRoot == NULL )
  {
      // Nothing has been added to this Tree yet, so we are not going to find this
      // object in it.
      return CUBIT_SUCCESS;
  }
  CubitStatus stat = recursive_find(myRoot, range_box, range_members);
  if ( stat != CUBIT_SUCCESS )
    return CUBIT_FAILURE;
  else
    return CUBIT_SUCCESS;
}

template<class Z>

MY_INLINE CubitStatus RTree< Z >::find	(	const CubitVector &	ray_origin,
		const CubitVector &	ray_direction,
		DLIList< Z > &	range_members
	)

Definition at line 296 of file RTree.cpp.

{
    //Find all of the members of the RTree that intersect this ray.
  if ( myRoot == NULL )
  {
      // Nothing has been added to this Tree yet, so we are not going to find this
      // object in it.
      return CUBIT_SUCCESS;
  }
  CubitStatus stat = recursive_find(myRoot, ray_origin, ray_direction, range_members);
  if ( stat != CUBIT_SUCCESS )
    return CUBIT_FAILURE;
  else
    return CUBIT_SUCCESS;
}

template<class Z>

double RTree< Z >::get_tol ( ) [inline, virtual]

Implements AbstractTree< Z >.

Definition at line 98 of file RTree.hpp.

    {return myTolerance;}

template<class Z>

MY_INLINE CubitStatus RTree< Z >::k_nearest_neighbor	(	CubitVector &	q,
		int	k,
		double &	closest_dist,
		DLIList< Z > &	nearest_neighbors,
		DistSqFunc	dist_sq_point_data
	)		`[virtual]`

Implements AbstractTree< Z >.

Definition at line 234 of file RTree.cpp.

{
    //first create the priority queue.
  PriorityQueue< RTreeNode<Z>*> near_queue(RTree<Z>::less_than_func);
  
  myRoot->set_dist(0.0);
  near_queue.push(myRoot);
  RTreeNode<Z> *element, *child_element;
  int num_found = 0;
  int ii;
  double data_dist, box_dist;
  Z data;
  
  while( !near_queue.empty() )
  {
    element = near_queue.top();
    near_queue.pop();
    if ( element->is_data() )
    {
      data = element->get_data();
        //calculate the exact distance.
      data_dist = dist_sq_point_data(q, data);
        //compare this distance with the next item's distance.
      if ( element->dist_is_box() && !near_queue.empty() &&
           data_dist > near_queue.top()->get_dist())
      {
          //If its bigger, add it back into the list
          //with the updated distance.
        element->set_dist(data_dist);
        near_queue.push(element);
        element->set_dist_is_box(0);
      }
      else
      {
        nearest_neighbors.append(element->get_data());
        if ( num_found == 0 )
          closest_dist = element->get_dist();
        num_found++;
        if ( num_found == k )
          return CUBIT_SUCCESS;
      }
    }
    else 
    {
      for ( ii = 0; ii < element->num_children(); ii++ )
      {
        child_element = element->get_child(ii);
        CubitBox bounding_box = child_element->bounding_box();
        box_dist = min_dist_sq(q, bounding_box);
        child_element->set_dist(box_dist);
        near_queue.push(child_element);
      }
    }
  }
  return CUBIT_FAILURE;
}

template<class Z>

MY_INLINE bool RTree< Z >::less_than_func	(	RTreeNode< Z > *&	node_a,
		RTreeNode< Z > *&	node_b
	)		`[static]`

Definition at line 224 of file RTree.cpp.

{
  if ( node_a->get_dist() < node_b->get_dist() )
    return true;
  else
    return false;
}

template<class Z >

MY_INLINE double RTree< Z >::min_dist_sq	(	CubitVector &	q,
		CubitBox &	b_box
	)		`[private]`

Definition at line 189 of file RTree.cpp.

{
  CubitVector b_min, b_max;
  b_min = b_box.minimum();
  b_max = b_box.maximum();
  double dist;
  CubitVector r;

  if ( q.x() < b_min.x() )
    r.x(b_min.x());
  else if ( q.x() > b_max.x() )
    r.x(b_max.x());
  else
    r.x(q.x());
  
  if ( q.y() < b_min.y() )
    r.y(b_min.y());
  else if ( q.y() > b_max.y() )
    r.y(b_max.y());
  else
    r.y(q.y());
  
  if ( q.z() < b_min.z() )
    r.z(b_min.z());
  else if ( q.z() > b_max.z() )
    r.z(b_max.z());
  else
    r.z(q.z());
  
  dist = (q-r).length_squared();

  return dist;
}

template<class Z>

MY_INLINE CubitStatus RTree< Z >::recursive_find	(	RTreeNode< Z > *	rect_tree,
		const CubitBox &	range_box,
		DLIList< Z > &	range_members
	)		`[private]`

Definition at line 127 of file RTree.cpp.

{
  CubitBox rect_box = rect_tree->bounding_box();
  if ( !range_box.overlap(myTolerance, rect_box ) )
    return CUBIT_SUCCESS;

    //Now see if this is a data member.  If it is, append the data to the
    //list.
  if (rect_tree->is_data() )
  {
    range_members.append(rect_tree->get_data());
    return CUBIT_SUCCESS;
  }
    //Now if this is anything else we need to keep iterating...
  int loop_size = rect_tree->num_children();
    //We are doing a depth-first search of the tree.  Not
    //all branches will need to be followed since they won't
    //all overlap...
  int ii;
  RTreeNode<Z> *curr_node;
  CubitStatus stat;
  for ( ii = 0; ii < loop_size; ii++ )
  {
    curr_node = rect_tree->get_child(ii);
    if ( curr_node == NULL )
    {
      PRINT_ERROR("Problems finding boxes in range.\n");
      assert(curr_node != NULL);
      return CUBIT_FAILURE;
    }
    stat = recursive_find(curr_node, range_box, range_members);
    if ( stat != CUBIT_SUCCESS )
      return stat;
  }
  
  return CUBIT_SUCCESS;
}

template<class Z>

MY_INLINE CubitStatus RTree< Z >::recursive_find	(	RTreeNode< Z > *	rect_tree,
		const CubitVector &	ray_origin,
		const CubitVector &	ray_direction,
		DLIList< Z > &	range_members
	)		`[private]`

Definition at line 314 of file RTree.cpp.

{
  CubitBox rect_box = rect_tree->bounding_box();
  //if ( !range_box.overlap(myTolerance, rect_box ) )
  if ( !rect_box.intersect(ray_origin, ray_direction) )
    return CUBIT_SUCCESS;

    //Now see if this is a data member.  If it is, append the data to the
    //list.
  if (rect_tree->is_data() )
  {
    range_members.append(rect_tree->get_data());
    return CUBIT_SUCCESS;
  }
    //Now if this is anything else we need to keep iterating...
  int loop_size = rect_tree->num_children();
    //We are doing a depth-first search of the tree.  Not
    //all branches will need to be followed since they won't
    //all overlap...
  int ii;
  RTreeNode<Z> *curr_node;
  CubitStatus stat;
  for ( ii = 0; ii < loop_size; ii++ )
  {
    curr_node = rect_tree->get_child(ii);
    if ( curr_node == NULL )
    {
      PRINT_ERROR("Problems finding boxes in range.\n");
      assert(curr_node != NULL);
      return CUBIT_FAILURE;
    }
    stat = recursive_find(curr_node, ray_origin, ray_direction, range_members);
    if ( stat != CUBIT_SUCCESS )
      return stat;
  }
  
  return CUBIT_SUCCESS;
}

template<class Z>

MY_INLINE CubitBoolean RTree< Z >::remove ( Z data ) [virtual]

Implements AbstractTree< Z >.

Definition at line 166 of file RTree.cpp.

{
  RTreeNode<Z> *new_root = NULL;
  CubitBoolean delete_root = CUBIT_FALSE;
  CubitBoolean return_val = myRoot->remove( data, new_root, delete_root );
  if ( new_root != NULL )
  {
      //Only if we are condensing the tree do we want to delete the root node.
      //There are other reasons the root has changed (rebalance...), in which
      //cases the root is now a child of the new root...
    if ( delete_root )
      delete myRoot;
    myRoot = new_root;
  }
  return return_val;
}

template<class Z>

void RTree< Z >::set_tol ( double tol ) [inline, virtual]

Implements AbstractTree< Z >.

Definition at line 96 of file RTree.hpp.

    {myTolerance = tol;}

template<class Z>

MY_INLINE void RTree< Z >::to_list	(	DLIList< RTreeNode< Z > * > &	member_list,
		RTreeNode< Z > *	top
	)		`[private]`

Definition at line 58 of file RTree.cpp.

{
    //Get the children of the top into the list.
  int ii;
  RTreeNode <Z> *curr_node;
  for ( ii = 0; ii < top->num_children(); ii++ )
  {
    curr_node = top->get_child(ii);
    member_list.append(curr_node);
      //don't go below the bottom level...
    if ( curr_node->get_leaf_level() == 0 )
      continue;
    to_list(member_list, curr_node);
  }
  return;
}

Member Data Documentation

template<class Z>

int RTree< Z >::maxChildren [private]

Definition at line 28 of file RTree.hpp.

template<class Z>

int RTree< Z >::minChildren [private]

Definition at line 29 of file RTree.hpp.

template<class Z>

RTreeNode<Z>* RTree< Z >::myRoot [private]

Definition at line 30 of file RTree.hpp.

template<class Z>

double RTree< Z >::myTolerance [private]

Definition at line 27 of file RTree.hpp.

The documentation for this class was generated from the following files:

Classes

Public Types

Public Member Functions

Static Public Member Functions

Private Member Functions

Private Attributes

Detailed Description

template<class Z> class RTree< Z >

Member Typedef Documentation

Constructor & Destructor Documentation

Member Function Documentation

Member Data Documentation

template<class Z>
class RTree< Z >