]>
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_PROPERTY_MERGE_HPP | |
9 | #define BOOST_POLYGON_PROPERTY_MERGE_HPP | |
10 | namespace boost { namespace polygon{ | |
11 | ||
12 | template <typename coordinate_type> | |
13 | class property_merge_point { | |
14 | private: | |
15 | coordinate_type x_, y_; | |
16 | public: | |
17 | inline property_merge_point() : x_(), y_() {} | |
18 | inline property_merge_point(coordinate_type x, coordinate_type y) : x_(x), y_(y) {} | |
19 | //use builtin assign and copy | |
20 | inline bool operator==(const property_merge_point& that) const { return x_ == that.x_ && y_ == that.y_; } | |
21 | inline bool operator!=(const property_merge_point& that) const { return !((*this) == that); } | |
22 | inline bool operator<(const property_merge_point& that) const { | |
23 | if(x_ < that.x_) return true; | |
24 | if(x_ > that.x_) return false; | |
25 | return y_ < that.y_; | |
26 | } | |
27 | inline coordinate_type x() const { return x_; } | |
28 | inline coordinate_type y() const { return y_; } | |
29 | inline void x(coordinate_type value) { x_ = value; } | |
30 | inline void y(coordinate_type value) { y_ = value; } | |
31 | }; | |
32 | ||
33 | template <typename coordinate_type> | |
34 | class property_merge_interval { | |
35 | private: | |
36 | coordinate_type low_, high_; | |
37 | public: | |
38 | inline property_merge_interval() : low_(), high_() {} | |
39 | inline property_merge_interval(coordinate_type low, coordinate_type high) : low_(low), high_(high) {} | |
40 | //use builtin assign and copy | |
41 | inline bool operator==(const property_merge_interval& that) const { return low_ == that.low_ && high_ == that.high_; } | |
42 | inline bool operator!=(const property_merge_interval& that) const { return !((*this) == that); } | |
43 | inline bool operator<(const property_merge_interval& that) const { | |
44 | if(low_ < that.low_) return true; | |
45 | if(low_ > that.low_) return false; | |
46 | return high_ < that.high_; | |
47 | } | |
48 | inline coordinate_type low() const { return low_; } | |
49 | inline coordinate_type high() const { return high_; } | |
50 | inline void low(coordinate_type value) { low_ = value; } | |
51 | inline void high(coordinate_type value) { high_ = value; } | |
52 | }; | |
53 | ||
54 | template <typename coordinate_type, typename property_type, typename polygon_set_type, typename keytype = std::set<property_type> > | |
55 | class merge_scanline { | |
56 | public: | |
57 | //definitions | |
58 | ||
59 | typedef keytype property_set; | |
60 | typedef std::vector<std::pair<property_type, int> > property_map; | |
61 | typedef std::pair<property_merge_point<coordinate_type>, std::pair<property_type, int> > vertex_property; | |
62 | typedef std::pair<property_merge_point<coordinate_type>, property_map> vertex_data; | |
63 | typedef std::vector<vertex_property> property_merge_data; | |
64 | //typedef std::map<property_set, polygon_set_type> Result; | |
65 | typedef std::map<coordinate_type, property_map> scanline_type; | |
66 | typedef typename scanline_type::iterator scanline_iterator; | |
67 | typedef std::pair<property_merge_interval<coordinate_type>, std::pair<property_set, property_set> > edge_property; | |
68 | typedef std::vector<edge_property> edge_property_vector; | |
69 | ||
70 | //static public member functions | |
71 | ||
72 | template <typename iT, typename orientation_2d_type> | |
73 | static inline void | |
74 | populate_property_merge_data(property_merge_data& pmd, iT input_begin, iT input_end, | |
75 | const property_type& property, orientation_2d_type orient) { | |
76 | for( ; input_begin != input_end; ++input_begin) { | |
77 | std::pair<property_merge_point<coordinate_type>, std::pair<property_type, int> > element; | |
78 | if(orient == HORIZONTAL) | |
79 | element.first = property_merge_point<coordinate_type>((*input_begin).second.first, (*input_begin).first); | |
80 | else | |
81 | element.first = property_merge_point<coordinate_type>((*input_begin).first, (*input_begin).second.first); | |
82 | element.second.first = property; | |
83 | element.second.second = (*input_begin).second.second; | |
84 | pmd.push_back(element); | |
85 | } | |
86 | } | |
87 | ||
88 | //public member functions | |
89 | ||
90 | merge_scanline() : output(), scanline(), currentVertex(), tmpVector(), previousY(), countFromBelow(), scanlinePosition() {} | |
91 | merge_scanline(const merge_scanline& that) : | |
92 | output(that.output), | |
93 | scanline(that.scanline), | |
94 | currentVertex(that.currentVertex), | |
95 | tmpVector(that.tmpVector), | |
96 | previousY(that.previousY), | |
97 | countFromBelow(that.countFromBelow), | |
98 | scanlinePosition(that.scanlinePosition) | |
99 | {} | |
100 | merge_scanline& operator=(const merge_scanline& that) { | |
101 | output = that.output; | |
102 | scanline = that.scanline; | |
103 | currentVertex = that.currentVertex; | |
104 | tmpVector = that.tmpVector; | |
105 | previousY = that.previousY; | |
106 | countFromBelow = that.countFromBelow; | |
107 | scanlinePosition = that.scanlinePosition; | |
108 | return *this; | |
109 | } | |
110 | ||
111 | template <typename result_type> | |
112 | inline void perform_merge(result_type& result, property_merge_data& data) { | |
113 | if(data.empty()) return; | |
114 | //sort | |
115 | polygon_sort(data.begin(), data.end(), less_vertex_data<vertex_property>()); | |
116 | //scanline | |
117 | bool firstIteration = true; | |
118 | scanlinePosition = scanline.end(); | |
119 | for(std::size_t i = 0; i < data.size(); ++i) { | |
120 | if(firstIteration) { | |
121 | mergeProperty(currentVertex.second, data[i].second); | |
122 | currentVertex.first = data[i].first; | |
123 | firstIteration = false; | |
124 | } else { | |
125 | if(data[i].first != currentVertex.first) { | |
126 | if(data[i].first.x() != currentVertex.first.x()) { | |
127 | processVertex(output); | |
128 | //std::cout << scanline.size() << " "; | |
129 | countFromBelow.clear(); //should already be clear | |
130 | writeOutput(currentVertex.first.x(), result, output); | |
131 | currentVertex.second.clear(); | |
132 | mergeProperty(currentVertex.second, data[i].second); | |
133 | currentVertex.first = data[i].first; | |
134 | //std::cout << assertRedundant(scanline) << "/" << scanline.size() << " "; | |
135 | } else { | |
136 | processVertex(output); | |
137 | currentVertex.second.clear(); | |
138 | mergeProperty(currentVertex.second, data[i].second); | |
139 | currentVertex.first = data[i].first; | |
140 | } | |
141 | } else { | |
142 | mergeProperty(currentVertex.second, data[i].second); | |
143 | } | |
144 | } | |
145 | } | |
146 | processVertex(output); | |
147 | writeOutput(currentVertex.first.x(), result, output); | |
148 | //std::cout << assertRedundant(scanline) << "/" << scanline.size() << "\n"; | |
149 | //std::cout << scanline.size() << "\n"; | |
150 | } | |
151 | ||
152 | private: | |
153 | //private supporting types | |
154 | ||
155 | template <class T> | |
156 | class less_vertex_data { | |
157 | public: | |
158 | less_vertex_data() {} | |
159 | bool operator()(const T& lvalue, const T& rvalue) const { | |
160 | if(lvalue.first.x() < rvalue.first.x()) return true; | |
161 | if(lvalue.first.x() > rvalue.first.x()) return false; | |
162 | if(lvalue.first.y() < rvalue.first.y()) return true; | |
163 | return false; | |
164 | } | |
165 | }; | |
166 | ||
167 | template <typename T> | |
168 | struct lessPropertyCount { | |
169 | lessPropertyCount() {} | |
170 | bool operator()(const T& a, const T& b) { | |
171 | return a.first < b.first; | |
172 | } | |
173 | }; | |
174 | ||
175 | //private static member functions | |
176 | ||
177 | static inline void mergeProperty(property_map& lvalue, std::pair<property_type, int>& rvalue) { | |
178 | typename property_map::iterator itr = std::lower_bound(lvalue.begin(), lvalue.end(), rvalue, | |
179 | lessPropertyCount<std::pair<property_type, int> >()); | |
180 | if(itr == lvalue.end() || | |
181 | (*itr).first != rvalue.first) { | |
182 | lvalue.insert(itr, rvalue); | |
183 | } else { | |
184 | (*itr).second += rvalue.second; | |
185 | if((*itr).second == 0) | |
186 | lvalue.erase(itr); | |
187 | } | |
188 | // if(assertSorted(lvalue)) { | |
189 | // std::cout << "in mergeProperty\n"; | |
190 | // exit(0); | |
191 | // } | |
192 | } | |
193 | ||
194 | // static inline bool assertSorted(property_map& pset) { | |
195 | // bool result = false; | |
196 | // for(std::size_t i = 1; i < pset.size(); ++i) { | |
197 | // if(pset[i] < pset[i-1]) { | |
198 | // std::cout << "Out of Order Error "; | |
199 | // result = true; | |
200 | // } | |
201 | // if(pset[i].first == pset[i-1].first) { | |
202 | // std::cout << "Duplicate Property Error "; | |
203 | // result = true; | |
204 | // } | |
205 | // if(pset[0].second == 0 || pset[1].second == 0) { | |
206 | // std::cout << "Empty Property Error "; | |
207 | // result = true; | |
208 | // } | |
209 | // } | |
210 | // return result; | |
211 | // } | |
212 | ||
213 | static inline void setProperty(property_set& pset, property_map& pmap) { | |
214 | for(typename property_map::iterator itr = pmap.begin(); itr != pmap.end(); ++itr) { | |
215 | if((*itr).second > 0) { | |
216 | pset.insert(pset.end(), (*itr).first); | |
217 | } | |
218 | } | |
219 | } | |
220 | ||
221 | //private data members | |
222 | ||
223 | edge_property_vector output; | |
224 | scanline_type scanline; | |
225 | vertex_data currentVertex; | |
226 | property_map tmpVector; | |
227 | coordinate_type previousY; | |
228 | property_map countFromBelow; | |
229 | scanline_iterator scanlinePosition; | |
230 | ||
231 | //private member functions | |
232 | ||
233 | inline void mergeCount(property_map& lvalue, property_map& rvalue) { | |
234 | typename property_map::iterator litr = lvalue.begin(); | |
235 | typename property_map::iterator ritr = rvalue.begin(); | |
236 | tmpVector.clear(); | |
237 | while(litr != lvalue.end() && ritr != rvalue.end()) { | |
238 | if((*litr).first <= (*ritr).first) { | |
239 | if(!tmpVector.empty() && | |
240 | (*litr).first == tmpVector.back().first) { | |
241 | tmpVector.back().second += (*litr).second; | |
242 | } else { | |
243 | tmpVector.push_back(*litr); | |
244 | } | |
245 | ++litr; | |
246 | } else if((*ritr).first <= (*litr).first) { | |
247 | if(!tmpVector.empty() && | |
248 | (*ritr).first == tmpVector.back().first) { | |
249 | tmpVector.back().second += (*ritr).second; | |
250 | } else { | |
251 | tmpVector.push_back(*ritr); | |
252 | } | |
253 | ++ritr; | |
254 | } | |
255 | } | |
256 | while(litr != lvalue.end()) { | |
257 | if(!tmpVector.empty() && | |
258 | (*litr).first == tmpVector.back().first) { | |
259 | tmpVector.back().second += (*litr).second; | |
260 | } else { | |
261 | tmpVector.push_back(*litr); | |
262 | } | |
263 | ++litr; | |
264 | } | |
265 | while(ritr != rvalue.end()) { | |
266 | if(!tmpVector.empty() && | |
267 | (*ritr).first == tmpVector.back().first) { | |
268 | tmpVector.back().second += (*ritr).second; | |
269 | } else { | |
270 | tmpVector.push_back(*ritr); | |
271 | } | |
272 | ++ritr; | |
273 | } | |
274 | lvalue.clear(); | |
275 | for(std::size_t i = 0; i < tmpVector.size(); ++i) { | |
276 | if(tmpVector[i].second != 0) { | |
277 | lvalue.push_back(tmpVector[i]); | |
278 | } | |
279 | } | |
280 | // if(assertSorted(lvalue)) { | |
281 | // std::cout << "in mergeCount\n"; | |
282 | // exit(0); | |
283 | // } | |
284 | } | |
285 | ||
286 | inline void processVertex(edge_property_vector& output) { | |
287 | if(!countFromBelow.empty()) { | |
288 | //we are processing an interval of change in scanline state between | |
289 | //previous vertex position and current vertex position where | |
290 | //count from below represents the change on the interval | |
291 | //foreach scanline element from previous to current we | |
292 | //write the interval on the scanline that is changing | |
293 | //the old value and the new value to output | |
294 | property_merge_interval<coordinate_type> currentInterval(previousY, currentVertex.first.y()); | |
295 | coordinate_type currentY = currentInterval.low(); | |
296 | if(scanlinePosition == scanline.end() || | |
297 | (*scanlinePosition).first != previousY) { | |
298 | scanlinePosition = scanline.lower_bound(previousY); | |
299 | } | |
300 | scanline_iterator previousScanlinePosition = scanlinePosition; | |
301 | ++scanlinePosition; | |
302 | while(scanlinePosition != scanline.end()) { | |
303 | coordinate_type elementY = (*scanlinePosition).first; | |
304 | if(elementY <= currentInterval.high()) { | |
305 | property_map& countOnLeft = (*previousScanlinePosition).second; | |
306 | edge_property element; | |
307 | output.push_back(element); | |
308 | output.back().first = property_merge_interval<coordinate_type>((*previousScanlinePosition).first, elementY); | |
309 | setProperty(output.back().second.first, countOnLeft); | |
310 | mergeCount(countOnLeft, countFromBelow); | |
311 | setProperty(output.back().second.second, countOnLeft); | |
312 | if(output.back().second.first == output.back().second.second) { | |
313 | output.pop_back(); //it was an internal vertical edge, not to be output | |
314 | } | |
315 | else if(output.size() > 1) { | |
316 | edge_property& secondToLast = output[output.size()-2]; | |
317 | if(secondToLast.first.high() == output.back().first.low() && | |
318 | secondToLast.second.first == output.back().second.first && | |
319 | secondToLast.second.second == output.back().second.second) { | |
320 | //merge output onto previous output because properties are | |
321 | //identical on both sides implying an internal horizontal edge | |
322 | secondToLast.first.high(output.back().first.high()); | |
323 | output.pop_back(); | |
324 | } | |
325 | } | |
326 | if(previousScanlinePosition == scanline.begin()) { | |
327 | if(countOnLeft.empty()) { | |
328 | scanline.erase(previousScanlinePosition); | |
329 | } | |
330 | } else { | |
331 | scanline_iterator tmpitr = previousScanlinePosition; | |
332 | --tmpitr; | |
333 | if((*tmpitr).second == (*previousScanlinePosition).second) | |
334 | scanline.erase(previousScanlinePosition); | |
335 | } | |
336 | ||
337 | } else if(currentY < currentInterval.high()){ | |
338 | //elementY > currentInterval.high() | |
339 | //split the interval between previous and current scanline elements | |
340 | std::pair<coordinate_type, property_map> elementScan; | |
341 | elementScan.first = currentInterval.high(); | |
342 | elementScan.second = (*previousScanlinePosition).second; | |
343 | scanlinePosition = scanline.insert(scanlinePosition, elementScan); | |
344 | continue; | |
345 | } else { | |
346 | break; | |
347 | } | |
348 | previousScanlinePosition = scanlinePosition; | |
349 | currentY = previousY = elementY; | |
350 | ++scanlinePosition; | |
351 | if(scanlinePosition == scanline.end() && | |
352 | currentY < currentInterval.high()) { | |
353 | //insert a new element for top of range | |
354 | std::pair<coordinate_type, property_map> elementScan; | |
355 | elementScan.first = currentInterval.high(); | |
356 | scanlinePosition = scanline.insert(scanline.end(), elementScan); | |
357 | } | |
358 | } | |
359 | if(scanlinePosition == scanline.end() && | |
360 | currentY < currentInterval.high()) { | |
361 | //handle case where we iterated to end of the scanline | |
362 | //we need to insert an element into the scanline at currentY | |
363 | //with property value coming from below | |
364 | //and another one at currentInterval.high() with empty property value | |
365 | mergeCount(scanline[currentY], countFromBelow); | |
366 | std::pair<coordinate_type, property_map> elementScan; | |
367 | elementScan.first = currentInterval.high(); | |
368 | scanline.insert(scanline.end(), elementScan); | |
369 | ||
370 | edge_property element; | |
371 | output.push_back(element); | |
372 | output.back().first = property_merge_interval<coordinate_type>(currentY, currentInterval.high()); | |
373 | setProperty(output.back().second.second, countFromBelow); | |
374 | mergeCount(countFromBelow, currentVertex.second); | |
375 | } else { | |
376 | mergeCount(countFromBelow, currentVertex.second); | |
377 | if(countFromBelow.empty()) { | |
378 | if(previousScanlinePosition == scanline.begin()) { | |
379 | if((*previousScanlinePosition).second.empty()) { | |
380 | scanline.erase(previousScanlinePosition); | |
381 | //previousScanlinePosition = scanline.end(); | |
382 | //std::cout << "ERASE_A "; | |
383 | } | |
384 | } else { | |
385 | scanline_iterator tmpitr = previousScanlinePosition; | |
386 | --tmpitr; | |
387 | if((*tmpitr).second == (*previousScanlinePosition).second) { | |
388 | scanline.erase(previousScanlinePosition); | |
389 | //previousScanlinePosition = scanline.end(); | |
390 | //std::cout << "ERASE_B "; | |
391 | } | |
392 | } | |
393 | } | |
394 | } | |
395 | } else { | |
396 | //count from below is empty, we are starting a new interval of change | |
397 | countFromBelow = currentVertex.second; | |
398 | scanlinePosition = scanline.lower_bound(currentVertex.first.y()); | |
399 | if(scanlinePosition != scanline.end()) { | |
400 | if((*scanlinePosition).first != currentVertex.first.y()) { | |
401 | if(scanlinePosition != scanline.begin()) { | |
402 | //decrement to get the lower position of the first interval this vertex intersects | |
403 | --scanlinePosition; | |
404 | //insert a new element into the scanline for the incoming vertex | |
405 | property_map& countOnLeft = (*scanlinePosition).second; | |
406 | std::pair<coordinate_type, property_map> element(currentVertex.first.y(), countOnLeft); | |
407 | scanlinePosition = scanline.insert(scanlinePosition, element); | |
408 | } else { | |
409 | property_map countOnLeft; | |
410 | std::pair<coordinate_type, property_map> element(currentVertex.first.y(), countOnLeft); | |
411 | scanlinePosition = scanline.insert(scanlinePosition, element); | |
412 | } | |
413 | } | |
414 | } else { | |
415 | property_map countOnLeft; | |
416 | std::pair<coordinate_type, property_map> element(currentVertex.first.y(), countOnLeft); | |
417 | scanlinePosition = scanline.insert(scanlinePosition, element); | |
418 | } | |
419 | } | |
420 | previousY = currentVertex.first.y(); | |
421 | } | |
422 | ||
423 | template <typename T> | |
424 | inline int assertRedundant(T& t) { | |
425 | if(t.empty()) return 0; | |
426 | int count = 0; | |
427 | typename T::iterator itr = t.begin(); | |
428 | if((*itr).second.empty()) | |
429 | ++count; | |
430 | typename T::iterator itr2 = itr; | |
431 | ++itr2; | |
432 | while(itr2 != t.end()) { | |
433 | if((*itr).second == (*itr2).second) | |
434 | ++count; | |
435 | itr = itr2; | |
436 | ++itr2; | |
437 | } | |
438 | return count; | |
439 | } | |
440 | ||
441 | template <typename T> | |
442 | inline void performExtract(T& result, property_merge_data& data) { | |
443 | if(data.empty()) return; | |
444 | //sort | |
445 | polygon_sort(data.begin(), data.end(), less_vertex_data<vertex_property>()); | |
446 | ||
447 | //scanline | |
448 | bool firstIteration = true; | |
449 | scanlinePosition = scanline.end(); | |
450 | for(std::size_t i = 0; i < data.size(); ++i) { | |
451 | if(firstIteration) { | |
452 | mergeProperty(currentVertex.second, data[i].second); | |
453 | currentVertex.first = data[i].first; | |
454 | firstIteration = false; | |
455 | } else { | |
456 | if(data[i].first != currentVertex.first) { | |
457 | if(data[i].first.x() != currentVertex.first.x()) { | |
458 | processVertex(output); | |
459 | //std::cout << scanline.size() << " "; | |
460 | countFromBelow.clear(); //should already be clear | |
461 | writeGraph(result, output, scanline); | |
462 | currentVertex.second.clear(); | |
463 | mergeProperty(currentVertex.second, data[i].second); | |
464 | currentVertex.first = data[i].first; | |
465 | } else { | |
466 | processVertex(output); | |
467 | currentVertex.second.clear(); | |
468 | mergeProperty(currentVertex.second, data[i].second); | |
469 | currentVertex.first = data[i].first; | |
470 | } | |
471 | } else { | |
472 | mergeProperty(currentVertex.second, data[i].second); | |
473 | } | |
474 | } | |
475 | } | |
476 | processVertex(output); | |
477 | writeGraph(result, output, scanline); | |
478 | //std::cout << scanline.size() << "\n"; | |
479 | } | |
480 | ||
481 | template <typename T> | |
482 | inline void insertEdges(T& graph, property_set& p1, property_set& p2) { | |
483 | for(typename property_set::iterator itr = p1.begin(); itr != p1.end(); ++itr) { | |
484 | for(typename property_set::iterator itr2 = p2.begin(); itr2 != p2.end(); ++itr2) { | |
485 | if(*itr != *itr2) { | |
486 | graph[*itr].insert(*itr2); | |
487 | graph[*itr2].insert(*itr); | |
488 | } | |
489 | } | |
490 | } | |
491 | } | |
492 | ||
493 | template <typename T> | |
494 | inline void propertySetAbove(coordinate_type y, property_set& ps, T& scanline) { | |
495 | ps.clear(); | |
496 | typename T::iterator itr = scanline.find(y); | |
497 | if(itr != scanline.end()) | |
498 | setProperty(ps, (*itr).second); | |
499 | } | |
500 | ||
501 | template <typename T> | |
502 | inline void propertySetBelow(coordinate_type y, property_set& ps, T& scanline) { | |
503 | ps.clear(); | |
504 | typename T::iterator itr = scanline.find(y); | |
505 | if(itr != scanline.begin()) { | |
506 | --itr; | |
507 | setProperty(ps, (*itr).second); | |
508 | } | |
509 | } | |
510 | ||
511 | template <typename T, typename T2> | |
512 | inline void writeGraph(T& graph, edge_property_vector& output, T2& scanline) { | |
513 | if(output.empty()) return; | |
514 | edge_property* previousEdgeP = &(output[0]); | |
515 | bool firstIteration = true; | |
516 | property_set ps; | |
517 | for(std::size_t i = 0; i < output.size(); ++i) { | |
518 | edge_property& previousEdge = *previousEdgeP; | |
519 | edge_property& edge = output[i]; | |
520 | if(previousEdge.first.high() == edge.first.low()) { | |
521 | //horizontal edge | |
522 | insertEdges(graph, edge.second.first, previousEdge.second.first); | |
523 | //corner 1 | |
524 | insertEdges(graph, edge.second.first, previousEdge.second.second); | |
525 | //other horizontal edge | |
526 | insertEdges(graph, edge.second.second, previousEdge.second.second); | |
527 | //corner 2 | |
528 | insertEdges(graph, edge.second.second, previousEdge.second.first); | |
529 | } else { | |
530 | if(!firstIteration){ | |
531 | //look up regions above previous edge | |
532 | propertySetAbove(previousEdge.first.high(), ps, scanline); | |
533 | insertEdges(graph, ps, previousEdge.second.first); | |
534 | insertEdges(graph, ps, previousEdge.second.second); | |
535 | } | |
536 | //look up regions below current edge in the scanline | |
537 | propertySetBelow(edge.first.high(), ps, scanline); | |
538 | insertEdges(graph, ps, edge.second.first); | |
539 | insertEdges(graph, ps, edge.second.second); | |
540 | } | |
541 | firstIteration = false; | |
542 | //vertical edge | |
543 | insertEdges(graph, edge.second.second, edge.second.first); | |
544 | //shared region to left | |
545 | insertEdges(graph, edge.second.second, edge.second.second); | |
546 | //shared region to right | |
547 | insertEdges(graph, edge.second.first, edge.second.first); | |
548 | previousEdgeP = &(output[i]); | |
549 | } | |
550 | edge_property& previousEdge = *previousEdgeP; | |
551 | propertySetAbove(previousEdge.first.high(), ps, scanline); | |
552 | insertEdges(graph, ps, previousEdge.second.first); | |
553 | insertEdges(graph, ps, previousEdge.second.second); | |
554 | output.clear(); | |
555 | } | |
556 | ||
557 | template <typename Result> | |
558 | inline void writeOutput(coordinate_type x, Result& result, edge_property_vector& output) { | |
559 | for(std::size_t i = 0; i < output.size(); ++i) { | |
560 | edge_property& edge = output[i]; | |
561 | //edge.second.first is the property set on the left of the edge | |
562 | if(!edge.second.first.empty()) { | |
563 | typename Result::iterator itr = result.find(edge.second.first); | |
564 | if(itr == result.end()) { | |
565 | std::pair<property_set, polygon_set_type> element(edge.second.first, polygon_set_type(VERTICAL)); | |
566 | itr = result.insert(result.end(), element); | |
567 | } | |
568 | std::pair<interval_data<coordinate_type>, int> element2(interval_data<coordinate_type>(edge.first.low(), edge.first.high()), -1); //right edge of figure | |
569 | (*itr).second.insert(x, element2); | |
570 | } | |
571 | if(!edge.second.second.empty()) { | |
572 | //edge.second.second is the property set on the right of the edge | |
573 | typename Result::iterator itr = result.find(edge.second.second); | |
574 | if(itr == result.end()) { | |
575 | std::pair<property_set, polygon_set_type> element(edge.second.second, polygon_set_type(VERTICAL)); | |
576 | itr = result.insert(result.end(), element); | |
577 | } | |
578 | std::pair<interval_data<coordinate_type>, int> element3(interval_data<coordinate_type>(edge.first.low(), edge.first.high()), 1); //left edge of figure | |
579 | (*itr).second.insert(x, element3); | |
580 | } | |
581 | } | |
582 | output.clear(); | |
583 | } | |
584 | }; | |
585 | ||
586 | } | |
587 | } | |
588 | #endif |