git.sesse.net Git - casparcg/blob - dependencies/boost/boost/polygon/detail/property_merge.hpp

   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     gtlsort(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     gtlsort(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(currentVertex.first.x(), 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(currentVertex.first.x(), 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(coordinate_type x, 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