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