00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023
00024
00025 #if !defined LABEL_COLLISION_DETECTOR
00026 #define LABEL_COLLISION_DETECTOR
00027
00028 #include <mapnik/quad_tree.hpp>
00029
00030 #include <vector>
00031 #include <unicode/unistr.h>
00032
00033 namespace mapnik
00034 {
00035
00036
00037
00038 struct label_collision_detector
00039 {
00040 typedef std::vector<Envelope<double> > label_placements;
00041
00042 bool has_plasement(Envelope<double> const& box)
00043 {
00044 label_placements::const_iterator itr=labels_.begin();
00045 for( ; itr !=labels_.end();++itr)
00046 {
00047 if (itr->intersects(box))
00048 {
00049 return false;
00050 }
00051 }
00052 labels_.push_back(box);
00053 return true;
00054 }
00055 void clear()
00056 {
00057 labels_.clear();
00058 }
00059
00060 private:
00061
00062 label_placements labels_;
00063 };
00064
00065
00066 class label_collision_detector2 : boost::noncopyable
00067 {
00068 typedef quad_tree<Envelope<double> > tree_t;
00069 tree_t tree_;
00070 public:
00071
00072 explicit label_collision_detector2(Envelope<double> const& extent)
00073 : tree_(extent) {}
00074
00075 bool has_placement(Envelope<double> const& box)
00076 {
00077 tree_t::query_iterator itr = tree_.query_in_box(box);
00078 tree_t::query_iterator end = tree_.query_end();
00079
00080 for ( ;itr != end; ++itr)
00081 {
00082 if (itr->intersects(box))
00083 {
00084 return false;
00085 }
00086 }
00087
00088 tree_.insert(box,box);
00089 return true;
00090 }
00091
00092 void clear()
00093 {
00094 tree_.clear();
00095 }
00096
00097 };
00098
00099
00100 class label_collision_detector3 : boost::noncopyable
00101 {
00102 typedef quad_tree< Envelope<double> > tree_t;
00103 tree_t tree_;
00104 public:
00105
00106 explicit label_collision_detector3(Envelope<double> const& extent)
00107 : tree_(extent) {}
00108
00109 bool has_placement(Envelope<double> const& box)
00110 {
00111 tree_t::query_iterator itr = tree_.query_in_box(box);
00112 tree_t::query_iterator end = tree_.query_end();
00113
00114 for ( ;itr != end; ++itr)
00115 {
00116 if (itr->intersects(box))
00117 {
00118 return false;
00119 }
00120 }
00121
00122 return true;
00123 }
00124
00125 void insert(Envelope<double> const& box)
00126 {
00127 tree_.insert(box, box);
00128 }
00129
00130 void clear()
00131 {
00132 tree_.clear();
00133 }
00134 };
00135
00136
00137
00138 class label_collision_detector4 : boost::noncopyable
00139 {
00140 struct label
00141 {
00142 label(Envelope<double> const& b) : box(b) {}
00143 label(Envelope<double> const& b, UnicodeString const& t) : box(b), text(t) {}
00144
00145 Envelope<double> box;
00146 UnicodeString text;
00147 };
00148
00149 typedef quad_tree< label > tree_t;
00150 Envelope<double> extent_;
00151 tree_t tree_;
00152
00153 public:
00154
00155 explicit label_collision_detector4(Envelope<double> const& extent)
00156 : extent_(extent),
00157 tree_(extent) {}
00158
00159 bool has_placement(Envelope<double> const& box)
00160 {
00161 tree_t::query_iterator itr = tree_.query_in_box(box);
00162 tree_t::query_iterator end = tree_.query_end();
00163
00164 for ( ;itr != end; ++itr)
00165 {
00166 if (itr->box.intersects(box))
00167 {
00168 return false;
00169 }
00170 }
00171
00172 return true;
00173 }
00174
00175 bool has_placement(Envelope<double> const& box, UnicodeString const& text, double distance)
00176 {
00177 Envelope<double> bigger_box(box.minx() - distance, box.miny() - distance, box.maxx() + distance, box.maxy() + distance);
00178
00179 tree_t::query_iterator itr = tree_.query_in_box(bigger_box);
00180 tree_t::query_iterator end = tree_.query_end();
00181
00182 for ( ;itr != end; ++itr)
00183 {
00184 if (itr->box.intersects(box) || (text == itr->text && itr->box.intersects(bigger_box)))
00185 {
00186 return false;
00187 }
00188 }
00189
00190 return true;
00191 }
00192
00193
00194 void insert(Envelope<double> const& box)
00195 {
00196 tree_.insert(label(box), box);
00197 }
00198
00199 void insert(Envelope<double> const& box, UnicodeString const& text)
00200 {
00201 tree_.insert(label(box, text), box);
00202 }
00203
00204 void clear()
00205 {
00206 tree_.clear();
00207 }
00208 Envelope<double> const& extent() const
00209 {
00210 return extent_;
00211 }
00212 };
00213 }
00214
00215 #endif