octree.cxx 7.65 KB
 Dave Partyka committed Sep 11, 2008 1 2 // Included from octree  3 4 /**\var template< typename T_, int d_, typename A_ > \ * typedef T_ octree::value_type  Dave Partyka committed Sep 11, 2008 5 6 7  *\brief Shorthand for the application-specific datatype. */  8 9 /**\var template< typename T_, int d_, typename A_ > \ * typedef T_* octree::pointer  Dave Partyka committed Sep 11, 2008 10 11 12  *\brief Shorthand for a pointer to application-specific data. */  13 14 /**\var template< typename T_, int d_, typename A_ > \ * typedef T_& octree::reference  Dave Partyka committed Sep 11, 2008 15 16 17  *\brief Shorthand for a reference to application-specific data. */  18 19 /**\var template< typename T_, int d_, typename A_ > \ * typedef const T_* octree::const_pointer  Dave Partyka committed Sep 11, 2008 20 21 22  *\brief Shorthand for a pointer to immutable application-specific data. */  23 24 /**\var template< typename T_, int d_, typename A_ > \ * typedef const T_& octree::const_reference  Dave Partyka committed Sep 11, 2008 25 26 27  *\brief Shorthand for a reference to immutable application-specific data. */  28 29 /**\var template< typename T_, int d_, typename A_ > \ * typedef octree octree::_self_type  Dave Partyka committed Sep 11, 2008 30 31 32  *\brief Shorthand for the datatype of this class. */  33 34 /**\var template< typename T_, int d_, typename A_ > \ * typedef _self_type* octree::_self_pointer  Dave Partyka committed Sep 11, 2008 35 36 37  *\brief Shorthand for a pointer to an object of this class. */  38 39 /**\var template< typename T_, int d_, typename A_ > \ * typedef octree_node* octree::octree_node_pointer  Dave Partyka committed Sep 11, 2008 40 41 42  *\brief Shorthand for a pointer to a node contained by the octree. */  43 44 /**\var template< typename T_, int d_, typename A_ > \ * typedef octree_node& octree::octree_node_reference  Dave Partyka committed Sep 11, 2008 45 46 47  *\brief Shorthand for a reference to a node contained by the octree. */  48 49 /**\var template< typename T_, int d_, typename A_ > \ * typedef const octree_node* octree::const_octree_node_pointer  Dave Partyka committed Sep 11, 2008 50 51 52  *\brief Shorthand for a pointer to an immutable node contained by the octree. */  53 54 /**\var template< typename T_, int d_, typename A_ > \ * typedef const octree_node& octree::const_octree_node_reference  Dave Partyka committed Sep 11, 2008 55 56 57  *\brief Shorthand for a reference to an immutable node contained by the octree. */  58 59 /**\var template< typename T_, int d_, typename A_ > \ * typedef A_ octree::allocator_type  Dave Partyka committed Sep 11, 2008 60 61 62  *\brief Shorthand for an allocator to be used by this class. */  63 64 /**\var template< typename T_, int d_, typename A_ > \ * typedef octree_iterator< T_, T_&, T_*, _self_type, _self_pointer, d_ > octree::iterator  Dave Partyka committed Sep 11, 2008 65 66 67  *\brief Shorthand for an iterator that traverses the nodes contained in the octree. */  68 69 /**\var template< typename T_, int d_, typename A_ > \ * typedef octree_iterator< T_, const T_&, const T_*, _self_type, _self_pointer, d_ > octree::const_iterator  Dave Partyka committed Sep 11, 2008 70 71 72  *\brief Shorthand for an iterator that traverses the nodes contained in the octree in a read-only manner. */  73 74 /**\var template< typename T_, int d_, typename A_ > \ * typedef octree_cursor< T_, T_&, T_*, _self_type, _self_pointer, d_ > octree::cursor  Dave Partyka committed Sep 11, 2008 75 76 77  *\brief Shorthand for a cursor that traverses the nodes contained in the octree. */  78 79 /**\var template< typename T_, int d_, typename A_ > \ * typedef octree_cursor< T_, const T_&, const T_*, _self_type, _self_pointer, d_ > octree::const_cursor  Dave Partyka committed Sep 11, 2008 80 81 82 83 84 85 86 87 88 89 90 91  *\brief Shorthand for a cursor that traverses the nodes contained in the octree in a read-only manner. */ /**\brief Octree constructor (deprecated). * * There is no default constructor because the size of the octree must be fixed at construction time. * If it were not fixed, then someone could change the root node's bounds later and (1) its * children would be inconsistently bounded and/or (2) any application-specific data dependent on the * geometry would be incorrect. * * Because this version does not properly initialize application-specific data at the root node, it is deprecated. *  David Thompson committed Jan 10, 2009 92  * @param[in] x_center An array of coordinates specifying the center of the octree  Dave Partyka committed Sep 11, 2008 93 94  * @param[in] length The length (size) of each side of the octree */  95 template< typename T_, int d_, typename A_ >  David Thompson committed Jan 10, 2009 96 octree::octree( const double* x_center, double length )  Dave Partyka committed Sep 11, 2008 97 {  David Thompson committed Jan 10, 2009 98 99 100  for ( int i = 0; i < d_; ++ i ) this->_M_center[i] = x_center[i]; this->_M_size = length;  David Thompson committed Jun 19, 2009 101  this->_M_root = new octree_node();  Dave Partyka committed Sep 11, 2008 102 103 104 105 106 107 108 109 110 111 112 113 } /**\brief Octree constructor. * * There is no default constructor because the size of the octree must be fixed at construction time. * If it were not fixed, then someone could change the root node's bounds later and (1) its * children would be inconsistently bounded and/or (2) any application-specific data dependent on the * geometry would be incorrect. * * This version takes a reference to application-specific data which is used to properly initialize * the root node's value. This is the preferred constructor. *  David Thompson committed Jan 10, 2009 114  * @param[in] x_center An array of coordinates specifying the center of the octree  Dave Partyka committed Sep 11, 2008 115 116 117  * @param[in] length The length (size) of each side of the octree * @param[in] value Application-specific data to store at the root node */  118 template< typename T_, int d_, typename A_ >  David Thompson committed Jan 10, 2009 119 octree::octree( const double* x_center, double length, const value_type& value )  Dave Partyka committed Sep 11, 2008 120 {  David Thompson committed Jan 10, 2009 121 122 123  for ( int i = 0; i < d_; ++ i ) this->_M_center[i] = x_center[i]; this->_M_size = length;  Kitware Robot committed Jul 26, 2017 124  this->_M_root = new octree_node( nullptr, value );  Dave Partyka committed Sep 11, 2008 125 126 127 128 129 130 } /**\brief Octree destructor. * * Deletes the octree nodes and any application-specific data stored with them. */  131 132 template< typename T_, int d_, typename A_ > octree::~octree()  Dave Partyka committed Sep 11, 2008 133 134 135 136 { delete this->_M_root; }  137 138 /**\fn template< typename T_, int d_, typename A_ > \ * octree_node_pointer octree::root()  Dave Partyka committed Sep 11, 2008 139 140 141 142 143 144 145 146 147 148 149  *\brief Returns the root (top-level) node of the octree. */ /**\brief Return the number of nodes in the octree (or optionally leaf nodes) * * By default, this will return the count of all the nodes in the tree -- not just leaf nodes. * If you set \a only_leaves to true, you will receive a count of just the leaf nodes. * Note that this is not the same as the default for iteration! * *\warning This is not a fast routine; it traverses the entire tree to count nodes. */  150 151 template< typename T_, int d_, typename A_ > size_t octree::size( bool only_leaves )  Dave Partyka committed Sep 11, 2008 152 153 154 155 156 157 158 159 { size_t number = 0; iterator it; for ( it = this->begin( only_leaves ); it != this->end(); ++it ) ++number; return number; }  David Thompson committed Jan 10, 2009 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 /**\fn template< typename T_, int d_, typename A_ > const double* octree::center() const *\brief Retrieve the geometric center of a node. * * Note that this, along with size() provide a way to compute the bounds of the node. * @retval A pointer to an array of _d coordinates. */ /**\fn template< typename T_, int d_, typename A_ > reference octree_node::size() const *\brief Retrieve the size (i.e., the length of any side) of a node. * * Note that this, along with center() provide a way to compute the bounds of the octree. * * \warning Some people refer to the diagonal length as the octree size; this is not how we use size. * If you would like the diagonal length, multiply size() by \f$\sqrt{3}\f$. * * @retval The length of a side of the octree. */  178 179 /**\var template< typename T_, int d_, typename A_ > \ * octree_node_pointer octree::_M_root  Dave Partyka committed Sep 11, 2008 180 181 182  *\brief The root (top-level) node of the octree. */  David Thompson committed Jan 10, 2009 183 184 185 186 187 188 189 190 191 192 /**\var template< typename T_, int d_, typename A_ > \ * double octree::_M_center[d_] *\brief The geometric center point of the octree. */ /**\var template< typename T_, int d_, typename A_ > \ * double octree::_M_size *\brief The geometric length of each side of the hypercube defining the octree. Also called the size of the node. */