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