1 /* 2 Copyright 2008 Intel Corporation 3 4 Use, modification and distribution are subject to the Boost Software License, 5 Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at 6 http://www.boost.org/LICENSE_1_0.txt). 7 */ 8 #ifndef BOOST_POLYGON_POLYGON_45_TOUCH_HPP 9 #define BOOST_POLYGON_POLYGON_45_TOUCH_HPP 10 namespace boost { namespace polygon{ 11 12 template <typename Unit> 13 struct polygon_45_touch { 14 15 typedef point_data<Unit> Point; 16 typedef typename coordinate_traits<Unit>::manhattan_area_type LongUnit; 17 18 template <typename property_map> merge_property_mapsboost::polygon::polygon_45_touch19 static inline void merge_property_maps(property_map& mp, const property_map& mp2, bool subtract = false) { 20 property_map newmp; 21 newmp.reserve(mp.size() + mp2.size()); 22 std::size_t i = 0; 23 std::size_t j = 0; 24 while(i != mp.size() && j != mp2.size()) { 25 if(mp[i].first < mp2[j].first) { 26 newmp.push_back(mp[i]); 27 ++i; 28 } else if(mp[i].first > mp2[j].first) { 29 newmp.push_back(mp2[j]); 30 if(subtract) newmp.back().second *= -1; 31 ++j; 32 } else { 33 int count = mp[i].second; 34 if(subtract) count -= mp2[j].second; 35 else count += mp2[j].second; 36 if(count) { 37 newmp.push_back(mp[i]); 38 newmp.back().second = count; 39 } 40 ++i; 41 ++j; 42 } 43 } 44 while(i != mp.size()) { 45 newmp.push_back(mp[i]); 46 ++i; 47 } 48 while(j != mp2.size()) { 49 newmp.push_back(mp2[j]); 50 if(subtract) newmp.back().second *= -1; 51 ++j; 52 } 53 mp.swap(newmp); 54 } 55 56 class CountTouch { 57 public: CountTouch()58 inline CountTouch() : counts() {} 59 //inline CountTouch(int count) { counts[0] = counts[1] = count; } 60 //inline CountTouch(int count1, int count2) { counts[0] = count1; counts[1] = count2; } CountTouch(const CountTouch & count)61 inline CountTouch(const CountTouch& count) : counts(count.counts) {} operator ==(const CountTouch & count) const62 inline bool operator==(const CountTouch& count) const { return counts == count.counts; } operator !=(const CountTouch & count) const63 inline bool operator!=(const CountTouch& count) const { return !((*this) == count); } 64 //inline CountTouch& operator=(int count) { counts[0] = counts[1] = count; return *this; } operator =(const CountTouch & count)65 inline CountTouch& operator=(const CountTouch& count) { counts = count.counts; return *this; } operator [](int index)66 inline int& operator[](int index) { 67 std::vector<std::pair<int, int> >::iterator itr = 68 std::lower_bound(counts.begin(), counts.end(), 69 std::make_pair(index, int(0))); 70 if(itr != counts.end() && itr->first == index) { 71 return itr->second; 72 } 73 itr = counts.insert(itr, std::make_pair(index, int(0))); 74 return itr->second; 75 } 76 // inline int operator[](int index) const { 77 // std::vector<std::pair<int, int> >::const_iterator itr = counts.begin(); 78 // for( ; itr != counts.end() && itr->first <= index; ++itr) { 79 // if(itr->first == index) { 80 // return itr->second; 81 // } 82 // } 83 // return 0; 84 // } operator +=(const CountTouch & count)85 inline CountTouch& operator+=(const CountTouch& count){ 86 merge_property_maps(counts, count.counts, false); 87 return *this; 88 } operator -=(const CountTouch & count)89 inline CountTouch& operator-=(const CountTouch& count){ 90 merge_property_maps(counts, count.counts, true); 91 return *this; 92 } operator +(const CountTouch & count) const93 inline CountTouch operator+(const CountTouch& count) const { 94 return CountTouch(*this)+=count; 95 } operator -(const CountTouch & count) const96 inline CountTouch operator-(const CountTouch& count) const { 97 return CountTouch(*this)-=count; 98 } invert() const99 inline CountTouch invert() const { 100 CountTouch retval; 101 retval -= *this; 102 return retval; 103 } 104 std::vector<std::pair<int, int> > counts; 105 }; 106 107 typedef std::pair<std::pair<Unit, std::map<Unit, std::set<int> > >, std::map<int, std::set<int> > > map_graph_o; 108 typedef std::pair<std::pair<Unit, std::map<Unit, std::set<int> > >, std::vector<std::set<int> > > vector_graph_o; 109 110 template <typename cT> process_previous_xboost::polygon::polygon_45_touch111 static void process_previous_x(cT& output) { 112 std::map<Unit, std::set<int> >& y_prop_map = output.first.second; 113 for(typename std::map<Unit, std::set<int> >::iterator itr = y_prop_map.begin(); 114 itr != y_prop_map.end(); ++itr) { 115 for(std::set<int>::iterator inner_itr = itr->second.begin(); 116 inner_itr != itr->second.end(); ++inner_itr) { 117 std::set<int>& output_edges = (*(output.second))[*inner_itr]; 118 std::set<int>::iterator inner_inner_itr = inner_itr; 119 ++inner_inner_itr; 120 for( ; inner_inner_itr != itr->second.end(); ++inner_inner_itr) { 121 output_edges.insert(output_edges.end(), *inner_inner_itr); 122 std::set<int>& output_edges_2 = (*(output.second))[*inner_inner_itr]; 123 output_edges_2.insert(output_edges_2.end(), *inner_itr); 124 } 125 } 126 } 127 y_prop_map.clear(); 128 } 129 130 struct touch_45_output_functor { 131 template <typename cT> operator ()boost::polygon::polygon_45_touch::touch_45_output_functor132 void operator()(cT& output, const CountTouch& count1, const CountTouch& count2, 133 const Point& pt, int , direction_1d ) { 134 Unit& x = output.first.first; 135 std::map<Unit, std::set<int> >& y_prop_map = output.first.second; 136 if(pt.x() != x) process_previous_x(output); 137 x = pt.x(); 138 std::set<int>& output_set = y_prop_map[pt.y()]; 139 for(std::vector<std::pair<int, int> >::const_iterator itr1 = count1.counts.begin(); 140 itr1 != count1.counts.end(); ++itr1) { 141 if(itr1->second > 0) { 142 output_set.insert(output_set.end(), itr1->first); 143 } 144 } 145 for(std::vector<std::pair<int, int> >::const_iterator itr2 = count2.counts.begin(); 146 itr2 != count2.counts.end(); ++itr2) { 147 if(itr2->second > 0) { 148 output_set.insert(output_set.end(), itr2->first); 149 } 150 } 151 } 152 }; 153 typedef typename std::pair<Point, 154 typename boolean_op_45<Unit>::template Scan45CountT<CountTouch> > Vertex45Compact; 155 typedef std::vector<Vertex45Compact> TouchSetData; 156 157 struct lessVertex45Compact { operator ()boost::polygon::polygon_45_touch::lessVertex45Compact158 bool operator()(const Vertex45Compact& l, const Vertex45Compact& r) { 159 return l.first < r.first; 160 } 161 }; 162 163 // template <typename TSD> 164 // static void print_tsd(TSD& tsd) { 165 // for(std::size_t i = 0; i < tsd.size(); ++i) { 166 // std::cout << tsd[i].first << ": "; 167 // for(unsigned int r = 0; r < 4; ++r) { 168 // std::cout << r << " { "; 169 // for(std::vector<std::pair<int, int> >::iterator itr = tsd[i].second[r].counts.begin(); 170 // itr != tsd[i].second[r].counts.end(); ++itr) { 171 // std::cout << itr->first << "," << itr->second << " "; 172 // } std::cout << "} "; 173 // } 174 // } std::cout << std::endl; 175 // } 176 177 // template <typename T> 178 // static void print_scanline(T& t) { 179 // for(typename T::iterator itr = t.begin(); itr != t.end(); ++itr) { 180 // std::cout << itr->x << "," << itr->y << " " << itr->rise << " "; 181 // for(std::vector<std::pair<int, int> >::iterator itr2 = itr->count.counts.begin(); 182 // itr2 != itr->count.counts.end(); ++itr2) { 183 // std::cout << itr2->first << ":" << itr2->second << " "; 184 // } std::cout << std::endl; 185 // } 186 // } 187 188 template <typename graph_type> performTouchboost::polygon::polygon_45_touch189 static void performTouch(graph_type& graph, TouchSetData& tsd) { 190 191 polygon_sort(tsd.begin(), tsd.end(), lessVertex45Compact()); 192 typedef std::vector<std::pair<Point, typename boolean_op_45<Unit>::template Scan45CountT<CountTouch> > > TSD; 193 TSD tsd_; 194 tsd_.reserve(tsd.size()); 195 for(typename TouchSetData::iterator itr = tsd.begin(); itr != tsd.end(); ) { 196 typename TouchSetData::iterator itr2 = itr; 197 ++itr2; 198 for(; itr2 != tsd.end() && itr2->first == itr->first; ++itr2) { 199 (itr->second) += (itr2->second); //accumulate 200 } 201 tsd_.push_back(std::make_pair(itr->first, itr->second)); 202 itr = itr2; 203 } 204 std::pair<std::pair<Unit, std::map<Unit, std::set<int> > >, graph_type*> output 205 (std::make_pair(std::make_pair((std::numeric_limits<Unit>::max)(), std::map<Unit, std::set<int> >()), &graph)); 206 typename boolean_op_45<Unit>::template Scan45<CountTouch, touch_45_output_functor> scanline; 207 for(typename TSD::iterator itr = tsd_.begin(); itr != tsd_.end(); ) { 208 typename TSD::iterator itr2 = itr; 209 ++itr2; 210 while(itr2 != tsd_.end() && itr2->first.x() == itr->first.x()) { 211 ++itr2; 212 } 213 scanline.scan(output, itr, itr2); 214 itr = itr2; 215 } 216 process_previous_x(output); 217 } 218 219 template <typename iT> populateTouchSetDataboost::polygon::polygon_45_touch220 static void populateTouchSetData(TouchSetData& tsd, iT begin, iT end, int nodeCount) { 221 for( ; begin != end; ++begin) { 222 Vertex45Compact vertex; 223 vertex.first = typename Vertex45Compact::first_type(begin->pt.x() * 2, begin->pt.y() * 2); 224 tsd.push_back(vertex); 225 for(unsigned int i = 0; i < 4; ++i) { 226 if(begin->count[i]) { 227 tsd.back().second[i][nodeCount] += begin->count[i]; 228 } 229 } 230 } 231 } 232 233 }; 234 235 236 } 237 } 238 #endif 239