octree.cxx 7.65 KB
Newer Older
Dave Partyka's avatar
Dave Partyka committed
1 2
// Included from octree

3 4
/**\var template< typename T_, int d_, typename A_ > \
  *     typedef T_ octree<T_,d_,A_>::value_type
Dave Partyka's avatar
Dave Partyka committed
5 6 7
  *\brief Shorthand for the application-specific datatype.
  */

8 9
/**\var template< typename T_, int d_, typename A_ > \
  *     typedef T_* octree<T_,d_,A_>::pointer
Dave Partyka's avatar
Dave Partyka committed
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<T_,d_,A_>::reference
Dave Partyka's avatar
Dave Partyka committed
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<T_,d_,A_>::const_pointer
Dave Partyka's avatar
Dave Partyka committed
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<T_,d_,A_>::const_reference
Dave Partyka's avatar
Dave Partyka committed
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<T_,d_,A_> octree<T_,d_,A_>::_self_type
Dave Partyka's avatar
Dave Partyka committed
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<T_,d_,A_>::_self_pointer
Dave Partyka's avatar
Dave Partyka committed
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<T_,d_,A_>* octree<T_,d_,A_>::octree_node_pointer
Dave Partyka's avatar
Dave Partyka committed
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<T_,d_,A_>& octree<T_,d_,A_>::octree_node_reference
Dave Partyka's avatar
Dave Partyka committed
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<T_,d_,A_>* octree<T_,d_,A_>::const_octree_node_pointer
Dave Partyka's avatar
Dave Partyka committed
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<T_,d_,A_>& octree<T_,d_,A_>::const_octree_node_reference
Dave Partyka's avatar
Dave Partyka committed
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<T_,d_,A_>::allocator_type
Dave Partyka's avatar
Dave Partyka committed
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<T_,d_,A_>::iterator
Dave Partyka's avatar
Dave Partyka committed
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<T_,d_,A_>::const_iterator
Dave Partyka's avatar
Dave Partyka committed
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<T_,d_,A_>::cursor
Dave Partyka's avatar
Dave Partyka committed
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<T_,d_,A_>::const_cursor
Dave Partyka's avatar
Dave Partyka committed
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.
  *
92
  * @param[in] x_center An array of coordinates specifying the center of the octree
Dave Partyka's avatar
Dave Partyka committed
93 94
  * @param[in] length The length (size) of each side of the octree
  */
95
template< typename T_, int d_, typename A_ >
96
octree<T_,d_,A_>::octree( const double* x_center, double length )
Dave Partyka's avatar
Dave Partyka committed
97
{
98 99 100
  for ( int i = 0; i < d_; ++ i )
    this->_M_center[i] = x_center[i];
  this->_M_size = length;
101
  this->_M_root = new octree_node<T_,d_,A_>();
Dave Partyka's avatar
Dave Partyka committed
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.
  *
114
  * @param[in] x_center An array of coordinates specifying the center of the octree
Dave Partyka's avatar
Dave Partyka committed
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_ >
119
octree<T_,d_,A_>::octree( const double* x_center, double length, const value_type& value )
Dave Partyka's avatar
Dave Partyka committed
120
{
121 122 123
  for ( int i = 0; i < d_; ++ i )
    this->_M_center[i] = x_center[i];
  this->_M_size = length;
124
  this->_M_root = new octree_node<T_,d_,A_>( nullptr, value );
Dave Partyka's avatar
Dave Partyka committed
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<T_,d_,A_>::~octree()
Dave Partyka's avatar
Dave Partyka committed
133 134 135 136
{
  delete this->_M_root;
}

137 138
/**\fn template< typename T_, int d_, typename A_ > \
  *    octree_node_pointer octree<T_,d_,A_>::root()
Dave Partyka's avatar
Dave Partyka committed
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<T_,d_,A_>::size( bool only_leaves )
Dave Partyka's avatar
Dave Partyka committed
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;
}

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<T_,d_,A_>::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<T_,d_,A_>::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 <b>not</b> 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<T_,d_,A_>::_M_root
Dave Partyka's avatar
Dave Partyka committed
180 181 182
  *\brief The root (top-level) node of the octree.
  */

183 184 185 186 187 188 189 190 191 192
/**\var template< typename T_, int d_, typename A_ > \
  *     double octree<T_,d_,A_>::_M_center[d_]
  *\brief The geometric center point of the octree.
  */

/**\var template< typename T_, int d_, typename A_ > \
  *     double octree<T_,d_,A_>::_M_size
  *\brief The geometric length of each side of the hypercube defining the octree. Also called the size of the node.
  */