HDK
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Pages
UT_RTree.C File Reference
#include "UT_RTree.h"
#include "UT_Assert.h"
#include <SYS/SYS_Math.h>
#include <SYS/SYS_StaticAssert.h>
#include <iostream>
#include <algorithm>
+ Include dependency graph for UT_RTree.C:

Go to the source code of this file.

Classes

struct  UT_BoxedItemT< T >
 
struct  UT_BoxedItemAxisOrderT< T >
 
class  UT_RNode< MAX_ORDER >
 
class  UT_RTreeResultAppenderIntArray
 
class  UT_RTreeResultAcceptorRawIntIterator
 

Functions

template<typename T >
std::ostream & operator<< (std::ostream &os, const UT_BoxT< T > &b)
 
template<typename T >
std::ostream & operator<< (std::ostream &os, const UT_BoxedItemT< T > &bf)
 
template<typename T >
void computeBoundingBox (UT_BoxT< T > &bounding_box, const UT_BoxT< T > *const begin, const UT_BoxT< T > *const end)
 
template<typename T >
void computeBoundingBox (UT_BoxT< T > &bounding_box, const UT_BoxedItemT< T > *const begin, const UT_BoxedItemT< T > *const end)
 
size_t subtreeDetermineNumNodes (const int MAX_ORDER, const size_t size)
 
template<typename T >
void partitionForSubtrees (UT_BoxedItemT< T > *const begin, UT_BoxedItemT< T > *const end, const UT_BoxedItemAxisOrderT< T > &order, int subtree_size, int num_subtrees)
 
template<int MAX_ORDER, typename T >
UT_RNode< MAX_ORDER > * subtreeCreate (UT_BoxT< T > &bounding_box, UT_BoxT< T > shared_boxes[], UT_BoxedItemT< T > *const begin, UT_BoxedItemT< T > *const end, UT_RNode< MAX_ORDER > *const shared_nodes, UT_RNode< MAX_ORDER > *&shared_nodes_end)
 
template<int MAX_ORDER, typename T >
void subtreeCreateBoxAssignment (UT_BoxT< T > &bounding_box, UT_BoxT< T > *const shared_boxes, const UT_RNode< MAX_ORDER > *const shared_nodes, const UT_RNode< MAX_ORDER > *const node, const UT_BoxT< T > item_boxes[])
 
template<typename QUERY_SHAPE , typename RESULT_ACCEPTOR , int MAX_ORDER, typename T >
void subtreeGetIntersectingItems (RESULT_ACCEPTOR &acceptor, const UT_RNode< MAX_ORDER > *const shared_nodes, const UT_BoxT< T > *const shared_boxes, const UT_RNode< MAX_ORDER > *const node, const QUERY_SHAPE &query_box)
 
template<int MAX_ORDER>
int UTsubtreeComputeMaxDepth (const UT_RNode< MAX_ORDER > shared_nodes[], const UT_RNode< MAX_ORDER > *const node)
 
template<typename QUERY_SHAPE , int MAX_ORDER, typename T >
void UTgetIntersectingItems (UT_IntArray &results, const UT_RTreeGeneric< MAX_ORDER > &tree, const QUERY_SHAPE &query_box, const UT_RTreeBoxAssignmentT< T > &assignment)
 
template<typename QUERY_SHAPE , int MAX_ORDER, typename T >
void UTappendIntersectingItems (UT_IntArray &results, const UT_RTreeGeneric< MAX_ORDER > &tree, const QUERY_SHAPE &query_box, const UT_RTreeBoxAssignmentT< T > &assignment, exint baseindex)
 
template<typename QUERY_SHAPE , int MAX_ORDER, typename T >
intUTgetIntersectingItems (const UT_RTreeGeneric< MAX_ORDER > &tree, const QUERY_SHAPE &query_box, const UT_RTreeBoxAssignmentT< T > &assignment, int *const items_begin)
 

Function Documentation

template<typename T >
void computeBoundingBox ( UT_BoxT< T > &  bounding_box,
const UT_BoxT< T > *const  begin,
const UT_BoxT< T > *const  end 
)
inline

Definition at line 290 of file UT_RTree.C.

