00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023
00024 #ifndef QUAD_TREE_HPP
00025 #define QUAD_TREE_HPP
00026
00027 #include <mapnik/envelope.hpp>
00028
00029 #include <boost/ptr_container/ptr_vector.hpp>
00030 #include <boost/noncopyable.hpp>
00031
00032 #include <vector>
00033 #include <cstring>
00034
00035 namespace mapnik
00036 {
00037 template <typename T>
00038 class quad_tree : boost::noncopyable
00039 {
00040 struct node
00041 {
00042 typedef T value_t;
00043 typedef std::vector<T> cont_t;
00044 typedef typename cont_t::iterator iterator;
00045 typedef typename cont_t::const_iterator const_iterator;
00046 Envelope<double> extent_;
00047 cont_t cont_;
00048 node * children_[4];
00049
00050 explicit node(Envelope<double> const& ext)
00051 : extent_(ext)
00052 {
00053 std::memset(children_,0,4*sizeof(node*));
00054 }
00055
00056 Envelope<double> const& extent() const
00057 {
00058 return extent_;
00059 }
00060
00061 iterator begin()
00062 {
00063 return cont_.begin();
00064 }
00065
00066 const_iterator begin() const
00067 {
00068 return cont_.begin();
00069 }
00070
00071 iterator end()
00072 {
00073 return cont_.end();
00074 }
00075
00076 const_iterator end() const
00077 {
00078 return cont_.end();
00079 }
00080 ~node () {}
00081 };
00082
00083 typedef boost::ptr_vector<node> nodes_t;
00084 typedef typename node::cont_t cont_t;
00085 typedef typename cont_t::iterator node_data_iterator;
00086
00087 nodes_t nodes_;
00088 node * root_;
00089 const unsigned int max_depth_;
00090 const double ratio_;
00091 public:
00092 typedef typename nodes_t::iterator iterator;
00093 typedef typename nodes_t::const_iterator const_iterator;
00094 typedef typename boost::ptr_vector<T,boost::view_clone_allocator> result_t;
00095 typedef typename result_t::iterator query_iterator;
00096
00097 result_t query_result_;
00098
00099 explicit quad_tree(Envelope<double> const& ext,
00100 unsigned int max_depth = 8,
00101 double ratio = 0.55)
00102 : max_depth_(max_depth),
00103 ratio_(ratio)
00104 {
00105 nodes_.push_back(new node(ext));
00106 root_ = &nodes_[0];
00107 }
00108
00109 void insert(T data, Envelope<double> const& box)
00110 {
00111 unsigned int depth=0;
00112 do_insert_data(data,box,root_,depth);
00113 }
00114
00115 query_iterator query_in_box(Envelope<double> const& box)
00116 {
00117 query_result_.clear();
00118 query_node(box,query_result_,root_);
00119 return query_result_.begin();
00120 }
00121
00122 query_iterator query_end()
00123 {
00124 return query_result_.end();
00125 }
00126
00127 iterator begin()
00128 {
00129 return nodes_.begin();
00130 }
00131
00132 const_iterator begin() const
00133 {
00134 return nodes_.begin();
00135 }
00136
00137 iterator end()
00138 {
00139 return nodes_.end();
00140 }
00141
00142 const_iterator end() const
00143 {
00144 return nodes_.end();
00145 }
00146
00147 void clear ()
00148 {
00149 Envelope<double> ext = root_->extent_;
00150 nodes_.clear();
00151 nodes_.push_back(new node(ext));
00152 root_ = &nodes_[0];
00153 }
00154
00155 private:
00156 void query_node(Envelope<double> const& box, result_t & result, node * node_) const
00157 {
00158 if (node_)
00159 {
00160 Envelope<double> const& node_extent = node_->extent();
00161 if (box.intersects(node_extent))
00162 {
00163 node_data_iterator i=node_->begin();
00164 node_data_iterator end=node_->end();
00165 while ( i!=end)
00166 {
00167 result.push_back(&(*i));
00168 ++i;
00169 }
00170 for (int k = 0; k < 4; ++k)
00171 {
00172 query_node(box,result,node_->children_[k]);
00173 }
00174 }
00175 }
00176 }
00177
00178 void do_insert_data(T data, Envelope<double> const& box, node * n, unsigned int& depth)
00179 {
00180 if (++depth >= max_depth_)
00181 {
00182 n->cont_.push_back(data);
00183 }
00184 else
00185 {
00186 Envelope<double> const& node_extent = n->extent();
00187 Envelope<double> ext[4];
00188 split_box(node_extent,ext);
00189 for (int i=0;i<4;++i)
00190 {
00191 if (ext[i].contains(box))
00192 {
00193 if (!n->children_[i])
00194 {
00195 nodes_.push_back(new node(ext[i]));
00196 n->children_[i]=&nodes_.back();
00197 }
00198 do_insert_data(data,box,n->children_[i],depth);
00199 return;
00200 }
00201 }
00202 n->cont_.push_back(data);
00203 }
00204 }
00205
00206 void split_box(Envelope<double> const& node_extent,Envelope<double> * ext)
00207 {
00208 coord2d c=node_extent.center();
00209
00210 double width=node_extent.width();
00211 double height=node_extent.height();
00212
00213 double lox=node_extent.minx();
00214 double loy=node_extent.miny();
00215 double hix=node_extent.maxx();
00216 double hiy=node_extent.maxy();
00217
00218 ext[0]=Envelope<double>(lox,loy,lox + width * ratio_,loy + height * ratio_);
00219 ext[1]=Envelope<double>(hix - width * ratio_,loy,hix,loy + height * ratio_);
00220 ext[2]=Envelope<double>(lox,hiy - height*ratio_,lox + width * ratio_,hiy);
00221 ext[3]=Envelope<double>(hix - width * ratio_,hiy - height*ratio_,hix,hiy);
00222 }
00223 };
00224 }
00225
00226 #endif