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