template<typename T >
void computeBoundingBox ( UT_BoxT< T > &  bounding_box,
const UT_BoxedItemT< T > *const  begin,
const UT_BoxedItemT< T > *const  end 
)
inline

Definition at line 309 of file UT_RTree.C.

template<typename T >
std::ostream& operator<< ( std::ostream &  os,
const UT_BoxT< T > &  b 
)
inline

Definition at line 225 of file UT_RTree.C.

template<typename T >
std::ostream& operator<< ( std::ostream &  os,
const UT_BoxedItemT< T > &  bf 
)
inline

Definition at line 276 of file UT_RTree.C.

template<typename T >
void partitionForSubtrees ( UT_BoxedItemT< T > *const  begin,
UT_BoxedItemT< T > *const  end,
const UT_BoxedItemAxisOrderT< T > &  order,
int  subtree_size,
int  num_subtrees 
)
inline

Partition the range of boxed items [begin, end) according to the given comparison function such that all items in the range [0, m-1] are less than or equal to all items in [m, 2m-1], which are less than or equal to all items in [2m, 3m-1], etc, where m is the subtree size.

Definition at line 535 of file UT_RTree.C.

template<int MAX_ORDER, typename T >
UT_RNode<MAX_ORDER>* subtreeCreate ( UT_BoxT< T > &  bounding_box,
UT_BoxT< T >  shared_boxes[],
UT_BoxedItemT< T > *const  begin,
UT_BoxedItemT< T > *const  end,
UT_RNode< MAX_ORDER > *const  shared_nodes,
UT_RNode< MAX_ORDER > *&  shared_nodes_end 
)
inline

Definition at line 562 of file UT_RTree.C.

template<int MAX_ORDER, typename T >
void subtreeCreateBoxAssignment ( UT_BoxT< T > &  bounding_box,
UT_BoxT< T > *const  shared_boxes,
const UT_RNode< MAX_ORDER > *const  shared_nodes,
const UT_RNode< MAX_ORDER > *const  node,
const UT_BoxT< T >  item_boxes[] 
)
inline

Definition at line 693 of file UT_RTree.C.

size_t subtreeDetermineNumNodes ( const int  MAX_ORDER,
const size_t  size 
)
inline

Definition at line 479 of file UT_RTree.C.

template<typename QUERY_SHAPE , typename RESULT_ACCEPTOR , int MAX_ORDER, typename T >
void subtreeGetIntersectingItems ( RESULT_ACCEPTOR &  acceptor,
const UT_RNode< MAX_ORDER > *const  shared_nodes,
const UT_BoxT< T > *const  shared_boxes,
const UT_RNode< MAX_ORDER > *const  node,
const QUERY_SHAPE &  query_box 
)
inline

Definition at line 749 of file UT_RTree.C.

template<typename QUERY_SHAPE , int MAX_ORDER, typename T >
void UTappendIntersectingItems ( UT_IntArray results,
const UT_RTreeGeneric< MAX_ORDER > &  tree,
const QUERY_SHAPE &  query_box,
const UT_RTreeBoxAssignmentT< T > &  assignment,
exint  baseindex 
)
inline

Definition at line 994 of file UT_RTree.C.

template<typename QUERY_SHAPE , int MAX_ORDER, typename T >
void UTgetIntersectingItems ( UT_IntArray results,
const UT_RTreeGeneric< MAX_ORDER > &  tree,
const QUERY_SHAPE &  query_box,
const UT_RTreeBoxAssignmentT< T > &  assignment 
)
inline

Definition at line 981 of file UT_RTree.C.

template<typename QUERY_SHAPE , int MAX_ORDER, typename T >
int* UTgetIntersectingItems ( const UT_RTreeGeneric< MAX_ORDER > &  tree,
const QUERY_SHAPE &  query_box,
const UT_RTreeBoxAssignmentT< T > &  assignment,
int *const  items_begin 
)
inline

Definition at line 1036 of file UT_RTree.C.

template<int MAX_ORDER>
int UTsubtreeComputeMaxDepth ( const UT_RNode< MAX_ORDER >  shared_nodes[],
const UT_RNode< MAX_ORDER > *const  node 
)
inline

Definition at line 803 of file UT_RTree.C.