polygon/detail/property_merge_45.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_PROPERTY_MERGE_45_HPP
0009 #define BOOST_POLYGON_PROPERTY_MERGE_45_HPP
0010 namespace boost { namespace polygon{
0011
0012   template <typename Unit, typename property_type>
0013   struct polygon_45_property_merge {
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       polygon_45_touch<Unit>::merge_property_maps(mp, mp2, subtract);
0021     }
0022
0023     class CountMerge {
0024     public:
0025       inline CountMerge() : counts() {}
0026       //inline CountMerge(int count) { counts[0] = counts[1] = count; }
0027       //inline CountMerge(int count1, int count2) { counts[0] = count1; counts[1] = count2; }
0028       inline CountMerge(const CountMerge& count) : counts(count.counts) {}
0029       inline bool operator==(const CountMerge& count) const { return counts == count.counts; }
0030       inline bool operator!=(const CountMerge& count) const { return !((*this) == count); }
0031       //inline CountMerge& operator=(int count) { counts[0] = counts[1] = count; return *this; }
0032       inline CountMerge& operator=(const CountMerge& count) { counts = count.counts; return *this; }
0033       inline int& operator[](property_type index) {
0034         std::vector<std::pair<int, int> >::iterator itr = lower_bound(counts.begin(), counts.end(), std::make_pair(index, int(0)));
0035         if(itr != counts.end() && itr->first == index) {
0036             return itr->second;
0037         }
0038         itr = counts.insert(itr, std::make_pair(index, int(0)));
0039         return itr->second;
0040       }
0041 //       inline int operator[](int index) const {
0042 //         std::vector<std::pair<int, int> >::const_iterator itr = counts.begin();
0043 //         for( ; itr != counts.end() && itr->first <= index; ++itr) {
0044 //           if(itr->first == index) {
0045 //             return itr->second;
0046 //           }
0047 //         }
0048 //         return 0;
0049 //       }
0050       inline CountMerge& operator+=(const CountMerge& count){
0051         merge_property_maps(counts, count.counts, false);
0052         return *this;
0053       }
0054       inline CountMerge& operator-=(const CountMerge& count){
0055         merge_property_maps(counts, count.counts, true);
0056         return *this;
0057       }
0058       inline CountMerge operator+(const CountMerge& count) const {
0059         return CountMerge(*this)+=count;
0060       }
0061       inline CountMerge operator-(const CountMerge& count) const {
0062         return CountMerge(*this)-=count;
0063       }
0064       inline CountMerge invert() const {
0065         CountMerge retval;
0066         retval -= *this;
0067         return retval;
0068       }
0069       std::vector<std::pair<property_type, int> > counts;
0070     };
0071
0072     //output is a std::map<std::set<property_type>, polygon_45_set_data<Unit> >
0073     struct merge_45_output_functor {
0074       template <typename cT>
0075       void operator()(cT& output, const CountMerge& count1, const CountMerge& count2,
0076                       const Point& pt, int rise, direction_1d end) {
0077         typedef typename cT::key_type keytype;
0078         keytype left;
0079         keytype right;
0080         int edgeType = end == LOW ? -1 : 1;
0081         for(typename std::vector<std::pair<property_type, int> >::const_iterator itr = count1.counts.begin();
0082             itr != count1.counts.end(); ++itr) {
0083           left.insert(left.end(), (*itr).first);
0084         }
0085         for(typename std::vector<std::pair<property_type, int> >::const_iterator itr = count2.counts.begin();
0086             itr != count2.counts.end(); ++itr) {
0087           right.insert(right.end(), (*itr).first);
0088         }
0089         if(left == right) return;
0090         if(!left.empty()) {
0091           //std::cout << pt.x() << " " << pt.y() << " " << rise << " " << edgeType << std::endl;
0092           output[left].insert_clean(typename boolean_op_45<Unit>::Vertex45(pt, rise, -edgeType));
0093         }
0094         if(!right.empty()) {
0095           //std::cout << pt.x() << " " << pt.y() << " " << rise << " " << -edgeType << std::endl;
0096           output[right].insert_clean(typename boolean_op_45<Unit>::Vertex45(pt, rise, edgeType));
0097         }
0098       }
0099     };
0100
0101     typedef typename std::pair<Point,
0102                                typename boolean_op_45<Unit>::template Scan45CountT<CountMerge> > Vertex45Compact;
0103     typedef std::vector<Vertex45Compact> MergeSetData;
0104
0105     struct lessVertex45Compact {
0106       bool operator()(const Vertex45Compact& l, const Vertex45Compact& r) {
0107         return l.first < r.first;
0108       }
0109     };
0110
0111     template <typename output_type>
0112     static void performMerge(output_type& result, MergeSetData& tsd) {
0113
0114       polygon_sort(tsd.begin(), tsd.end(), lessVertex45Compact());
0115       typedef std::vector<std::pair<Point, typename boolean_op_45<Unit>::template Scan45CountT<CountMerge> > > TSD;
0116       TSD tsd_;
0117       tsd_.reserve(tsd.size());
0118       for(typename MergeSetData::iterator itr = tsd.begin(); itr != tsd.end(); ) {
0119         typename MergeSetData::iterator itr2 = itr;
0120         ++itr2;
0121         for(; itr2 != tsd.end() && itr2->first == itr->first; ++itr2) {
0122           (itr->second) += (itr2->second); //accumulate
0123         }
0124         tsd_.push_back(std::make_pair(itr->first, itr->second));
0125         itr = itr2;
0126       }
0127       typename boolean_op_45<Unit>::template Scan45<CountMerge, merge_45_output_functor> scanline;
0128       for(typename TSD::iterator itr = tsd_.begin(); itr != tsd_.end(); ) {
0129         typename TSD::iterator itr2 = itr;
0130         ++itr2;
0131         while(itr2 != tsd_.end() && itr2->first.x() == itr->first.x()) {
0132           ++itr2;
0133         }
0134         scanline.scan(result, itr, itr2);
0135         itr = itr2;
0136       }
0137     }
0138
0139     template <typename iT>
0140     static void populateMergeSetData(MergeSetData& tsd, iT begin, iT end, property_type property) {
0141       for( ; begin != end; ++begin) {
0142         Vertex45Compact vertex;
0143         vertex.first = typename Vertex45Compact::first_type(begin->pt.x() * 2, begin->pt.y() * 2);
0144         tsd.push_back(vertex);
0145         for(unsigned int i = 0; i < 4; ++i) {
0146           if(begin->count[i]) {
0147             tsd.back().second[i][property] += begin->count[i];
0148           }
0149         }
0150       }
0151     }
0152
0153   };
0154
0155
0156
0157 }
0158 }
0159
0160 #endif