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