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 _OCTREE_HPP_
00025 #define _OCTREE_HPP_
00026
00027 #include <boost/format.hpp>
00028 #include <boost/utility.hpp>
00029 #include <vector>
00030 #include <iostream>
00031 #include <deque>
00032
00033 namespace mapnik {
00034
00035 typedef uint8_t byte ;
00036 struct rgb
00037 {
00038 byte r;
00039 byte g;
00040 byte b;
00041 rgb(byte r_, byte b_, byte g_)
00042 : r(r_), g(g_), b(b_) {}
00043 };
00044
00045 struct RGBPolicy
00046 {
00047 const static unsigned MAX_LEVELS = 6;
00048 inline static unsigned index_from_level(unsigned level, rgb const& c)
00049 {
00050 unsigned shift = (MAX_LEVELS + 1) - level;
00051 return (((c.r >> shift) & 1) << 2)
00052 | (((c.g >> shift) & 1) << 1)
00053 | ((c.b >> shift) & 1);
00054 }
00055 };
00056
00057 template <typename T, typename InsertPolicy = RGBPolicy >
00058 class octree : private boost::noncopyable
00059 {
00060 struct node
00061 {
00062 node ()
00063 : reds(0),
00064 greens(0),
00065 blues(0),
00066 count(0),
00067 index(0)
00068 {
00069 memset(&children_[0],0,sizeof(children_));
00070 }
00071
00072 ~node ()
00073 {
00074 for (unsigned i = 0;i < 8; ++i) {
00075 if (children_[i] != 0) delete children_[i],children_[i]=0;
00076 }
00077 }
00078
00079 bool is_leaf() const { return count == 0; }
00080 node * children_[8];
00081 unsigned reds;
00082 unsigned greens;
00083 unsigned blues;
00084 unsigned count;
00085 uint8_t index;
00086 };
00087 struct node_cmp
00088 {
00089 bool operator() ( const node * lhs,const node* rhs) const
00090 {
00091 unsigned left_total=0;
00092 unsigned right_total=0;
00093 for (unsigned i=0; i<8;++i)
00094 {
00095 if (lhs->children_[i]) left_total+=lhs->children_[i]->count;
00096 if (rhs->children_[i]) right_total+=rhs->children_[i]->count;
00097 }
00098 return left_total < right_total;
00099 }
00100 };
00101
00102 std::deque<node*> reducible_[InsertPolicy::MAX_LEVELS];
00103 unsigned max_colors_;
00104 unsigned colors_;
00105 unsigned leaf_level_;
00106
00107 public:
00108 explicit octree(unsigned max_colors=256)
00109 : max_colors_(max_colors),
00110 colors_(0),
00111 leaf_level_(InsertPolicy::MAX_LEVELS),
00112 root_(new node())
00113 {}
00114
00115 ~octree() { delete root_;}
00116
00117 void insert(T const& data)
00118 {
00119 unsigned level = 0;
00120 node * cur_node = root_;
00121 while (true) {
00122
00123 if ( cur_node->count > 0 || level == leaf_level_)
00124 {
00125 cur_node->reds += data.r;
00126 cur_node->greens += data.g;
00127 cur_node->blues += data.b;
00128 cur_node->count += 1;
00129 if (cur_node->count == 1) ++colors_;
00130
00131
00132 break;
00133 }
00134
00135 unsigned idx = InsertPolicy::index_from_level(level,data);
00136 if (cur_node->children_[idx] == 0) {
00137 cur_node->children_[idx] = new node();
00138 if (level < leaf_level_-1)
00139 {
00140 reducible_[level+1].push_back(cur_node->children_[idx]);
00141 }
00142 }
00143 cur_node = cur_node->children_[idx];
00144 ++level;
00145 }
00146 }
00147
00148 int quantize(rgb const& c) const
00149 {
00150 unsigned level = 0;
00151 node * cur_node = root_;
00152 while (cur_node)
00153 {
00154 if (cur_node->count != 0) return cur_node->index;
00155 unsigned idx = InsertPolicy::index_from_level(level,c);
00156 cur_node = cur_node->children_[idx];
00157 ++level;
00158 }
00159 return -1;
00160 }
00161
00162 void create_palette(std::vector<rgb> & palette)
00163 {
00164 reduce();
00165 palette.reserve(colors_);
00166 create_palette(palette, root_);
00167 }
00168
00169 void reduce()
00170 {
00171
00172 for (unsigned i=0;i<InsertPolicy::MAX_LEVELS;++i)
00173 {
00174 std::sort(reducible_[i].begin(), reducible_[i].end(),node_cmp());
00175 }
00176
00177 while ( colors_ >= max_colors_ - 1)
00178 {
00179 while (leaf_level_ >0 && reducible_[leaf_level_-1].size() == 0)
00180 {
00181 --leaf_level_;
00182 }
00183
00184 if (leaf_level_ < 1) continue;
00185
00186 if ( reducible_[leaf_level_-1].size() == 0) return;
00187
00188 typename std::deque<node*>::iterator pos = reducible_[leaf_level_-1].begin();
00189 node * cur_node = *pos;
00190 unsigned num_children = 0;
00191 for (unsigned idx=0; idx < 8; ++idx)
00192 {
00193 if (cur_node->children_[idx] != 0)
00194 {
00195 ++num_children;
00196 cur_node->reds += cur_node->children_[idx]->reds;
00197 cur_node->greens += cur_node->children_[idx]->greens;
00198 cur_node->blues += cur_node->children_[idx]->blues;
00199 cur_node->count += cur_node->children_[idx]->count;
00200 delete cur_node->children_[idx], cur_node->children_[idx]=0;
00201 }
00202 }
00203
00204 reducible_[leaf_level_-1].erase(pos);
00205 if (num_children > 0 )
00206 {
00207 colors_ -= (num_children - 1);
00208 }
00209 }
00210 }
00211
00212 void create_palette(std::vector<rgb> & palette, node * itr) const
00213 {
00214 if (itr->count != 0)
00215 {
00216 unsigned count = itr->count;
00217 palette.push_back(rgb(uint8_t(itr->reds/float(count)),
00218 uint8_t(itr->greens/float(count)),
00219 uint8_t(itr->blues/float(count))));
00220 itr->index = palette.size() - 1;
00221 }
00222 for (unsigned i=0; i < 8 ;++i)
00223 {
00224 if (itr->children_[i] != 0)
00225 create_palette(palette, itr->children_[i]);
00226 }
00227 }
00228 private:
00229 node * root_;
00230 };
00231 }
00232
00233 #endif