CountingOcTree.cpp
Go to the documentation of this file.
1 /*
2  * OctoMap - An Efficient Probabilistic 3D Mapping Framework Based on Octrees
3  * http://octomap.github.com/
4  *
5  * Copyright (c) 2009-2013, K.M. Wurm and A. Hornung, University of Freiburg
6  * All rights reserved.
7  * License: New BSD
8  *
9  * Redistribution and use in source and binary forms, with or without
10  * modification, are permitted provided that the following conditions are met:
11  *
12  * * Redistributions of source code must retain the above copyright
13  * notice, this list of conditions and the following disclaimer.
14  * * Redistributions in binary form must reproduce the above copyright
15  * notice, this list of conditions and the following disclaimer in the
16  * documentation and/or other materials provided with the distribution.
17  * * Neither the name of the University of Freiburg nor the names of its
18  * contributors may be used to endorse or promote products derived from
19  * this software without specific prior written permission.
20  *
21  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
22  * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
23  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
24  * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE
25  * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
26  * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
27  * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
28  * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
29  * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
30  * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
31  * POSSIBILITY OF SUCH DAMAGE.
32  */
33 
34 #include <cassert>
35 #include <octomap/CountingOcTree.h>
36 
37 namespace octomap {
38 
39 
41 
43  : OcTreeDataNode<unsigned int>(0)
44  {
45  }
46 
48 
49  }
50 
52  assert(!hasChildren());
53 
54  // divide "counts" evenly to children
55  unsigned int childCount = (unsigned int)(value/ 8.0 +0.5);
56  for (unsigned int k=0; k<8; k++) {
57  createChild(k);
58  children[k]->setValue(childCount);
59  }
60  }
61 
62  bool CountingOcTreeNode::createChild(unsigned int i) {
63  if (children == NULL) {
64  allocChildren();
65  }
66  assert (children[i] == NULL);
67  children[i] = new CountingOcTreeNode();
68  return true;
69  }
70 
71 
73  CountingOcTree::CountingOcTree(double resolution)
74  : OcTreeBase<CountingOcTreeNode>(resolution) {
76  }
77 
79 
80  OcTreeKey key;
81  if (!coordToKeyChecked(value, key)) return NULL;
82  return updateNode(key);
83  }
84 
85 
86  // Note: do not inline this method, will decrease speed (KMW)
88 
89  CountingOcTreeNode* curNode (root);
90  curNode->increaseCount();
91 
92 
93  // follow or construct nodes down to last level...
94  for (int i=(tree_depth-1); i>=0; i--) {
95 
96  unsigned int pos = computeChildIdx(k, i);
97 
98  // requested node does not exist
99  if (!curNode->childExists(pos)) {
100  curNode->createChild(pos);
101  tree_size++;
102  }
103  // descent tree
104  curNode = static_cast<CountingOcTreeNode*> (curNode->getChild(pos));
105  curNode->increaseCount(); // modify traversed nodes
106  }
107 
108  return curNode;
109  }
110 
111 
112  void CountingOcTree::getCentersMinHits(point3d_list& node_centers, unsigned int min_hits) const {
113 
114  OcTreeKey root_key;
115  root_key[0] = root_key[1] = root_key[2] = this->tree_max_val;
116  getCentersMinHitsRecurs(node_centers, min_hits, this->tree_depth, this->root, 0, root_key);
117  }
118 
119 
121  unsigned int& min_hits,
122  unsigned int max_depth,
123  CountingOcTreeNode* node, unsigned int depth,
124  const OcTreeKey& parent_key) const {
125 
126  if (depth < max_depth && node->hasChildren()) {
127 
128  unsigned short int center_offset_key = this->tree_max_val >> (depth + 1);
129  OcTreeKey search_key;
130 
131  for (unsigned int i=0; i<8; ++i) {
132  if (node->childExists(i)) {
133  computeChildKey(i, center_offset_key, parent_key, search_key);
134  getCentersMinHitsRecurs(node_centers, min_hits, max_depth, node->getChild(i), depth+1, search_key);
135  }
136  }
137  }
138 
139  else { // max level reached
140 
141  if (node->getCount() >= min_hits) {
142  node_centers.push_back(this->keyToCoord(parent_key, depth));
143  }
144  }
145  }
146 
148 
149 
150 } // namespace
unsigned int value
stored data (payload)
unsigned char computeChildIdx(const OcTreeKey &key, int depth)
generate child index (between 0 and 7) from key at given tree depth
Definition: OcTreeKey.h:184
const unsigned int tree_depth
Maximum tree depth is fixed to 16 currently.
void setValue(T v)
sets value to be stored in the node
void computeChildKey(const unsigned int &pos, const unsigned short int &center_offset_key, const OcTreeKey &parent_key, OcTreeKey &child_key)
Definition: OcTreeKey.h:170
bool childExists(unsigned int i) const
bool coordToKeyChecked(const point3d &coord, OcTreeKey &key) const
CountingOcTreeNode * getChild(unsigned int i)
double keyToCoord(unsigned short int key, unsigned depth) const
CountingOcTree(double resolution)
Default constructor, sets resolution of leafs.
OcTreeDataNode< unsigned int > ** children
pointer to array of children, may be NULL
void getCentersMinHits(point3d_list &node_centers, unsigned int min_hits) const
void getCentersMinHitsRecurs(point3d_list &node_centers, unsigned int &min_hits, unsigned int max_depth, CountingOcTreeNode *node, unsigned int depth, const OcTreeKey &parent_key) const
static StaticMemberInitializer countingOcTreeMemberInit
static member to ensure static initialization (only once)
bool createChild(unsigned int i)
std::list< octomath::Vector3 > point3d_list
Definition: octomap_types.h:53
This class represents a three-dimensional vector.
Definition: Vector3.h:50
CountingOcTreeNode()
implementation of CountingOcTreeNode -------------------------------—
virtual CountingOcTreeNode * updateNode(const point3d &value)
CountingOcTreeNode * root
Pointer to the root NODE, NULL for empty tree.
unsigned int getCount() const


octomap
Author(s): Kai M. Wurm , Armin Hornung
autogenerated on Mon Jun 10 2019 14:00:13