1 #ifndef brip_quadtree_h 2 #define brip_quadtree_h 3 //----------------------------------------------------------------- 4 //: 5 // \file 6 // \author J.L. Mundy March 8, 2008 7 // \brief A quadtree structure for 2-d arrays (not necessarily an image) 8 // 9 // \verbatim 10 // a quadtree node has the structure: 11 // ( node ) 12 // ./ | | \. 13 // q00 q01 q10 q11 (indexed by i, j as qij) 14 // \endverbatim 15 // The quadtree can hold any datatype, not necessarily image data. 16 // 17 // \verbatim 18 // Modifications: 19 // None 20 // \endverbatim 21 //------------------------------------------------------------------ 22 23 #include <iostream> 24 #include <vector> 25 #ifdef _MSC_VER 26 # include <vcl_msvc_warnings.h> 27 #endif 28 #include <vbl/vbl_ref_count.h> 29 #include <brip/brip_quadtree_node_base_sptr.h> 30 31 //: the base class representing the quadtree datastructure - holds no data 32 class brip_quadtree_node_base : public vbl_ref_count 33 { 34 public: brip_quadtree_node_base()35 brip_quadtree_node_base() 36 : iul_(0), jul_(0), ilr_(0), jlr_(0), valid_(false), 37 children_(std::vector<brip_quadtree_node_base_sptr>(4)) {} 38 39 brip_quadtree_node_base(unsigned iul, unsigned jul, 40 unsigned ilr, unsigned jlr, bool valid = false) iul_(iul)41 : iul_(iul), jul_(jul), ilr_(ilr), jlr_(jlr), valid_(valid), 42 children_(std::vector<brip_quadtree_node_base_sptr>(4)) {} 43 44 ~brip_quadtree_node_base() override = default; 45 data_valid()46 bool data_valid() const { return valid_; } 47 48 //: return the child, qij child(unsigned i,unsigned j)49 brip_quadtree_node_base_sptr child(unsigned i, unsigned j) 50 { return children_[2*j+i]; } 51 52 //: set the child, qij set_child(unsigned i,unsigned j,brip_quadtree_node_base_sptr const & child)53 void set_child(unsigned i, unsigned j, 54 brip_quadtree_node_base_sptr const& child) 55 { children_[2*j+i] = child; } 56 57 //: the number of non-null child nodes n_children()58 unsigned n_children() const 59 { unsigned n=0; for (unsigned i=0; i<4; ++i) if (children_[i]) ++n; return n;} 60 61 //: the parent node to *this node parent()62 brip_quadtree_node_base_sptr parent() { return parent_; } 63 64 //: set the parent set_parent(brip_quadtree_node_base_sptr const & parent)65 void set_parent(brip_quadtree_node_base_sptr const& parent) {parent_=parent;} 66 67 //: the region in the array represented by *this node region(unsigned & iul,unsigned & jul,unsigned & ilr,unsigned & jlr)68 void region(unsigned& iul, unsigned& jul, unsigned& ilr, unsigned& jlr) const 69 { iul = iul_; jul = jul_; ilr = ilr_; jlr = jlr_; } 70 71 //: set the region in the array represented by *this node set_region(unsigned iul,unsigned jul,unsigned ilr,unsigned jlr)72 void set_region(unsigned iul, unsigned jul, unsigned ilr, unsigned jlr) 73 { iul_ = iul; jul_ = jul; ilr_ = ilr; jlr_ = jlr;} 74 75 protected: 76 unsigned iul_, jul_; 77 unsigned ilr_, jlr_; 78 bool valid_; // data valid 79 brip_quadtree_node_base_sptr parent_; 80 std::vector<brip_quadtree_node_base_sptr> children_; 81 }; 82 83 //: the templated subclass that holds data values, T, in a quadtree structure 84 template <class T> 85 class brip_quadtree_node : public brip_quadtree_node_base 86 { 87 // PUBLIC INTERFACE----------------------------------------------- 88 89 public: 90 91 // Constructors/Initializers/Destructors-------------------------- brip_quadtree_node()92 brip_quadtree_node() 93 : data_(T(0)) {} 94 brip_quadtree_node(unsigned iul,unsigned jul,unsigned ilr,unsigned jlr)95 brip_quadtree_node(unsigned iul, unsigned jul, unsigned ilr, unsigned jlr) 96 : brip_quadtree_node_base(iul, jul, ilr, jlr, false) {} 97 brip_quadtree_node(unsigned iul,unsigned jul,unsigned ilr,unsigned jlr,T data)98 brip_quadtree_node(unsigned iul, unsigned jul, unsigned ilr, 99 unsigned jlr, T data) 100 : brip_quadtree_node_base(iul, jul, ilr, jlr, true),data_(data){} 101 102 ~brip_quadtree_node() override= default; 103 104 // Data Access---------------------------------------------------- 105 data()106 T data() const { return data_; } 107 108 // Utility Methods 109 110 protected: 111 T data_;// pixel value 112 }; 113 114 template <> 115 class brip_quadtree_node<float> : public brip_quadtree_node_base 116 { 117 public: 118 // Constructors/Initializers/Destructors-------------------------- brip_quadtree_node()119 brip_quadtree_node() 120 : data_(float(0)) {} 121 brip_quadtree_node(unsigned iul,unsigned jul,unsigned ilr,unsigned jlr)122 brip_quadtree_node(unsigned iul, unsigned jul, unsigned ilr, unsigned jlr) 123 : brip_quadtree_node_base(iul, jul, ilr, jlr, false) {} 124 brip_quadtree_node(unsigned iul,unsigned jul,unsigned ilr,unsigned jlr,float data)125 brip_quadtree_node(unsigned iul, unsigned jul, unsigned ilr, 126 unsigned jlr, float data) 127 : brip_quadtree_node_base(iul, jul, ilr, jlr, true), data_(data) {} 128 129 ~brip_quadtree_node() override = default; 130 131 // Data Access---------------------------------------------------- 132 data()133 float data() const { return data_; } 134 135 protected: 136 float data_; // pixel value 137 }; 138 139 #endif // brip_quadtree_h 140