[Boost-commit] svn:boost r54819 - in sandbox/gtl/boost/polygon: . detail

Subject: [Boost-commit] svn:boost r54819 - in sandbox/gtl/boost/polygon: . detail
From: lucanus.j.simonson_at_[hidden]
Date: 2009-07-08 18:08:05

Author: ljsimons
Date: 2009-07-08 18:08:04 EDT (Wed, 08 Jul 2009)
New Revision: 54819
URL: http://svn.boost.org/trac/boost/changeset/54819

Log:
adding 45 degree property merge
Added:
   sandbox/gtl/boost/polygon/detail/property_merge_45.hpp   (contents, props changed)
Text files modified: 
   sandbox/gtl/boost/polygon/detail/polygon_45_touch.hpp |    41 ------------                            
   sandbox/gtl/boost/polygon/gtl_boost_unit_test.cpp     |    64 +++++++++++++++++++                     
   sandbox/gtl/boost/polygon/polygon.hpp                 |     3                                         
   sandbox/gtl/boost/polygon/polygon_45_set_data.hpp     |   129 ++++++++++++++++++++++++++++++++++++++++
   4 files changed, 196 insertions(+), 41 deletions(-)

Modified: sandbox/gtl/boost/polygon/detail/polygon_45_touch.hpp
==============================================================================
--- sandbox/gtl/boost/polygon/detail/polygon_45_touch.hpp	(original)
+++ sandbox/gtl/boost/polygon/detail/polygon_45_touch.hpp	2009-07-08 18:08:04 EDT (Wed, 08 Jul 2009)
@@ -230,46 +230,7 @@
     
   };
 
-  //ConnectivityExtraction computes the graph of connectivity between rectangle, polygon and
-  //polygon set graph nodes where an edge is created whenever the geometry in two nodes overlap
-  template <typename coordinate_type>
-  class connectivity_extraction_45 {
-  private:
-    typedef typename coordinate_traits<coordinate_type>::manhattan_area_type big_coord;
-    typedef typename polygon_45_touch<big_coord>::TouchSetData tsd;
-    tsd tsd_;
-    unsigned int nodeCount_;
-  public:
-    inline connectivity_extraction_45() : tsd_(), nodeCount_(0) {}
-    inline connectivity_extraction_45(const connectivity_extraction_45& that) : tsd_(that.tsd_),
-                                                                          nodeCount_(that.nodeCount_) {}
-    inline connectivity_extraction_45& operator=(const connectivity_extraction_45& that) { 
-      tsd_ = that.tsd_; 
-      nodeCount_ = that.nodeCount_; {}
-      return *this;
-    }
-    
-    //insert a polygon set graph node, the value returned is the id of the graph node
-    inline unsigned int insert(const polygon_45_set_data<coordinate_type>& ps) {
-      ps.clean();
-      polygon_45_touch<big_coord>::populateTouchSetData(tsd_, ps.begin(), ps.end(), nodeCount_);
-      return nodeCount_++;
-    }
-    template <class GeoObjT>
-    inline unsigned int insert(const GeoObjT& geoObj) {
-      polygon_45_set_data<coordinate_type> ps;
-      ps.insert(geoObj);
-      return insert(ps);
-    }
-    
-    //extract connectivity and store the edges in the graph
-    //graph must be indexable by graph node id and the indexed value must be a std::set of
-    //graph node id
-    template <class GraphT>
-    inline void extract(GraphT& graph) {
-      polygon_45_touch<big_coord>::performTouch(graph, tsd_);
-    }
-  };
+
 }
 }
 #endif 

