]>
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_RECTANGLE_FORMATION_HPP | |
9 | #define BOOST_POLYGON_RECTANGLE_FORMATION_HPP | |
10 | namespace boost { namespace polygon{ | |
11 | ||
12 | namespace rectangle_formation { | |
13 | template <class T> | |
14 | class ScanLineToRects { | |
15 | public: | |
16 | typedef T rectangle_type; | |
17 | typedef typename rectangle_traits<T>::coordinate_type coordinate_type; | |
18 | typedef rectangle_data<coordinate_type> scan_rect_type; | |
19 | private: | |
20 | ||
21 | typedef std::set<scan_rect_type, less_rectangle_concept<scan_rect_type, scan_rect_type> > ScanData; | |
22 | ScanData scanData_; | |
23 | bool haveCurrentRect_; | |
24 | scan_rect_type currentRect_; | |
25 | orientation_2d orient_; | |
26 | typename rectangle_traits<T>::coordinate_type currentCoordinate_; | |
27 | public: | |
28 | inline ScanLineToRects() : scanData_(), haveCurrentRect_(), currentRect_(), orient_(), currentCoordinate_() {} | |
29 | ||
30 | inline ScanLineToRects(orientation_2d orient, rectangle_type model) : | |
31 | scanData_(orientation_2d(orient.to_int() ? VERTICAL : HORIZONTAL)), | |
32 | haveCurrentRect_(false), currentRect_(), orient_(orient), currentCoordinate_() { | |
33 | assign(currentRect_, model); | |
34 | currentCoordinate_ = (std::numeric_limits<coordinate_type>::max)(); | |
35 | } | |
36 | ||
37 | template <typename CT> | |
38 | inline ScanLineToRects& processEdge(CT& rectangles, const interval_data<coordinate_type>& edge); | |
39 | ||
40 | inline ScanLineToRects& nextMajorCoordinate(coordinate_type currentCoordinate) { | |
41 | if(haveCurrentRect_) { | |
42 | scanData_.insert(scanData_.end(), currentRect_); | |
43 | haveCurrentRect_ = false; | |
44 | } | |
45 | currentCoordinate_ = currentCoordinate; | |
46 | return *this; | |
47 | } | |
48 | ||
49 | }; | |
50 | ||
51 | template <class CT, class ST, class rectangle_type, typename interval_type, typename coordinate_type> inline CT& | |
52 | processEdge_(CT& rectangles, ST& scanData, const interval_type& edge, | |
53 | bool& haveCurrentRect, rectangle_type& currentRect, coordinate_type currentCoordinate, orientation_2d orient) | |
54 | { | |
55 | typedef typename CT::value_type result_type; | |
56 | bool edgeProcessed = false; | |
57 | if(!scanData.empty()) { | |
58 | ||
59 | //process all rectangles in the scanData that touch the edge | |
60 | typename ST::iterator dataIter = scanData.lower_bound(rectangle_type(edge, edge)); | |
61 | //decrement beginIter until its low is less than edge's low | |
62 | while((dataIter == scanData.end() || (*dataIter).get(orient).get(LOW) > edge.get(LOW)) && | |
63 | dataIter != scanData.begin()) | |
64 | { | |
65 | --dataIter; | |
66 | } | |
67 | //process each rectangle until the low end of the rectangle | |
68 | //is greater than the high end of the edge | |
69 | while(dataIter != scanData.end() && | |
70 | (*dataIter).get(orient).get(LOW) <= edge.get(HIGH)) | |
71 | { | |
72 | const rectangle_type& rect = *dataIter; | |
73 | //if the rectangle data intersects the edge at all | |
74 | if(rect.get(orient).get(HIGH) >= edge.get(LOW)) { | |
75 | if(contains(rect.get(orient), edge, true)) { | |
76 | //this is a closing edge | |
77 | //we need to write out the intersecting rectangle and | |
78 | //insert between 0 and 2 rectangles into the scanData | |
79 | //write out rectangle | |
80 | rectangle_type tmpRect = rect; | |
81 | ||
82 | if(rect.get(orient.get_perpendicular()).get(LOW) < currentCoordinate) { | |
83 | //set the high coordinate perpedicular to slicing orientation | |
84 | //to the current coordinate of the scan event | |
85 | tmpRect.set(orient.get_perpendicular().get_direction(HIGH), | |
86 | currentCoordinate); | |
87 | result_type result; | |
88 | assign(result, tmpRect); | |
89 | rectangles.insert(rectangles.end(), result); | |
90 | } | |
91 | //erase the rectangle from the scan data | |
92 | typename ST::iterator nextIter = dataIter; | |
93 | ++nextIter; | |
94 | scanData.erase(dataIter); | |
95 | if(tmpRect.get(orient).get(LOW) < edge.get(LOW)) { | |
96 | //insert a rectangle for the overhang of the bottom | |
97 | //of the rectangle back into scan data | |
98 | rectangle_type lowRect(tmpRect); | |
99 | lowRect.set(orient.get_perpendicular(), interval_data<coordinate_type>(currentCoordinate, | |
100 | currentCoordinate)); | |
101 | lowRect.set(orient.get_direction(HIGH), edge.get(LOW)); | |
102 | scanData.insert(nextIter, lowRect); | |
103 | } | |
104 | if(tmpRect.get(orient).get(HIGH) > edge.get(HIGH)) { | |
105 | //insert a rectangle for the overhang of the top | |
106 | //of the rectangle back into scan data | |
107 | rectangle_type highRect(tmpRect); | |
108 | highRect.set(orient.get_perpendicular(), interval_data<coordinate_type>(currentCoordinate, | |
109 | currentCoordinate)); | |
110 | highRect.set(orient.get_direction(LOW), edge.get(HIGH)); | |
111 | scanData.insert(nextIter, highRect); | |
112 | } | |
113 | //we are done with this edge | |
114 | edgeProcessed = true; | |
115 | break; | |
116 | } else { | |
117 | //it must be an opening edge | |
118 | //assert that rect does not overlap the edge but only touches | |
119 | //write out rectangle | |
120 | rectangle_type tmpRect = rect; | |
121 | //set the high coordinate perpedicular to slicing orientation | |
122 | //to the current coordinate of the scan event | |
123 | if(tmpRect.get(orient.get_perpendicular().get_direction(LOW)) < currentCoordinate) { | |
124 | tmpRect.set(orient.get_perpendicular().get_direction(HIGH), | |
125 | currentCoordinate); | |
126 | result_type result; | |
127 | assign(result, tmpRect); | |
128 | rectangles.insert(rectangles.end(), result); | |
129 | } | |
130 | //erase the rectangle from the scan data | |
131 | typename ST::iterator nextIter = dataIter; | |
132 | ++nextIter; | |
133 | scanData.erase(dataIter); | |
134 | dataIter = nextIter; | |
135 | if(haveCurrentRect) { | |
136 | if(currentRect.get(orient).get(HIGH) >= edge.get(LOW)){ | |
137 | if(!edgeProcessed && currentRect.get(orient.get_direction(HIGH)) > edge.get(LOW)){ | |
138 | rectangle_type tmpRect2(currentRect); | |
139 | tmpRect2.set(orient.get_direction(HIGH), edge.get(LOW)); | |
140 | scanData.insert(nextIter, tmpRect2); | |
141 | if(currentRect.get(orient.get_direction(HIGH)) > edge.get(HIGH)) { | |
142 | currentRect.set(orient, interval_data<coordinate_type>(edge.get(HIGH), currentRect.get(orient.get_direction(HIGH)))); | |
143 | } else { | |
144 | haveCurrentRect = false; | |
145 | } | |
146 | } else { | |
147 | //extend the top of current rect | |
148 | currentRect.set(orient.get_direction(HIGH), | |
149 | (std::max)(edge.get(HIGH), | |
150 | tmpRect.get(orient.get_direction(HIGH)))); | |
151 | } | |
152 | } else { | |
153 | //insert current rect into the scanData | |
154 | scanData.insert(nextIter, currentRect); | |
155 | //create a new current rect | |
156 | currentRect.set(orient.get_perpendicular(), interval_data<coordinate_type>(currentCoordinate, | |
157 | currentCoordinate)); | |
158 | currentRect.set(orient, interval_data<coordinate_type>((std::min)(tmpRect.get(orient).get(LOW), | |
159 | edge.get(LOW)), | |
160 | (std::max)(tmpRect.get(orient).get(HIGH), | |
161 | edge.get(HIGH)))); | |
162 | } | |
163 | } else { | |
164 | haveCurrentRect = true; | |
165 | currentRect.set(orient.get_perpendicular(), interval_data<coordinate_type>(currentCoordinate, | |
166 | currentCoordinate)); | |
167 | currentRect.set(orient, interval_data<coordinate_type>((std::min)(tmpRect.get(orient).get(LOW), | |
168 | edge.get(LOW)), | |
169 | (std::max)(tmpRect.get(orient).get(HIGH), | |
170 | edge.get(HIGH)))); | |
171 | } | |
172 | //skip to nextIter position | |
173 | edgeProcessed = true; | |
174 | continue; | |
175 | } | |
176 | //edgeProcessed = true; | |
177 | } | |
178 | ++dataIter; | |
179 | } //end while edge intersects rectangle data | |
180 | ||
181 | } | |
182 | if(!edgeProcessed) { | |
183 | if(haveCurrentRect) { | |
184 | if(currentRect.get(orient.get_perpendicular().get_direction(HIGH)) | |
185 | == currentCoordinate && | |
186 | currentRect.get(orient.get_direction(HIGH)) >= edge.get(LOW)) | |
187 | { | |
188 | if(currentRect.get(orient.get_direction(HIGH)) > edge.get(LOW)){ | |
189 | rectangle_type tmpRect(currentRect); | |
190 | tmpRect.set(orient.get_direction(HIGH), edge.get(LOW)); | |
191 | scanData.insert(scanData.end(), tmpRect); | |
192 | if(currentRect.get(orient.get_direction(HIGH)) > edge.get(HIGH)) { | |
193 | currentRect.set(orient, | |
194 | interval_data<coordinate_type>(edge.get(HIGH), | |
195 | currentRect.get(orient.get_direction(HIGH)))); | |
196 | return rectangles; | |
197 | } else { | |
198 | haveCurrentRect = false; | |
199 | return rectangles; | |
200 | } | |
201 | } | |
202 | //extend current rect | |
203 | currentRect.set(orient.get_direction(HIGH), edge.get(HIGH)); | |
204 | return rectangles; | |
205 | } | |
206 | scanData.insert(scanData.end(), currentRect); | |
207 | haveCurrentRect = false; | |
208 | } | |
209 | rectangle_type tmpRect(currentRect); | |
210 | tmpRect.set(orient.get_perpendicular(), interval_data<coordinate_type>(currentCoordinate, | |
211 | currentCoordinate)); | |
212 | tmpRect.set(orient, edge); | |
213 | scanData.insert(tmpRect); | |
214 | return rectangles; | |
215 | } | |
216 | return rectangles; | |
217 | ||
218 | } | |
219 | ||
220 | template <class T> | |
221 | template <class CT> | |
222 | inline | |
223 | ScanLineToRects<T>& ScanLineToRects<T>::processEdge(CT& rectangles, const interval_data<coordinate_type>& edge) | |
224 | { | |
225 | processEdge_(rectangles, scanData_, edge, haveCurrentRect_, currentRect_, currentCoordinate_, orient_); | |
226 | return *this; | |
227 | } | |
228 | ||
229 | ||
230 | } //namespace rectangle_formation | |
231 | ||
232 | template <typename T, typename T2> | |
233 | struct get_coordinate_type_for_rectangles { | |
234 | typedef typename polygon_traits<T>::coordinate_type type; | |
235 | }; | |
236 | template <typename T> | |
237 | struct get_coordinate_type_for_rectangles<T, rectangle_concept> { | |
238 | typedef typename rectangle_traits<T>::coordinate_type type; | |
239 | }; | |
240 | ||
241 | template <typename output_container, typename iterator_type, typename rectangle_concept> | |
242 | void form_rectangles(output_container& output, iterator_type begin, iterator_type end, | |
243 | orientation_2d orient, rectangle_concept ) { | |
244 | typedef typename output_container::value_type rectangle_type; | |
245 | typedef typename get_coordinate_type_for_rectangles<rectangle_type, typename geometry_concept<rectangle_type>::type>::type Unit; | |
246 | rectangle_data<Unit> model; | |
247 | Unit prevPos = (std::numeric_limits<Unit>::max)(); | |
248 | rectangle_formation::ScanLineToRects<rectangle_data<Unit> > scanlineToRects(orient, model); | |
249 | for(iterator_type itr = begin; | |
250 | itr != end; ++ itr) { | |
251 | Unit pos = (*itr).first; | |
252 | if(pos != prevPos) { | |
253 | scanlineToRects.nextMajorCoordinate(pos); | |
254 | prevPos = pos; | |
255 | } | |
256 | Unit lowy = (*itr).second.first; | |
257 | iterator_type tmp_itr = itr; | |
258 | ++itr; | |
259 | Unit highy = (*itr).second.first; | |
260 | scanlineToRects.processEdge(output, interval_data<Unit>(lowy, highy)); | |
261 | if(std::abs((*itr).second.second) > 1) itr = tmp_itr; //next edge begins from this vertex | |
262 | } | |
263 | } | |
264 | } | |
265 | } | |
266 | #endif |