[Boost-commit] svn:boost r47499 - sandbox/gtl/gtl

From: lucanus.j.simonson_at_[hidden]
Date: 2008-07-16 20:25:30

Author: ljsimons
Date: 2008-07-16 20:25:30 EDT (Wed, 16 Jul 2008)
New Revision: 47499
URL: http://svn.boost.org/trac/boost/changeset/47499

Log:
added scanline property merge algorithm
Added:
   sandbox/gtl/gtl/property_merge.hpp   (contents, props changed)

Added: sandbox/gtl/gtl/property_merge.hpp
==============================================================================
--- (empty file)
+++ sandbox/gtl/gtl/property_merge.hpp	2008-07-16 20:25:30 EDT (Wed, 16 Jul 2008)
@@ -0,0 +1,587 @@
+/*
+  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 GTL_PROPERTY_MERGE_HPP
+#define GTL_PROPERTY_MERGE_HPP
+namespace gtl {
+
+template <typename coordinate_type>
+class property_merge_point {
+private:
+  coordinate_type x_, y_;
+public:
+  inline property_merge_point() {}
+  inline property_merge_point(coordinate_type x, coordinate_type y) : x_(x), y_(y) {}
+  //use builtin assign and copy
+  inline bool operator==(const property_merge_point& that) const { return x_ == that.x_ && y_ == that.y_; }
+  inline bool operator!=(const property_merge_point& that) const { return !((*this) == that); }
+  inline bool operator<(const property_merge_point& that) const {
+    if(x_ < that.x_) return true;
+    if(x_ > that.x_) return false;
+    return y_ < that.y_;
+  }
+  inline coordinate_type x() const { return x_; }
+  inline coordinate_type y() const { return y_; }
+  inline void x(coordinate_type value) { x_ = value; }
+  inline void y(coordinate_type value) { y_ = value; }
+};
+
+template <typename coordinate_type>
+class property_merge_interval {
+private:
+  coordinate_type low_, high_;
+public:
+  inline property_merge_interval() {}
+  inline property_merge_interval(coordinate_type low, coordinate_type high) : low_(low), high_(high) {}
+  //use builtin assign and copy
+  inline bool operator==(const property_merge_interval& that) const { return low_ == that.low_ && high_ == that.high_; }
+  inline bool operator!=(const property_merge_interval& that) const { return !((*this) == that); }
+  inline bool operator<(const property_merge_interval& that) const {
+    if(low_ < that.low_) return true;
+    if(low_ > that.low_) return false;
+    return high_ < that.high_;
+  }
+  inline coordinate_type low() const { return low_; }
+  inline coordinate_type high() const { return high_; }
+  inline void low(coordinate_type value) { low_ = value; }
+  inline void high(coordinate_type value) { high_ = value; }
+};
+
+template <typename coordinate_type, typename property_type, typename polygon_set_type, typename keytype = std::set<property_type> >
+class merge_scanline {
+public:
+  //definitions
+
+  typedef keytype property_set;
+  typedef std::vector<std::pair<property_type, int> > property_map;
+  typedef std::pair<property_merge_point<coordinate_type>, std::pair<property_type, int> > vertex_property;
+  typedef std::pair<property_merge_point<coordinate_type>, property_map> vertex_data;
+  typedef std::vector<vertex_property> property_merge_data;
+  //typedef std::map<property_set, polygon_set_type> Result;
+  typedef std::map<coordinate_type, property_map> scanline_type;
+  typedef typename scanline_type::iterator scanline_iterator;
+  typedef std::pair<property_merge_interval<coordinate_type>, std::pair<property_set, property_set> > edge_property;
+  typedef std::vector<edge_property> edge_property_vector;
+
+  //static public member functions
+
+  template <typename iT, typename orientation_2d_type>
+  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) {
+    for( ; input_begin != input_end; ++input_begin) {
+      std::pair<property_merge_point<coordinate_type>, std::pair<property_type, int> > element;
+      if(orient == HORIZONTAL)
+        element.first = property_merge_point<coordinate_type>((*input_begin).second.first, (*input_begin).first);
+      else
+        element.first = property_merge_point<coordinate_type>((*input_begin).first, (*input_begin).second.first);
+      element.second.first = property;
+      element.second.second = (*input_begin).second.second;
+      pmd.push_back(element);
+    }
+  }
+
+  //public member functions
+
+  merge_scanline() {}
+  merge_scanline(const merge_scanline& that) :
+    output(that.output),
+    scanline(that.scanline),
+    currentVertex(that.currentVertex),
+    tmpVector(that.tmpVector),
+    previousY(that.previousY),
+    countFromBelow(that.countFromBelow),
+    scanlinePosition(that.scanlinePosition)
+  {}
+  merge_scanline& operator=(const merge_scanline& that) {
+    output = that.output;
+    scanline = that.scanline;
+    currentVertex = that.currentVertex;
+    tmpVector = that.tmpVector;
+    previousY = that.previousY;
+    countFromBelow = that.countFromBelow;
+    scanlinePosition = that.scanlinePosition;
+  }
+
+  template <typename result_type>
+  inline void perform_merge(result_type& result, property_merge_data& data) {
+    if(data.empty()) return;
+    //sort
+    std::sort(data.begin(), data.end(), less_vertex_data<vertex_property>());
+    //scanline
+    bool firstIteration = true;
+    scanlinePosition = scanline.end();
+    for(unsigned int i = 0; i < data.size(); ++i) {
+      if(firstIteration) {
+        mergeProperty(currentVertex.second, data[i].second);
+        currentVertex.first = data[i].first;
+        firstIteration = false;
+      } else {
+        if(data[i].first != currentVertex.first) {
+          if(data[i].first.x() != currentVertex.first.x()) {
+            processVertex(output);
+            //std::cout << scanline.size() << " ";
+            countFromBelow.clear(); //should already be clear
+            writeOutput(currentVertex.first.x(), result, output);
+            currentVertex.second.clear();
+            mergeProperty(currentVertex.second, data[i].second);
+            currentVertex.first = data[i].first;
+            //std::cout << assertRedundant(scanline) << "/" << scanline.size() << " ";
+          } else {
+            processVertex(output);
+            currentVertex.second.clear();
+            mergeProperty(currentVertex.second, data[i].second);
+            currentVertex.first = data[i].first;
+          }
+        } else {
+          mergeProperty(currentVertex.second, data[i].second);
+        }
+      }
+    }
+    processVertex(output);
+    writeOutput(currentVertex.first.x(), result, output);
+    //std::cout << assertRedundant(scanline) << "/" << scanline.size() << "\n";
+    //std::cout << scanline.size() << "\n";
+  }
+
+private:
+  //private supporting types
+
+  template <class T>
+  class less_vertex_data {
+  public:
+    less_vertex_data() {}
+    bool operator()(const T& lvalue, const T& rvalue) {
+      if(lvalue.first.x() < rvalue.first.x()) return true;
+      if(lvalue.first.x() > rvalue.first.x()) return false;
+      if(lvalue.first.y() < rvalue.first.y()) return true;
+      return false;
+    }
+  };
+
+  template <typename T>
+  struct lessPropertyCount {
+    lessPropertyCount() {}
+    bool operator()(const T& a, const T& b) {
+      return a.first < b.first;
+    }
+  };
+
+  //private static member functions
+
+  static inline void mergeProperty(property_map& lvalue, std::pair<property_type, int>& rvalue) {
+    typename property_map::iterator itr = std::lower_bound(lvalue.begin(), lvalue.end(), rvalue, 
+                                                          lessPropertyCount<std::pair<property_type, int> >());
+    if(itr == lvalue.end() ||
+       (*itr).first != rvalue.first) {
+      lvalue.insert(itr, rvalue);
+    } else {
+      (*itr).second += rvalue.second;
+      if((*itr).second == 0)
+        lvalue.erase(itr);
+    }
+//     if(assertSorted(lvalue)) {
+//       std::cout << "in mergeProperty\n";
+//       exit(0);
+//     }
+  }
+
+  static inline bool assertSorted(property_map& pset) {
+    bool result = false;
+    for(unsigned int i = 1; i < pset.size(); ++i) {
+      if(pset[i] < pset[i-1]) {
+        std::cout << "Out of Order Error ";
+        result = true;
+      }
+      if(pset[i].first == pset[i-1].first) {
+        std::cout << "Duplicate Property Error ";
+        result = true;
+      }
+      if(pset[0].second == 0 || pset[1].second == 0) {
+        std::cout << "Empty Property Error ";
+        result = true;
+      }
+    }
+    return result;
+  }
+
+  static inline void setProperty(property_set& pset, property_map& pmap) {
+    for(typename property_map::iterator itr = pmap.begin(); itr != pmap.end(); ++itr) {
+      if((*itr).second > 0) {
+        pset.insert(pset.end(), (*itr).first);
+      }
+    }
+  }
+
+  //private data members
+
+  edge_property_vector output;
+  scanline_type scanline;
+  vertex_data currentVertex;
+  property_map tmpVector;
+  coordinate_type previousY;
+  property_map countFromBelow;
+  scanline_iterator scanlinePosition;
+
+  //private member functions
+
+  inline void mergeCount(property_map& lvalue, property_map& rvalue) {
+    typename property_map::iterator litr = lvalue.begin();
+    typename property_map::iterator ritr = rvalue.begin();
+    tmpVector.clear();
+    while(litr != lvalue.end() && ritr != rvalue.end()) {
+      if((*litr).first <= (*ritr).first) {
+        if(!tmpVector.empty() &&
+           (*litr).first == tmpVector.back().first) {
+          tmpVector.back().second += (*litr).second;
+        } else {
+          tmpVector.push_back(*litr);
+        }
+        ++litr;
+      } else if((*ritr).first <= (*litr).first) {
+        if(!tmpVector.empty() &&
+           (*ritr).first == tmpVector.back().first) {
+          tmpVector.back().second += (*ritr).second;
+        } else {
+          tmpVector.push_back(*ritr);
+        }
+        ++ritr;
+      }
+    }
+    while(litr != lvalue.end()) {
+      if(!tmpVector.empty() &&
+         (*litr).first == tmpVector.back().first) {
+        tmpVector.back().second += (*litr).second;
+      } else {
+        tmpVector.push_back(*litr);
+      }
+      ++litr;
+    }
+    while(ritr != rvalue.end()) {
+      if(!tmpVector.empty() &&
+         (*ritr).first == tmpVector.back().first) {
+        tmpVector.back().second += (*ritr).second;
+      } else {
+        tmpVector.push_back(*ritr);
+      }
+      ++ritr;
+    }
+    lvalue.clear();
+    for(unsigned int i = 0; i < tmpVector.size(); ++i) {
+      if(tmpVector[i].second != 0) {
+        lvalue.push_back(tmpVector[i]);
+      }
+    }
+//     if(assertSorted(lvalue)) {
+//       std::cout << "in mergeCount\n";
+//       exit(0);
+//     }
+  }
+
+  inline void processVertex(edge_property_vector& output) {
+    if(!countFromBelow.empty()) {
+      //we are processing an interval of change in scanline state between
+      //previous vertex position and current vertex position where 
+      //count from below represents the change on the interval
+      //foreach scanline element from previous to current we
+      //write the interval on the scanline that is changing
+      //the old value and the new value to output
+      property_merge_interval<coordinate_type> currentInterval(previousY, currentVertex.first.y());
+      coordinate_type currentY = currentInterval.low();
+      if(scanlinePosition == scanline.end() ||
+         (*scanlinePosition).first != previousY) {
+        scanlinePosition = scanline.lower_bound(previousY);
+      }
+      scanline_iterator previousScanlinePosition = scanlinePosition;
+      ++scanlinePosition;
+      while(scanlinePosition != scanline.end()) {
+        coordinate_type elementY = (*scanlinePosition).first;
+        if(elementY <= currentInterval.high()) {
+          property_map& countOnLeft = (*previousScanlinePosition).second;
+          edge_property element;
+          output.push_back(element);
+          output.back().first = property_merge_interval<coordinate_type>((*previousScanlinePosition).first, elementY);
+          setProperty(output.back().second.first, countOnLeft);
+          mergeCount(countOnLeft, countFromBelow);
+          setProperty(output.back().second.second, countOnLeft);
+          if(output.back().second.first == output.back().second.second) {
+            output.pop_back(); //it was an internal vertical edge, not to be output
+          }
+          else if(output.size() > 1) {
+            edge_property& secondToLast = output[output.size()-2];
+            if(secondToLast.first.high() == output.back().first.low() &&
+               secondToLast.second.first == output.back().second.first &&
+               secondToLast.second.second == output.back().second.second) {
+              //merge output onto previous output because properties are
+              //identical on both sides implying an internal horizontal edge
+              secondToLast.first.high(output.back().first.high());
+              output.pop_back();
+            }
+          }
+          if(previousScanlinePosition == scanline.begin()) {
+            if(countOnLeft.empty()) {
+              scanline.erase(previousScanlinePosition);
+            }
+          } else {
+            scanline_iterator tmpitr = previousScanlinePosition;
+            --tmpitr;
+            if((*tmpitr).second == (*previousScanlinePosition).second)
+              scanline.erase(previousScanlinePosition);
+          }
+             
+        } else if(currentY < currentInterval.high()){
+          //elementY > currentInterval.high()
+          //split the interval between previous and current scanline elements
+          std::pair<coordinate_type, property_map> elementScan;
+          elementScan.first = currentInterval.high();
+          elementScan.second = (*previousScanlinePosition).second;
+          scanlinePosition = scanline.insert(scanlinePosition, elementScan);
+          continue;
+        } else {
+          break;
+        }
+        previousScanlinePosition = scanlinePosition;
+        currentY = previousY = elementY;
+        ++scanlinePosition;
+        if(scanlinePosition == scanline.end() &&
+           currentY < currentInterval.high()) {
+          //insert a new element for top of range
+          std::pair<coordinate_type, property_map> elementScan;
+          elementScan.first = currentInterval.high();
+          scanlinePosition = scanline.insert(scanline.end(), elementScan);
+        } 
+      }
+      if(scanlinePosition == scanline.end() &&
+         currentY < currentInterval.high()) {
+        //handle case where we iterated to end of the scanline
+        //we need to insert an element into the scanline at currentY
+        //with property value coming from below
+        //and another one at currentInterval.high() with empty property value
+        mergeCount(scanline[currentY], countFromBelow);
+        std::pair<coordinate_type, property_map> elementScan;
+        elementScan.first = currentInterval.high();
+        scanline.insert(scanline.end(), elementScan);
+
+        edge_property element;
+        output.push_back(element);
+        output.back().first = property_merge_interval<coordinate_type>(currentY, currentInterval.high());
+        setProperty(output.back().second.second, countFromBelow);
+        mergeCount(countFromBelow, currentVertex.second);
+      } else {
+        mergeCount(countFromBelow, currentVertex.second);
+        if(countFromBelow.empty()) {
+          if(previousScanlinePosition == scanline.begin()) {
+            if((*previousScanlinePosition).second.empty()) {
+              scanline.erase(previousScanlinePosition);
+              //previousScanlinePosition = scanline.end();
+              //std::cout << "ERASE_A ";
+            }
+          } else {
+            scanline_iterator tmpitr = previousScanlinePosition;
+            --tmpitr;
+            if((*tmpitr).second == (*previousScanlinePosition).second) {
+              scanline.erase(previousScanlinePosition);
+              //previousScanlinePosition = scanline.end();
+              //std::cout << "ERASE_B ";
+            }
+          }
+        }
+      }
+    } else {
+      //count from below is empty, we are starting a new interval of change
+      countFromBelow = currentVertex.second;
+      scanlinePosition = scanline.lower_bound(currentVertex.first.y());
+      if(scanlinePosition != scanline.end()) {
+        if((*scanlinePosition).first != currentVertex.first.y()) {
+          if(scanlinePosition != scanline.begin()) {
+            //decrement to get the lower position of the first interval this vertex intersects
+            --scanlinePosition;
+            //insert a new element into the scanline for the incoming vertex
+            property_map& countOnLeft = (*scanlinePosition).second;
+            std::pair<coordinate_type, property_map> element(currentVertex.first.y(), countOnLeft);
+            scanlinePosition = scanline.insert(scanlinePosition, element);
+          } else {
+            property_map countOnLeft;
+            std::pair<coordinate_type, property_map> element(currentVertex.first.y(), countOnLeft);
+            scanlinePosition = scanline.insert(scanlinePosition, element);
+          }
+        }
+      } else {
+        property_map countOnLeft;
+        std::pair<coordinate_type, property_map> element(currentVertex.first.y(), countOnLeft);
+        scanlinePosition = scanline.insert(scanlinePosition, element);
+      }
+    }
+    previousY = currentVertex.first.y();
+  }
+
+  template <typename T>
+  inline int assertRedundant(T& t) {
+    if(t.empty()) return 0;
+    int count = 0; 
+    typename T::iterator itr = t.begin();
+    if((*itr).second.empty())
+      ++count;
+    typename T::iterator itr2 = itr;
+    ++itr2;
+    while(itr2 != t.end()) {
+      if((*itr).second == (*itr2).second)
+        ++count;
+      itr = itr2;
+      ++itr2;
+    }
+    return count;
+  }
+
+  template <typename T>
+  inline void performExtract(T& result, property_merge_data& data) {
+    if(data.empty()) return;
+    //sort
+    std::sort(data.begin(), data.end(), less_vertex_data<vertex_property>());
+    
+    //scanline
+    bool firstIteration = true;
+    scanlinePosition = scanline.end();
+    for(unsigned int i = 0; i < data.size(); ++i) {
+      if(firstIteration) {
+        mergeProperty(currentVertex.second, data[i].second);
+        currentVertex.first = data[i].first;
+        firstIteration = false;
+      } else {
+        if(data[i].first != currentVertex.first) {
+          if(data[i].first.x() != currentVertex.first.x()) {
+            processVertex(output);
+            //std::cout << scanline.size() << " ";
+            countFromBelow.clear(); //should already be clear
+            writeGraph(currentVertex.first.x(), result, output, scanline);
+            currentVertex.second.clear();
+            mergeProperty(currentVertex.second, data[i].second);
+            currentVertex.first = data[i].first;
+          } else {
+            processVertex(output);
+            currentVertex.second.clear();
+            mergeProperty(currentVertex.second, data[i].second);
+            currentVertex.first = data[i].first;
+          }
+        } else {
+          mergeProperty(currentVertex.second, data[i].second);
+        }
+      }
+    }
+    processVertex(output);
+    writeGraph(currentVertex.first.x(), result, output, scanline);
+    //std::cout << scanline.size() << "\n";
+  }
+
+  template <typename T>
+  inline void insertEdges(T& graph, property_set& p1, property_set& p2) {
+    for(typename property_set::iterator itr = p1.begin(); itr != p1.end(); ++itr) {
+      for(typename property_set::iterator itr2 = p2.begin(); itr2 != p2.end(); ++itr2) {
+        if(*itr != *itr2) {
+          graph[*itr].insert(*itr2);
+          graph[*itr2].insert(*itr);
+        }
+      }
+    }
+  }
+
+  template <typename T>
+  inline void propertySetAbove(coordinate_type y, property_set& ps, T& scanline) {
+    ps.clear();
+    typename T::iterator itr = scanline.find(y);
+    if(itr != scanline.end())
+      setProperty(ps, (*itr).second);
+  }
+
+  template <typename T>
+  inline void propertySetBelow(coordinate_type y, property_set& ps, T& scanline) {
+    ps.clear();
+    typename T::iterator itr = scanline.find(y);
+    if(itr != scanline.begin()) {
+      --itr;
+      setProperty(ps, (*itr).second);
+    }
+  }
+
+  template <typename T, typename T2>
+  inline void writeGraph(coordinate_type x, T& graph, edge_property_vector& output, T2& scanline) {
+    if(output.empty()) return;
+    edge_property* previousEdgeP = &(output[0]);
+    bool firstIteration = true;
+    property_set ps;
+    for(unsigned int i = 0; i < output.size(); ++i) {
+      edge_property& previousEdge = *previousEdgeP;
+      edge_property& edge = output[i];
+      if(previousEdge.first.high() == edge.first.low()) {
+        //horizontal edge
+        insertEdges(graph, edge.second.first, previousEdge.second.first);
+        //corner 1
+        insertEdges(graph, edge.second.first, previousEdge.second.second);
+        //other horizontal edge
+        insertEdges(graph, edge.second.second, previousEdge.second.second);
+        //corner 2
+        insertEdges(graph, edge.second.second, previousEdge.second.first);
+      } else {
+        if(!firstIteration){
+          //look up regions above previous edge 
+          propertySetAbove(previousEdge.first.high(), ps, scanline);
+          insertEdges(graph, ps, previousEdge.second.first);
+          insertEdges(graph, ps, previousEdge.second.second);
+        }
+        //look up regions below current edge in the scanline
+        propertySetBelow(edge.first.high(), ps, scanline);
+        insertEdges(graph, ps, edge.second.first);
+        insertEdges(graph, ps, edge.second.second);
+      }
+      firstIteration = false;
+      //vertical edge
+      insertEdges(graph, edge.second.second, edge.second.first);
+      //shared region to left
+      insertEdges(graph, edge.second.second, edge.second.second);
+      //shared region to right
+      insertEdges(graph, edge.second.first, edge.second.first);
+      previousEdgeP = &(output[i]);
+    }
+    edge_property& previousEdge = *previousEdgeP;
+    propertySetAbove(previousEdge.first.high(), ps, scanline);
+    insertEdges(graph, ps, previousEdge.second.first);
+    insertEdges(graph, ps, previousEdge.second.second);
+    output.clear();
+  }
+
+  template <typename Result>
+  inline void writeOutput(coordinate_type x, Result& result, edge_property_vector& output) {
+    for(unsigned int i = 0; i < output.size(); ++i) {
+      edge_property& edge = output[i];
+      //edge.second.first is the property set on the left of the edge
+      if(!edge.second.first.empty()) {
+        typename Result::iterator itr = result.find(edge.second.first);
+        if(itr == result.end()) {
+          std::pair<property_set, polygon_set_type> element(edge.second.first, polygon_set_type(VERTICAL));
+          itr = result.insert(result.end(), element);
+        }
+        std::pair<interval_data<coordinate_type>, int> element2(interval_data<coordinate_type>(edge.first.low(), edge.first.high()), -1); //right edge of figure
+        (*itr).second.insert(x, element2);
+      }
+      if(!edge.second.second.empty()) {
+        //edge.second.second is the property set on the right of the edge
+        typename Result::iterator itr = result.find(edge.second.second);
+        if(itr == result.end()) {
+          std::pair<property_set, polygon_set_type> element(edge.second.second, polygon_set_type(VERTICAL));
+          itr = result.insert(result.end(), element);
+        }
+        std::pair<interval_data<coordinate_type>, int> element3(interval_data<coordinate_type>(edge.first.low(), edge.first.high()), 1); //left edge of figure
+        (*itr).second.insert(x, element3);
+      }
+    }
+    output.clear();
+  }
+};
+
+
+}
+#endif