path: root/boost/polygon/detail/property_merge.hpp

/*
  Copyright 2008 Intel Corporation

  Use, modification and distribution are subject to the Boost Software License,
  Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
  http://www.boost.org/LICENSE_1_0.txt).
*/
#ifndef BOOST_POLYGON_PROPERTY_MERGE_HPP
#define BOOST_POLYGON_PROPERTY_MERGE_HPP
namespace boost { namespace polygon{

template <typename coordinate_type>
class property_merge_point {
private:
  coordinate_type x_, y_;
public:
  inline property_merge_point() : x_(), y_() {}
  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() : low_(), high_() {}
  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() : output(), scanline(), currentVertex(), tmpVector(), previousY(), countFromBelow(), scanlinePosition() {}
  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;
    return *this;
  }

  template <typename result_type>
  inline void perform_merge(result_type& result, property_merge_data& data) {
    if(data.empty()) return;
    //sort
    polygon_sort(data.begin(), data.end(), less_vertex_data<vertex_property>());
    //scanline
    bool firstIteration = true;
    scanlinePosition = scanline.end();
    for(std::size_t 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) const {
      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(std::size_t 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(std::size_t 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
    polygon_sort(data.begin(), data.end(), less_vertex_data<vertex_property>());

    //scanline
    bool firstIteration = true;
    scanlinePosition = scanline.end();
    for(std::size_t 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(std::size_t 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(std::size_t 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