]>
Commit | Line | Data |
---|---|---|
7c673cae FG |
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> | |
19 | 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: | |
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; } | |
61 | inline CountTouch(const CountTouch& count) : counts(count.counts) {} | |
62 | inline bool operator==(const CountTouch& count) const { return counts == count.counts; } | |
63 | inline bool operator!=(const CountTouch& count) const { return !((*this) == count); } | |
64 | //inline CountTouch& operator=(int count) { counts[0] = counts[1] = count; return *this; } | |
65 | inline CountTouch& operator=(const CountTouch& count) { counts = count.counts; return *this; } | |
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 | // } | |
85 | inline CountTouch& operator+=(const CountTouch& count){ | |
86 | merge_property_maps(counts, count.counts, false); | |
87 | return *this; | |
88 | } | |
89 | inline CountTouch& operator-=(const CountTouch& count){ | |
90 | merge_property_maps(counts, count.counts, true); | |
91 | return *this; | |
92 | } | |
93 | inline CountTouch operator+(const CountTouch& count) const { | |
94 | return CountTouch(*this)+=count; | |
95 | } | |
96 | inline CountTouch operator-(const CountTouch& count) const { | |
97 | return CountTouch(*this)-=count; | |
98 | } | |
99 | 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> | |
111 | 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> | |
132 | 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 { | |
158 | 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> | |
189 | 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> | |
220 | 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 |