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: property_merge_point()17 inline property_merge_point() : x_(), y_() {} property_merge_point(coordinate_type x,coordinate_type y)18 inline property_merge_point(coordinate_type x, coordinate_type y) : x_(x), y_(y) {} 19 //use builtin assign and copy operator ==(const property_merge_point & that) const20 inline bool operator==(const property_merge_point& that) const { return x_ == that.x_ && y_ == that.y_; } operator !=(const property_merge_point & that) const21 inline bool operator!=(const property_merge_point& that) const { return !((*this) == that); } operator <(const property_merge_point & that) const22 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 } x() const27 inline coordinate_type x() const { return x_; } y() const28 inline coordinate_type y() const { return y_; } x(coordinate_type value)29 inline void x(coordinate_type value) { x_ = value; } y(coordinate_type 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: property_merge_interval()38 inline property_merge_interval() : low_(), high_() {} property_merge_interval(coordinate_type low,coordinate_type high)39 inline property_merge_interval(coordinate_type low, coordinate_type high) : low_(low), high_(high) {} 40 //use builtin assign and copy operator ==(const property_merge_interval & that) const41 inline bool operator==(const property_merge_interval& that) const { return low_ == that.low_ && high_ == that.high_; } operator !=(const property_merge_interval & that) const42 inline bool operator!=(const property_merge_interval& that) const { return !((*this) == that); } operator <(const property_merge_interval & that) const43 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 } low() const48 inline coordinate_type low() const { return low_; } high() const49 inline coordinate_type high() const { return high_; } low(coordinate_type value)50 inline void low(coordinate_type value) { low_ = value; } high(coordinate_type 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 populate_property_merge_data(property_merge_data & pmd,iT input_begin,iT input_end,const property_type & property,orientation_2d_type orient)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 merge_scanline()90 merge_scanline() : output(), scanline(), currentVertex(), tmpVector(), previousY(), countFromBelow(), scanlinePosition() {} merge_scanline(const merge_scanline & that)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 {} operator =(const merge_scanline & that)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> perform_merge(result_type & result,property_merge_data & data)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: less_vertex_data()158 less_vertex_data() {} operator ()(const T & lvalue,const T & rvalue) const159 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 { lessPropertyCountboost::polygon::merge_scanline::lessPropertyCount169 lessPropertyCount() {} operator ()boost::polygon::merge_scanline::lessPropertyCount170 bool operator()(const T& a, const T& b) { 171 return a.first < b.first; 172 } 173 }; 174 175 //private static member functions 176 mergeProperty(property_map & lvalue,std::pair<property_type,int> & rvalue)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 setProperty(property_set & pset,property_map & pmap)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 mergeCount(property_map & lvalue,property_map & rvalue)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 processVertex(edge_property_vector & output)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> assertRedundant(T & 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> performExtract(T & result,property_merge_data & data)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> insertEdges(T & graph,property_set & p1,property_set & p2)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> propertySetAbove(coordinate_type y,property_set & ps,T & scanline)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> propertySetBelow(coordinate_type y,property_set & ps,T & scanline)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> writeGraph(T & graph,edge_property_vector & output,T2 & scanline)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> writeOutput(coordinate_type x,Result & result,edge_property_vector & output)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 589