Chris@16: /*
Chris@16:   Copyright 2008 Intel Corporation
Chris@16: 
Chris@16:   Use, modification and distribution are subject to the Boost Software License,
Chris@16:   Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
Chris@16:   http://www.boost.org/LICENSE_1_0.txt).
Chris@16: */
Chris@16: #ifndef BOOST_POLYGON_POLYGON_90_SET_DATA_HPP
Chris@16: #define BOOST_POLYGON_POLYGON_90_SET_DATA_HPP
Chris@16: #include "isotropy.hpp"
Chris@16: #include "point_concept.hpp"
Chris@16: #include "transform.hpp"
Chris@16: #include "interval_concept.hpp"
Chris@16: #include "rectangle_concept.hpp"
Chris@16: #include "segment_concept.hpp"
Chris@16: #include "detail/iterator_points_to_compact.hpp"
Chris@16: #include "detail/iterator_compact_to_points.hpp"
Chris@16: #include "polygon_traits.hpp"
Chris@16: 
Chris@16: //manhattan boolean algorithms
Chris@16: #include "detail/boolean_op.hpp"
Chris@16: #include "detail/polygon_formation.hpp"
Chris@16: #include "detail/rectangle_formation.hpp"
Chris@16: #include "detail/max_cover.hpp"
Chris@16: #include "detail/property_merge.hpp"
Chris@16: #include "detail/polygon_90_touch.hpp"
Chris@16: #include "detail/iterator_geometry_to_set.hpp"
Chris@16: 
Chris@16: namespace boost { namespace polygon{
Chris@16:   template <typename ltype, typename rtype, typename op_type>
Chris@16:   class polygon_90_set_view;
Chris@16: 
Chris@16:   template <typename T>
Chris@16:   class polygon_90_set_data {
Chris@16:   public:
Chris@16:     typedef T coordinate_type;
Chris@16:     typedef std::vector<std::pair<coordinate_type, std::pair<coordinate_type, int> > > value_type;
Chris@16:     typedef typename std::vector<std::pair<coordinate_type, std::pair<coordinate_type, int> > >::const_iterator iterator_type;
Chris@16:     typedef polygon_90_set_data operator_arg_type;
Chris@16: 
Chris@16:     // default constructor
Chris@16:     inline polygon_90_set_data() : orient_(HORIZONTAL), data_(), dirty_(false), unsorted_(false) {}
Chris@16: 
Chris@16:     // constructor
Chris@16:     inline polygon_90_set_data(orientation_2d orient) : orient_(orient), data_(), dirty_(false), unsorted_(false) {}
Chris@16: 
Chris@16:     // constructor from an iterator pair over vertex data
Chris@16:     template <typename iT>
Chris@16:     inline polygon_90_set_data(orientation_2d orient, iT input_begin, iT input_end) :
Chris@16:       orient_(HORIZONTAL), data_(), dirty_(false), unsorted_(false) {
Chris@16:       dirty_ = true;
Chris@16:       unsorted_ = true;
Chris@16:       for( ; input_begin != input_end; ++input_begin) { insert(*input_begin); }
Chris@16:     }
Chris@16: 
Chris@16:     // copy constructor
Chris@16:     inline polygon_90_set_data(const polygon_90_set_data& that) :
Chris@16:       orient_(that.orient_), data_(that.data_), dirty_(that.dirty_), unsorted_(that.unsorted_) {}
Chris@16: 
Chris@16:     template <typename ltype, typename rtype, typename op_type>
Chris@16:     inline polygon_90_set_data(const polygon_90_set_view<ltype, rtype, op_type>& that);
Chris@16: 
Chris@16:     // copy with orientation change constructor
Chris@16:     inline polygon_90_set_data(orientation_2d orient, const polygon_90_set_data& that) :
Chris@16:       orient_(orient), data_(), dirty_(false), unsorted_(false) {
Chris@16:       insert(that, false, that.orient_);
Chris@16:     }
Chris@16: 
Chris@16:     // destructor
Chris@16:     inline ~polygon_90_set_data() {}
Chris@16: 
Chris@16:     // assignement operator
Chris@16:     inline polygon_90_set_data& operator=(const polygon_90_set_data& that) {
Chris@16:       if(this == &that) return *this;
Chris@16:       orient_ = that.orient_;
Chris@16:       data_ = that.data_;
Chris@16:       dirty_ = that.dirty_;
Chris@16:       unsorted_ = that.unsorted_;
Chris@16:       return *this;
Chris@16:     }
Chris@16: 
Chris@16:     template <typename ltype, typename rtype, typename op_type>
Chris@16:     inline polygon_90_set_data& operator=(const polygon_90_set_view<ltype, rtype, op_type>& that);
Chris@16: 
Chris@16:     template <typename geometry_object>
Chris@16:     inline polygon_90_set_data& operator=(const geometry_object& geometry) {
Chris@16:       data_.clear();
Chris@16:       insert(geometry);
Chris@16:       return *this;
Chris@16:     }
Chris@16: 
Chris@16:     // insert iterator range
Chris@16:     inline void insert(iterator_type input_begin, iterator_type input_end, orientation_2d orient = HORIZONTAL) {
Chris@16:       if(input_begin == input_end || (!data_.empty() && &(*input_begin) == &(*(data_.begin())))) return;
Chris@16:       dirty_ = true;
Chris@16:       unsorted_ = true;
Chris@16:       if(orient == orient_)
Chris@16:         data_.insert(data_.end(), input_begin, input_end);
Chris@16:       else {
Chris@16:         for( ; input_begin != input_end; ++input_begin) {
Chris@16:           insert(*input_begin, false, orient);
Chris@16:         }
Chris@16:       }
Chris@16:     }
Chris@16: 
Chris@16:     // insert iterator range
Chris@16:     template <typename iT>
Chris@16:     inline void insert(iT input_begin, iT input_end, orientation_2d orient = HORIZONTAL) {
Chris@16:       if(input_begin == input_end) return;
Chris@16:       dirty_ = true;
Chris@16:       unsorted_ = true;
Chris@16:       for( ; input_begin != input_end; ++input_begin) {
Chris@16:         insert(*input_begin, false, orient);
Chris@16:       }
Chris@16:     }
Chris@16: 
Chris@16:     inline void insert(const polygon_90_set_data& polygon_set) {
Chris@16:       insert(polygon_set.begin(), polygon_set.end(), polygon_set.orient());
Chris@16:     }
Chris@16: 
Chris@16:     inline void insert(const std::pair<std::pair<point_data<coordinate_type>, point_data<coordinate_type> >, int>& edge, bool is_hole = false,
Chris@16:                        orientation_2d orient = HORIZONTAL) {
Chris@16:       std::pair<coordinate_type, std::pair<coordinate_type, int> > vertex;
Chris@16:       vertex.first = edge.first.first.x();
Chris@16:       vertex.second.first = edge.first.first.y();
Chris@16:       vertex.second.second = edge.second * (is_hole ? -1 : 1);
Chris@16:       insert(vertex, false, VERTICAL);
Chris@16:       vertex.first = edge.first.second.x();
Chris@16:       vertex.second.first = edge.first.second.y();
Chris@16:       vertex.second.second *= -1;
Chris@16:       insert(vertex, false, VERTICAL);
Chris@16:     }
Chris@16: 
Chris@16:     template <typename geometry_type>
Chris@16:     inline void insert(const geometry_type& geometry_object, bool is_hole = false, orientation_2d = HORIZONTAL) {
Chris@16:       iterator_geometry_to_set<typename geometry_concept<geometry_type>::type, geometry_type>
Chris@16:         begin_input(geometry_object, LOW, orient_, is_hole), end_input(geometry_object, HIGH, orient_, is_hole);
Chris@16:       insert(begin_input, end_input, orient_);
Chris@16:     }
Chris@16: 
Chris@16:     inline void insert(const std::pair<coordinate_type, std::pair<coordinate_type, int> >& vertex, bool is_hole = false,
Chris@16:                        orientation_2d orient = HORIZONTAL) {
Chris@16:       data_.push_back(vertex);
Chris@16:       if(orient != orient_) std::swap(data_.back().first, data_.back().second.first);
Chris@16:       if(is_hole) data_.back().second.second *= -1;
Chris@16:       dirty_ = true;
Chris@16:       unsorted_ = true;
Chris@16:     }
Chris@16: 
Chris@16:     inline void insert(coordinate_type major_coordinate, const std::pair<interval_data<coordinate_type>, int>& edge) {
Chris@16:       std::pair<coordinate_type, std::pair<coordinate_type, int> > vertex;
Chris@16:       vertex.first = major_coordinate;
Chris@16:       vertex.second.first = edge.first.get(LOW);
Chris@16:       vertex.second.second = edge.second;
Chris@16:       insert(vertex, false, orient_);
Chris@16:       vertex.second.first = edge.first.get(HIGH);
Chris@16:       vertex.second.second *= -1;
Chris@16:       insert(vertex, false, orient_);
Chris@16:     }
Chris@16: 
Chris@16:     template <typename output_container>
Chris@16:     inline void get(output_container& output) const {
Chris@16:       get_dispatch(output, typename geometry_concept<typename output_container::value_type>::type());
Chris@16:     }
Chris@16: 
Chris@16:     template <typename output_container>
Chris@16:     inline void get(output_container& output, size_t vthreshold) const {
Chris@16:       get_dispatch(output, typename geometry_concept<typename output_container::value_type>::type(), vthreshold);
Chris@16:     }
Chris@16: 
Chris@16: 
Chris@16:     template <typename output_container>
Chris@16:     inline void get_polygons(output_container& output) const {
Chris@16:       get_dispatch(output, polygon_90_concept());
Chris@16:     }
Chris@16: 
Chris@16:     template <typename output_container>
Chris@16:     inline void get_rectangles(output_container& output) const {
Chris@16:       clean();
Chris@16:       form_rectangles(output, data_.begin(), data_.end(), orient_, rectangle_concept());
Chris@16:     }
Chris@16: 
Chris@16:     template <typename output_container>
Chris@16:     inline void get_rectangles(output_container& output, orientation_2d slicing_orientation) const {
Chris@16:       if(slicing_orientation == orient_) {
Chris@16:         get_rectangles(output);
Chris@16:       } else {
Chris@16:         polygon_90_set_data<coordinate_type> ps(*this);
Chris@16:         ps.transform(axis_transformation(axis_transformation::SWAP_XY));
Chris@16:         output_container result;
Chris@16:         ps.get_rectangles(result);
Chris@16:         for(typename output_container::iterator itr = result.begin(); itr != result.end(); ++itr) {
Chris@16:           ::boost::polygon::transform(*itr, axis_transformation(axis_transformation::SWAP_XY));
Chris@16:         }
Chris@16:         output.insert(output.end(), result.begin(), result.end());
Chris@16:       }
Chris@16:     }
Chris@16: 
Chris@16:     // equivalence operator
Chris@16:     inline bool operator==(const polygon_90_set_data& p) const {
Chris@16:       if(orient_ == p.orient()) {
Chris@16:         clean();
Chris@16:         p.clean();
Chris@16:         return data_ == p.data_;
Chris@16:       } else {
Chris@16:         return false;
Chris@16:       }
Chris@16:     }
Chris@16: 
Chris@16:     // inequivalence operator
Chris@16:     inline bool operator!=(const polygon_90_set_data& p) const {
Chris@16:       return !((*this) == p);
Chris@16:     }
Chris@16: 
Chris@16:     // get iterator to begin vertex data
Chris@16:     inline iterator_type begin() const {
Chris@16:       return data_.begin();
Chris@16:     }
Chris@16: 
Chris@16:     // get iterator to end vertex data
Chris@16:     inline iterator_type end() const {
Chris@16:       return data_.end();
Chris@16:     }
Chris@16: 
Chris@16:     const value_type& value() const {
Chris@16:       return data_;
Chris@16:     }
Chris@16: 
Chris@16:     // clear the contents of the polygon_90_set_data
Chris@16:     inline void clear() { data_.clear(); dirty_ = unsorted_ = false; }
Chris@16: 
Chris@16:     // find out if Polygon set is empty
Chris@16:     inline bool empty() const { clean(); return data_.empty(); }
Chris@16: 
Chris@16:     // get the Polygon set size in vertices
Chris@16:     inline std::size_t size() const { clean(); return data_.size(); }
Chris@16: 
Chris@16:     // get the current Polygon set capacity in vertices
Chris@16:     inline std::size_t capacity() const { return data_.capacity(); }
Chris@16: 
Chris@16:     // reserve size of polygon set in vertices
Chris@16:     inline void reserve(std::size_t size) { return data_.reserve(size); }
Chris@16: 
Chris@16:     // find out if Polygon set is sorted
Chris@16:     inline bool sorted() const { return !unsorted_; }
Chris@16: 
Chris@16:     // find out if Polygon set is clean
Chris@16:     inline bool dirty() const { return dirty_; }
Chris@16: 
Chris@16:     // get the scanline orientation of the polygon set
Chris@16:     inline orientation_2d orient() const { return orient_; }
Chris@16: 
Chris@16:     // Start BM
Chris@16:     // The problem: If we have two polygon sets with two different scanline orientations:
Chris@16:     // I tried changing the orientation of one to coincide with other (If not, resulting boolean operation
Chris@16:     // produces spurious results).
Chris@16:     // First I tried copying polygon data from one of the sets into another set with corrected orientation
Chris@16:     // using one of the copy constructor that takes in orientation (see somewhere above in this file) --> copy constructor throws error
Chris@16:     // Then I tried another approach:(see below). This approach also fails to produce the desired results when test case is run.
Chris@16:     // Here is the part that beats me: If I comment out the whole section, I can do all the operations (^=, -=, &= )these commented out
Chris@16:     // operations perform. So then why do we need them?. Hence, I commented out this whole section.
Chris@16:     // End BM
Chris@16:     // polygon_90_set_data<coordinate_type>& operator-=(const polygon_90_set_data& that) {
Chris@16:     //   sort();
Chris@16:     //   that.sort();
Chris@16:     //   value_type data;
Chris@16:     //   std::swap(data, data_);
Chris@16:     //   applyBooleanBinaryOp(data.begin(), data.end(),
Chris@16:     //                        that.begin(), that.end(), boolean_op::BinaryCount<boolean_op::BinaryNot>());
Chris@16:     //   return *this;
Chris@16:     // }
Chris@16:     // polygon_90_set_data<coordinate_type>& operator^=(const polygon_90_set_data& that) {
Chris@16:     //   sort();
Chris@16:     //   that.sort();
Chris@16:     //   value_type data;
Chris@16:     //   std::swap(data, data_);
Chris@16:     //   applyBooleanBinaryOp(data.begin(), data.end(),
Chris@16:     //                        that.begin(), that.end(),  boolean_op::BinaryCount<boolean_op::BinaryXor>());
Chris@16:     //   return *this;
Chris@16:     // }
Chris@16:     // polygon_90_set_data<coordinate_type>& operator&=(const polygon_90_set_data& that) {
Chris@16:     //   sort();
Chris@16:     //   that.sort();
Chris@16:     //   value_type data;
Chris@16:     //   std::swap(data, data_);
Chris@16:     //   applyBooleanBinaryOp(data.begin(), data.end(),
Chris@16:     //                        that.begin(), that.end(), boolean_op::BinaryCount<boolean_op::BinaryAnd>());
Chris@16:     //   return *this;
Chris@16:     // }
Chris@16:     // polygon_90_set_data<coordinate_type>& operator|=(const polygon_90_set_data& that) {
Chris@16:     //   insert(that);
Chris@16:     //   return *this;
Chris@16:     // }
Chris@16: 
Chris@16:     void clean() const {
Chris@16:       sort();
Chris@16:       if(dirty_) {
Chris@16:         boolean_op::default_arg_workaround<int>::applyBooleanOr(data_);
Chris@16:         dirty_ = false;
Chris@16:       }
Chris@16:     }
Chris@16: 
Chris@16:     void sort() const{
Chris@16:       if(unsorted_) {
Chris@16:         polygon_sort(data_.begin(), data_.end());
Chris@16:         unsorted_ = false;
Chris@16:       }
Chris@16:     }
Chris@16: 
Chris@16:     template <typename input_iterator_type>
Chris@16:     void set(input_iterator_type input_begin, input_iterator_type input_end, orientation_2d orient) {
Chris@16:       data_.clear();
Chris@16:       reserve(std::distance(input_begin, input_end));
Chris@16:       data_.insert(data_.end(), input_begin, input_end);
Chris@16:       orient_ = orient;
Chris@16:       dirty_ = true;
Chris@16:       unsorted_ = true;
Chris@16:     }
Chris@16: 
Chris@16:     void set(const value_type& value, orientation_2d orient) {
Chris@16:       data_ = value;
Chris@16:       orient_ = orient;
Chris@16:       dirty_ = true;
Chris@16:       unsorted_ = true;
Chris@16:     }
Chris@16: 
Chris@16:     //extents
Chris@16:     template <typename rectangle_type>
Chris@16:     bool
Chris@16:     extents(rectangle_type& extents_rectangle) const {
Chris@16:       clean();
Chris@16:       if(data_.empty()) return false;
Chris@16:       if(orient_ == HORIZONTAL)
Chris@16:         set_points(extents_rectangle, point_data<coordinate_type>(data_[0].second.first, data_[0].first),
Chris@16:                    point_data<coordinate_type>(data_[data_.size() - 1].second.first, data_[data_.size() - 1].first));
Chris@16:       else
Chris@16:         set_points(extents_rectangle, point_data<coordinate_type>(data_[0].first, data_[0].second.first),
Chris@16:                    point_data<coordinate_type>(data_[data_.size() - 1].first, data_[data_.size() - 1].second.first));
Chris@16:       for(std::size_t i = 1; i < data_.size() - 1; ++i) {
Chris@16:         if(orient_ == HORIZONTAL)
Chris@16:           encompass(extents_rectangle, point_data<coordinate_type>(data_[i].second.first, data_[i].first));
Chris@16:         else
Chris@16:           encompass(extents_rectangle, point_data<coordinate_type>(data_[i].first, data_[i].second.first));
Chris@16:       }
Chris@16:       return true;
Chris@16:     }
Chris@16: 
Chris@16:     polygon_90_set_data&
Chris@16:     bloat2(typename coordinate_traits<coordinate_type>::unsigned_area_type west_bloating,
Chris@16:           typename coordinate_traits<coordinate_type>::unsigned_area_type east_bloating,
Chris@16:           typename coordinate_traits<coordinate_type>::unsigned_area_type south_bloating,
Chris@16:           typename coordinate_traits<coordinate_type>::unsigned_area_type north_bloating) {
Chris@16:       std::vector<rectangle_data<coordinate_type> > rects;
Chris@16:       clean();
Chris@16:       rects.reserve(data_.size() / 2);
Chris@16:       get(rects);
Chris@16:       rectangle_data<coordinate_type> convolutionRectangle(interval_data<coordinate_type>(-((coordinate_type)west_bloating),
Chris@16:                                                                                           (coordinate_type)east_bloating),
Chris@16:                                                            interval_data<coordinate_type>(-((coordinate_type)south_bloating),
Chris@16:                                                                                           (coordinate_type)north_bloating));
Chris@16:       for(typename std::vector<rectangle_data<coordinate_type> >::iterator itr = rects.begin();
Chris@16:           itr != rects.end(); ++itr) {
Chris@16:         convolve(*itr, convolutionRectangle);
Chris@16:       }
Chris@16:       clear();
Chris@16:       insert(rects.begin(), rects.end());
Chris@16:       return *this;
Chris@16:     }
Chris@16: 
Chris@16:     static void modify_pt(point_data<coordinate_type>& pt, const point_data<coordinate_type>&  prev_pt,
Chris@16:                           const point_data<coordinate_type>&  current_pt,  const point_data<coordinate_type>&  next_pt,
Chris@16:                           coordinate_type west_bloating,
Chris@16:                           coordinate_type east_bloating,
Chris@16:                           coordinate_type south_bloating,
Chris@16:                           coordinate_type north_bloating) {
Chris@16:       bool pxl = prev_pt.x() < current_pt.x();
Chris@16:       bool pyl = prev_pt.y() < current_pt.y();
Chris@16:       bool nxl = next_pt.x() < current_pt.x();
Chris@16:       bool nyl = next_pt.y() < current_pt.y();
Chris@16:       bool pxg = prev_pt.x() > current_pt.x();
Chris@16:       bool pyg = prev_pt.y() > current_pt.y();
Chris@16:       bool nxg = next_pt.x() > current_pt.x();
Chris@16:       bool nyg = next_pt.y() > current_pt.y();
Chris@16:       //two of the four if statements will execute
Chris@16:       if(pxl)
Chris@16:         pt.y(current_pt.y() - south_bloating);
Chris@16:       if(pxg)
Chris@16:         pt.y(current_pt.y() + north_bloating);
Chris@16:       if(nxl)
Chris@16:         pt.y(current_pt.y() + north_bloating);
Chris@16:       if(nxg)
Chris@16:         pt.y(current_pt.y() - south_bloating);
Chris@16:       if(pyl)
Chris@16:         pt.x(current_pt.x() + east_bloating);
Chris@16:       if(pyg)
Chris@16:         pt.x(current_pt.x() - west_bloating);
Chris@16:       if(nyl)
Chris@16:         pt.x(current_pt.x() - west_bloating);
Chris@16:       if(nyg)
Chris@16:         pt.x(current_pt.x() + east_bloating);
Chris@16:     }
Chris@16:     static void resize_poly_up(std::vector<point_data<coordinate_type> >& poly,
Chris@16:                                coordinate_type west_bloating,
Chris@16:                                coordinate_type east_bloating,
Chris@16:                                coordinate_type south_bloating,
Chris@16:                                coordinate_type north_bloating) {
Chris@16:       point_data<coordinate_type> first_pt = poly[0];
Chris@16:       point_data<coordinate_type> second_pt = poly[1];
Chris@16:       point_data<coordinate_type> prev_pt = poly[0];
Chris@16:       point_data<coordinate_type> current_pt = poly[1];
Chris@16:       for(std::size_t i = 2; i < poly.size(); ++i) {
Chris@16:         point_data<coordinate_type> next_pt = poly[i];
Chris@16:         modify_pt(poly[i-1], prev_pt, current_pt, next_pt, west_bloating, east_bloating, south_bloating, north_bloating);
Chris@16:         prev_pt = current_pt;
Chris@16:         current_pt = next_pt;
Chris@16:       }
Chris@16:       point_data<coordinate_type> next_pt = first_pt;
Chris@16:       modify_pt(poly.back(), prev_pt, current_pt, next_pt, west_bloating, east_bloating, south_bloating, north_bloating);
Chris@16:       prev_pt = current_pt;
Chris@16:       current_pt = next_pt;
Chris@16:       next_pt = second_pt;
Chris@16:       modify_pt(poly[0], prev_pt, current_pt, next_pt, west_bloating, east_bloating, south_bloating, north_bloating);
Chris@16:       remove_colinear_pts(poly);
Chris@16:     }
Chris@16:     static bool resize_poly_down(std::vector<point_data<coordinate_type> >& poly,
Chris@16:                                  coordinate_type west_shrinking,
Chris@16:                                  coordinate_type east_shrinking,
Chris@16:                                  coordinate_type south_shrinking,
Chris@16:                                  coordinate_type north_shrinking) {
Chris@16:       rectangle_data<coordinate_type> extents_rectangle;
Chris@16:       set_points(extents_rectangle, poly[0], poly[0]);
Chris@16:       point_data<coordinate_type> first_pt = poly[0];
Chris@16:       point_data<coordinate_type> second_pt = poly[1];
Chris@16:       point_data<coordinate_type> prev_pt = poly[0];
Chris@16:       point_data<coordinate_type> current_pt = poly[1];
Chris@16:       encompass(extents_rectangle, current_pt);
Chris@16:       for(std::size_t i = 2; i < poly.size(); ++i) {
Chris@16:         point_data<coordinate_type> next_pt = poly[i];
Chris@16:         encompass(extents_rectangle, next_pt);
Chris@16:         modify_pt(poly[i-1], prev_pt, current_pt, next_pt, west_shrinking, east_shrinking, south_shrinking, north_shrinking);
Chris@16:         prev_pt = current_pt;
Chris@16:         current_pt = next_pt;
Chris@16:       }
Chris@16:       if(delta(extents_rectangle, HORIZONTAL) < std::abs(west_shrinking + east_shrinking))
Chris@16:         return false;
Chris@16:       if(delta(extents_rectangle, VERTICAL) < std::abs(north_shrinking + south_shrinking))
Chris@16:         return false;
Chris@16:       point_data<coordinate_type> next_pt = first_pt;
Chris@16:       modify_pt(poly.back(), prev_pt, current_pt, next_pt, west_shrinking, east_shrinking, south_shrinking, north_shrinking);
Chris@16:       prev_pt = current_pt;
Chris@16:       current_pt = next_pt;
Chris@16:       next_pt = second_pt;
Chris@16:       modify_pt(poly[0], prev_pt, current_pt, next_pt, west_shrinking, east_shrinking, south_shrinking, north_shrinking);
Chris@16:       return remove_colinear_pts(poly);
Chris@16:     }
Chris@16: 
Chris@16:     static bool remove_colinear_pts(std::vector<point_data<coordinate_type> >& poly) {
Chris@16:       bool found_colinear = true;
Chris@16:       while(found_colinear && poly.size() >= 4) {
Chris@16:         found_colinear = false;
Chris@16:         typename std::vector<point_data<coordinate_type> >::iterator itr = poly.begin();
Chris@16:         itr += poly.size() - 1; //get last element position
Chris@16:         typename std::vector<point_data<coordinate_type> >::iterator itr2 = poly.begin();
Chris@16:         typename std::vector<point_data<coordinate_type> >::iterator itr3 = itr2;
Chris@16:         ++itr3;
Chris@16:         std::size_t count = 0;
Chris@16:         for( ; itr3 < poly.end(); ++itr3) {
Chris@16:           if(((*itr).x() == (*itr2).x() && (*itr).x() == (*itr3).x()) ||
Chris@16:              ((*itr).y() == (*itr2).y() && (*itr).y() == (*itr3).y()) ) {
Chris@16:             ++count;
Chris@16:             found_colinear = true;
Chris@16:           } else {
Chris@16:             itr = itr2;
Chris@16:             ++itr2;
Chris@16:           }
Chris@16:           *itr2 = *itr3;
Chris@16:         }
Chris@16:         itr3 = poly.begin();
Chris@16:         if(((*itr).x() == (*itr2).x() && (*itr).x() == (*itr3).x()) ||
Chris@16:            ((*itr).y() == (*itr2).y() && (*itr).y() == (*itr3).y()) ) {
Chris@16:           ++count;
Chris@16:           found_colinear = true;
Chris@16:         }
Chris@16:         poly.erase(poly.end() - count, poly.end());
Chris@16:       }
Chris@16:       return poly.size() >= 4;
Chris@16:     }
Chris@16: 
Chris@16:     polygon_90_set_data&
Chris@16:     bloat(typename coordinate_traits<coordinate_type>::unsigned_area_type west_bloating,
Chris@16:            typename coordinate_traits<coordinate_type>::unsigned_area_type east_bloating,
Chris@16:            typename coordinate_traits<coordinate_type>::unsigned_area_type south_bloating,
Chris@16:            typename coordinate_traits<coordinate_type>::unsigned_area_type north_bloating) {
Chris@16:       std::list<polygon_45_with_holes_data<coordinate_type> > polys;
Chris@16:       get(polys);
Chris@16:       clear();
Chris@16:       for(typename std::list<polygon_45_with_holes_data<coordinate_type> >::iterator itr = polys.begin();
Chris@16:           itr != polys.end(); ++itr) {
Chris@16:         //polygon_90_set_data<coordinate_type> psref;
Chris@16:         //psref.insert(view_as<polygon_90_concept>((*itr).self_));
Chris@16:         //rectangle_data<coordinate_type> prerect;
Chris@16:         //psref.extents(prerect);
Chris@16:         resize_poly_up((*itr).self_.coords_, (coordinate_type)west_bloating, (coordinate_type)east_bloating,
Chris@16:                        (coordinate_type)south_bloating, (coordinate_type)north_bloating);
Chris@16:         iterator_geometry_to_set<polygon_90_concept, view_of<polygon_90_concept, polygon_45_data<coordinate_type> > >
Chris@16:           begin_input(view_as<polygon_90_concept>((*itr).self_), LOW, orient_, false, true, COUNTERCLOCKWISE),
Chris@16:           end_input(view_as<polygon_90_concept>((*itr).self_), HIGH, orient_, false, true, COUNTERCLOCKWISE);
Chris@16:         insert(begin_input, end_input, orient_);
Chris@16:         //polygon_90_set_data<coordinate_type> pstest;
Chris@16:         //pstest.insert(view_as<polygon_90_concept>((*itr).self_));
Chris@16:         //psref.bloat2(west_bloating, east_bloating, south_bloating, north_bloating);
Chris@16:         //if(!equivalence(psref, pstest)) {
Chris@16:         // std::cout << "test failed\n";
Chris@16:         //}
Chris@16:         for(typename std::list<polygon_45_data<coordinate_type> >::iterator itrh = (*itr).holes_.begin();
Chris@16:             itrh != (*itr).holes_.end(); ++itrh) {
Chris@16:           //rectangle_data<coordinate_type> rect;
Chris@16:           //psref.extents(rect);
Chris@16:           //polygon_90_set_data<coordinate_type> psrefhole;
Chris@16:           //psrefhole.insert(prerect);
Chris@16:           //psrefhole.insert(view_as<polygon_90_concept>(*itrh), true);
Chris@16:           //polygon_45_data<coordinate_type> testpoly(*itrh);
Chris@16:           if(resize_poly_down((*itrh).coords_,(coordinate_type)west_bloating, (coordinate_type)east_bloating,
Chris@16:                               (coordinate_type)south_bloating, (coordinate_type)north_bloating)) {
Chris@16:             iterator_geometry_to_set<polygon_90_concept, view_of<polygon_90_concept, polygon_45_data<coordinate_type> > >
Chris@16:               begin_input2(view_as<polygon_90_concept>(*itrh), LOW, orient_, true, true),
Chris@16:               end_input2(view_as<polygon_90_concept>(*itrh), HIGH, orient_, true, true);
Chris@16:             insert(begin_input2, end_input2, orient_);
Chris@16:             //polygon_90_set_data<coordinate_type> pstesthole;
Chris@16:             //pstesthole.insert(rect);
Chris@16:             //iterator_geometry_to_set<polygon_90_concept, view_of<polygon_90_concept, polygon_45_data<coordinate_type> > >
Chris@16:             // begin_input2(view_as<polygon_90_concept>(*itrh), LOW, orient_, true, true);
Chris@16:             //pstesthole.insert(begin_input2, end_input, orient_);
Chris@16:             //psrefhole.bloat2(west_bloating, east_bloating, south_bloating, north_bloating);
Chris@16:             //if(!equivalence(psrefhole, pstesthole)) {
Chris@16:             // std::cout << (winding(testpoly) == CLOCKWISE) << std::endl;
Chris@16:             // std::cout << (winding(*itrh) == CLOCKWISE) << std::endl;
Chris@16:             // polygon_90_set_data<coordinate_type> c(psrefhole);
Chris@16:             // c.clean();
Chris@16:             // polygon_90_set_data<coordinate_type> a(pstesthole);
Chris@16:             // polygon_90_set_data<coordinate_type> b(pstesthole);
Chris@16:             // a.sort();
Chris@16:             // b.clean();
Chris@16:             // std::cout << "test hole failed\n";
Chris@16:             // //std::cout << testpoly << std::endl;
Chris@16:             //}
Chris@16:           }
Chris@16:         }
Chris@16:       }
Chris@16:       return *this;
Chris@16:     }
Chris@16: 
Chris@16:     polygon_90_set_data&
Chris@16:     shrink(typename coordinate_traits<coordinate_type>::unsigned_area_type west_shrinking,
Chris@16:            typename coordinate_traits<coordinate_type>::unsigned_area_type east_shrinking,
Chris@16:            typename coordinate_traits<coordinate_type>::unsigned_area_type south_shrinking,
Chris@16:            typename coordinate_traits<coordinate_type>::unsigned_area_type north_shrinking) {
Chris@16:       std::list<polygon_45_with_holes_data<coordinate_type> > polys;
Chris@16:       get(polys);
Chris@16:       clear();
Chris@16:       for(typename std::list<polygon_45_with_holes_data<coordinate_type> >::iterator itr = polys.begin();
Chris@16:           itr != polys.end(); ++itr) {
Chris@16:         //polygon_90_set_data<coordinate_type> psref;
Chris@16:         //psref.insert(view_as<polygon_90_concept>((*itr).self_));
Chris@16:         //rectangle_data<coordinate_type> prerect;
Chris@16:         //psref.extents(prerect);
Chris@16:         //polygon_45_data<coordinate_type> testpoly((*itr).self_);
Chris@16:         if(resize_poly_down((*itr).self_.coords_, -(coordinate_type)west_shrinking, -(coordinate_type)east_shrinking,
Chris@16:                             -(coordinate_type)south_shrinking, -(coordinate_type)north_shrinking)) {
Chris@16:           iterator_geometry_to_set<polygon_90_concept, view_of<polygon_90_concept, polygon_45_data<coordinate_type> > >
Chris@16:             begin_input(view_as<polygon_90_concept>((*itr).self_), LOW, orient_, false, true, COUNTERCLOCKWISE),
Chris@16:             end_input(view_as<polygon_90_concept>((*itr).self_), HIGH, orient_, false, true, COUNTERCLOCKWISE);
Chris@16:           insert(begin_input, end_input, orient_);
Chris@16:           //iterator_geometry_to_set<polygon_90_concept, view_of<polygon_90_concept, polygon_45_data<coordinate_type> > >
Chris@16:           //  begin_input2(view_as<polygon_90_concept>((*itr).self_), LOW, orient_, false, true, COUNTERCLOCKWISE);
Chris@16:           //polygon_90_set_data<coordinate_type> pstest;
Chris@16:           //pstest.insert(begin_input2, end_input, orient_);
Chris@16:           //psref.shrink2(west_shrinking, east_shrinking, south_shrinking, north_shrinking);
Chris@16:           //if(!equivalence(psref, pstest)) {
Chris@16:           //  std::cout << "test failed\n";
Chris@16:           //}
Chris@16:           for(typename std::list<polygon_45_data<coordinate_type> >::iterator itrh = (*itr).holes_.begin();
Chris@16:               itrh != (*itr).holes_.end(); ++itrh) {
Chris@16:             //rectangle_data<coordinate_type> rect;
Chris@16:             //psref.extents(rect);
Chris@16:             //polygon_90_set_data<coordinate_type> psrefhole;
Chris@16:             //psrefhole.insert(prerect);
Chris@16:             //psrefhole.insert(view_as<polygon_90_concept>(*itrh), true);
Chris@16:             //polygon_45_data<coordinate_type> testpoly(*itrh);
Chris@16:             resize_poly_up((*itrh).coords_, -(coordinate_type)west_shrinking, -(coordinate_type)east_shrinking,
Chris@16:                             -(coordinate_type)south_shrinking, -(coordinate_type)north_shrinking);
Chris@16:             iterator_geometry_to_set<polygon_90_concept, view_of<polygon_90_concept, polygon_45_data<coordinate_type> > >
Chris@16:               begin_input2(view_as<polygon_90_concept>(*itrh), LOW, orient_, true, true),
Chris@16:               end_input2(view_as<polygon_90_concept>(*itrh), HIGH, orient_, true, true);
Chris@16:             insert(begin_input2, end_input2, orient_);
Chris@16:             //polygon_90_set_data<coordinate_type> pstesthole;
Chris@16:             //pstesthole.insert(rect);
Chris@16:             //iterator_geometry_to_set<polygon_90_concept, view_of<polygon_90_concept, polygon_45_data<coordinate_type> > >
Chris@16:             //  begin_input2(view_as<polygon_90_concept>(*itrh), LOW, orient_, true, true);
Chris@16:             //pstesthole.insert(begin_input2, end_input, orient_);
Chris@16:             //psrefhole.shrink2(west_shrinking, east_shrinking, south_shrinking, north_shrinking);
Chris@16:             //if(!equivalence(psrefhole, pstesthole)) {
Chris@16:             //  std::cout << (winding(testpoly) == CLOCKWISE) << std::endl;
Chris@16:             //  std::cout << (winding(*itrh) == CLOCKWISE) << std::endl;
Chris@16:             //  polygon_90_set_data<coordinate_type> c(psrefhole);
Chris@16:             //  c.clean();
Chris@16:             //  polygon_90_set_data<coordinate_type> a(pstesthole);
Chris@16:             //  polygon_90_set_data<coordinate_type> b(pstesthole);
Chris@16:             //  a.sort();
Chris@16:             //  b.clean();
Chris@16:             //  std::cout << "test hole failed\n";
Chris@16:             //  //std::cout << testpoly << std::endl;
Chris@16:             //}
Chris@16:           }
Chris@16:         }
Chris@16:       }
Chris@16:       return *this;
Chris@16:     }
Chris@16: 
Chris@16:     polygon_90_set_data&
Chris@16:     shrink2(typename coordinate_traits<coordinate_type>::unsigned_area_type west_shrinking,
Chris@16:             typename coordinate_traits<coordinate_type>::unsigned_area_type east_shrinking,
Chris@16:             typename coordinate_traits<coordinate_type>::unsigned_area_type south_shrinking,
Chris@16:             typename coordinate_traits<coordinate_type>::unsigned_area_type north_shrinking) {
Chris@16:       rectangle_data<coordinate_type> externalBoundary;
Chris@16:       if(!extents(externalBoundary)) return *this;
Chris@16:       ::boost::polygon::bloat(externalBoundary, 10); //bloat by diferential ammount
Chris@16:       //insert a hole that encompasses the data
Chris@16:       insert(externalBoundary, true); //note that the set is in a dirty state now
Chris@16:       sort();  //does not apply implicit OR operation
Chris@16:       std::vector<rectangle_data<coordinate_type> > rects;
Chris@16:       rects.reserve(data_.size() / 2);
Chris@16:       //begin does not apply implicit or operation, this is a dirty range
Chris@16:       form_rectangles(rects, data_.begin(), data_.end(), orient_, rectangle_concept());
Chris@16:       clear();
Chris@16:       rectangle_data<coordinate_type> convolutionRectangle(interval_data<coordinate_type>(-((coordinate_type)east_shrinking),
Chris@16:                                                                                           (coordinate_type)west_shrinking),
Chris@16:                                                            interval_data<coordinate_type>(-((coordinate_type)north_shrinking),
Chris@16:                                                                                           (coordinate_type)south_shrinking));
Chris@16:       for(typename std::vector<rectangle_data<coordinate_type> >::iterator itr = rects.begin();
Chris@16:           itr != rects.end(); ++itr) {
Chris@16:         rectangle_data<coordinate_type>& rect = *itr;
Chris@16:         convolve(rect, convolutionRectangle);
Chris@16:         //insert rectangle as a hole
Chris@16:         insert(rect, true);
Chris@16:       }
Chris@16:       convolve(externalBoundary, convolutionRectangle);
Chris@16:       //insert duplicate of external boundary as solid to cancel out the external hole boundaries
Chris@16:       insert(externalBoundary);
Chris@16:       clean(); //we have negative values in the set, so we need to apply an OR operation to make it valid input to a boolean
Chris@16:       return *this;
Chris@16:     }
Chris@16: 
Chris@16:     polygon_90_set_data&
Chris@16:     shrink(direction_2d dir, typename coordinate_traits<coordinate_type>::unsigned_area_type shrinking) {
Chris@16:       if(dir == WEST)
Chris@16:         return shrink(shrinking, 0, 0, 0);
Chris@16:       if(dir == EAST)
Chris@16:         return shrink(0, shrinking, 0, 0);
Chris@16:       if(dir == SOUTH)
Chris@16:         return shrink(0, 0, shrinking, 0);
Chris@16:       return shrink(0, 0, 0, shrinking);
Chris@16:     }
Chris@16: 
Chris@16:     polygon_90_set_data&
Chris@16:     bloat(direction_2d dir, typename coordinate_traits<coordinate_type>::unsigned_area_type shrinking) {
Chris@16:       if(dir == WEST)
Chris@16:         return bloat(shrinking, 0, 0, 0);
Chris@16:       if(dir == EAST)
Chris@16:         return bloat(0, shrinking, 0, 0);
Chris@16:       if(dir == SOUTH)
Chris@16:         return bloat(0, 0, shrinking, 0);
Chris@16:       return bloat(0, 0, 0, shrinking);
Chris@16:     }
Chris@16: 
Chris@16:     polygon_90_set_data&
Chris@16:     resize(coordinate_type west, coordinate_type east, coordinate_type south, coordinate_type north);
Chris@16: 
Chris@16:     polygon_90_set_data& move(coordinate_type x_delta, coordinate_type y_delta) {
Chris@16:       for(typename std::vector<std::pair<coordinate_type, std::pair<coordinate_type, int> > >::iterator
Chris@16:             itr = data_.begin(); itr != data_.end(); ++itr) {
Chris@16:         if(orient_ == orientation_2d(VERTICAL)) {
Chris@16:           (*itr).first += x_delta;
Chris@16:           (*itr).second.first += y_delta;
Chris@16:         } else {
Chris@16:           (*itr).second.first += x_delta;
Chris@16:           (*itr).first += y_delta;
Chris@16:         }
Chris@16:       }
Chris@16:       return *this;
Chris@16:     }
Chris@16: 
Chris@16:     // transform set
Chris@16:     template <typename transformation_type>
Chris@16:     polygon_90_set_data& transform(const transformation_type& transformation) {
Chris@16:       direction_2d dir1, dir2;
Chris@16:       transformation.get_directions(dir1, dir2);
Chris@16:       int sign = dir1.get_sign() * dir2.get_sign();
Chris@16:       for(typename std::vector<std::pair<coordinate_type, std::pair<coordinate_type, int> > >::iterator
Chris@16:             itr = data_.begin(); itr != data_.end(); ++itr) {
Chris@16:         if(orient_ == orientation_2d(VERTICAL)) {
Chris@16:           transformation.transform((*itr).first, (*itr).second.first);
Chris@16:         } else {
Chris@16:           transformation.transform((*itr).second.first, (*itr).first);
Chris@16:         }
Chris@16:         (*itr).second.second *= sign;
Chris@16:       }
Chris@16:       if(dir1 != EAST || dir2 != NORTH)
Chris@16:         unsorted_ = true; //some mirroring or rotation must have happened
Chris@16:       return *this;
Chris@16:     }
Chris@16: 
Chris@16:     // scale set
Chris@16:     polygon_90_set_data& scale_up(typename coordinate_traits<coordinate_type>::unsigned_area_type factor) {
Chris@16:       for(typename std::vector<std::pair<coordinate_type, std::pair<coordinate_type, int> > >::iterator
Chris@16:             itr = data_.begin(); itr != data_.end(); ++itr) {
Chris@16:         (*itr).first *= (coordinate_type)factor;
Chris@16:         (*itr).second.first *= (coordinate_type)factor;
Chris@16:       }
Chris@16:       return *this;
Chris@16:     }
Chris@16:     polygon_90_set_data& scale_down(typename coordinate_traits<coordinate_type>::unsigned_area_type factor) {
Chris@16:       typedef typename coordinate_traits<coordinate_type>::coordinate_distance dt;
Chris@16:       for(typename std::vector<std::pair<coordinate_type, std::pair<coordinate_type, int> > >::iterator
Chris@16:             itr = data_.begin(); itr != data_.end(); ++itr) {
Chris@16:         (*itr).first = scaling_policy<coordinate_type>::round((dt)((*itr).first) / (dt)factor);
Chris@16:         (*itr).second.first = scaling_policy<coordinate_type>::round((dt)((*itr).second.first) / (dt)factor);
Chris@16:       }
Chris@16:       unsorted_ = true; //scaling down can make coordinates equal that were not previously equal
Chris@16:       return *this;
Chris@16:     }
Chris@16:     template <typename scaling_type>
Chris@16:     polygon_90_set_data& scale(const anisotropic_scale_factor<scaling_type>& scaling) {
Chris@16:       for(typename std::vector<std::pair<coordinate_type, std::pair<coordinate_type, int> > >::iterator
Chris@16:             itr = data_.begin(); itr != data_.end(); ++itr) {
Chris@16:         if(orient_ == orientation_2d(VERTICAL)) {
Chris@16:           scaling.scale((*itr).first, (*itr).second.first);
Chris@16:         } else {
Chris@16:           scaling.scale((*itr).second.first, (*itr).first);
Chris@16:         }
Chris@16:       }
Chris@16:       unsorted_ = true;
Chris@16:       return *this;
Chris@16:     }
Chris@16:     template <typename scaling_type>
Chris@16:     polygon_90_set_data& scale_with(const scaling_type& scaling) {
Chris@16:       for(typename std::vector<std::pair<coordinate_type, std::pair<coordinate_type, int> > >::iterator
Chris@16:             itr = data_.begin(); itr != data_.end(); ++itr) {
Chris@16:         if(orient_ == orientation_2d(VERTICAL)) {
Chris@16:           scaling.scale((*itr).first, (*itr).second.first);
Chris@16:         } else {
Chris@16:           scaling.scale((*itr).second.first, (*itr).first);
Chris@16:         }
Chris@16:       }
Chris@16:       unsorted_ = true;
Chris@16:       return *this;
Chris@16:     }
Chris@16:     polygon_90_set_data& scale(double factor) {
Chris@16:       typedef typename coordinate_traits<coordinate_type>::coordinate_distance dt;
Chris@16:       for(typename std::vector<std::pair<coordinate_type, std::pair<coordinate_type, int> > >::iterator
Chris@16:             itr = data_.begin(); itr != data_.end(); ++itr) {
Chris@16:         (*itr).first = scaling_policy<coordinate_type>::round((dt)((*itr).first) * (dt)factor);
Chris@16:         (*itr).second.first = scaling_policy<coordinate_type>::round((dt)((*itr).second.first) * (dt)factor);
Chris@16:       }
Chris@16:       unsorted_ = true; //scaling make coordinates equal that were not previously equal
Chris@16:       return *this;
Chris@16:     }
Chris@16: 
Chris@16:     polygon_90_set_data& self_xor() {
Chris@16:       sort();
Chris@16:       if(dirty_) { //if it is clean it is a no-op
Chris@16:         boolean_op::default_arg_workaround<boolean_op::UnaryCount>::applyBooleanOr(data_);
Chris@16:         dirty_ = false;
Chris@16:       }
Chris@16:       return *this;
Chris@16:     }
Chris@16: 
Chris@16:     polygon_90_set_data& self_intersect() {
Chris@16:       sort();
Chris@16:       if(dirty_) { //if it is clean it is a no-op
Chris@16:         interval_data<coordinate_type> ivl((std::numeric_limits<coordinate_type>::min)(), (std::numeric_limits<coordinate_type>::max)());
Chris@16:         rectangle_data<coordinate_type> rect(ivl, ivl);
Chris@16:         insert(rect, true);
Chris@16:         clean();
Chris@16:       }
Chris@16:       return *this;
Chris@16:     }
Chris@16: 
Chris@16:     inline polygon_90_set_data& interact(const polygon_90_set_data& that) {
Chris@16:       typedef coordinate_type Unit;
Chris@16:       if(that.dirty_) that.clean();
Chris@16:       typename touch_90_operation<Unit>::TouchSetData tsd;
Chris@16:       touch_90_operation<Unit>::populateTouchSetData(tsd, that.data_, 0);
Chris@16:       std::vector<polygon_90_data<Unit> > polys;
Chris@16:       get(polys);
Chris@16:       std::vector<std::set<int> > graph(polys.size()+1, std::set<int>());
Chris@16:       for(std::size_t i = 0; i < polys.size(); ++i){
Chris@16:         polygon_90_set_data<Unit> psTmp(that.orient_);
Chris@16:         psTmp.insert(polys[i]);
Chris@16:         psTmp.clean();
Chris@16:         touch_90_operation<Unit>::populateTouchSetData(tsd, psTmp.data_, i+1);
Chris@16:       }
Chris@16:       touch_90_operation<Unit>::performTouch(graph, tsd);
Chris@16:       clear();
Chris@16:       for(std::set<int>::iterator itr = graph[0].begin(); itr != graph[0].end(); ++itr){
Chris@16:         insert(polys[(*itr)-1]);
Chris@16:       }
Chris@16:       dirty_ = false;
Chris@16:       return *this;
Chris@16:     }
Chris@16: 
Chris@16: 
Chris@16:     template <class T2, typename iterator_type_1, typename iterator_type_2>
Chris@16:     void applyBooleanBinaryOp(iterator_type_1 itr1, iterator_type_1 itr1_end,
Chris@16:                               iterator_type_2 itr2, iterator_type_2 itr2_end,
Chris@16:                               T2 defaultCount) {
Chris@16:       data_.clear();
Chris@16:       boolean_op::applyBooleanBinaryOp(data_, itr1, itr1_end, itr2, itr2_end, defaultCount);
Chris@16:     }
Chris@16: 
Chris@16:   private:
Chris@16:     orientation_2d orient_;
Chris@16:     mutable value_type data_;
Chris@16:     mutable bool dirty_;
Chris@16:     mutable bool unsorted_;
Chris@16: 
Chris@16:   private:
Chris@16:     //functions
Chris@16:     template <typename output_container>
Chris@16:     void get_dispatch(output_container& output, rectangle_concept ) const {
Chris@16:       clean();
Chris@16:       form_rectangles(output, data_.begin(), data_.end(), orient_, rectangle_concept());
Chris@16:     }
Chris@16:     template <typename output_container>
Chris@16:     void get_dispatch(output_container& output, polygon_90_concept tag) const {
Chris@16:       get_fracture(output, true, tag);
Chris@16:     }
Chris@16: 
Chris@16:     template <typename output_container>
Chris@16:     void get_dispatch(output_container& output, polygon_90_concept tag, 
Chris@16:       size_t vthreshold) const {
Chris@16:       get_fracture(output, true, tag, vthreshold);
Chris@16:     }
Chris@16: 
Chris@16:     template <typename output_container>
Chris@16:     void get_dispatch(output_container& output, polygon_90_with_holes_concept tag) const {
Chris@16:       get_fracture(output, false, tag);
Chris@16:     }
Chris@16: 
Chris@16:     template <typename output_container>
Chris@16:     void get_dispatch(output_container& output, polygon_90_with_holes_concept tag,
Chris@16:       size_t vthreshold) const {
Chris@16:       get_fracture(output, false, tag, vthreshold);
Chris@16:     }
Chris@16: 
Chris@16: 
Chris@16:     template <typename output_container>
Chris@16:     void get_dispatch(output_container& output, polygon_45_concept tag) const {
Chris@16:       get_fracture(output, true, tag);
Chris@16:     }
Chris@16:     template <typename output_container>
Chris@16:     void get_dispatch(output_container& output, polygon_45_with_holes_concept tag) const {
Chris@16:       get_fracture(output, false, tag);
Chris@16:     }
Chris@16:     template <typename output_container>
Chris@16:     void get_dispatch(output_container& output, polygon_concept tag) const {
Chris@16:       get_fracture(output, true, tag);
Chris@16:     }
Chris@16:     template <typename output_container>
Chris@16:     void get_dispatch(output_container& output, polygon_with_holes_concept tag) const {
Chris@16:       get_fracture(output, false, tag);
Chris@16:     }
Chris@16:     template <typename output_container, typename concept_type>
Chris@16:     void get_fracture(output_container& container, bool fracture_holes, concept_type tag) const {
Chris@16:       clean();
Chris@16:       ::boost::polygon::get_polygons(container, data_.begin(), data_.end(), orient_, fracture_holes, tag);
Chris@16:     }
Chris@16: 
Chris@16:     template <typename output_container, typename concept_type>
Chris@16:     void get_fracture(output_container& container, bool fracture_holes, concept_type tag,
Chris@16:       size_t vthreshold) const {
Chris@16:       clean();
Chris@16:       ::boost::polygon::get_polygons(container, data_.begin(), data_.end(), orient_, fracture_holes, tag, vthreshold);
Chris@16:     }
Chris@16:   };
Chris@16: 
Chris@16:   template <typename coordinate_type>
Chris@16:   polygon_90_set_data<coordinate_type>&
Chris@16:   polygon_90_set_data<coordinate_type>::resize(coordinate_type west,
Chris@16:                                                coordinate_type east,
Chris@16:                                                coordinate_type south,
Chris@16:                                                coordinate_type north) {
Chris@16:     move(-west, -south);
Chris@16:     coordinate_type e_total = west + east;
Chris@16:     coordinate_type n_total = south + north;
Chris@16:     if((e_total < 0) ^ (n_total < 0)) {
Chris@16:       //different signs
Chris@16:       if(e_total < 0) {
Chris@16:         shrink(0, -e_total, 0, 0);
Chris@16:         if(n_total != 0)
Chris@16:           return bloat(0, 0, 0, n_total);
Chris@16:         else
Chris@16:           return (*this);
Chris@16:       } else {
Chris@16:         shrink(0, 0, 0, -n_total); //shrink first
Chris@16:         if(e_total != 0)
Chris@16:           return bloat(0, e_total, 0, 0);
Chris@16:         else
Chris@16:           return (*this);
Chris@16:       }
Chris@16:     } else {
Chris@16:       if(e_total < 0) {
Chris@16:         return shrink(0, -e_total, 0, -n_total);
Chris@16:       }
Chris@16:       return bloat(0, e_total, 0, n_total);
Chris@16:     }
Chris@16:   }
Chris@16: 
Chris@16:   template <typename coordinate_type, typename property_type>
Chris@16:   class property_merge_90 {
Chris@16:   private:
Chris@16:     std::vector<std::pair<property_merge_point<coordinate_type>, std::pair<property_type, int> > > pmd_;
Chris@16:   public:
Chris@16:     inline property_merge_90() : pmd_() {}
Chris@16:     inline property_merge_90(const property_merge_90& that) : pmd_(that.pmd_) {}
Chris@16:     inline property_merge_90& operator=(const property_merge_90& that) { pmd_ = that.pmd_; return *this; }
Chris@16:     inline void insert(const polygon_90_set_data<coordinate_type>& ps, const property_type& property) {
Chris@16:       merge_scanline<coordinate_type, property_type, polygon_90_set_data<coordinate_type> >::
Chris@16:         populate_property_merge_data(pmd_, ps.begin(), ps.end(), property, ps.orient());
Chris@16:     }
Chris@16:     template <class GeoObjT>
Chris@16:     inline void insert(const GeoObjT& geoObj, const property_type& property) {
Chris@16:       polygon_90_set_data<coordinate_type> ps;
Chris@16:       ps.insert(geoObj);
Chris@16:       insert(ps, property);
Chris@16:     }
Chris@16:     //merge properties of input geometries and store the resulting geometries of regions
Chris@16:     //with unique sets of merged properties to polygons sets in a map keyed by sets of properties
Chris@16:     // T = std::map<std::set<property_type>, polygon_90_set_data<coordiante_type> > or
Chris@16:     // T = std::map<std::vector<property_type>, polygon_90_set_data<coordiante_type> >
Chris@16:     template <typename ResultType>
Chris@16:     inline void merge(ResultType& result) {
Chris@16:       merge_scanline<coordinate_type, property_type, polygon_90_set_data<coordinate_type>, typename ResultType::key_type> ms;
Chris@16:       ms.perform_merge(result, pmd_);
Chris@16:     }
Chris@16:   };
Chris@16: 
Chris@16:   //ConnectivityExtraction computes the graph of connectivity between rectangle, polygon and
Chris@16:   //polygon set graph nodes where an edge is created whenever the geometry in two nodes overlap
Chris@16:   template <typename coordinate_type>
Chris@16:   class connectivity_extraction_90 {
Chris@16:   private:
Chris@16:     typedef typename touch_90_operation<coordinate_type>::TouchSetData tsd;
Chris@16:     tsd tsd_;
Chris@16:     unsigned int nodeCount_;
Chris@16:   public:
Chris@16:     inline connectivity_extraction_90() : tsd_(), nodeCount_(0) {}
Chris@16:     inline connectivity_extraction_90(const connectivity_extraction_90& that) : tsd_(that.tsd_),
Chris@16:                                                                           nodeCount_(that.nodeCount_) {}
Chris@16:     inline connectivity_extraction_90& operator=(const connectivity_extraction_90& that) {
Chris@16:       tsd_ = that.tsd_;
Chris@16:       nodeCount_ = that.nodeCount_; {}
Chris@16:       return *this;
Chris@16:     }
Chris@16: 
Chris@16:     //insert a polygon set graph node, the value returned is the id of the graph node
Chris@16:     inline unsigned int insert(const polygon_90_set_data<coordinate_type>& ps) {
Chris@16:       ps.clean();
Chris@16:       touch_90_operation<coordinate_type>::populateTouchSetData(tsd_, ps.begin(), ps.end(), nodeCount_);
Chris@16:       return nodeCount_++;
Chris@16:     }
Chris@16:     template <class GeoObjT>
Chris@16:     inline unsigned int insert(const GeoObjT& geoObj) {
Chris@16:       polygon_90_set_data<coordinate_type> ps;
Chris@16:       ps.insert(geoObj);
Chris@16:       return insert(ps);
Chris@16:     }
Chris@16: 
Chris@16:     //extract connectivity and store the edges in the graph
Chris@16:     //graph must be indexable by graph node id and the indexed value must be a std::set of
Chris@16:     //graph node id
Chris@16:     template <class GraphT>
Chris@16:     inline void extract(GraphT& graph) {
Chris@16:       touch_90_operation<coordinate_type>::performTouch(graph, tsd_);
Chris@16:     }
Chris@16:   };
Chris@16: }
Chris@16: }
Chris@16: #endif