Added: sandbox/gtl/boost/polygon/detail/property_merge_45.hpp
==============================================================================
--- (empty file)
+++ sandbox/gtl/boost/polygon/detail/property_merge_45.hpp	2009-07-08 18:08:04 EDT (Wed, 08 Jul 2009)
@@ -0,0 +1,160 @@
+/*
+  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_45_HPP
+#define BOOST_POLYGON_PROPERTY_MERGE_45_HPP
+namespace boost { namespace polygon{
+
+  template <typename Unit, typename property_type>
+  struct polygon_45_property_merge {
+
+    typedef point_data<Unit> Point;
+    typedef typename coordinate_traits<Unit>::manhattan_area_type LongUnit;
+
+    template <typename property_map>
+    static inline void merge_property_maps(property_map& mp, const property_map& mp2, bool subtract = false) {
+      polygon_45_touch<Unit>::merge_property_maps(mp, mp2, subtract);
+    }
+
+    class CountMerge {
+    public:
+      inline CountMerge() : counts() {}
+      //inline CountMerge(int count) { counts[0] = counts[1] = count; }
+      //inline CountMerge(int count1, int count2) { counts[0] = count1; counts[1] = count2; }
+      inline CountMerge(const CountMerge& count) : counts(count.counts) {}
+      inline bool operator==(const CountMerge& count) const { return counts == count.counts; }
+      inline bool operator!=(const CountMerge& count) const { return !((*this) == count); }
+      //inline CountMerge& operator=(int count) { counts[0] = counts[1] = count; return *this; }
+      inline CountMerge& operator=(const CountMerge& count) { counts = count.counts; return *this; }
+      inline int& operator[](property_type index) { 
+        std::vector<std::pair<int, int> >::iterator itr = lower_bound(counts.begin(), counts.end(), std::make_pair(index, int(0)));
+        if(itr != counts.end() && itr->first == index) {
+            return itr->second;
+        }
+        itr = counts.insert(itr, std::make_pair(index, int(0)));
+        return itr->second;
+      }
+//       inline int operator[](int index) const {
+//         std::vector<std::pair<int, int> >::const_iterator itr = counts.begin();
+//         for( ; itr != counts.end() && itr->first <= index; ++itr) {
+//           if(itr->first == index) {
+//             return itr->second;
+//           }
+//         }
+//         return 0;
+//       }
+      inline CountMerge& operator+=(const CountMerge& count){
+        merge_property_maps(counts, count.counts, false);
+        return *this;
+      }
+      inline CountMerge& operator-=(const CountMerge& count){
+        merge_property_maps(counts, count.counts, true);
+        return *this;
+      }
+      inline CountMerge operator+(const CountMerge& count) const {
+        return CountMerge(*this)+=count;
+      }
+      inline CountMerge operator-(const CountMerge& count) const {
+        return CountMerge(*this)-=count;
+      }
+      inline CountMerge invert() const {
+        CountMerge retval;
+        retval -= *this;
+        return retval;
+      }
+      std::vector<std::pair<property_type, int> > counts;
+    };
+
+    //output is a std::map<std::set<property_type>, polygon_45_set_data<Unit> >
+    struct merge_45_output_functor {
+      template <typename cT>
+      void operator()(cT& output, const CountMerge& count1, const CountMerge& count2, 
+                      const Point& pt, int rise, direction_1d end) {
+        typedef typename cT::key_type keytype;
+        keytype left;
+        keytype right;
+        int edgeType = end == LOW ? -1 : 1;
+        for(typename std::vector<std::pair<property_type, int> >::const_iterator itr = count1.counts.begin();
+            itr != count1.counts.end(); ++itr) {
+          left.insert(left.end(), (*itr).first);
+        }
+        for(typename std::vector<std::pair<property_type, int> >::const_iterator itr = count2.counts.begin();
+            itr != count2.counts.end(); ++itr) {
+          right.insert(right.end(), (*itr).first);
+        }
+        if(left == right) return;
+        if(!left.empty()) {
+          //std::cout << pt.x() << " " << pt.y() << " " << rise << " " << edgeType << std::endl;
+          output[left].insert_clean(typename boolean_op_45<Unit>::Vertex45(pt, rise, -edgeType));
+        }
+        if(!right.empty()) {
+          //std::cout << pt.x() << " " << pt.y() << " " << rise << " " << -edgeType << std::endl;
+          output[right].insert_clean(typename boolean_op_45<Unit>::Vertex45(pt, rise, edgeType));
+        }
+      }
+    };
+
+    typedef typename std::pair<Point, 
+                               typename boolean_op_45<Unit>::template Scan45CountT<CountMerge> > Vertex45Compact;
+    typedef std::vector<Vertex45Compact> MergeSetData;
+    
+    struct lessVertex45Compact {
+      bool operator()(const Vertex45Compact& l, const Vertex45Compact& r) {
+        return l.first < r.first;
+      }
+    };
+    
+    template <typename output_type>
+    static void performMerge(output_type& result, MergeSetData& tsd) {
+      
+      std::sort(tsd.begin(), tsd.end(), lessVertex45Compact());
+      typedef std::vector<std::pair<Point, typename boolean_op_45<Unit>::template Scan45CountT<CountMerge> > > TSD;
+      TSD tsd_;
+      tsd_.reserve(tsd.size());
+      for(typename MergeSetData::iterator itr = tsd.begin(); itr != tsd.end(); ) {
+        typename MergeSetData::iterator itr2 = itr;
+        ++itr2;
+        for(; itr2 != tsd.end() && itr2->first == itr->first; ++itr2) {
+          (itr->second) += (itr2->second); //accumulate
+        }
+        tsd_.push_back(std::make_pair(itr->first, itr->second));
+        itr = itr2;
+      }
+      typename boolean_op_45<Unit>::template Scan45<CountMerge, merge_45_output_functor> scanline;
+      for(typename TSD::iterator itr = tsd_.begin(); itr != tsd_.end(); ) {
+        typename TSD::iterator itr2 = itr;
+        ++itr2;
+        while(itr2 != tsd_.end() && itr2->first.x() == itr->first.x()) {
+          ++itr2;
+        }
+        scanline.scan(result, itr, itr2);
+        itr = itr2;
+      }
+    }
+
+    template <typename iT>
+    static void populateMergeSetData(MergeSetData& tsd, iT begin, iT end, property_type property) {
+      for( ; begin != end; ++begin) {
+        Vertex45Compact vertex;
+        vertex.first = typename Vertex45Compact::first_type(begin->pt.x() * 2, begin->pt.y() * 2);
+        tsd.push_back(vertex);
+        for(unsigned int i = 0; i < 4; ++i) {
+          if(begin->count[i]) {
+            tsd.back().second[i][property] += begin->count[i];
+          }
+        }
+      }
+    }
+    
+  };
+
+
+
+}
+}
+
+#endif

Modified: sandbox/gtl/boost/polygon/gtl_boost_unit_test.cpp
==============================================================================
--- sandbox/gtl/boost/polygon/gtl_boost_unit_test.cpp	(original)
+++ sandbox/gtl/boost/polygon/gtl_boost_unit_test.cpp	2009-07-08 18:08:04 EDT (Wed, 08 Jul 2009)
@@ -3074,6 +3074,70 @@
     if(!empty(ps90_1)) return 1;
   }
   if(!nonInteger45StessTest()) return 1;
+  {
+  using namespace gtl;
+  typedef polygon_45_property_merge<int, int> p45pm;
+  p45pm::MergeSetData msd;
+  polygon_45_set_data<int> ps;
+  ps += rectangle_data<int>(0, 0, 10, 10);
+  p45pm::populateMergeSetData(msd, ps.begin(), ps.end(), 444);
+  ps.clear();
+  ps += rectangle_data<int>(5, 5, 15, 15);
+  p45pm::populateMergeSetData(msd, ps.begin(), ps.end(), 333);
+  std::map<std::set<int>, polygon_45_set_data<int> > result;
+  p45pm::performMerge(result, msd);
+  int i = 0;
+  for(std::map<std::set<int>, polygon_45_set_data<int> >::iterator itr = result.begin();
+      itr != result.end(); ++itr) {
+    for(std::set<int>::iterator itr2 = (*itr).first.begin();
+        itr2 != (*itr).first.end(); ++itr2) {
+      std::cout << *itr2 << " ";
+    } std::cout << " : ";
+    std::cout << area((*itr).second) << std::endl;
+    if(i == 1) {
+      if(area((*itr).second) != 100) return 1;
+    } else
+      if(area((*itr).second) != 300) return 1;
+    ++i;
+  }
+
+
+  property_merge_45<int, int> pm;
+  pm.insert(rectangle_data<int>(0, 0, 10, 10), 444);
+  pm.insert(rectangle_data<int>(5, 5, 15, 15), 333);
+  std::map<std::set<int>, polygon_45_set_data<int> > mp;
+  pm.merge(mp);
+  i = 0;
+  for(std::map<std::set<int>, polygon_45_set_data<int> >::iterator itr = mp.begin();
+      itr != mp.end(); ++itr) {
+    for(std::set<int>::const_iterator itr2 = (*itr).first.begin();
+        itr2 != (*itr).first.end(); ++itr2) {
+      std::cout << *itr2 << " ";
+    } std::cout << " : ";
+    std::cout << area((*itr).second) << std::endl;
+    if(i == 1) {
+      if(area((*itr).second) != 25) return 1;
+    } else
+      if(area((*itr).second) != 75) return 1;
+    ++i;
+  }
+  std::map<std::vector<int>, polygon_45_set_data<int> > mp2;
+  pm.merge(mp2);
+  i = 0;
+  for(std::map<std::vector<int>, polygon_45_set_data<int> >::iterator itr = mp2.begin();
+      itr != mp2.end(); ++itr) {
+    for(std::vector<int>::const_iterator itr2 = (*itr).first.begin();
+        itr2 != (*itr).first.end(); ++itr2) {
+      std::cout << *itr2 << " ";
+    } std::cout << " : ";
+    std::cout << area((*itr).second) << std::endl;
+    if(i == 1) {
+      if(area((*itr).second) != 25) return 1;
+    } else
+      if(area((*itr).second) != 75) return 1;
+    ++i;
+  }
+  }
   std::cout << "ALL TESTS COMPLETE\n";
   return 0;
 }

Modified: sandbox/gtl/boost/polygon/polygon.hpp
==============================================================================
--- sandbox/gtl/boost/polygon/polygon.hpp	(original)
+++ sandbox/gtl/boost/polygon/polygon.hpp	2009-07-08 18:08:04 EDT (Wed, 08 Jul 2009)
@@ -82,9 +82,10 @@
 #include "detail/polygon_90_set_view.hpp"
 
 //45 boolean op algorithms
+#include "detail/polygon_45_touch.hpp"
+#include "detail/property_merge_45.hpp"
 #include "polygon_45_set_data.hpp"
 #include "polygon_45_set_traits.hpp"
-#include "detail/polygon_45_touch.hpp"
 #include "polygon_45_set_concept.hpp"
 #include "detail/polygon_45_set_view.hpp"
 

Modified: sandbox/gtl/boost/polygon/polygon_45_set_data.hpp
==============================================================================
--- sandbox/gtl/boost/polygon/polygon_45_set_data.hpp	(original)
+++ sandbox/gtl/boost/polygon/polygon_45_set_data.hpp	2009-07-08 18:08:04 EDT (Wed, 08 Jul 2009)
@@ -10,6 +10,8 @@
 #include "polygon_90_set_data.hpp"
 #include "detail/boolean_op_45.hpp"
 #include "detail/polygon_45_formation.hpp"
+#include "detail/polygon_45_touch.hpp"
+#include "detail/property_merge_45.hpp"
 namespace boost { namespace polygon{
 
   enum RoundingOption { CLOSEST = 0, OVERSIZE = 1, UNDERSIZE = 2, SQRT2 = 3, SQRT1OVER2 = 4 };
@@ -102,6 +104,8 @@
     }
 
     inline void insert(const polygon_45_set_data& polygon_set, bool is_hole = false);
+    template <typename coord_type>
+    inline void insert(const polygon_45_set_data<coord_type>& polygon_set, bool is_hole = false);
 
     template <typename geometry_type>
     inline void insert(const geometry_type& geometry_object, bool is_hole = false) {
@@ -565,6 +569,39 @@
     if(polygon_set.is_manhattan_ == false) is_manhattan_ = false;
     return;
   }
+  // insert polygon set
+  template <typename Unit>
+  template <typename coord_type>
+  inline void polygon_45_set_data<Unit>::insert(const polygon_45_set_data<coord_type>& polygon_set, bool is_hole) {
+    std::size_t count = data_.size();
+    for(typename polygon_45_set_data<coord_type>::iterator_type itr = polygon_set.begin();
+        itr != polygon_set.end(); ++itr) {
+      const typename polygon_45_set_data<coord_type>::Vertex45Compact& v = *itr;
+      typename polygon_45_set_data<Unit>::Vertex45Compact v2;
+      assign(v2.pt, v.pt);
+      v2.count = typename polygon_45_formation<Unit>::Vertex45Count(v.count[0], v.count[1], v.count[2], v.count[3]);
+      data_.push_back(v2);
+    }
+    polygon_45_set_data<coord_type> tmp;
+    polygon_set.get_error_data(tmp);
+    for(typename polygon_45_set_data<coord_type>::iterator_type itr = tmp.begin();
+        itr != tmp.end(); ++itr) {
+      const typename polygon_45_set_data<coord_type>::Vertex45Compact& v = *itr;
+      typename polygon_45_set_data<Unit>::Vertex45Compact v2;
+      assign(v2.pt, v.pt);
+      v2.count = typename polygon_45_formation<Unit>::Vertex45Count(v.count[0], v.count[1], v.count[2], v.count[3]);
+      error_data_.push_back(v2);
+    }
+    if(is_hole) {
+      for(std::size_t i = count; i < data_.size(); ++i) {
+        data_[i].count = data_[i].count.invert();
+      }
+    }
+    dirty_ = true;
+    unsorted_ = true;
+    if(polygon_set.is_manhattan() == false) is_manhattan_ = false;
+    return;
+  }
 
   template <typename cT, typename rT>
   void insert_rectangle_into_vector_45(cT& output, const rT& rect, bool is_hole) {
@@ -1713,7 +1750,99 @@
     is_manhattan_ = result.is_manhattan_;
   }
 
+  template <typename coordinate_type, typename property_type>
+  class property_merge_45 {
+  private:
+    typedef typename coordinate_traits<coordinate_type>::manhattan_area_type big_coord;
+    typedef typename polygon_45_property_merge<big_coord, property_type>::MergeSetData tsd;
+    tsd tsd_;
+  public:
+    inline property_merge_45() : tsd_() {}
+    inline property_merge_45(const property_merge_45& that) : tsd_(that.tsd_) {}
+    inline property_merge_45& operator=(const property_merge_45& that) { 
+      tsd_ = that.tsd_; 
+      return *this;
+    }
+    
+    inline void insert(const polygon_45_set_data<coordinate_type>& ps, property_type property) {
+      ps.clean();
+      polygon_45_property_merge<big_coord, property_type>::populateMergeSetData(tsd_, ps.begin(), ps.end(), property);
+    }
+    template <class GeoObjT>
+    inline void insert(const GeoObjT& geoObj, property_type property) {
+      polygon_45_set_data<coordinate_type> ps;
+      ps.insert(geoObj);
+      insert(ps, property);
+    }
+
+    //merge properties of input geometries and store the resulting geometries of regions
+    //with unique sets of merged properties to polygons sets in a map keyed by sets of properties
+    // T = std::map<std::set<property_type>, polygon_45_set_data<coordiante_type> > or
+    // T = std::map<std::vector<property_type>, polygon_45_set_data<coordiante_type> >
+    template <class result_type>
+    inline void merge(result_type& result) {
+      typedef typename result_type::key_type keytype;
+      typedef std::map<keytype, polygon_45_set_data<big_coord> > bigtype;
+      bigtype result_big;
+      polygon_45_property_merge<big_coord, property_type>::performMerge(result_big, tsd_);
+      std::vector<polygon_45_with_holes_data<big_coord> > polys;
+      std::vector<rectangle_data<big_coord> > pos_error_rects;
+      std::vector<rectangle_data<big_coord> > neg_error_rects;
+      for(typename std::map<keytype, polygon_45_set_data<big_coord> >::iterator itr = result_big.begin();
+          itr != result_big.end(); ++itr) {
+        polys.clear();
+        (*itr).second.get(polys);
+        for(std::size_t i = 0; i < polys.size(); ++i) {
+          get_error_rects(pos_error_rects, neg_error_rects, polys[i]);
+        }
+        (*itr).second += pos_error_rects;
+        (*itr).second -= neg_error_rects;
+        (*itr).second.scale_down(2);
+        result[(*itr).first].insert((*itr).second);
+      }
+    }
+  };
 
+  //ConnectivityExtraction computes the graph of connectivity between rectangle, polygon and
+  //polygon set graph nodes where an edge is created whenever the geometry in two nodes overlap
+  template <typename coordinate_type>
+  class connectivity_extraction_45 {
+  private:
+    typedef typename coordinate_traits<coordinate_type>::manhattan_area_type big_coord;
+    typedef typename polygon_45_touch<big_coord>::TouchSetData tsd;
+    tsd tsd_;
+    unsigned int nodeCount_;
+  public:
+    inline connectivity_extraction_45() : tsd_(), nodeCount_(0) {}
+    inline connectivity_extraction_45(const connectivity_extraction_45& that) : tsd_(that.tsd_),
+                                                                          nodeCount_(that.nodeCount_) {}
+    inline connectivity_extraction_45& operator=(const connectivity_extraction_45& that) { 
+      tsd_ = that.tsd_; 
+      nodeCount_ = that.nodeCount_; {}
+      return *this;
+    }
+    
+    //insert a polygon set graph node, the value returned is the id of the graph node
+    inline unsigned int insert(const polygon_45_set_data<coordinate_type>& ps) {
+      ps.clean();
+      polygon_45_touch<big_coord>::populateTouchSetData(tsd_, ps.begin(), ps.end(), nodeCount_);
+      return nodeCount_++;
+    }
+    template <class GeoObjT>
+    inline unsigned int insert(const GeoObjT& geoObj) {
+      polygon_45_set_data<coordinate_type> ps;
+      ps.insert(geoObj);
+      return insert(ps);
+    }
+    
+    //extract connectivity and store the edges in the graph
+    //graph must be indexable by graph node id and the indexed value must be a std::set of
+    //graph node id
+    template <class GraphT>
+    inline void extract(GraphT& graph) {
+      polygon_45_touch<big_coord>::performTouch(graph, tsd_);
+    }
+  };
 }
 }
 #endif