polygon/detail/polygon_45_touch.hpp

0001 /*
0002   Copyright 2008 Intel Corporation
0003
0004   Use, modification and distribution are subject to the Boost Software License,
0005   Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
0006   http://www.boost.org/LICENSE_1_0.txt).
0007 */
0008 #ifndef BOOST_POLYGON_POLYGON_45_TOUCH_HPP
0009 #define BOOST_POLYGON_POLYGON_45_TOUCH_HPP
0010 namespace boost { namespace polygon{
0011
0012   template <typename Unit>
0013   struct polygon_45_touch {
0014
0015     typedef point_data<Unit> Point;
0016     typedef typename coordinate_traits<Unit>::manhattan_area_type LongUnit;
0017
0018     template <typename property_map>
0019     static inline void merge_property_maps(property_map& mp, const property_map& mp2, bool subtract = false) {
0020       property_map newmp;
0021       newmp.reserve(mp.size() + mp2.size());
0022       std::size_t i = 0;
0023       std::size_t j = 0;
0024       while(i != mp.size() && j != mp2.size()) {
0025         if(mp[i].first < mp2[j].first) {
0026           newmp.push_back(mp[i]);
0027           ++i;
0028         } else if(mp[i].first > mp2[j].first) {
0029           newmp.push_back(mp2[j]);
0030           if(subtract) newmp.back().second *= -1;
0031           ++j;
0032         } else {
0033           int count = mp[i].second;
0034           if(subtract) count -= mp2[j].second;
0035           else count += mp2[j].second;
0036           if(count) {
0037             newmp.push_back(mp[i]);
0038             newmp.back().second = count;
0039           }
0040           ++i;
0041           ++j;
0042         }
0043       }
0044       while(i != mp.size()) {
0045         newmp.push_back(mp[i]);
0046         ++i;
0047       }
0048       while(j != mp2.size()) {
0049         newmp.push_back(mp2[j]);
0050         if(subtract) newmp.back().second *= -1;
0051         ++j;
0052       }
0053       mp.swap(newmp);
0054     }
0055
0056     class CountTouch {
0057     public:
0058       inline CountTouch() : counts() {}
0059       //inline CountTouch(int count) { counts[0] = counts[1] = count; }
0060       //inline CountTouch(int count1, int count2) { counts[0] = count1; counts[1] = count2; }
0061       inline CountTouch(const CountTouch& count) : counts(count.counts) {}
0062       inline bool operator==(const CountTouch& count) const { return counts == count.counts; }
0063       inline bool operator!=(const CountTouch& count) const { return !((*this) == count); }
0064       //inline CountTouch& operator=(int count) { counts[0] = counts[1] = count; return *this; }
0065       inline CountTouch& operator=(const CountTouch& count) { counts = count.counts; return *this; }
0066       inline int& operator[](int index) {
0067         std::vector<std::pair<int, int> >::iterator itr =
0068             std::lower_bound(counts.begin(), counts.end(),
0069                              std::make_pair(index, int(0)));
0070         if(itr != counts.end() && itr->first == index) {
0071             return itr->second;
0072         }
0073         itr = counts.insert(itr, std::make_pair(index, int(0)));
0074         return itr->second;
0075       }
0076 //       inline int operator[](int index) const {
0077 //         std::vector<std::pair<int, int> >::const_iterator itr = counts.begin();
0078 //         for( ; itr != counts.end() && itr->first <= index; ++itr) {
0079 //           if(itr->first == index) {
0080 //             return itr->second;
0081 //           }
0082 //         }
0083 //         return 0;
0084 //       }
0085       inline CountTouch& operator+=(const CountTouch& count){
0086         merge_property_maps(counts, count.counts, false);
0087         return *this;
0088       }
0089       inline CountTouch& operator-=(const CountTouch& count){
0090         merge_property_maps(counts, count.counts, true);
0091         return *this;
0092       }
0093       inline CountTouch operator+(const CountTouch& count) const {
0094         return CountTouch(*this)+=count;
0095       }
0096       inline CountTouch operator-(const CountTouch& count) const {
0097         return CountTouch(*this)-=count;
0098       }
0099       inline CountTouch invert() const {
0100         CountTouch retval;
0101         retval -= *this;
0102         return retval;
0103       }
0104       std::vector<std::pair<int, int> > counts;
0105     };
0106
0107     typedef std::pair<std::pair<Unit, std::map<Unit, std::set<int> > >, std::map<int, std::set<int> > > map_graph_o;
0108     typedef std::pair<std::pair<Unit, std::map<Unit, std::set<int> > >, std::vector<std::set<int> > > vector_graph_o;
0109
0110     template <typename cT>
0111     static void process_previous_x(cT& output) {
0112       std::map<Unit, std::set<int> >& y_prop_map = output.first.second;
0113       for(typename std::map<Unit, std::set<int> >::iterator itr = y_prop_map.begin();
0114           itr != y_prop_map.end(); ++itr) {
0115         for(std::set<int>::iterator inner_itr = itr->second.begin();
0116             inner_itr != itr->second.end(); ++inner_itr) {
0117           std::set<int>& output_edges = (*(output.second))[*inner_itr];
0118           std::set<int>::iterator inner_inner_itr = inner_itr;
0119           ++inner_inner_itr;
0120           for( ; inner_inner_itr != itr->second.end(); ++inner_inner_itr) {
0121             output_edges.insert(output_edges.end(), *inner_inner_itr);
0122             std::set<int>& output_edges_2 = (*(output.second))[*inner_inner_itr];
0123             output_edges_2.insert(output_edges_2.end(), *inner_itr);
0124           }
0125         }
0126       }
0127       y_prop_map.clear();
0128     }
0129
0130     struct touch_45_output_functor {
0131       template <typename cT>
0132       void operator()(cT& output, const CountTouch& count1, const CountTouch& count2,
0133                       const Point& pt, int , direction_1d ) {
0134         Unit& x = output.first.first;
0135         std::map<Unit, std::set<int> >& y_prop_map = output.first.second;
0136         if(pt.x() != x) process_previous_x(output);
0137         x = pt.x();
0138         std::set<int>& output_set = y_prop_map[pt.y()];
0139         for(std::vector<std::pair<int, int> >::const_iterator itr1 = count1.counts.begin();
0140             itr1 != count1.counts.end(); ++itr1) {
0141           if(itr1->second > 0) {
0142             output_set.insert(output_set.end(), itr1->first);
0143           }
0144         }
0145         for(std::vector<std::pair<int, int> >::const_iterator itr2 = count2.counts.begin();
0146             itr2 != count2.counts.end(); ++itr2) {
0147           if(itr2->second > 0) {
0148             output_set.insert(output_set.end(), itr2->first);
0149           }
0150         }
0151       }
0152     };
0153     typedef typename std::pair<Point,
0154                                typename boolean_op_45<Unit>::template Scan45CountT<CountTouch> > Vertex45Compact;
0155     typedef std::vector<Vertex45Compact> TouchSetData;
0156
0157     struct lessVertex45Compact {
0158       bool operator()(const Vertex45Compact& l, const Vertex45Compact& r) {
0159         return l.first < r.first;
0160       }
0161     };
0162
0163 //     template <typename TSD>
0164 //     static void print_tsd(TSD& tsd) {
0165 //       for(std::size_t i = 0; i < tsd.size(); ++i) {
0166 //         std::cout << tsd[i].first << ": ";
0167 //         for(unsigned int r = 0; r < 4; ++r) {
0168 //           std::cout << r << " { ";
0169 //           for(std::vector<std::pair<int, int> >::iterator itr = tsd[i].second[r].counts.begin();
0170 //               itr != tsd[i].second[r].counts.end(); ++itr) {
0171 //             std::cout << itr->first << "," << itr->second << " ";
0172 //           } std::cout << "} ";
0173 //         }
0174 //       } std::cout << std::endl;
0175 //     }
0176
0177 //     template <typename T>
0178 //     static void print_scanline(T& t) {
0179 //       for(typename T::iterator itr = t.begin(); itr != t.end(); ++itr) {
0180 //         std::cout << itr->x << "," << itr->y << " " << itr->rise << " ";
0181 //         for(std::vector<std::pair<int, int> >::iterator itr2 = itr->count.counts.begin();
0182 //             itr2 != itr->count.counts.end(); ++itr2) {
0183 //           std::cout << itr2->first << ":" << itr2->second << " ";
0184 //         } std::cout << std::endl;
0185 //       }
0186 //     }
0187
0188     template <typename graph_type>
0189     static void performTouch(graph_type& graph, TouchSetData& tsd) {
0190
0191       polygon_sort(tsd.begin(), tsd.end(), lessVertex45Compact());
0192       typedef std::vector<std::pair<Point, typename boolean_op_45<Unit>::template Scan45CountT<CountTouch> > > TSD;
0193       TSD tsd_;
0194       tsd_.reserve(tsd.size());
0195       for(typename TouchSetData::iterator itr = tsd.begin(); itr != tsd.end(); ) {
0196         typename TouchSetData::iterator itr2 = itr;
0197         ++itr2;
0198         for(; itr2 != tsd.end() && itr2->first == itr->first; ++itr2) {
0199           (itr->second) += (itr2->second); //accumulate
0200         }
0201         tsd_.push_back(std::make_pair(itr->first, itr->second));
0202         itr = itr2;
0203       }
0204       std::pair<std::pair<Unit, std::map<Unit, std::set<int> > >, graph_type*> output
0205         (std::make_pair(std::make_pair((std::numeric_limits<Unit>::max)(), std::map<Unit, std::set<int> >()), &graph));
0206       typename boolean_op_45<Unit>::template Scan45<CountTouch, touch_45_output_functor> scanline;
0207       for(typename TSD::iterator itr = tsd_.begin(); itr != tsd_.end(); ) {
0208         typename TSD::iterator itr2 = itr;
0209         ++itr2;
0210         while(itr2 != tsd_.end() && itr2->first.x() == itr->first.x()) {
0211           ++itr2;
0212         }
0213         scanline.scan(output, itr, itr2);
0214         itr = itr2;
0215       }
0216       process_previous_x(output);
0217     }
0218
0219     template <typename iT>
0220     static void populateTouchSetData(TouchSetData& tsd, iT begin, iT end, int nodeCount) {
0221       for( ; begin != end; ++begin) {
0222         Vertex45Compact vertex;
0223         vertex.first = typename Vertex45Compact::first_type(begin->pt.x() * 2, begin->pt.y() * 2);
0224         tsd.push_back(vertex);
0225         for(unsigned int i = 0; i < 4; ++i) {
0226           if(begin->count[i]) {
0227             tsd.back().second[i][nodeCount] += begin->count[i];
0228           }
0229         }
0230       }
0231     }
0232
0233   };
0234
0235
0236 }
0237 }
0238 #endif