Point Cloud Library (PCL) 1.12.0
Loading...
Searching...
No Matches
octree_iterator.h
1/*
2 * Software License Agreement (BSD License)
3 *
4 * Point Cloud Library (PCL) - www.pointclouds.org
5 * Copyright (c) 2010-2012, Willow Garage, Inc.
6 * Copyright (c) 2017-, Open Perception, Inc.
7 *
8 * All rights reserved.
9 *
10 * Redistribution and use in source and binary forms, with or without
11 * modification, are permitted provided that the following conditions
12 * are met:
13 *
14 * * Redistributions of source code must retain the above copyright
15 * notice, this list of conditions and the following disclaimer.
16 * * Redistributions in binary form must reproduce the above
17 * copyright notice, this list of conditions and the following
18 * disclaimer in the documentation and/or other materials provided
19 * with the distribution.
20 * * Neither the name of Willow Garage, Inc. nor the names of its
21 * contributors may be used to endorse or promote products derived
22 * from this software without specific prior written permission.
23 *
24 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
25 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
26 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
27 * FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE
28 * COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
29 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING,
30 * BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
31 * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
32 * CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
33 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN
34 * ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
35 * POSSIBILITY OF SUCH DAMAGE.
36 *
37 * $Id$
38 */
39
40#pragma once
41
42#include <pcl/octree/octree_key.h>
43#include <pcl/octree/octree_nodes.h>
44
45#include <cstddef>
46#include <deque>
47#include <iterator>
48#include <vector>
49
50// Ignore warnings in the above headers
51#ifdef __GNUC__
52#pragma GCC system_header
53#endif
54
55namespace pcl {
56namespace octree {
57
58// Octree iterator state pushed on stack/list
64
65/** \brief @b Abstract octree iterator class
66 * \note Octree iterator base class
67 * \ingroup octree
68 * \author Julius Kammerl (julius@kammerl.de)
69 */
70template <typename OctreeT>
71class OctreeIteratorBase : public std::iterator<std::forward_iterator_tag,
72 const OctreeNode,
73 void,
74 const OctreeNode*,
75 const OctreeNode&> {
76public:
77 using LeafNode = typename OctreeT::LeafNode;
78 using BranchNode = typename OctreeT::BranchNode;
79
80 using LeafContainer = typename OctreeT::LeafContainer;
81 using BranchContainer = typename OctreeT::BranchContainer;
82
83 /** \brief Empty constructor.
84 */
86
87 /** \brief Constructor.
88 * \param[in] max_depth_arg Depth limitation during traversal
89 */
95
96 /** \brief Constructor.
97 * \param[in] octree_arg Octree to be iterated. Initially the iterator is set to its
98 * root node.
99 * \param[in] max_depth_arg Depth limitation during traversal
100 */
102
103 /** \brief Constructor.
104 * \param[in] octree_arg Octree to be iterated. Initially the iterator is set to its
105 * root node.
106 * \param[in] max_depth_arg Depth limitation during traversal
107 */
113
114 /** \brief Constructor.
115 * \param[in] octree_arg Octree to be iterated. Initially the iterator is set to its
116 * root node.
117 * \param[in] max_depth_arg Depth limitation during traversal
118 * \param[in] current_state A pointer to the current iterator state
119 *
120 * \warning For advanced users only.
121 */
127
128 /** \brief Empty deconstructor. */
130
131 /** \brief Equal comparison operator
132 * \param[in] other OctreeIteratorBase to compare with
133 */
134 bool
136 {
137 if (this == &other) // same object
138 return true;
139 if (octree_ != other.octree_) // refer to different octrees
140 return false;
141 if (!current_state_ && !other.current_state_) // both are end iterators
142 return true;
143 if (max_octree_depth_ == other.max_octree_depth_ && current_state_ &&
144 other.current_state_ && // null dereference protection
145 current_state_->key_ == other.current_state_->key_)
146 return true;
147 return false;
148 }
149
150 /** \brief Inequal comparison operator
151 * \param[in] other OctreeIteratorBase to compare with
152 */
153 bool
155 {
156 return !operator==(other);
157 }
158
159 /** \brief Reset iterator */
160 inline void
162 {
163 current_state_ = 0;
164 if (octree_ && (!max_octree_depth_)) {
165 max_octree_depth_ = octree_->getTreeDepth();
166 }
167 }
168
169 /** \brief Get octree key for the current iterator octree node
170 * \return octree key of current node
171 */
172 inline const OctreeKey&
174 {
175 assert(octree_ != 0);
177
178 return (current_state_->key_);
179 }
180
181 /** \brief Get the current depth level of octree
182 * \return depth level
183 */
184 inline uindex_t
186 {
187 assert(octree_ != 0);
189
190 return (current_state_->depth_);
191 }
192
193 /** \brief Get the current octree node
194 * \return pointer to current octree node
195 */
196 inline OctreeNode*
198 {
199 assert(octree_ != 0);
201
202 return (current_state_->node_);
203 }
204
205 /** \brief check if current node is a branch node
206 * \return true if current node is a branch node, false otherwise
207 */
208 inline bool
210 {
211 assert(octree_ != 0);
213
215 }
216
217 /** \brief check if current node is a branch node
218 * \return true if current node is a branch node, false otherwise
219 */
220 inline bool
222 {
223 assert(octree_ != 0);
225
227 }
228
229 /** \brief *operator.
230 * \return pointer to the current octree node
231 */
232 inline OctreeNode*
233 operator*() const
234 { // return designated object
235 if (octree_ && current_state_) {
236 return (current_state_->node_);
237 }
238 else {
239 return 0;
240 }
241 }
242
243 /** \brief Get bit pattern of children configuration of current node
244 * \return bit pattern (byte) describing the existence of 8 children of the current
245 * node
246 */
247 inline char
249 {
250 char ret = 0;
251
252 assert(octree_ != 0);
254
255 if (isBranchNode()) {
256
257 // current node is a branch node
259 static_cast<const BranchNode*>(current_state_->node_);
260
261 // get child configuration bit pattern
262 ret = octree_->getBranchBitPattern(*current_branch);
263 }
264
265 return (ret);
266 }
267
268 /** \brief Method for retrieving a single leaf container from the octree leaf node
269 * \return Reference to container class of leaf node.
270 */
271 const LeafContainer&
273 {
274 assert(octree_ != 0);
276 assert(this->isLeafNode());
277
279
280 return leaf_node->getContainer();
281 }
282
283 /** \brief Method for retrieving a single leaf container from the octree leaf node
284 * \return Reference to container class of leaf node.
285 */
288 {
289 assert(octree_ != 0);
291 assert(this->isLeafNode());
292
294
295 return leaf_node->getContainer();
296 }
297
298 /** \brief Method for retrieving the container from an octree branch node
299 * \return BranchContainer.
300 */
301 const BranchContainer&
303 {
304 assert(octree_ != 0);
306 assert(this->isBranchNode());
307
309
310 return branch_node->getContainer();
311 }
312
313 /** \brief Method for retrieving the container from an octree branch node
314 * \return BranchContainer.
315 */
318 {
319 assert(octree_ != 0);
321 assert(this->isBranchNode());
322
324
325 return branch_node->getContainer();
326 }
327
328 /** \brief get a integer identifier for current node (note: identifier depends on tree
329 * depth). \return node id.
330 */
331 virtual unsigned long
332 getNodeID() const
333 {
334 unsigned long id = 0;
335
336 assert(octree_ != 0);
338
339 if (current_state_) {
340 const OctreeKey& key = getCurrentOctreeKey();
341 // calculate integer id with respect to octree key
342 uindex_t depth = octree_->getTreeDepth();
343 id = static_cast<unsigned long>(key.x) << (depth * 2) |
344 static_cast<unsigned long>(key.y) << (depth * 1) |
345 static_cast<unsigned long>(key.z) << (depth * 0);
346 }
347
348 return id;
349 }
350
351protected:
352 /** \brief Reference to octree class. */
353 OctreeT* octree_;
354
355 /** \brief Pointer to current iterator state. */
357
358 /** \brief Maximum octree depth */
360};
361
362//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
363/** \brief @b Octree iterator class
364 * \note This class implements a forward iterator for traversing octrees in a
365 * depth-first manner.
366 * \ingroup octree
367 * \author Julius Kammerl (julius@kammerl.de)
368 */
369template <typename OctreeT>
371
372public:
375
376 /** \brief Empty constructor.
377 * \param[in] max_depth_arg Depth limitation during traversal
378 */
380
381 /** \brief Constructor.
382 * \param[in] octree_arg Octree to be iterated. Initially the iterator is set to its
383 * root node.
384 * \param[in] max_depth_arg Depth limitation during traversal
385 */
387
388 /** \brief Constructor.
389 * \param[in] octree_arg Octree to be iterated. Initially the iterator is set to its
390 * root node.
391 * \param[in] max_depth_arg Depth limitation during traversal
392 * \param[in] current_state A pointer to the current iterator state
393 *
394 * \warning For advanced users only.
395 */
397 OctreeT* octree_arg,
400 const std::vector<IteratorState>& stack = std::vector<IteratorState>())
402 {}
403
404 /** \brief Copy Constructor.
405 * \param[in] other Another OctreeDepthFirstIterator to copy from
406 */
412
413 /** \brief Copy assignment
414 * \param[in] src the iterator to copy into this
415 */
418 {
419
421
422 stack_ = src.stack_;
423
424 if (stack_.size()) {
425 this->current_state_ = &stack_.back();
426 }
427 else {
428 this->current_state_ = 0;
429 }
430
431 return (*this);
432 }
433
434 /** \brief Reset the iterator to the root node of the octree
435 */
436 virtual void
437 reset();
438
439 /** \brief Preincrement operator.
440 * \note recursively step to next octree node
441 */
443 operator++();
444
445 /** \brief postincrement operator.
446 * \note recursively step to next octree node
447 */
450 {
452 ++*this;
453 return (_Tmp);
454 }
455
456 /** \brief Skip all child voxels of current node and return to parent node.
457 */
458 void
460
461protected:
462 /** Stack structure. */
463 std::vector<IteratorState> stack_;
464};
465
466//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
467/** \brief @b Octree iterator class
468 * \note This class implements a forward iterator for traversing octrees in a
469 * breadth-first manner.
470 * \ingroup octree
471 * \author Julius Kammerl (julius@kammerl.de)
472 */
473template <typename OctreeT>
475public:
476 // public typedefs
479
480 /** \brief Empty constructor.
481 * \param[in] max_depth_arg Depth limitation during traversal
482 */
484
485 /** \brief Constructor.
486 * \param[in] octree_arg Octree to be iterated. Initially the iterator is set to its
487 * root node.
488 * \param[in] max_depth_arg Depth limitation during traversal
489 */
491
492 /** \brief Constructor.
493 * \param[in] octree_arg Octree to be iterated. Initially the iterator is set to its
494 * root node.
495 * \param[in] max_depth_arg Depth limitation during traversal
496 * \param[in] current_state A pointer to the current iterator state
497 *
498 * \warning For advanced users only.
499 */
501 OctreeT* octree_arg,
504 const std::deque<IteratorState>& fifo = std::deque<IteratorState>())
506 {}
507
508 /** \brief Copy Constructor.
509 * \param[in] other Another OctreeBreadthFirstIterator to copy from
510 */
516
517 /** \brief Copy operator.
518 * \param[in] src the iterator to copy into this
519 */
522 {
523
525
526 FIFO_ = src.FIFO_;
527
528 if (FIFO_.size()) {
529 this->current_state_ = &FIFO_.front();
530 }
531 else {
532 this->current_state_ = 0;
533 }
534
535 return (*this);
536 }
537
538 /** \brief Reset the iterator to the root node of the octree
539 */
540 void
541 reset();
542
543 /** \brief Preincrement operator.
544 * \note step to next octree node
545 */
547 operator++();
548
549 /** \brief postincrement operator.
550 * \note step to next octree node
551 */
554 {
556 ++*this;
557 return (_Tmp);
558 }
559
560protected:
561 /** FIFO list */
562 std::deque<IteratorState> FIFO_;
563};
564
565//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
566/** \brief @b Octree iterator class
567 * \note Iterator over all existing nodes at a given depth. It walks across an octree
568 * in a breadth-first manner.
569 * \ingroup octree
570 * \author Fabien Rozar (fabien.rozar@gmail.com)
571 */
572template <typename OctreeT>
574public:
575 // public typedefs
578
579 /** \brief Empty constructor.
580 */
582
583 /** \brief Constructor.
584 * \param[in] octree_arg Octree to be iterated. Initially the iterator is set to its
585 * root node.
586 * \param[in] fixed_depth_arg Depth level during traversal
587 */
589
590 /** \brief Constructor.
591 * \param[in] octree_arg Octree to be iterated. Initially the iterator is set to its
592 * root node.
593 * \param[in] fixed_depth_arg Depth level during traversal
594 * \param[in] current_state A pointer to the current iterator state
595 * \param[in] fifo Internal container of octree node to go through
596 *
597 * \warning For advanced users only.
598 */
600 OctreeT* octree_arg,
603 const std::deque<IteratorState>& fifo = std::deque<IteratorState>())
607 {}
608
609 /** \brief Copy Constructor.
610 * \param[in] other Another OctreeFixedDepthIterator to copy from
611 */
617
618 /** \brief Copy assignment.
619 * \param[in] src the iterator to copy into this
620 * \return pointer to the current octree node
621 */
630
631 /** \brief Reset the iterator to the first node at the depth given as parameter
632 * \param[in] fixed_depth_arg Depth level during traversal
633 */
634 void
636
637 /** \brief Reset the iterator to the first node at the current depth
638 */
639 void
641 {
642 this->reset(fixed_depth_);
643 }
644
645protected:
647
648 /** \brief Given level of the node to be iterated */
650};
651
652//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
653/** \brief Octree leaf node iterator class
654 * \note This class implements a forward iterator for traversing the leaf nodes of an
655 * octree data structure.
656 * \ingroup octree
657 * \author Julius Kammerl (julius@kammerl.de)
658 */
659//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
660template <typename OctreeT>
662 using BranchNode = typename OctreeDepthFirstIterator<OctreeT>::BranchNode;
663 using LeafNode = typename OctreeDepthFirstIterator<OctreeT>::LeafNode;
664
665public:
666 /** \brief Empty constructor.
667 * \param[in] max_depth_arg Depth limitation during traversal
668 */
674
675 /** \brief Constructor.
676 * \param[in] octree_arg Octree to be iterated. Initially the iterator is set to its
677 * root node.
678 * \param[in] max_depth_arg Depth limitation during traversal
679 */
686
687 /** \brief Constructor.
688 * \param[in] octree_arg Octree to be iterated. Initially the iterator is set to its
689 * root node.
690 * \param[in] max_depth_arg Depth limitation during traversal
691 * \param[in] current_state A pointer to the current iterator state
692 *
693 * \warning For advanced users only.
694 */
696 OctreeT* octree_arg,
699 const std::vector<IteratorState>& stack = std::vector<IteratorState>())
701 {}
702
703 /** \brief Reset the iterator to the root node of the octree
704 */
705 inline void
711
712 /** \brief Preincrement operator.
713 * \note recursively step to next octree leaf node
714 */
717 {
718 do {
720 } while ((this->current_state_) &&
722
723 return (*this);
724 }
725
726 /** \brief postincrement operator.
727 * \note step to next octree node
728 */
731 {
733 ++*this;
734 return (_Tmp);
735 }
736
737 /** \brief *operator.
738 * \return pointer to the current octree leaf node
739 */
741 operator*() const
742 {
743 // return designated object
744 OctreeNode* ret = 0;
745
746 if (this->current_state_ &&
748 ret = this->current_state_->node_;
749 return (ret);
750 }
751};
752
753//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
754/** \brief Octree leaf node iterator class
755 * \note This class implements a forward iterator for traversing the leaf nodes of an
756 * octree data structure in the breadth first way.
757 * \ingroup octree
758 * \author Fabien Rozar
759 * (fabien.rozar@gmail.com)
760 */
761//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
762template <typename OctreeT>
764 using BranchNode = typename OctreeBreadthFirstIterator<OctreeT>::BranchNode;
765 using LeafNode = typename OctreeBreadthFirstIterator<OctreeT>::LeafNode;
766
767public:
768 /** \brief Empty constructor.
769 * \param[in] max_depth_arg Depth limitation during traversal
770 */
772
773 /** \brief Constructor.
774 * \param[in] octree_arg Octree to be iterated. Initially the iterator is set to its
775 * root node.
776 * \param[in] max_depth_arg Depth limitation during traversal
777 */
780
781 /** \brief Copy constructor.
782 * \param[in] octree_arg Octree to be iterated. Initially the iterator is set to its
783 * root node.
784 * \param[in] max_depth_arg Depth limitation during traversal
785 * \param[in] current_state A pointer to the current iterator state
786 * \param[in] fifo Internal container of octree node to go through
787 *
788 * \warning For advanced users only.
789 */
791 OctreeT* octree_arg,
794 const std::deque<IteratorState>& fifo = std::deque<IteratorState>());
795
796 /** \brief Reset the iterator to the first leaf in the breadth first way.
797 */
798 inline void
799 reset();
800
801 /** \brief Preincrement operator.
802 * \note recursively step to next octree leaf node
803 */
805 operator++();
806
807 /** \brief Postincrement operator.
808 * \note step to next octree node
809 */
811 operator++(int);
812};
813
814} // namespace octree
815} // namespace pcl
816
817/*
818 * Note: Since octree iterators depend on octrees, don't precompile them.
819 */
820#include <pcl/octree/impl/octree_iterator.hpp>
Iterator class for point clouds with or without given indices.
typename OctreeIteratorBase< OctreeT >::LeafNode LeafNode
OctreeBreadthFirstIterator & operator=(const OctreeBreadthFirstIterator &src)
Copy operator.
OctreeBreadthFirstIterator(const OctreeBreadthFirstIterator &other)
Copy Constructor.
OctreeBreadthFirstIterator & operator++()
Preincrement operator.
OctreeBreadthFirstIterator(OctreeT *octree_arg, uindex_t max_depth_arg, IteratorState *current_state, const std::deque< IteratorState > &fifo=std::deque< IteratorState >())
Constructor.
void reset()
Reset the iterator to the root node of the octree.
OctreeBreadthFirstIterator(uindex_t max_depth_arg=0)
Empty constructor.
std::deque< IteratorState > FIFO_
FIFO list.
OctreeBreadthFirstIterator operator++(int)
postincrement operator.
typename OctreeIteratorBase< OctreeT >::BranchNode BranchNode
OctreeDepthFirstIterator & operator=(const OctreeDepthFirstIterator &src)
Copy assignment.
typename OctreeIteratorBase< OctreeT >::BranchNode BranchNode
typename OctreeIteratorBase< OctreeT >::LeafNode LeafNode
OctreeDepthFirstIterator(const OctreeDepthFirstIterator &other)
Copy Constructor.
std::vector< IteratorState > stack_
Stack structure.
void skipChildVoxels()
Skip all child voxels of current node and return to parent node.
OctreeDepthFirstIterator & operator++()
Preincrement operator.
OctreeDepthFirstIterator operator++(int)
postincrement operator.
OctreeDepthFirstIterator(OctreeT *octree_arg, uindex_t max_depth_arg, IteratorState *current_state, const std::vector< IteratorState > &stack=std::vector< IteratorState >())
Constructor.
virtual void reset()
Reset the iterator to the root node of the octree.
OctreeDepthFirstIterator(uindex_t max_depth_arg=0)
Empty constructor.
OctreeFixedDepthIterator(OctreeT *octree_arg, uindex_t fixed_depth_arg, IteratorState *current_state, const std::deque< IteratorState > &fifo=std::deque< IteratorState >())
Constructor.
void reset()
Reset the iterator to the first node at the current depth.
OctreeFixedDepthIterator(const OctreeFixedDepthIterator &other)
Copy Constructor.
OctreeFixedDepthIterator & operator=(const OctreeFixedDepthIterator &src)
Copy assignment.
uindex_t fixed_depth_
Given level of the node to be iterated.
Abstract octree iterator class
char getNodeConfiguration() const
Get bit pattern of children configuration of current node.
const LeafContainer & getLeafContainer() const
Method for retrieving a single leaf container from the octree leaf node.
const OctreeKey & getCurrentOctreeKey() const
Get octree key for the current iterator octree node.
OctreeIteratorBase(uindex_t max_depth_arg)
Constructor.
OctreeNode * operator*() const
*operator.
OctreeT * octree_
Reference to octree class.
typename OctreeT::BranchNode BranchNode
BranchContainer & getBranchContainer()
Method for retrieving the container from an octree branch node.
OctreeIteratorBase(OctreeT *octree_arg, uindex_t max_depth_arg, IteratorState *current_state)
Constructor.
uindex_t max_octree_depth_
Maximum octree depth.
uindex_t getCurrentOctreeDepth() const
Get the current depth level of octree.
OctreeIteratorBase()
Empty constructor.
OctreeIteratorBase(OctreeT *octree_arg, uindex_t max_depth_arg)
Constructor.
virtual ~OctreeIteratorBase()
Empty deconstructor.
bool isBranchNode() const
check if current node is a branch node
OctreeIteratorBase(OctreeT *octree_arg)
Constructor.
virtual unsigned long getNodeID() const
get a integer identifier for current node (note: identifier depends on tree depth).
const BranchContainer & getBranchContainer() const
Method for retrieving the container from an octree branch node.
typename OctreeT::LeafNode LeafNode
LeafContainer & getLeafContainer()
Method for retrieving a single leaf container from the octree leaf node.
bool operator==(const OctreeIteratorBase &other) const
Equal comparison operator.
bool operator!=(const OctreeIteratorBase &other) const
Inequal comparison operator.
OctreeNode * getCurrentOctreeNode() const
Get the current octree node.
typename OctreeT::BranchContainer BranchContainer
IteratorState * current_state_
Pointer to current iterator state.
typename OctreeT::LeafContainer LeafContainer
bool isLeafNode() const
check if current node is a branch node
Octree key class
Definition octree_key.h:52
OctreeLeafNodeBreadthFirstIterator(uindex_t max_depth_arg=0)
Empty constructor.
void reset()
Reset the iterator to the first leaf in the breadth first way.
OctreeLeafNodeBreadthFirstIterator & operator++()
Preincrement operator.
OctreeLeafNodeDepthFirstIterator(OctreeT *octree_arg, uindex_t max_depth_arg, IteratorState *current_state, const std::vector< IteratorState > &stack=std::vector< IteratorState >())
Constructor.
OctreeLeafNodeDepthFirstIterator operator++(int)
postincrement operator.
OctreeLeafNodeDepthFirstIterator & operator++()
Preincrement operator.
OctreeLeafNodeDepthFirstIterator(OctreeT *octree_arg, uindex_t max_depth_arg=0)
Constructor.
void reset()
Reset the iterator to the root node of the octree.
OctreeLeafNodeDepthFirstIterator(uindex_t max_depth_arg=0)
Empty constructor.
Abstract octree node class
virtual node_type_t getNodeType() const =0
Pure virtual method for receiving the type of octree node (branch or leaf)
detail::int_type_t< detail::index_type_size, false > uindex_t
Type used for an unsigned index in PCL.
Definition types.h:120