34#ifndef OCTOMAP_OCTREE_BASE_IMPL_H
35#define OCTOMAP_OCTREE_BASE_IMPL_H
52 class AbstractOcTreeNode;
74 template <
class NODE,
class INTERFACE>
133 NODE*
getNodeChild(NODE* node,
unsigned int childIdx)
const;
136 const NODE*
getNodeChild(
const NODE* node,
unsigned int childIdx)
const;
186 NODE*
search(
double x,
double y,
double z,
unsigned int depth = 0)
const;
193 NODE*
search(
const point3d& value,
unsigned int depth = 0)
const;
207 bool deleteNode(
double x,
double y,
double z,
unsigned int depth = 0);
232 virtual void prune();
258 virtual void getMetricSize(
double& x,
double& y,
double& z)
const;
260 virtual void getMetricMin(
double& x,
double& y,
double& z);
262 void getMetricMin(
double& x,
double& y,
double& z)
const;
264 virtual void getMetricMax(
double& x,
double& y,
double& z);
266 void getMetricMax(
double& x,
double& y,
double& z)
const;
318 std::istream&
readData(std::istream &s);
322 std::ostream&
writeData(std::ostream &s)
const;
527 void pruneRecurs(NODE* node,
unsigned int depth,
unsigned int max_depth,
unsigned int& num_pruned);
530 void expandRecurs(NODE* node,
unsigned int depth,
unsigned int max_depth);
Bounding-box leaf iterator.
Definition: OcTreeIterator.hxx:335
Iterator to iterate over all leafs of the tree.
Definition: OcTreeIterator.hxx:263
Definition: OcTreeKey.h:139
OcTree base class, to be used with with any kind of OcTreeDataNode.
Definition: OcTreeBaseImpl.h:75
size_t getNumLeafNodesRecurs(const NODE *parent) const
Definition: OcTreeBaseImpl.hxx:1095
NODE * getNodeChild(NODE *node, unsigned int childIdx) const
Definition: OcTreeBaseImpl.hxx:200
std::istream & readData(std::istream &s)
Read all nodes from the input stream (without file header), for this the tree needs to be already cre...
Definition: OcTreeBaseImpl.hxx:801
const unsigned int tree_max_val
Definition: OcTreeBaseImpl.h:546
double max_value[3]
max in x, y, z
Definition: OcTreeBaseImpl.h:556
const leaf_bbx_iterator leaf_iterator_bbx_end
Definition: OcTreeBaseImpl.h:565
key_type coordToKey(double coordinate) const
Converts from a single coordinate into a discrete key.
Definition: OcTreeBaseImpl.h:357
bool coordToKeyChecked(const point3d &coord, OcTreeKey &key) const
Converts a 3D coordinate into a 3D OcTreeKey, with boundary checking.
Definition: OcTreeBaseImpl.hxx:340
virtual void getMetricMax(double &x, double &y, double &z)
maximum value of the bounding box of all known space in x, y, z
Definition: OcTreeBaseImpl.hxx:950
point3d keyToCoord(const OcTreeKey &key) const
converts from an addressing key at the lowest tree level into a coordinate corresponding to the key's...
Definition: OcTreeBaseImpl.h:490
unsigned int getTreeDepth() const
Definition: OcTreeBaseImpl.h:111
virtual void getMetricMin(double &x, double &y, double &z)
minimum value of the bounding box of all known space in x, y, z
Definition: OcTreeBaseImpl.hxx:942
OcTreeKey coordToKey(const point3d &coord, unsigned depth) const
Converts from a 3D coordinate into a 3D addressing key at a given depth.
Definition: OcTreeBaseImpl.h:376
virtual size_t memoryUsage() const
Definition: OcTreeBaseImpl.hxx:1039
void deleteNodeRecurs(NODE *node)
Recursively delete a node and all children. Deallocates memory but does NOT set the node ptr to NULL ...
Definition: OcTreeBaseImpl.hxx:662
bool nodeChildExists(const NODE *node, unsigned int childIdx) const
Safe test if node has a child at index childIdx.
Definition: OcTreeBaseImpl.hxx:235
virtual void prune()
Lossless compression of the octree: A node will replace all of its eight children if they have identi...
Definition: OcTreeBaseImpl.hxx:523
bool deleteNode(double x, double y, double z, unsigned int depth=0)
Delete a node (if exists) given a 3d point.
Definition: OcTreeBaseImpl.hxx:488
void clearKeyRays()
Clear KeyRay vector to minimize unneeded memory.
Definition: OcTreeBaseImpl.h:120
double keyToCoord(key_type key) const
converts from a discrete key at the lowest tree level into a coordinate corresponding to the key's ce...
Definition: OcTreeBaseImpl.h:484
const iterator end() const
Definition: OcTreeBaseImpl.h:329
double keyToCoord(key_type key, unsigned depth) const
converts from a discrete key at a given depth into a coordinate corresponding to the key's center
Definition: OcTreeBaseImpl.hxx:394
virtual void expandNode(NODE *node)
Expands a node (reverse of pruning): All children are created and their occupancy probability is set ...
Definition: OcTreeBaseImpl.hxx:257
void setResolution(double r)
Change the resolution of the octree, scaling all voxels. This will not preserve the (metric) scale!
Definition: OcTreeBaseImpl.hxx:156
const tree_iterator end_tree() const
Definition: OcTreeBaseImpl.h:350
OcTreeBaseImpl(const OcTreeBaseImpl< NODE, INTERFACE > &rhs)
Deep copy constructor.
NODE * getRoot() const
Definition: OcTreeBaseImpl.h:179
const unsigned int tree_depth
Maximum tree depth is fixed to 16 currently.
Definition: OcTreeBaseImpl.h:545
NODE NodeType
Make the templated NODE type available from the outside.
Definition: OcTreeBaseImpl.h:79
void expandRecurs(NODE *node, unsigned int depth, unsigned int max_depth)
recursive call of expand()
Definition: OcTreeBaseImpl.hxx:742
virtual void expand()
Expands all pruned nodes (reverse of prune())
Definition: OcTreeBaseImpl.hxx:536
double resolution
in meters
Definition: OcTreeBaseImpl.h:547
virtual size_t memoryUsageNode() const
Definition: OcTreeBaseImpl.h:247
double getResolution() const
Definition: OcTreeBaseImpl.h:109
size_t calcNumNodes() const
Traverses the tree to calculate the total number of nodes.
Definition: OcTreeBaseImpl.hxx:1016
std::vector< KeyRay > keyrays
data structure for ray casting, array for multithreading
Definition: OcTreeBaseImpl.h:562
const tree_iterator tree_iterator_end
Definition: OcTreeBaseImpl.h:566
const leaf_bbx_iterator end_leafs_bbx() const
Definition: OcTreeBaseImpl.h:345
leaf_bbx_iterator begin_leafs_bbx(const OcTreeKey &min, const OcTreeKey &max, unsigned char maxDepth=0) const
Definition: OcTreeBaseImpl.h:337
std::string getTreeType() const
Definition: OcTreeBaseImpl.h:104
std::ostream & writeData(std::ostream &s) const
Write complete state of tree to stream (without file header) unmodified. Pruning the tree first produ...
Definition: OcTreeBaseImpl.hxx:763
virtual ~OcTreeBaseImpl()
Definition: OcTreeBaseImpl.hxx:68
bool operator==(const OcTreeBaseImpl< NODE, INTERFACE > &rhs) const
Comparison between two octrees, all meta data, all nodes, and the structure must be identical.
Definition: OcTreeBaseImpl.hxx:125
void swapContent(OcTreeBaseImpl< NODE, INTERFACE > &rhs)
Swap contents of two octrees, i.e., only the underlying pointer / tree structure.
Definition: OcTreeBaseImpl.hxx:114
leaf_iterator iterator
Definition: OcTreeBaseImpl.h:324
void deleteNodeChild(NODE *node, unsigned int childIdx)
Deletes the i-th child of the node.
Definition: OcTreeBaseImpl.hxx:189
OcTreeKey coordToKey(double x, double y, double z, unsigned depth) const
Converts from a 3D coordinate into a 3D addressing key at a given depth.
Definition: OcTreeBaseImpl.h:384
iterator begin(unsigned char maxDepth=0) const
Definition: OcTreeBaseImpl.h:327
void pruneRecurs(NODE *node, unsigned int depth, unsigned int max_depth, unsigned int &num_pruned)
recursive call of prune()
Definition: OcTreeBaseImpl.hxx:719
unsigned long long memoryFullGrid() const
Definition: OcTreeBaseImpl.hxx:850
point3d keyToCoord(const OcTreeKey &key, unsigned depth) const
converts from an addressing key at a given depth into a coordinate corresponding to the key's center
Definition: OcTreeBaseImpl.h:496
void clear()
Deletes the complete tree structure.
Definition: OcTreeBaseImpl.hxx:512
NODE * createNodeChild(NODE *node, unsigned int childIdx)
Creates (allocates) the i-th child of the node.
Definition: OcTreeBaseImpl.hxx:173
double volume()
Definition: OcTreeBaseImpl.hxx:1112
tree_iterator begin_tree(unsigned char maxDepth=0) const
Definition: OcTreeBaseImpl.h:348
void calcNumNodesRecurs(NODE *node, size_t &num_nodes) const
Definition: OcTreeBaseImpl.hxx:1026
const leaf_iterator end_leafs() const
Definition: OcTreeBaseImpl.h:334
void getUnknownLeafCenters(point3d_list &node_centers, point3d pmin, point3d pmax, unsigned int depth=0) const
return centers of leafs that do NOT exist (but could) in a given bounding box
Definition: OcTreeBaseImpl.hxx:1046
void init()
initialize non-trivial members, helper for constructors
Definition: OcTreeBaseImpl.hxx:87
point3d tree_center
Definition: OcTreeBaseImpl.h:554
virtual bool pruneNode(NODE *node)
Prunes a node when it is collapsible.
Definition: OcTreeBaseImpl.hxx:267
double resolution_factor
= 1. / resolution
Definition: OcTreeBaseImpl.h:548
bool computeRay(const point3d &origin, const point3d &end, std::vector< point3d > &ray)
Traces a ray from origin to end (excluding), returning the coordinates of all nodes traversed by the ...
Definition: OcTreeBaseImpl.hxx:651
bool nodeHasChildren(const NODE *node) const
Safe test if node has any children.
Definition: OcTreeBaseImpl.hxx:244
virtual size_t size() const
Definition: OcTreeBaseImpl.h:241
virtual bool isNodeCollapsible(const NODE *node) const
A node is collapsible if all children exist, don't have children of their own and have the same occup...
Definition: OcTreeBaseImpl.hxx:214
OcTreeKey coordToKey(double x, double y, double z) const
Converts from a 3D coordinate into a 3D addressing key.
Definition: OcTreeBaseImpl.h:371
bool size_changed
Definition: OcTreeBaseImpl.h:552
OcTreeKey coordToKey(const point3d &coord) const
Converts from a 3D coordinate into a 3D addressing key.
Definition: OcTreeBaseImpl.h:366
std::ostream & writeNodesRecurs(const NODE *, std::ostream &s) const
recursive call of writeData()
Definition: OcTreeBaseImpl.hxx:771
NODE * search(double x, double y, double z, unsigned int depth=0) const
Search node at specified depth given a 3d point (depth=0: search full tree depth).
Definition: OcTreeBaseImpl.hxx:421
size_t tree_size
number of nodes in tree flag to denote whether the octree extent changed (for lazy min/max eval)
Definition: OcTreeBaseImpl.h:550
leaf_iterator begin_leafs(unsigned char maxDepth=0) const
Definition: OcTreeBaseImpl.h:332
size_t getNumLeafNodes() const
Traverses the tree to calculate the total number of leaf nodes.
Definition: OcTreeBaseImpl.hxx:1086
std::istream & readNodesRecurs(NODE *, std::istream &s)
recursive call of readData()
Definition: OcTreeBaseImpl.hxx:824
bool computeRayKeys(const point3d &origin, const point3d &end, KeyRay &ray) const
Traces a ray from origin to end (excluding), returning an OcTreeKey of all nodes traversed by the bea...
Definition: OcTreeBaseImpl.hxx:542
leaf_bbx_iterator begin_leafs_bbx(const point3d &min, const point3d &max, unsigned char maxDepth=0) const
Definition: OcTreeBaseImpl.h:341
double getNodeSize(unsigned depth) const
Definition: OcTreeBaseImpl.h:113
virtual void getMetricSize(double &x, double &y, double &z)
Size of OcTree (all known space) in meters for x, y and z dimension.
Definition: OcTreeBaseImpl.hxx:872
std::vector< double > sizeLookupTable
Definition: OcTreeBaseImpl.h:559
NODE * root
Pointer to the root NODE, NULL for empty tree.
Definition: OcTreeBaseImpl.h:542
double min_value[3]
min in x, y, z contains the size of a voxel at level i (0: root node). tree_depth+1 levels (incl....
Definition: OcTreeBaseImpl.h:557
void allocNodeChildren(NODE *node)
Definition: OcTreeBaseImpl.hxx:286
OcTreeKey adjustKeyAtDepth(const OcTreeKey &key, unsigned int depth) const
Adjusts a 3D key from the lowest level to correspond to a higher depth (by shifting the key values)
Definition: OcTreeBaseImpl.h:399
void calcMinMax()
recalculates min and max in x, y, z. Does nothing when tree size didn't change.
Definition: OcTreeBaseImpl.hxx:900
const leaf_iterator leaf_iterator_end
Definition: OcTreeBaseImpl.h:564
OcTreeBaseImpl(double resolution)
Definition: OcTreeBaseImpl.hxx:46
OcTreeKey is a container class for internal key addressing.
Definition: OcTreeKey.h:70
This class represents a three-dimensional vector.
Definition: Vector3.h:50
Iterator over the complete tree (inner nodes and leafs).
Definition: OcTreeIterator.hxx:207
Namespace the OctoMap library and visualization tools.
uint16_t key_type
Definition: OcTreeKey.h:63
std::list< octomath::Vector3 > point3d_list
Definition: octomap_types.h:54
octomath::Vector3 point3d
Use Vector3 (float precision) as a point3d in octomap.
Definition: octomap_types.h:49