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_45_SET_DATA_HPP
Chris@16: #define BOOST_POLYGON_POLYGON_45_SET_DATA_HPP
Chris@16: #include "polygon_90_set_data.hpp"
Chris@16: #include "detail/boolean_op_45.hpp"
Chris@16: #include "detail/polygon_45_formation.hpp"
Chris@16: #include "detail/polygon_45_touch.hpp"
Chris@16: #include "detail/property_merge_45.hpp"
Chris@16: namespace boost { namespace polygon{
Chris@16: 
Chris@16:   enum RoundingOption { CLOSEST = 0, OVERSIZE = 1, UNDERSIZE = 2, SQRT2 = 3, SQRT1OVER2 = 4 };
Chris@16:   enum CornerOption { INTERSECTION = 0, ORTHOGONAL = 1, UNFILLED = 2 };
Chris@16: 
Chris@16:   template <typename ltype, typename rtype, int op_type>
Chris@16:   class polygon_45_set_view;
Chris@16: 
Chris@16:   struct polygon_45_set_concept {};
Chris@16: 
Chris@16:   template <typename Unit>
Chris@16:   class polygon_45_set_data {
Chris@16:   public:
Chris@16:     typedef typename polygon_45_formation<Unit>::Vertex45Compact Vertex45Compact;
Chris@16:     typedef std::vector<Vertex45Compact> Polygon45VertexData;
Chris@16: 
Chris@16:     typedef Unit coordinate_type;
Chris@16:     typedef Polygon45VertexData value_type;
Chris@16:     typedef typename value_type::const_iterator iterator_type;
Chris@16:     typedef polygon_45_set_data operator_arg_type;
Chris@16: 
Chris@16:     // default constructor
Chris@16:     inline polygon_45_set_data() : error_data_(), data_(), dirty_(false), unsorted_(false), is_manhattan_(true) {}
Chris@16: 
Chris@16:     // constructor from a geometry object
Chris@16:     template <typename geometry_type>
Chris@16:     inline polygon_45_set_data(const geometry_type& that) : error_data_(), data_(), dirty_(false), unsorted_(false), is_manhattan_(true) {
Chris@16:       insert(that);
Chris@16:     }
Chris@16: 
Chris@16:     // copy constructor
Chris@16:     inline polygon_45_set_data(const polygon_45_set_data& that) :
Chris@16:       error_data_(that.error_data_), data_(that.data_), dirty_(that.dirty_),
Chris@16:       unsorted_(that.unsorted_), is_manhattan_(that.is_manhattan_) {}
Chris@16: 
Chris@16:     template <typename ltype, typename rtype, int op_type>
Chris@16:     inline polygon_45_set_data(const polygon_45_set_view<ltype, rtype, op_type>& that) :
Chris@16:       error_data_(), data_(), dirty_(false), unsorted_(false), is_manhattan_(true) {
Chris@16:       (*this) = that.value();
Chris@16:     }
Chris@16: 
Chris@16:     // destructor
Chris@16:     inline ~polygon_45_set_data() {}
Chris@16: 
Chris@16:     // assignement operator
Chris@16:     inline polygon_45_set_data& operator=(const polygon_45_set_data& that) {
Chris@16:       if(this == &that) return *this;
Chris@16:       error_data_ = that.error_data_;
Chris@16:       data_ = that.data_;
Chris@16:       dirty_ = that.dirty_;
Chris@16:       unsorted_ = that.unsorted_;
Chris@16:       is_manhattan_ = that.is_manhattan_;
Chris@16:       return *this;
Chris@16:     }
Chris@16: 
Chris@16:     template <typename ltype, typename rtype, int op_type>
Chris@16:     inline polygon_45_set_data& operator=(const polygon_45_set_view<ltype, rtype, op_type>& that) {
Chris@16:       (*this) = that.value();
Chris@16:       return *this;
Chris@16:     }
Chris@16: 
Chris@16:     template <typename geometry_object>
Chris@16:     inline polygon_45_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, bool is_hole = false) {
Chris@16:       if(input_begin == input_end || (!data_.empty() && &(*input_begin) == &(*(data_.begin())))) return;
Chris@16:       dirty_ = true;
Chris@16:       unsorted_ = true;
Chris@16:       while(input_begin != input_end) {
Chris@16:         insert(*input_begin, is_hole);
Chris@16:         ++input_begin;
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, bool is_hole = false) {
Chris@16:       if(input_begin == input_end) return;
Chris@16:       dirty_ = true;
Chris@16:       unsorted_ = true;
Chris@16:       while(input_begin != input_end) {
Chris@16:         insert(*input_begin, is_hole);
Chris@16:         ++input_begin;
Chris@16:       }
Chris@16:     }
Chris@16: 
Chris@16:     inline void insert(const polygon_45_set_data& polygon_set, bool is_hole = false);
Chris@16:     template <typename coord_type>
Chris@16:     inline void insert(const polygon_45_set_data<coord_type>& polygon_set, bool is_hole = false);
Chris@16: 
Chris@16:     template <typename geometry_type>
Chris@16:     inline void insert(const geometry_type& geometry_object, bool is_hole = false) {
Chris@16:       insert_dispatch(geometry_object, is_hole, typename geometry_concept<geometry_type>::type());
Chris@16:     }
Chris@16: 
Chris@16:     inline void insert_clean(const Vertex45Compact& vertex_45, bool is_hole = false) {
Chris@16:       if(vertex_45.count.is_45()) is_manhattan_ = false;
Chris@16:       data_.push_back(vertex_45);
Chris@16:       if(is_hole) data_.back().count.invert();
Chris@16:     }
Chris@16: 
Chris@16:     inline void insert(const Vertex45Compact& vertex_45, bool is_hole = false) {
Chris@16:       dirty_ = true;
Chris@16:       unsorted_ = true;
Chris@16:       insert_clean(vertex_45, is_hole);
Chris@16:     }
Chris@16: 
Chris@16:     template <typename coordinate_type_2>
Chris@16:     inline void insert(const polygon_90_set_data<coordinate_type_2>& polygon_set, bool is_hole = false) {
Chris@16:       if(polygon_set.orient() == VERTICAL) {
Chris@16:         for(typename polygon_90_set_data<coordinate_type_2>::iterator_type itr = polygon_set.begin();
Chris@16:             itr != polygon_set.end(); ++itr) {
Chris@16:           Vertex45Compact vertex_45(point_data<Unit>((*itr).first, (*itr).second.first), 2, (*itr).second.second);
Chris@16:           vertex_45.count[1] = (*itr).second.second;
Chris@16:           if(is_hole) vertex_45.count[1] *= - 1;
Chris@16:           insert_clean(vertex_45, is_hole);
Chris@16:         }
Chris@16:       } else {
Chris@16:         for(typename polygon_90_set_data<coordinate_type_2>::iterator_type itr = polygon_set.begin();
Chris@16:             itr != polygon_set.end(); ++itr) {
Chris@16:           Vertex45Compact vertex_45(point_data<Unit>((*itr).second.first, (*itr).first), 2, (*itr).second.second);
Chris@16:           vertex_45.count[1] = (*itr).second.second;
Chris@16:           if(is_hole) vertex_45.count[1] *= - 1;
Chris@16:           insert_clean(vertex_45, is_hole);
Chris@16:         }
Chris@16:       }
Chris@16:       dirty_ = true;
Chris@16:       unsorted_ = true;
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:     inline bool has_error_data() const { return !error_data_.empty(); }
Chris@16:     inline std::size_t error_count() const { return error_data_.size() / 4; }
Chris@16:     inline void get_error_data(polygon_45_set_data& p) const {
Chris@16:       p.data_.insert(p.data_.end(), error_data_.begin(), error_data_.end());
Chris@16:     }
Chris@16: 
Chris@16:     // equivalence operator
Chris@16:     inline bool operator==(const polygon_45_set_data& p) const {
Chris@16:       clean();
Chris@16:       p.clean();
Chris@16:       return data_ == p.data_;
Chris@16:     }
Chris@16: 
Chris@16:     // inequivalence operator
Chris@16:     inline bool operator!=(const polygon_45_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_45_set_data
Chris@16:     inline void clear() { data_.clear(); error_data_.clear(); dirty_ = unsorted_ = false; is_manhattan_ = true; }
Chris@16: 
Chris@16:     // find out if Polygon set is empty
Chris@16:     inline bool empty() const { 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:     // find out if Polygon set is clean
Chris@16:     inline bool is_manhattan() const { return is_manhattan_; }
Chris@16: 
Chris@16:     bool clean() const;
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) {
Chris@16:       data_.clear();
Chris@16:       reserve(std::distance(input_begin, input_end));
Chris@16:       insert(input_begin, input_end);
Chris@16:       dirty_ = true;
Chris@16:       unsorted_ = true;
Chris@16:     }
Chris@16: 
Chris@16:     void set_clean(const value_type& value) {
Chris@16:       data_ = value;
Chris@16:       dirty_ = false;
Chris@16:       unsorted_ = false;
Chris@16:     }
Chris@16: 
Chris@16:     void set(const value_type& value) {
Chris@16:       data_ = value;
Chris@16:       dirty_ = true;
Chris@16:       unsorted_ = true;
Chris@16:     }
Chris@16: 
Chris@16:     // append to the container cT with polygons (holes will be fractured vertically)
Chris@16:     template <class cT>
Chris@16:     void get_polygons(cT& container) const {
Chris@16:       get_dispatch(container, polygon_45_concept());
Chris@16:     }
Chris@16: 
Chris@16:     // append to the container cT with PolygonWithHoles objects
Chris@16:     template <class cT>
Chris@16:     void get_polygons_with_holes(cT& container) const {
Chris@16:       get_dispatch(container, polygon_45_with_holes_concept());
Chris@16:     }
Chris@16: 
Chris@16:     // append to the container cT with polygons of three or four verticies
Chris@16:     // slicing orientation is vertical
Chris@16:     template <class cT>
Chris@16:     void get_trapezoids(cT& container) const {
Chris@16:       clean();
Chris@16:       typename polygon_45_formation<Unit>::Polygon45Tiling pf;
Chris@16:       //std::cout << "FORMING POLYGONS\n";
Chris@16:       pf.scan(container, data_.begin(), data_.end());
Chris@16:       //std::cout << "DONE FORMING POLYGONS\n";
Chris@16:     }
Chris@16: 
Chris@16:     // append to the container cT with polygons of three or four verticies
Chris@16:     template <class cT>
Chris@16:     void get_trapezoids(cT& container, orientation_2d slicing_orientation) const {
Chris@16:       if(slicing_orientation == VERTICAL) {
Chris@16:         get_trapezoids(container);
Chris@16:       } else {
Chris@16:         polygon_45_set_data<Unit> ps(*this);
Chris@16:         ps.transform(axis_transformation(axis_transformation::SWAP_XY));
Chris@16:         cT result;
Chris@16:         ps.get_trapezoids(result);
Chris@16:         for(typename cT::iterator itr = result.begin(); itr != result.end(); ++itr) {
Chris@16:           ::boost::polygon::transform(*itr, axis_transformation(axis_transformation::SWAP_XY));
Chris@16:         }
Chris@16:         container.insert(container.end(), result.begin(), result.end());
Chris@16:       }
Chris@16:     }
Chris@16: 
Chris@16:     // insert vertex sequence
Chris@16:     template <class iT>
Chris@16:     void insert_vertex_sequence(iT begin_vertex, iT end_vertex,
Chris@16:                                 direction_1d winding, bool is_hole = false);
Chris@16: 
Chris@16:     // get the external boundary rectangle
Chris@16:     template <typename rectangle_type>
Chris@16:     bool extents(rectangle_type& rect) const;
Chris@16: 
Chris@16:     // snap verticies of set to even,even or odd,odd coordinates
Chris@16:     void snap() const;
Chris@16: 
Chris@16:     // |= &= += *= -= ^= binary operators
Chris@16:     polygon_45_set_data& operator|=(const polygon_45_set_data& b);
Chris@16:     polygon_45_set_data& operator&=(const polygon_45_set_data& b);
Chris@16:     polygon_45_set_data& operator+=(const polygon_45_set_data& b);
Chris@16:     polygon_45_set_data& operator*=(const polygon_45_set_data& b);
Chris@16:     polygon_45_set_data& operator-=(const polygon_45_set_data& b);
Chris@16:     polygon_45_set_data& operator^=(const polygon_45_set_data& b);
Chris@16: 
Chris@16:     // resizing operations
Chris@16:     polygon_45_set_data& operator+=(Unit delta);
Chris@16:     polygon_45_set_data& operator-=(Unit delta);
Chris@16: 
Chris@16:     // shrink the Polygon45Set by shrinking
Chris@16:     polygon_45_set_data& resize(coordinate_type resizing, RoundingOption rounding = CLOSEST,
Chris@16:                                 CornerOption corner = INTERSECTION);
Chris@16: 
Chris@16:     // transform set
Chris@16:     template <typename transformation_type>
Chris@16:     polygon_45_set_data& transform(const transformation_type& tr);
Chris@16: 
Chris@16:     // scale set
Chris@16:     polygon_45_set_data& scale_up(typename coordinate_traits<Unit>::unsigned_area_type factor);
Chris@16:     polygon_45_set_data& scale_down(typename coordinate_traits<Unit>::unsigned_area_type factor);
Chris@16:     polygon_45_set_data& scale(double scaling);
Chris@16: 
Chris@16:     // self_intersect
Chris@16:     polygon_45_set_data& self_intersect() {
Chris@16:       sort();
Chris@16:       applyAdaptiveUnary_<1>(); //1 = AND
Chris@16:       dirty_ = false;
Chris@16:       return *this;
Chris@16:     }
Chris@16: 
Chris@16:     // self_xor
Chris@16:     polygon_45_set_data& self_xor() {
Chris@16:       sort();
Chris@16:       applyAdaptiveUnary_<3>(); //3 = XOR
Chris@16:       dirty_ = false;
Chris@16:       return *this;
Chris@16:     }
Chris@16: 
Chris@16:     // accumulate the bloated polygon
Chris@16:     template <typename geometry_type>
Chris@16:     polygon_45_set_data& insert_with_resize(const geometry_type& poly,
Chris@16:                                             coordinate_type resizing, RoundingOption rounding = CLOSEST,
Chris@16:                                             CornerOption corner = INTERSECTION,
Chris@16:                                             bool hole = false) {
Chris@16:       return insert_with_resize_dispatch(poly, resizing, rounding, corner, hole, typename geometry_concept<geometry_type>::type());
Chris@16:     }
Chris@16: 
Chris@16:   private:
Chris@16:     mutable value_type error_data_;
Chris@16:     mutable value_type data_;
Chris@16:     mutable bool dirty_;
Chris@16:     mutable bool unsorted_;
Chris@16:     mutable bool is_manhattan_;
Chris@16: 
Chris@16:   private:
Chris@16:     //functions
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 ) const {
Chris@16:       clean();
Chris@16:       typename polygon_45_formation<Unit>::Polygon45Formation pf(fracture_holes);
Chris@16:       //std::cout << "FORMING POLYGONS\n";
Chris@16:       pf.scan(container, data_.begin(), data_.end());
Chris@16:     }
Chris@16: 
Chris@16:     template <typename geometry_type>
Chris@16:     void insert_dispatch(const geometry_type& geometry_object, bool is_hole, undefined_concept) {
Chris@16:       insert(geometry_object.begin(), geometry_object.end(), is_hole);
Chris@16:     }
Chris@16:     template <typename geometry_type>
Chris@16:     void insert_dispatch(const geometry_type& geometry_object, bool is_hole, rectangle_concept tag);
Chris@16:     template <typename geometry_type>
Chris@16:     void insert_dispatch(const geometry_type& geometry_object, bool is_hole, polygon_90_concept ) {
Chris@16:       insert_vertex_sequence(begin_points(geometry_object), end_points(geometry_object), winding(geometry_object), is_hole);
Chris@16:     }
Chris@16:     template <typename geometry_type>
Chris@16:     void insert_dispatch(const geometry_type& geometry_object, bool is_hole, polygon_90_with_holes_concept ) {
Chris@16:       insert_vertex_sequence(begin_points(geometry_object), end_points(geometry_object), winding(geometry_object), is_hole);
Chris@16:       for(typename polygon_with_holes_traits<geometry_type>::iterator_holes_type itr =
Chris@16:             begin_holes(geometry_object); itr != end_holes(geometry_object);
Chris@16:           ++itr) {
Chris@16:         insert_vertex_sequence(begin_points(*itr), end_points(*itr), winding(*itr), !is_hole);
Chris@16:       }
Chris@16:     }
Chris@16:     template <typename geometry_type>
Chris@16:     void insert_dispatch(const geometry_type& geometry_object, bool is_hole, polygon_45_concept ) {
Chris@16:       insert_vertex_sequence(begin_points(geometry_object), end_points(geometry_object), winding(geometry_object), is_hole);
Chris@16:     }
Chris@16:     template <typename geometry_type>
Chris@16:     void insert_dispatch(const geometry_type& geometry_object, bool is_hole, polygon_45_with_holes_concept ) {
Chris@16:       insert_vertex_sequence(begin_points(geometry_object), end_points(geometry_object), winding(geometry_object), is_hole);
Chris@16:       for(typename polygon_with_holes_traits<geometry_type>::iterator_holes_type itr =
Chris@16:             begin_holes(geometry_object); itr != end_holes(geometry_object);
Chris@16:           ++itr) {
Chris@16:         insert_vertex_sequence(begin_points(*itr), end_points(*itr), winding(*itr), !is_hole);
Chris@16:       }
Chris@16:     }
Chris@16:     template <typename geometry_type>
Chris@16:     void insert_dispatch(const geometry_type& geometry_object, bool is_hole, polygon_45_set_concept ) {
Chris@16:       polygon_45_set_data ps;
Chris@16:       assign(ps, geometry_object);
Chris@16:       insert(ps, is_hole);
Chris@16:     }
Chris@16:     template <typename geometry_type>
Chris@16:     void insert_dispatch(const geometry_type& geometry_object, bool is_hole, polygon_90_set_concept ) {
Chris@16:       std::list<polygon_90_data<coordinate_type> > pl;
Chris@16:       assign(pl, geometry_object);
Chris@16:       insert(pl.begin(), pl.end(), is_hole);
Chris@16:     }
Chris@16: 
Chris@16:     void insert_vertex_half_edge_45_pair(const point_data<Unit>& pt1, point_data<Unit>& pt2,
Chris@16:                                          const point_data<Unit>& pt3, direction_1d wdir);
Chris@16: 
Chris@16:     template <typename geometry_type>
Chris@16:     polygon_45_set_data& insert_with_resize_dispatch(const geometry_type& poly,
Chris@16:                                                      coordinate_type resizing, RoundingOption rounding,
Chris@16:                                                      CornerOption corner, bool hole, polygon_45_concept tag);
Chris@16: 
Chris@16:     // accumulate the bloated polygon with holes
Chris@16:     template <typename geometry_type>
Chris@16:     polygon_45_set_data& insert_with_resize_dispatch(const geometry_type& poly,
Chris@16:                                                      coordinate_type resizing, RoundingOption rounding,
Chris@16:                                                      CornerOption corner, bool hole, polygon_45_with_holes_concept tag);
Chris@16: 
Chris@16:     static void snap_vertex_45(Vertex45Compact& vertex);
Chris@16: 
Chris@16:   public:
Chris@16:     template <int op>
Chris@16:     void applyAdaptiveBoolean_(const polygon_45_set_data& rvalue) const;
Chris@16:     template <int op>
Chris@16:     void applyAdaptiveBoolean_(polygon_45_set_data& result, const polygon_45_set_data& rvalue) const;
Chris@16:     template <int op>
Chris@16:     void applyAdaptiveUnary_() const;
Chris@16:   };
Chris@16: 
Chris@16:   template <typename T>
Chris@16:   struct geometry_concept<polygon_45_set_data<T> > {
Chris@16:     typedef polygon_45_set_concept type;
Chris@16:   };
Chris@16: 
Chris@16:   template <typename iT, typename T>
Chris@16:   void scale_up_vertex_45_compact_range(iT beginr, iT endr, T factor) {
Chris@16:     for( ; beginr != endr; ++beginr) {
Chris@16:       scale_up((*beginr).pt, factor);
Chris@16:     }
Chris@16:   }
Chris@16:   template <typename iT, typename T>
Chris@16:   void scale_down_vertex_45_compact_range_blindly(iT beginr, iT endr, T factor) {
Chris@16:     for( ; beginr != endr; ++beginr) {
Chris@16:       scale_down((*beginr).pt, factor);
Chris@16:     }
Chris@16:   }
Chris@16: 
Chris@16:   template <typename Unit>
Chris@16:   inline std::pair<int, int> characterizeEdge45(const point_data<Unit>& pt1, const point_data<Unit>& pt2) {
Chris@16:     std::pair<int, int> retval(0, 1);
Chris@16:     if(pt1.x() == pt2.x()) {
Chris@16:       retval.first = 3;
Chris@16:       retval.second = -1;
Chris@16:       return retval;
Chris@16:     }
Chris@16:     //retval.second = pt1.x() < pt2.x() ? -1 : 1;
Chris@16:     retval.second = 1;
Chris@16:     if(pt1.y() == pt2.y()) {
Chris@16:       retval.first = 1;
Chris@16:     } else if(pt1.x() < pt2.x()) {
Chris@16:       if(pt1.y() < pt2.y()) {
Chris@16:         retval.first = 2;
Chris@16:       } else {
Chris@16:         retval.first = 0;
Chris@16:       }
Chris@16:     } else {
Chris@16:       if(pt1.y() < pt2.y()) {
Chris@16:         retval.first = 0;
Chris@16:       } else {
Chris@16:         retval.first = 2;
Chris@16:       }
Chris@16:     }
Chris@16:     return retval;
Chris@16:   }
Chris@16: 
Chris@16:   template <typename cT, typename pT>
Chris@16:   bool insert_vertex_half_edge_45_pair_into_vector(cT& output,
Chris@16:                                        const pT& pt1, pT& pt2,
Chris@16:                                        const pT& pt3,
Chris@16:                                        direction_1d wdir) {
Chris@16:     int multiplier = wdir == LOW ? -1 : 1;
Chris@16:     typename cT::value_type vertex(pt2, 0, 0);
Chris@16:     //std::cout << pt1 << " " << pt2 << " " << pt3 << std::endl;
Chris@16:     std::pair<int, int> check;
Chris@16:     check = characterizeEdge45(pt1, pt2);
Chris@16:     //std::cout << "index " << check.first << " " << check.second * -multiplier << std::endl;
Chris@16:     vertex.count[check.first] += check.second * -multiplier;
Chris@16:     check = characterizeEdge45(pt2, pt3);
Chris@16:     //std::cout << "index " << check.first << " " << check.second * multiplier << std::endl;
Chris@16:     vertex.count[check.first] += check.second * multiplier;
Chris@16:     output.push_back(vertex);
Chris@16:     return vertex.count.is_45();
Chris@16:   }
Chris@16: 
Chris@16:   template <typename Unit>
Chris@16:   inline void polygon_45_set_data<Unit>::insert_vertex_half_edge_45_pair(const point_data<Unit>& pt1, point_data<Unit>& pt2,
Chris@16:                                                                          const point_data<Unit>& pt3,
Chris@16:                                                                          direction_1d wdir) {
Chris@16:     if(insert_vertex_half_edge_45_pair_into_vector(data_, pt1, pt2, pt3, wdir)) is_manhattan_ = false;
Chris@16:   }
Chris@16: 
Chris@16:   template <typename Unit>
Chris@16:   template <class iT>
Chris@16:   inline void polygon_45_set_data<Unit>::insert_vertex_sequence(iT begin_vertex, iT end_vertex,
Chris@16:                                                                 direction_1d winding, bool is_hole) {
Chris@16:     if(begin_vertex == end_vertex) return;
Chris@16:     if(is_hole) winding = winding.backward();
Chris@16:     iT itr = begin_vertex;
Chris@16:     if(itr == end_vertex) return;
Chris@16:     point_data<Unit> firstPt = *itr;
Chris@16:     ++itr;
Chris@16:     point_data<Unit> secondPt(firstPt);
Chris@16:     //skip any duplicate points
Chris@16:     do {
Chris@16:       if(itr == end_vertex) return;
Chris@16:       secondPt = *itr;
Chris@16:       ++itr;
Chris@16:     } while(secondPt == firstPt);
Chris@16:     point_data<Unit> prevPt = secondPt;
Chris@16:     point_data<Unit> prevPrevPt = firstPt;
Chris@16:     while(itr != end_vertex) {
Chris@16:       point_data<Unit> pt = *itr;
Chris@16:       //skip any duplicate points
Chris@16:       if(pt == prevPt) {
Chris@16:         ++itr;
Chris@16:         continue;
Chris@16:       }
Chris@16:       //operate on the three points
Chris@16:       insert_vertex_half_edge_45_pair(prevPrevPt, prevPt, pt, winding);
Chris@16:       prevPrevPt = prevPt;
Chris@16:       prevPt = pt;
Chris@16:       ++itr;
Chris@16:     }
Chris@16:     if(prevPt != firstPt) {
Chris@16:       insert_vertex_half_edge_45_pair(prevPrevPt, prevPt, firstPt, winding);
Chris@16:       insert_vertex_half_edge_45_pair(prevPt, firstPt, secondPt, winding);
Chris@16:     } else {
Chris@16:       insert_vertex_half_edge_45_pair(prevPrevPt, firstPt, secondPt, winding);
Chris@16:     }
Chris@16:     dirty_ = true;
Chris@16:     unsorted_ = true;
Chris@16:   }
Chris@16: 
Chris@16:   // insert polygon set
Chris@16:   template <typename Unit>
Chris@16:   inline void polygon_45_set_data<Unit>::insert(const polygon_45_set_data<Unit>& polygon_set, bool is_hole) {
Chris@16:     std::size_t count = data_.size();
Chris@16:     data_.insert(data_.end(), polygon_set.data_.begin(), polygon_set.data_.end());
Chris@16:     error_data_.insert(error_data_.end(), polygon_set.error_data_.begin(),
Chris@16:                        polygon_set.error_data_.end());
Chris@16:     if(is_hole) {
Chris@16:       for(std::size_t i = count; i < data_.size(); ++i) {
Chris@16:         data_[i].count = data_[i].count.invert();
Chris@16:       }
Chris@16:     }
Chris@16:     dirty_ = true;
Chris@16:     unsorted_ = true;
Chris@16:     if(polygon_set.is_manhattan_ == false) is_manhattan_ = false;
Chris@16:     return;
Chris@16:   }
Chris@16:   // insert polygon set
Chris@16:   template <typename Unit>
Chris@16:   template <typename coord_type>
Chris@16:   inline void polygon_45_set_data<Unit>::insert(const polygon_45_set_data<coord_type>& polygon_set, bool is_hole) {
Chris@16:     std::size_t count = data_.size();
Chris@16:     for(typename polygon_45_set_data<coord_type>::iterator_type itr = polygon_set.begin();
Chris@16:         itr != polygon_set.end(); ++itr) {
Chris@16:       const typename polygon_45_set_data<coord_type>::Vertex45Compact& v = *itr;
Chris@16:       typename polygon_45_set_data<Unit>::Vertex45Compact v2;
Chris@16:       v2.pt.x(static_cast<Unit>(v.pt.x()));
Chris@16:       v2.pt.y(static_cast<Unit>(v.pt.y()));
Chris@16:       v2.count = typename polygon_45_formation<Unit>::Vertex45Count(v.count[0], v.count[1], v.count[2], v.count[3]);
Chris@16:       data_.push_back(v2);
Chris@16:     }
Chris@16:     polygon_45_set_data<coord_type> tmp;
Chris@16:     polygon_set.get_error_data(tmp);
Chris@16:     for(typename polygon_45_set_data<coord_type>::iterator_type itr = tmp.begin();
Chris@16:         itr != tmp.end(); ++itr) {
Chris@16:       const typename polygon_45_set_data<coord_type>::Vertex45Compact& v = *itr;
Chris@16:       typename polygon_45_set_data<Unit>::Vertex45Compact v2;
Chris@16:       v2.pt.x(static_cast<Unit>(v.pt.x()));
Chris@16:       v2.pt.y(static_cast<Unit>(v.pt.y()));
Chris@16:       v2.count = typename polygon_45_formation<Unit>::Vertex45Count(v.count[0], v.count[1], v.count[2], v.count[3]);
Chris@16:       error_data_.push_back(v2);
Chris@16:     }
Chris@16:     if(is_hole) {
Chris@16:       for(std::size_t i = count; i < data_.size(); ++i) {
Chris@16:         data_[i].count = data_[i].count.invert();
Chris@16:       }
Chris@16:     }
Chris@16:     dirty_ = true;
Chris@16:     unsorted_ = true;
Chris@16:     if(polygon_set.is_manhattan() == false) is_manhattan_ = false;
Chris@16:     return;
Chris@16:   }
Chris@16: 
Chris@16:   template <typename cT, typename rT>
Chris@16:   void insert_rectangle_into_vector_45(cT& output, const rT& rect, bool is_hole) {
Chris@16:     point_data<typename rectangle_traits<rT>::coordinate_type>
Chris@16:       llpt = ll(rect), lrpt = lr(rect), ulpt = ul(rect), urpt = ur(rect);
Chris@16:     direction_1d dir = COUNTERCLOCKWISE;
Chris@16:     if(is_hole) dir = CLOCKWISE;
Chris@16:     insert_vertex_half_edge_45_pair_into_vector(output, llpt, lrpt, urpt, dir);
Chris@16:     insert_vertex_half_edge_45_pair_into_vector(output, lrpt, urpt, ulpt, dir);
Chris@16:     insert_vertex_half_edge_45_pair_into_vector(output, urpt, ulpt, llpt, dir);
Chris@16:     insert_vertex_half_edge_45_pair_into_vector(output, ulpt, llpt, lrpt, dir);
Chris@16:   }
Chris@16: 
Chris@16:   template <typename Unit>
Chris@16:   template <typename geometry_type>
Chris@16:   inline void polygon_45_set_data<Unit>::insert_dispatch(const geometry_type& geometry_object,
Chris@16:                                                          bool is_hole, rectangle_concept ) {
Chris@16:     dirty_ = true;
Chris@16:     unsorted_ = true;
Chris@16:     insert_rectangle_into_vector_45(data_, geometry_object, is_hole);
Chris@16:   }
Chris@16: 
Chris@16:   // get the external boundary rectangle
Chris@16:   template <typename Unit>
Chris@16:   template <typename rectangle_type>
Chris@16:   inline bool polygon_45_set_data<Unit>::extents(rectangle_type& rect) const{
Chris@16:     clean();
Chris@16:     if(empty()) {
Chris@16:       return false;
Chris@16:     }
Chris@16:     Unit low = (std::numeric_limits<Unit>::max)();
Chris@16:     Unit high = (std::numeric_limits<Unit>::min)();
Chris@16:     interval_data<Unit> xivl(low, high);
Chris@16:     interval_data<Unit> yivl(low, high);
Chris@16:     for(typename value_type::const_iterator itr = data_.begin();
Chris@16:         itr != data_.end(); ++ itr) {
Chris@16:       if((*itr).pt.x() > xivl.get(HIGH))
Chris@16:         xivl.set(HIGH, (*itr).pt.x());
Chris@16:       if((*itr).pt.x() < xivl.get(LOW))
Chris@16:         xivl.set(LOW, (*itr).pt.x());
Chris@16:       if((*itr).pt.y() > yivl.get(HIGH))
Chris@16:         yivl.set(HIGH, (*itr).pt.y());
Chris@16:       if((*itr).pt.y() < yivl.get(LOW))
Chris@16:         yivl.set(LOW, (*itr).pt.y());
Chris@16:     }
Chris@16:     rect = construct<rectangle_type>(xivl, yivl);
Chris@16:     return true;
Chris@16:   }
Chris@16: 
Chris@16:   //this function snaps the vertex and two half edges
Chris@16:   //to be both even or both odd coordinate values if one of the edges is 45
Chris@16:   //and throws an excpetion if an edge is non-manhattan, non-45.
Chris@16:   template <typename Unit>
Chris@16:   inline void polygon_45_set_data<Unit>::snap_vertex_45(typename polygon_45_set_data<Unit>::Vertex45Compact& vertex) {
Chris@16:     bool plus45 = vertex.count[2] != 0;
Chris@16:     bool minus45 = vertex.count[0] != 0;
Chris@16:     if(plus45 || minus45) {
Chris@16:       if(abs(vertex.pt.x()) % 2 != abs(vertex.pt.y()) % 2) {
Chris@16:         if(vertex.count[1] != 0 ||
Chris@16:            (plus45 && minus45)) {
Chris@16:           //move right
Chris@16:           vertex.pt.x(vertex.pt.x() + 1);
Chris@16:         } else {
Chris@16:           //assert that vertex.count[3] != 0
Chris@16:           Unit modifier = plus45 ? -1 : 1;
Chris@16:           vertex.pt.y(vertex.pt.y() + modifier);
Chris@16:         }
Chris@16:       }
Chris@16:     }
Chris@16:   }
Chris@16: 
Chris@16:   template <typename Unit>
Chris@16:   inline void polygon_45_set_data<Unit>::snap() const {
Chris@16:     for(typename value_type::iterator itr = data_.begin();
Chris@16:         itr != data_.end(); ++itr) {
Chris@16:       snap_vertex_45(*itr);
Chris@16:     }
Chris@16:   }
Chris@16: 
Chris@16:   // |= &= += *= -= ^= binary operators
Chris@16:   template <typename Unit>
Chris@16:   inline polygon_45_set_data<Unit>& polygon_45_set_data<Unit>::operator|=(const polygon_45_set_data<Unit>& b) {
Chris@16:     insert(b);
Chris@16:     return *this;
Chris@16:   }
Chris@16:   template <typename Unit>
Chris@16:   inline polygon_45_set_data<Unit>& polygon_45_set_data<Unit>::operator&=(const polygon_45_set_data<Unit>& b) {
Chris@16:     //b.sort();
Chris@16:     //sort();
Chris@16:     applyAdaptiveBoolean_<1>(b);
Chris@16:     dirty_ = false;
Chris@16:     unsorted_ = false;
Chris@16:     return *this;
Chris@16:   }
Chris@16:   template <typename Unit>
Chris@16:   inline polygon_45_set_data<Unit>& polygon_45_set_data<Unit>::operator+=(const polygon_45_set_data<Unit>& b) {
Chris@16:     return (*this) |= b;
Chris@16:   }
Chris@16:   template <typename Unit>
Chris@16:   inline polygon_45_set_data<Unit>& polygon_45_set_data<Unit>::operator*=(const polygon_45_set_data<Unit>& b) {
Chris@16:     return (*this) &= b;
Chris@16:   }
Chris@16:   template <typename Unit>
Chris@16:   inline polygon_45_set_data<Unit>& polygon_45_set_data<Unit>::operator-=(const polygon_45_set_data<Unit>& b) {
Chris@16:     //b.sort();
Chris@16:     //sort();
Chris@16:     applyAdaptiveBoolean_<2>(b);
Chris@16:     dirty_ = false;
Chris@16:     unsorted_ = false;
Chris@16:     return *this;
Chris@16:   }
Chris@16:   template <typename Unit>
Chris@16:   inline polygon_45_set_data<Unit>& polygon_45_set_data<Unit>::operator^=(const polygon_45_set_data<Unit>& b) {
Chris@16:     //b.sort();
Chris@16:     //sort();
Chris@16:     applyAdaptiveBoolean_<3>(b);
Chris@16:     dirty_ = false;
Chris@16:     unsorted_ = false;
Chris@16:     return *this;
Chris@16:   }
Chris@16: 
Chris@16:   template <typename Unit>
Chris@16:   inline polygon_45_set_data<Unit>& polygon_45_set_data<Unit>::operator+=(Unit delta) {
Chris@16:     return resize(delta);
Chris@16:   }
Chris@16:   template <typename Unit>
Chris@16:   inline polygon_45_set_data<Unit>& polygon_45_set_data<Unit>::operator-=(Unit delta) {
Chris@16:     return (*this) += -delta;
Chris@16:   }
Chris@16: 
Chris@16:   template <typename Unit>
Chris@16:   inline polygon_45_set_data<Unit>&
Chris@16:   polygon_45_set_data<Unit>::resize(Unit resizing, RoundingOption rounding, CornerOption corner) {
Chris@16:     if(resizing == 0) return *this;
Chris@16:     std::list<polygon_45_with_holes_data<Unit> > pl;
Chris@16:     get_polygons_with_holes(pl);
Chris@16:     clear();
Chris@16:     for(typename std::list<polygon_45_with_holes_data<Unit> >::iterator itr = pl.begin(); itr != pl.end(); ++itr) {
Chris@16:       insert_with_resize(*itr, resizing, rounding, corner);
Chris@16:     }
Chris@16:     clean();
Chris@16:     //perterb 45 edges to prevent non-integer intersection errors upon boolean op
Chris@16:     //snap();
Chris@16:     return *this;
Chris@16:   }
Chris@16: 
Chris@16:   //distance is assumed to be positive
Chris@16:   inline int roundClosest(double distance) {
Chris@16:     int f = (int)distance;
Chris@16:     if(distance - (double)f < 0.5) return f;
Chris@16:     return f+1;
Chris@16:   }
Chris@16: 
Chris@16:   //distance is assumed to be positive
Chris@16:   template <typename Unit>
Chris@16:   inline Unit roundWithOptions(double distance, RoundingOption rounding) {
Chris@16:     if(rounding == CLOSEST) {
Chris@16:       return roundClosest(distance);
Chris@16:     } else if(rounding == OVERSIZE) {
Chris@16:       return (Unit)distance + 1;
Chris@16:     } else { //UNDERSIZE
Chris@16:       return (Unit)distance;
Chris@16:     }
Chris@16:   }
Chris@16: 
Chris@16:   // 0 is east, 1 is northeast, 2 is north, 3 is northwest, 4 is west, 5 is southwest, 6 is south
Chris@16:   // 7 is southwest
Chris@16:   template <typename Unit>
Chris@16:   inline point_data<Unit> bloatVertexInDirWithOptions(const point_data<Unit>& point, unsigned int dir,
Chris@16:                                                       Unit bloating, RoundingOption rounding) {
Chris@16:     const double sqrt2 = 1.4142135623730950488016887242097;
Chris@16:     if(dir & 1) {
Chris@16:       Unit unitDistance = (Unit)bloating;
Chris@16:       if(rounding != SQRT2) {
Chris@16:         //45 degree bloating
Chris@16:         double distance = (double)bloating;
Chris@16:         distance /= sqrt2;  // multiply by 1/sqrt2
Chris@16:         unitDistance = roundWithOptions<Unit>(distance, rounding);
Chris@16:       }
Chris@16:       int xMultiplier = 1;
Chris@16:       int yMultiplier = 1;
Chris@16:       if(dir == 3 || dir == 5) xMultiplier = -1;
Chris@16:       if(dir == 5 || dir == 7) yMultiplier = -1;
Chris@16:       return point_data<Unit>(point.x()+xMultiplier*unitDistance,
Chris@16:                    point.y()+yMultiplier*unitDistance);
Chris@16:     } else {
Chris@16:       if(dir == 0)
Chris@16:         return point_data<Unit>(point.x()+bloating, point.y());
Chris@16:       if(dir == 2)
Chris@16:         return point_data<Unit>(point.x(), point.y()+bloating);
Chris@16:       if(dir == 4)
Chris@16:         return point_data<Unit>(point.x()-bloating, point.y());
Chris@16:       if(dir == 6)
Chris@16:         return point_data<Unit>(point.x(), point.y()-bloating);
Chris@16:       return point_data<Unit>();
Chris@16:     }
Chris@16:   }
Chris@16: 
Chris@16:   template <typename Unit>
Chris@16:   inline unsigned int getEdge45Direction(const point_data<Unit>& pt1, const point_data<Unit>& pt2) {
Chris@16:     if(pt1.x() == pt2.x()) {
Chris@16:       if(pt1.y() < pt2.y()) return 2;
Chris@16:       return 6;
Chris@16:     }
Chris@16:     if(pt1.y() == pt2.y()) {
Chris@16:       if(pt1.x() < pt2.x()) return 0;
Chris@16:       return 4;
Chris@16:     }
Chris@16:     if(pt2.y() > pt1.y()) {
Chris@16:       if(pt2.x() > pt1.x()) return 1;
Chris@16:       return 3;
Chris@16:     }
Chris@16:     if(pt2.x() > pt1.x()) return 7;
Chris@16:     return 5;
Chris@16:   }
Chris@16: 
Chris@16:   inline unsigned int getEdge45NormalDirection(unsigned int dir, int multiplier) {
Chris@16:     if(multiplier < 0)
Chris@16:       return (dir + 2) % 8;
Chris@16:     return (dir + 4 + 2) % 8;
Chris@16:   }
Chris@16: 
Chris@16:   template <typename Unit>
Chris@16:   inline point_data<Unit> getIntersectionPoint(const point_data<Unit>& pt1, unsigned int slope1,
Chris@16:                                                const point_data<Unit>& pt2, unsigned int slope2) {
Chris@16:     //the intention here is to use all integer arithmetic without causing overflow
Chris@16:     //turncation error or divide by zero error
Chris@16:     //I don't use floating point arithmetic because its precision may not be high enough
Chris@16:     //at the extremes of the integer range
Chris@16:     typedef typename coordinate_traits<Unit>::area_type LongUnit;
Chris@16:     const Unit rises[8] = {0, 1, 1, 1, 0, -1, -1, -1};
Chris@16:     const Unit runs[8] = {1, 1, 0, -1, -1, -1, 0, 1};
Chris@16:     LongUnit rise1 = rises[slope1];
Chris@16:     LongUnit rise2 = rises[slope2];
Chris@16:     LongUnit run1 = runs[slope1];
Chris@16:     LongUnit run2 = runs[slope2];
Chris@16:     LongUnit x1 = (LongUnit)pt1.x();
Chris@16:     LongUnit x2 = (LongUnit)pt2.x();
Chris@16:     LongUnit y1 = (LongUnit)pt1.y();
Chris@16:     LongUnit y2 = (LongUnit)pt2.y();
Chris@16:     Unit x = 0;
Chris@16:     Unit y = 0;
Chris@16:     if(run1 == 0) {
Chris@16:       x = pt1.x();
Chris@16:       y = (Unit)(((x1 - x2) * rise2) / run2) + pt2.y();
Chris@16:     } else if(run2 == 0) {
Chris@16:       x = pt2.x();
Chris@16:       y = (Unit)(((x2 - x1) * rise1) / run1) + pt1.y();
Chris@16:     } else {
Chris@16:       // y - y1 = (rise1/run1)(x - x1)
Chris@16:       // y - y2 = (rise2/run2)(x - x2)
Chris@16:       // y = (rise1/run1)(x - x1) + y1 = (rise2/run2)(x - x2) + y2
Chris@16:       // (rise1/run1 - rise2/run2)x = y2 - y1 + rise1/run1 x1 - rise2/run2 x2
Chris@16:       // x = (y2 - y1 + rise1/run1 x1 - rise2/run2 x2)/(rise1/run1 - rise2/run2)
Chris@16:       // x = (y2 - y1 + rise1/run1 x1 - rise2/run2 x2)(rise1 run2 - rise2 run1)/(run1 run2)
Chris@16:       x = (Unit)((y2 - y1 + ((rise1 * x1) / run1) - ((rise2 * x2) / run2)) *
Chris@16:                  (run1 * run2) / (rise1 * run2 - rise2 * run1));
Chris@16:       if(rise1 == 0) {
Chris@16:         y = pt1.y();
Chris@16:       } else if(rise2 == 0) {
Chris@16:         y = pt2.y();
Chris@16:       } else {
Chris@16:         // y - y1 = (rise1/run1)(x - x1)
Chris@16:         // (run1/rise1)(y - y1) = x - x1
Chris@16:         // x = (run1/rise1)(y - y1) + x1 = (run2/rise2)(y - y2) + x2
Chris@16:         y = (Unit)((x2 - x1 + ((run1 * y1) / rise1) - ((run2 * y2) / rise2)) *
Chris@16:                    (rise1 * rise2) / (run1 * rise2 - run2 * rise1));
Chris@16:       }
Chris@16:     }
Chris@16:     return point_data<Unit>(x, y);
Chris@16:   }
Chris@16: 
Chris@16:   template <typename Unit>
Chris@16:   inline
Chris@16:   void handleResizingEdge45_SQRT1OVER2(polygon_45_set_data<Unit>& sizingSet, point_data<Unit> first,
Chris@16:                                        point_data<Unit> second, Unit resizing, CornerOption corner) {
Chris@16:     if(first.x() == second.x()) {
Chris@16:       sizingSet.insert(rectangle_data<Unit>(first.x() - resizing, first.y(), first.x() + resizing, second.y()));
Chris@16:       return;
Chris@16:     }
Chris@16:     if(first.y() == second.y()) {
Chris@16:       sizingSet.insert(rectangle_data<Unit>(first.x(), first.y() - resizing, second.x(), first.y() + resizing));
Chris@16:       return;
Chris@16:     }
Chris@16:     std::vector<point_data<Unit> > pts;
Chris@16:     Unit bloating = resizing < 0 ? -resizing : resizing;
Chris@16:     if(corner == UNFILLED) {
Chris@16:       //we have to round up
Chris@16:       bloating = bloating / 2 + bloating % 2 ; //round up
Chris@16:       if(second.x() < first.x()) std::swap(first, second);
Chris@16:       if(first.y() < second.y()) { //upward sloping
Chris@16:         pts.push_back(point_data<Unit>(first.x() + bloating, first.y() - bloating));
Chris@16:         pts.push_back(point_data<Unit>(first.x() - bloating, first.y() + bloating));
Chris@16:         pts.push_back(point_data<Unit>(second.x() - bloating, second.y() + bloating));
Chris@16:         pts.push_back(point_data<Unit>(second.x() + bloating, second.y() - bloating));
Chris@16:         sizingSet.insert_vertex_sequence(pts.begin(), pts.end(), CLOCKWISE, false);
Chris@16:       } else { //downward sloping
Chris@16:         pts.push_back(point_data<Unit>(first.x() + bloating, first.y() + bloating));
Chris@16:         pts.push_back(point_data<Unit>(first.x() - bloating, first.y() - bloating));
Chris@16:         pts.push_back(point_data<Unit>(second.x() - bloating, second.y() - bloating));
Chris@16:         pts.push_back(point_data<Unit>(second.x() + bloating, second.y() + bloating));
Chris@16:         sizingSet.insert_vertex_sequence(pts.begin(), pts.end(), COUNTERCLOCKWISE, false);
Chris@16:       }
Chris@16:       return;
Chris@16:     }
Chris@16:     if(second.x() < first.x()) std::swap(first, second);
Chris@16:     if(first.y() < second.y()) { //upward sloping
Chris@16:       pts.push_back(point_data<Unit>(first.x(), first.y() - bloating));
Chris@16:       pts.push_back(point_data<Unit>(first.x() - bloating, first.y()));
Chris@16:       pts.push_back(point_data<Unit>(second.x(), second.y() + bloating));
Chris@16:       pts.push_back(point_data<Unit>(second.x() + bloating, second.y()));
Chris@16:       sizingSet.insert_vertex_sequence(pts.begin(), pts.end(), CLOCKWISE, false);
Chris@16:     } else { //downward sloping
Chris@16:       pts.push_back(point_data<Unit>(first.x() - bloating, first.y()));
Chris@16:       pts.push_back(point_data<Unit>(first.x(), first.y() + bloating));
Chris@16:       pts.push_back(point_data<Unit>(second.x() + bloating, second.y()));
Chris@16:       pts.push_back(point_data<Unit>(second.x(), second.y() - bloating));
Chris@16:       sizingSet.insert_vertex_sequence(pts.begin(), pts.end(), CLOCKWISE, false);
Chris@16:     }
Chris@16:   }
Chris@16: 
Chris@16: 
Chris@16:   template <typename Unit>
Chris@16:   inline
Chris@16:   void handleResizingEdge45(polygon_45_set_data<Unit>& sizingSet, point_data<Unit> first,
Chris@16:                             point_data<Unit> second, Unit resizing, RoundingOption rounding) {
Chris@16:     if(first.x() == second.x()) {
Chris@16:       sizingSet.insert(rectangle_data<int>(first.x() - resizing, first.y(), first.x() + resizing, second.y()));
Chris@16:       return;
Chris@16:     }
Chris@16:     if(first.y() == second.y()) {
Chris@16:       sizingSet.insert(rectangle_data<int>(first.x(), first.y() - resizing, second.x(), first.y() + resizing));
Chris@16:       return;
Chris@16:     }
Chris@16:     //edge is 45
Chris@16:     std::vector<point_data<Unit> > pts;
Chris@16:     Unit bloating = resizing < 0 ? -resizing : resizing;
Chris@16:     if(second.x() < first.x()) std::swap(first, second);
Chris@16:     if(first.y() < second.y()) {
Chris@16:       pts.push_back(bloatVertexInDirWithOptions(first, 3, bloating, rounding));
Chris@16:       pts.push_back(bloatVertexInDirWithOptions(first, 7, bloating, rounding));
Chris@16:       pts.push_back(bloatVertexInDirWithOptions(second, 7, bloating, rounding));
Chris@16:       pts.push_back(bloatVertexInDirWithOptions(second, 3, bloating, rounding));
Chris@16:       sizingSet.insert_vertex_sequence(pts.begin(), pts.end(), HIGH, false);
Chris@16:     } else {
Chris@16:       pts.push_back(bloatVertexInDirWithOptions(first, 1, bloating, rounding));
Chris@16:       pts.push_back(bloatVertexInDirWithOptions(first, 5, bloating, rounding));
Chris@16:       pts.push_back(bloatVertexInDirWithOptions(second, 5, bloating, rounding));
Chris@16:       pts.push_back(bloatVertexInDirWithOptions(second, 1, bloating, rounding));
Chris@16:       sizingSet.insert_vertex_sequence(pts.begin(), pts.end(), HIGH, false);
Chris@16:     }
Chris@16:   }
Chris@16: 
Chris@16:   template <typename Unit>
Chris@16:   inline point_data<Unit> bloatVertexInDirWithSQRT1OVER2(int edge1, int normal1, const point_data<Unit>& second, Unit bloating,
Chris@16:                                                          bool first) {
Chris@16:     orientation_2d orient = first ? HORIZONTAL : VERTICAL;
Chris@16:     orientation_2d orientp = orient.get_perpendicular();
Chris@16:     int multiplier = first ? 1 : -1;
Chris@16:     point_data<Unit> pt1(second);
Chris@16:     if(edge1 == 1) {
Chris@16:       if(normal1 == 3) {
Chris@16:         move(pt1, orient, -multiplier * bloating);
Chris@16:       } else {
Chris@16:         move(pt1, orientp, -multiplier * bloating);
Chris@16:       }
Chris@16:     } else if(edge1 == 3) {
Chris@16:       if(normal1 == 1) {
Chris@16:         move(pt1, orient, multiplier * bloating);
Chris@16:       } else {
Chris@16:         move(pt1, orientp, -multiplier * bloating);
Chris@16:       }
Chris@16:     } else if(edge1 == 5) {
Chris@16:       if(normal1 == 3) {
Chris@16:         move(pt1, orientp, multiplier * bloating);
Chris@16:       } else {
Chris@16:         move(pt1, orient, multiplier * bloating);
Chris@16:       }
Chris@16:     } else {
Chris@16:       if(normal1 == 5) {
Chris@16:         move(pt1, orient, -multiplier * bloating);
Chris@16:       } else {
Chris@16:         move(pt1, orientp, multiplier * bloating);
Chris@16:       }
Chris@16:     }
Chris@16:     return pt1;
Chris@16:   }
Chris@16: 
Chris@16:   template <typename Unit>
Chris@16:   inline
Chris@16:   void handleResizingVertex45(polygon_45_set_data<Unit>& sizingSet, const point_data<Unit>& first,
Chris@16:                               const point_data<Unit>& second, const point_data<Unit>& third, Unit resizing,
Chris@16:                               RoundingOption rounding, CornerOption corner,
Chris@16:                               int multiplier) {
Chris@16:     unsigned int edge1 = getEdge45Direction(first, second);
Chris@16:     unsigned int edge2 = getEdge45Direction(second, third);
Chris@16:     unsigned int diffAngle;
Chris@16:     if(multiplier < 0)
Chris@16:       diffAngle = (edge2 + 8 - edge1) % 8;
Chris@16:     else
Chris@16:       diffAngle = (edge1 + 8 - edge2) % 8;
Chris@16:     if(diffAngle < 4) {
Chris@16:       if(resizing > 0) return; //accute interior corner
Chris@16:       else multiplier *= -1; //make it appear to be an accute exterior angle
Chris@16:     }
Chris@16:     Unit bloating = abs(resizing);
Chris@16:     if(rounding == SQRT1OVER2) {
Chris@16:       if(edge1 % 2 && edge2 % 2) return;
Chris@16:       if(corner == ORTHOGONAL && edge1 % 2 == 0 && edge2 % 2 == 0) {
Chris@16:         rectangle_data<Unit> insertion_rect;
Chris@16:         set_points(insertion_rect, second, second);
Chris@16:         bloat(insertion_rect, bloating);
Chris@16:         sizingSet.insert(insertion_rect);
Chris@16:       } else if(corner != ORTHOGONAL) {
Chris@16:         point_data<Unit> pt1(0, 0);
Chris@16:         point_data<Unit> pt2(0, 0);
Chris@16:         unsigned int normal1 = getEdge45NormalDirection(edge1, multiplier);
Chris@16:         unsigned int normal2 = getEdge45NormalDirection(edge2, multiplier);
Chris@16:         if(edge1 % 2) {
Chris@16:           pt1 = bloatVertexInDirWithSQRT1OVER2(edge1, normal1, second, bloating, true);
Chris@16:         } else {
Chris@16:           pt1 = bloatVertexInDirWithOptions(second, normal1, bloating, UNDERSIZE);
Chris@16:         }
Chris@16:         if(edge2 % 2) {
Chris@16:           pt2 = bloatVertexInDirWithSQRT1OVER2(edge2, normal2, second, bloating, false);
Chris@16:         } else {
Chris@16:           pt2 = bloatVertexInDirWithOptions(second, normal2, bloating, UNDERSIZE);
Chris@16:         }
Chris@16:         std::vector<point_data<Unit> > pts;
Chris@16:         pts.push_back(pt1);
Chris@16:         pts.push_back(second);
Chris@16:         pts.push_back(pt2);
Chris@16:         pts.push_back(getIntersectionPoint(pt1, edge1, pt2, edge2));
Chris@16:         polygon_45_data<Unit> poly(pts.begin(), pts.end());
Chris@16:         sizingSet.insert(poly);
Chris@16:       } else {
Chris@16:         //ORTHOGONAL of a 45 degree corner
Chris@16:         int normal = 0;
Chris@16:         if(edge1 % 2) {
Chris@16:           normal = getEdge45NormalDirection(edge2, multiplier);
Chris@16:         } else {
Chris@16:           normal = getEdge45NormalDirection(edge1, multiplier);
Chris@16:         }
Chris@16:         rectangle_data<Unit> insertion_rect;
Chris@16:         point_data<Unit> edgePoint = bloatVertexInDirWithOptions(second, normal, bloating, UNDERSIZE);
Chris@16:         set_points(insertion_rect, second, edgePoint);
Chris@16:         if(normal == 0 || normal == 4)
Chris@16:           bloat(insertion_rect, VERTICAL, bloating);
Chris@16:         else
Chris@16:           bloat(insertion_rect, HORIZONTAL, bloating);
Chris@16:         sizingSet.insert(insertion_rect);
Chris@16:       }
Chris@16:       return;
Chris@16:     }
Chris@16:     unsigned int normal1 = getEdge45NormalDirection(edge1, multiplier);
Chris@16:     unsigned int normal2 = getEdge45NormalDirection(edge2, multiplier);
Chris@16:     point_data<Unit> edgePoint1 = bloatVertexInDirWithOptions(second, normal1, bloating, rounding);
Chris@16:     point_data<Unit> edgePoint2 = bloatVertexInDirWithOptions(second, normal2, bloating, rounding);
Chris@16:     //if the change in angle is 135 degrees it is an accute exterior corner
Chris@16:     if((edge1+ multiplier * 3) % 8 == edge2) {
Chris@16:       if(corner == ORTHOGONAL) {
Chris@16:         rectangle_data<Unit> insertion_rect;
Chris@16:         set_points(insertion_rect, edgePoint1, edgePoint2);
Chris@16:         sizingSet.insert(insertion_rect);
Chris@16:         return;
Chris@16:       }
Chris@16:     }
Chris@16:     std::vector<point_data<Unit> > pts;
Chris@16:     pts.push_back(edgePoint1);
Chris@16:     pts.push_back(second);
Chris@16:     pts.push_back(edgePoint2);
Chris@16:     pts.push_back(getIntersectionPoint(edgePoint1, edge1, edgePoint2, edge2));
Chris@16:     polygon_45_data<Unit> poly(pts.begin(), pts.end());
Chris@16:     sizingSet.insert(poly);
Chris@16:   }
Chris@16: 
Chris@16:   template <typename Unit>
Chris@16:   template <typename geometry_type>
Chris@16:   inline polygon_45_set_data<Unit>&
Chris@16:   polygon_45_set_data<Unit>::insert_with_resize_dispatch(const geometry_type& poly,
Chris@16:                                                          coordinate_type resizing,
Chris@16:                                                          RoundingOption rounding,
Chris@16:                                                          CornerOption corner,
Chris@16:                                                          bool hole, polygon_45_concept ) {
Chris@16:     direction_1d wdir = winding(poly);
Chris@16:     int multiplier = wdir == LOW ? -1 : 1;
Chris@16:     if(hole) resizing *= -1;
Chris@16:     typedef typename polygon_45_data<Unit>::iterator_type piterator;
Chris@16:     piterator first, second, third, end, real_end;
Chris@16:     real_end = end_points(poly);
Chris@16:     third = begin_points(poly);
Chris@16:     first = third;
Chris@16:     if(first == real_end) return *this;
Chris@16:     ++third;
Chris@16:     if(third == real_end) return *this;
Chris@16:     second = end = third;
Chris@16:     ++third;
Chris@16:     if(third == real_end) return *this;
Chris@16:     polygon_45_set_data<Unit> sizingSet;
Chris@16:     //insert minkofski shapes on edges and corners
Chris@16:     do {
Chris@16:       if(rounding != SQRT1OVER2) {
Chris@16:         handleResizingEdge45(sizingSet, *first, *second, resizing, rounding);
Chris@16:       } else {
Chris@16:         handleResizingEdge45_SQRT1OVER2(sizingSet, *first, *second, resizing, corner);
Chris@16:       }
Chris@16:       if(corner != UNFILLED)
Chris@16:         handleResizingVertex45(sizingSet, *first, *second, *third, resizing, rounding, corner, multiplier);
Chris@16:       first = second;
Chris@16:       second = third;
Chris@16:       ++third;
Chris@16:       if(third == real_end) {
Chris@16:         third = begin_points(poly);
Chris@16:         if(*second == *third) {
Chris@16:           ++third; //skip first point if it is duplicate of last point
Chris@16:         }
Chris@16:       }
Chris@16:     } while(second != end);
Chris@16:     //sizingSet.snap();
Chris@16:     polygon_45_set_data<Unit> tmp;
Chris@16:     //insert original shape
Chris@16:     tmp.insert_dispatch(poly, false, polygon_45_concept());
Chris@16:     if(resizing < 0) tmp -= sizingSet;
Chris@16:     else tmp += sizingSet;
Chris@16:     tmp.clean();
Chris@16:     insert(tmp, hole);
Chris@16:     dirty_ = true;
Chris@16:     unsorted_ = true;
Chris@16:     return (*this);
Chris@16:   }
Chris@16: 
Chris@16:   // accumulate the bloated polygon with holes
Chris@16:   template <typename Unit>
Chris@16:   template <typename geometry_type>
Chris@16:   inline polygon_45_set_data<Unit>&
Chris@16:   polygon_45_set_data<Unit>::insert_with_resize_dispatch(const geometry_type& poly,
Chris@16:                                                          coordinate_type resizing,
Chris@16:                                                          RoundingOption rounding,
Chris@16:                                                          CornerOption corner,
Chris@16:                                                          bool hole, polygon_45_with_holes_concept ) {
Chris@16:     insert_with_resize_dispatch(poly, resizing, rounding, corner, hole, polygon_45_concept());
Chris@16:     for(typename polygon_with_holes_traits<geometry_type>::iterator_holes_type itr =
Chris@16:           begin_holes(poly); itr != end_holes(poly);
Chris@16:         ++itr) {
Chris@16:       insert_with_resize_dispatch(*itr, resizing, rounding, corner, !hole, polygon_45_concept());
Chris@16:     }
Chris@16:     return *this;
Chris@16:   }
Chris@16: 
Chris@16:   // transform set
Chris@16:   template <typename Unit>
Chris@16:   template <typename transformation_type>
Chris@16:   inline polygon_45_set_data<Unit>& polygon_45_set_data<Unit>::transform(const transformation_type& tr){
Chris@16:     clean();
Chris@16:     std::vector<polygon_45_with_holes_data<Unit> > polys;
Chris@16:     get(polys);
Chris@16:     for(typename std::vector<polygon_45_with_holes_data<Unit> >::iterator itr = polys.begin();
Chris@16:         itr != polys.end(); ++itr) {
Chris@16:       ::boost::polygon::transform(*itr, tr);
Chris@16:     }
Chris@16:     clear();
Chris@16:     insert(polys.begin(), polys.end());
Chris@16:     dirty_ = true;
Chris@16:     unsorted_ = true;
Chris@16:     return *this;
Chris@16:   }
Chris@16: 
Chris@16:   template <typename Unit>
Chris@16:   inline polygon_45_set_data<Unit>& polygon_45_set_data<Unit>::scale_up(typename coordinate_traits<Unit>::unsigned_area_type factor) {
Chris@16:     scale_up_vertex_45_compact_range(data_.begin(), data_.end(), factor);
Chris@16:     return *this;
Chris@16:   }
Chris@16: 
Chris@16:   template <typename Unit>
Chris@16:   inline polygon_45_set_data<Unit>& polygon_45_set_data<Unit>::scale_down(typename coordinate_traits<Unit>::unsigned_area_type factor) {
Chris@16:     clean();
Chris@16:     std::vector<polygon_45_with_holes_data<Unit> > polys;
Chris@16:     get_polygons_with_holes(polys);
Chris@16:     for(typename std::vector<polygon_45_with_holes_data<Unit> >::iterator itr = polys.begin();
Chris@16:         itr != polys.end(); ++itr) {
Chris@16:       ::boost::polygon::scale_down(*itr, factor);
Chris@16:     }
Chris@16:     clear();
Chris@16:     insert(polys.begin(), polys.end());
Chris@16:     dirty_ = true;
Chris@16:     unsorted_ = true;
Chris@16:     return *this;
Chris@16:   }
Chris@16: 
Chris@16:   template <typename Unit>
Chris@16:   inline polygon_45_set_data<Unit>& polygon_45_set_data<Unit>::scale(double factor) {
Chris@16:     clean();
Chris@16:     std::vector<polygon_45_with_holes_data<Unit> > polys;
Chris@16:     get_polygons_with_holes(polys);
Chris@16:     for(typename std::vector<polygon_45_with_holes_data<Unit> >::iterator itr = polys.begin();
Chris@16:         itr != polys.end(); ++itr) {
Chris@16:       ::boost::polygon::scale(*itr, factor);
Chris@16:     }
Chris@16:     clear();
Chris@16:     insert(polys.begin(), polys.end());
Chris@16:     dirty_ = true;
Chris@16:     unsorted_ = true;
Chris@16:     return *this;
Chris@16:   }
Chris@16: 
Chris@16:   template <typename Unit>
Chris@16:   inline bool polygon_45_set_data<Unit>::clean() const {
Chris@16:     if(unsorted_) sort();
Chris@16:     if(dirty_) {
Chris@16:       applyAdaptiveUnary_<0>();
Chris@16:       dirty_ = false;
Chris@16:     }
Chris@16:     return true;
Chris@16:   }
Chris@16: 
Chris@16:   template <typename Unit>
Chris@16:   template <int op>
Chris@16:   inline void polygon_45_set_data<Unit>::applyAdaptiveBoolean_(const polygon_45_set_data<Unit>& rvalue) const {
Chris@16:     polygon_45_set_data<Unit> tmp;
Chris@16:     applyAdaptiveBoolean_<op>(tmp, rvalue);
Chris@16:     data_.swap(tmp.data_); //swapping vectors should be constant time operation
Chris@16:     error_data_.swap(tmp.error_data_);
Chris@16:     is_manhattan_ = tmp.is_manhattan_;
Chris@16:     unsorted_ = false;
Chris@16:     dirty_ = false;
Chris@16:   }
Chris@16: 
Chris@16:   template <typename Unit2, int op>
Chris@16:   bool applyBoolean45OpOnVectors(std::vector<typename polygon_45_formation<Unit2>::Vertex45Compact>& result_data,
Chris@16:                                  std::vector<typename polygon_45_formation<Unit2>::Vertex45Compact>& lvalue_data,
Chris@16:                                  std::vector<typename polygon_45_formation<Unit2>::Vertex45Compact>& rvalue_data
Chris@16:                                  ) {
Chris@16:     bool result_is_manhattan_ = true;
Chris@16:     typename boolean_op_45<Unit2>::template Scan45<typename boolean_op_45<Unit2>::Count2,
Chris@16:       typename boolean_op_45<Unit2>::template boolean_op_45_output_functor<op> > scan45;
Chris@16:     std::vector<typename boolean_op_45<Unit2>::Vertex45> eventOut;
Chris@16:     typedef std::pair<typename boolean_op_45<Unit2>::Point,
Chris@16:       typename boolean_op_45<Unit2>::template Scan45CountT<typename boolean_op_45<Unit2>::Count2> > Scan45Vertex;
Chris@16:     std::vector<Scan45Vertex> eventIn;
Chris@16:     typedef std::vector<typename polygon_45_formation<Unit2>::Vertex45Compact> value_type;
Chris@16:     typename value_type::const_iterator iter1 = lvalue_data.begin();
Chris@16:     typename value_type::const_iterator iter2 = rvalue_data.begin();
Chris@16:     typename value_type::const_iterator end1 = lvalue_data.end();
Chris@16:     typename value_type::const_iterator end2 = rvalue_data.end();
Chris@16:     const Unit2 UnitMax = (std::numeric_limits<Unit2>::max)();
Chris@16:     Unit2 x = UnitMax;
Chris@16:     while(iter1 != end1 || iter2 != end2) {
Chris@16:       Unit2 currentX = UnitMax;
Chris@16:       if(iter1 != end1) currentX = iter1->pt.x();
Chris@16:       if(iter2 != end2) currentX = (std::min)(currentX, iter2->pt.x());
Chris@16:       if(currentX != x) {
Chris@16:         //std::cout << "SCAN " << currentX << "\n";
Chris@16:         //scan event
Chris@16:         scan45.scan(eventOut, eventIn.begin(), eventIn.end());
Chris@16:         polygon_sort(eventOut.begin(), eventOut.end());
Chris@16:         std::size_t ptCount = 0;
Chris@16:         for(std::size_t i = 0; i < eventOut.size(); ++i) {
Chris@16:           if(!result_data.empty() &&
Chris@16:              result_data.back().pt == eventOut[i].pt) {
Chris@16:             result_data.back().count += eventOut[i];
Chris@16:             ++ptCount;
Chris@16:           } else {
Chris@16:             if(!result_data.empty()) {
Chris@16:               if(result_data.back().count.is_45()) {
Chris@16:                 result_is_manhattan_ = false;
Chris@16:               }
Chris@16:               if(ptCount == 2 && result_data.back().count == (typename polygon_45_formation<Unit2>::Vertex45Count(0, 0, 0, 0))) {
Chris@16:                 result_data.pop_back();
Chris@16:               }
Chris@16:             }
Chris@16:             result_data.push_back(eventOut[i]);
Chris@16:             ptCount = 1;
Chris@16:           }
Chris@16:         }
Chris@16:         if(ptCount == 2 && result_data.back().count == (typename polygon_45_formation<Unit2>::Vertex45Count(0, 0, 0, 0))) {
Chris@16:           result_data.pop_back();
Chris@16:         }
Chris@16:         eventOut.clear();
Chris@16:         eventIn.clear();
Chris@16:         x = currentX;
Chris@16:       }
Chris@16:       //std::cout << "get next\n";
Chris@16:       if(iter2 != end2 && (iter1 == end1 || iter2->pt.x() < iter1->pt.x() ||
Chris@16:                            (iter2->pt.x() == iter1->pt.x() &&
Chris@16:                             iter2->pt.y() < iter1->pt.y()) )) {
Chris@16:         //std::cout << "case1 next\n";
Chris@16:         eventIn.push_back(Scan45Vertex
Chris@16:                           (iter2->pt,
Chris@16:                            typename polygon_45_formation<Unit2>::
Chris@16:                            Scan45Count(typename polygon_45_formation<Unit2>::Count2(0, iter2->count[0]),
Chris@16:                                        typename polygon_45_formation<Unit2>::Count2(0, iter2->count[1]),
Chris@16:                                        typename polygon_45_formation<Unit2>::Count2(0, iter2->count[2]),
Chris@16:                                        typename polygon_45_formation<Unit2>::Count2(0, iter2->count[3]))));
Chris@16:         ++iter2;
Chris@16:       } else if(iter1 != end1 && (iter2 == end2 || iter1->pt.x() < iter2->pt.x() ||
Chris@16:                                   (iter1->pt.x() == iter2->pt.x() &&
Chris@16:                                    iter1->pt.y() < iter2->pt.y()) )) {
Chris@16:         //std::cout << "case2 next\n";
Chris@16:         eventIn.push_back(Scan45Vertex
Chris@16:                           (iter1->pt,
Chris@16:                            typename polygon_45_formation<Unit2>::
Chris@16:                            Scan45Count(
Chris@16:                                        typename polygon_45_formation<Unit2>::Count2(iter1->count[0], 0),
Chris@16:                                        typename polygon_45_formation<Unit2>::Count2(iter1->count[1], 0),
Chris@16:                                        typename polygon_45_formation<Unit2>::Count2(iter1->count[2], 0),
Chris@16:                                        typename polygon_45_formation<Unit2>::Count2(iter1->count[3], 0))));
Chris@16:         ++iter1;
Chris@16:       } else {
Chris@16:         //std::cout << "case3 next\n";
Chris@16:         eventIn.push_back(Scan45Vertex
Chris@16:                           (iter2->pt,
Chris@16:                            typename polygon_45_formation<Unit2>::
Chris@16:                            Scan45Count(typename polygon_45_formation<Unit2>::Count2(iter1->count[0],
Chris@16:                                                                                     iter2->count[0]),
Chris@16:                                        typename polygon_45_formation<Unit2>::Count2(iter1->count[1],
Chris@16:                                                                                     iter2->count[1]),
Chris@16:                                        typename polygon_45_formation<Unit2>::Count2(iter1->count[2],
Chris@16:                                                                                     iter2->count[2]),
Chris@16:                                        typename polygon_45_formation<Unit2>::Count2(iter1->count[3],
Chris@16:                                                                                     iter2->count[3]))));
Chris@16:         ++iter1;
Chris@16:         ++iter2;
Chris@16:       }
Chris@16:     }
Chris@16:     scan45.scan(eventOut, eventIn.begin(), eventIn.end());
Chris@16:     polygon_sort(eventOut.begin(), eventOut.end());
Chris@16: 
Chris@16:     std::size_t ptCount = 0;
Chris@16:     for(std::size_t i = 0; i < eventOut.size(); ++i) {
Chris@16:       if(!result_data.empty() &&
Chris@16:          result_data.back().pt == eventOut[i].pt) {
Chris@16:         result_data.back().count += eventOut[i];
Chris@16:         ++ptCount;
Chris@16:       } else {
Chris@16:         if(!result_data.empty()) {
Chris@16:           if(result_data.back().count.is_45()) {
Chris@16:             result_is_manhattan_ = false;
Chris@16:           }
Chris@16:           if(ptCount == 2 && result_data.back().count == (typename polygon_45_formation<Unit2>::Vertex45Count(0, 0, 0, 0))) {
Chris@16:             result_data.pop_back();
Chris@16:           }
Chris@16:         }
Chris@16:         result_data.push_back(eventOut[i]);
Chris@16:         ptCount = 1;
Chris@16:       }
Chris@16:     }
Chris@16:     if(ptCount == 2 && result_data.back().count == (typename polygon_45_formation<Unit2>::Vertex45Count(0, 0, 0, 0))) {
Chris@16:       result_data.pop_back();
Chris@16:     }
Chris@16:     if(!result_data.empty() &&
Chris@16:        result_data.back().count.is_45()) {
Chris@16:       result_is_manhattan_ = false;
Chris@16:     }
Chris@16:     return result_is_manhattan_;
Chris@16:   }
Chris@16: 
Chris@16:   template <typename Unit2, int op>
Chris@16:   bool applyUnary45OpOnVectors(std::vector<typename polygon_45_formation<Unit2>::Vertex45Compact>& result_data,
Chris@16:                                  std::vector<typename polygon_45_formation<Unit2>::Vertex45Compact>& lvalue_data ) {
Chris@16:     bool result_is_manhattan_ = true;
Chris@16:     typename boolean_op_45<Unit2>::template Scan45<typename boolean_op_45<Unit2>::Count1,
Chris@16:       typename boolean_op_45<Unit2>::template unary_op_45_output_functor<op> > scan45;
Chris@16:     std::vector<typename boolean_op_45<Unit2>::Vertex45> eventOut;
Chris@16:     typedef typename boolean_op_45<Unit2>::template Scan45CountT<typename boolean_op_45<Unit2>::Count1> Scan45Count;
Chris@16:     typedef std::pair<typename boolean_op_45<Unit2>::Point, Scan45Count> Scan45Vertex;
Chris@16:     std::vector<Scan45Vertex> eventIn;
Chris@16:     typedef std::vector<typename polygon_45_formation<Unit2>::Vertex45Compact> value_type;
Chris@16:     typename value_type::const_iterator iter1 = lvalue_data.begin();
Chris@16:     typename value_type::const_iterator end1 = lvalue_data.end();
Chris@16:     const Unit2 UnitMax = (std::numeric_limits<Unit2>::max)();
Chris@16:     Unit2 x = UnitMax;
Chris@16:     while(iter1 != end1) {
Chris@16:       Unit2 currentX = iter1->pt.x();
Chris@16:       if(currentX != x) {
Chris@16:         //std::cout << "SCAN " << currentX << "\n";
Chris@16:         //scan event
Chris@16:         scan45.scan(eventOut, eventIn.begin(), eventIn.end());
Chris@16:         polygon_sort(eventOut.begin(), eventOut.end());
Chris@16:         std::size_t ptCount = 0;
Chris@16:         for(std::size_t i = 0; i < eventOut.size(); ++i) {
Chris@16:           if(!result_data.empty() &&
Chris@16:              result_data.back().pt == eventOut[i].pt) {
Chris@16:             result_data.back().count += eventOut[i];
Chris@16:             ++ptCount;
Chris@16:           } else {
Chris@16:             if(!result_data.empty()) {
Chris@16:               if(result_data.back().count.is_45()) {
Chris@16:                 result_is_manhattan_ = false;
Chris@16:               }
Chris@16:               if(ptCount == 2 && result_data.back().count == (typename polygon_45_formation<Unit2>::Vertex45Count(0, 0, 0, 0))) {
Chris@16:                 result_data.pop_back();
Chris@16:               }
Chris@16:             }
Chris@16:             result_data.push_back(eventOut[i]);
Chris@16:             ptCount = 1;
Chris@16:           }
Chris@16:         }
Chris@16:         if(ptCount == 2 && result_data.back().count == (typename polygon_45_formation<Unit2>::Vertex45Count(0, 0, 0, 0))) {
Chris@16:           result_data.pop_back();
Chris@16:         }
Chris@16:         eventOut.clear();
Chris@16:         eventIn.clear();
Chris@16:         x = currentX;
Chris@16:       }
Chris@16:       //std::cout << "get next\n";
Chris@16:       eventIn.push_back(Scan45Vertex
Chris@16:                         (iter1->pt,
Chris@16:                          Scan45Count( typename boolean_op_45<Unit2>::Count1(iter1->count[0]),
Chris@16:                                       typename boolean_op_45<Unit2>::Count1(iter1->count[1]),
Chris@16:                                       typename boolean_op_45<Unit2>::Count1(iter1->count[2]),
Chris@16:                                       typename boolean_op_45<Unit2>::Count1(iter1->count[3]))));
Chris@16:       ++iter1;
Chris@16:     }
Chris@16:     scan45.scan(eventOut, eventIn.begin(), eventIn.end());
Chris@16:     polygon_sort(eventOut.begin(), eventOut.end());
Chris@16: 
Chris@16:     std::size_t ptCount = 0;
Chris@16:     for(std::size_t i = 0; i < eventOut.size(); ++i) {
Chris@16:       if(!result_data.empty() &&
Chris@16:          result_data.back().pt == eventOut[i].pt) {
Chris@16:         result_data.back().count += eventOut[i];
Chris@16:         ++ptCount;
Chris@16:       } else {
Chris@16:         if(!result_data.empty()) {
Chris@16:           if(result_data.back().count.is_45()) {
Chris@16:             result_is_manhattan_ = false;
Chris@16:           }
Chris@16:           if(ptCount == 2 && result_data.back().count == (typename polygon_45_formation<Unit2>::Vertex45Count(0, 0, 0, 0))) {
Chris@16:             result_data.pop_back();
Chris@16:           }
Chris@16:         }
Chris@16:         result_data.push_back(eventOut[i]);
Chris@16:         ptCount = 1;
Chris@16:       }
Chris@16:     }
Chris@16:     if(ptCount == 2 && result_data.back().count == (typename polygon_45_formation<Unit2>::Vertex45Count(0, 0, 0, 0))) {
Chris@16:       result_data.pop_back();
Chris@16:     }
Chris@16:     if(!result_data.empty() &&
Chris@16:        result_data.back().count.is_45()) {
Chris@16:       result_is_manhattan_ = false;
Chris@16:     }
Chris@16:     return result_is_manhattan_;
Chris@16:   }
Chris@16: 
Chris@16:   template <typename cT, typename iT>
Chris@16:   void get_error_rects_shell(cT& posE, cT& negE, iT beginr, iT endr) {
Chris@16:     typedef typename std::iterator_traits<iT>::value_type Point;
Chris@16:     typedef typename point_traits<Point>::coordinate_type Unit;
Chris@16:     typedef typename coordinate_traits<Unit>::area_type area_type;
Chris@16:     Point pt1, pt2, pt3;
Chris@16:     bool i1 = true;
Chris@16:     bool i2 = true;
Chris@16:     bool not_done = beginr != endr;
Chris@16:     bool next_to_last = false;
Chris@16:     bool last = false;
Chris@16:     Point first, second;
Chris@16:     while(not_done) {
Chris@16:       if(last) {
Chris@16:         last = false;
Chris@16:         not_done = false;
Chris@16:         pt3 = second;
Chris@16:       } else if(next_to_last) {
Chris@16:         next_to_last = false;
Chris@16:         last = true;
Chris@16:         pt3 = first;
Chris@16:       } else if(i1) {
Chris@16:         const Point& pt = *beginr;
Chris@16:         first = pt1 = pt;
Chris@16:         i1 = false;
Chris@16:         i2 = true;
Chris@16:         ++beginr;
Chris@16:         if(beginr == endr) return; //too few points
Chris@16:         continue;
Chris@16:       } else if (i2) {
Chris@16:         const Point& pt = *beginr;
Chris@16:         second = pt2 = pt;
Chris@16:         i2 = false;
Chris@16:         ++beginr;
Chris@16:         if(beginr == endr) return; //too few points
Chris@16:         continue;
Chris@16:       } else {
Chris@16:         const Point& pt = *beginr;
Chris@16:         pt3 = pt;
Chris@16:         ++beginr;
Chris@16:         if(beginr == endr) {
Chris@16:           next_to_last = true;
Chris@16:           //skip last point equal to first
Chris@16:           continue;
Chris@16:         }
Chris@16:       }
Chris@16:       if(local_abs(x(pt2)) % 2) { //y % 2 should also be odd
Chris@16:         //is corner concave or convex?
Chris@16:         Point pts[] = {pt1, pt2, pt3};
Chris@16:         area_type ar = point_sequence_area<Point*, area_type>(pts, pts+3);
Chris@16:         direction_1d dir = ar < 0 ? COUNTERCLOCKWISE : CLOCKWISE;
Chris@16:         //std::cout << pt1 << " " << pt2 << " " << pt3 << " " << ar << std::endl;
Chris@16:         if(dir == CLOCKWISE) {
Chris@16:           posE.push_back(rectangle_data<typename Point::coordinate_type>
Chris@16:                          (x(pt2) - 1, y(pt2) - 1, x(pt2) + 1, y(pt2) + 1));
Chris@16: 
Chris@16:         } else {
Chris@16:           negE.push_back(rectangle_data<typename Point::coordinate_type>
Chris@16:                          (x(pt2) - 1, y(pt2) - 1, x(pt2) + 1, y(pt2) + 1));
Chris@16:         }
Chris@16:       }
Chris@16:       pt1 = pt2;
Chris@16:       pt2 = pt3;
Chris@16:     }
Chris@16:   }
Chris@16: 
Chris@16:   template <typename cT, typename pT>
Chris@16:   void get_error_rects(cT& posE, cT& negE, const pT& p) {
Chris@16:     get_error_rects_shell(posE, negE, p.begin(), p.end());
Chris@16:     for(typename pT::iterator_holes_type iHb = p.begin_holes();
Chris@16:         iHb != p.end_holes(); ++iHb) {
Chris@16:       get_error_rects_shell(posE, negE, iHb->begin(), iHb->end());
Chris@16:     }
Chris@16:   }
Chris@16: 
Chris@16:   template <typename Unit>
Chris@16:   template <int op>
Chris@16:   inline void polygon_45_set_data<Unit>::applyAdaptiveBoolean_(polygon_45_set_data<Unit>& result,
Chris@16:                                                                const polygon_45_set_data<Unit>& rvalue) const {
Chris@16:     result.clear();
Chris@16:     result.error_data_ = error_data_;
Chris@16:     result.error_data_.insert(result.error_data_.end(), rvalue.error_data_.begin(),
Chris@16:                               rvalue.error_data_.end());
Chris@16:     if(is_manhattan() && rvalue.is_manhattan()) {
Chris@16:       //convert each into polygon_90_set data and call boolean operations
Chris@16:       polygon_90_set_data<Unit> l90sd(VERTICAL), r90sd(VERTICAL), output(VERTICAL);
Chris@16:       for(typename value_type::const_iterator itr = data_.begin(); itr != data_.end(); ++itr) {
Chris@16:         if((*itr).count[3] == 0) continue; //skip all non vertical edges
Chris@16:         l90sd.insert(std::make_pair((*itr).pt.x(), std::make_pair<Unit, int>((*itr).pt.y(), (*itr).count[3])), false, VERTICAL);
Chris@16:       }
Chris@16:       for(typename value_type::const_iterator itr = rvalue.data_.begin(); itr != rvalue.data_.end(); ++itr) {
Chris@16:         if((*itr).count[3] == 0) continue; //skip all non vertical edges
Chris@16:         r90sd.insert(std::make_pair((*itr).pt.x(), std::make_pair<Unit, int>((*itr).pt.y(), (*itr).count[3])), false, VERTICAL);
Chris@16:       }
Chris@16:       l90sd.sort();
Chris@16:       r90sd.sort();
Chris@16: #ifdef BOOST_POLYGON_MSVC
Chris@16: #pragma warning (push)
Chris@16: #pragma warning (disable: 4127)
Chris@16: #endif
Chris@16:       if(op == 0) {
Chris@16:         output.applyBooleanBinaryOp(l90sd.begin(), l90sd.end(),
Chris@16:                                     r90sd.begin(), r90sd.end(), boolean_op::BinaryCount<boolean_op::BinaryOr>());
Chris@16:       } else if (op == 1) {
Chris@16:         output.applyBooleanBinaryOp(l90sd.begin(), l90sd.end(),
Chris@16:                                     r90sd.begin(), r90sd.end(), boolean_op::BinaryCount<boolean_op::BinaryAnd>());
Chris@16:       } else if (op == 2) {
Chris@16:         output.applyBooleanBinaryOp(l90sd.begin(), l90sd.end(),
Chris@16:                                     r90sd.begin(), r90sd.end(), boolean_op::BinaryCount<boolean_op::BinaryNot>());
Chris@16:       } else if (op == 3) {
Chris@16:         output.applyBooleanBinaryOp(l90sd.begin(), l90sd.end(),
Chris@16:                                     r90sd.begin(), r90sd.end(), boolean_op::BinaryCount<boolean_op::BinaryXor>());
Chris@16:       }
Chris@16: #ifdef BOOST_POLYGON_MSVC
Chris@16: #pragma warning (pop)
Chris@16: #endif
Chris@16:       result.data_.clear();
Chris@16:       result.insert(output);
Chris@16:       result.is_manhattan_ = true;
Chris@16:       result.dirty_ = false;
Chris@16:       result.unsorted_ = false;
Chris@16:     } else {
Chris@16:       sort();
Chris@16:       rvalue.sort();
Chris@16:       try {
Chris@16:         result.is_manhattan_ = applyBoolean45OpOnVectors<Unit, op>(result.data_, data_, rvalue.data_);
Chris@16:       } catch (std::string str) {
Chris@16:         std::string msg = "GTL 45 Boolean error, precision insufficient to represent edge intersection coordinate value.";
Chris@16:         if(str == msg) {
Chris@16:           result.clear();
Chris@16:           typedef typename coordinate_traits<Unit>::manhattan_area_type Unit2;
Chris@16:           typedef typename polygon_45_formation<Unit2>::Vertex45Compact Vertex45Compact2;
Chris@16:           typedef std::vector<Vertex45Compact2> Data2;
Chris@16:           Data2 rvalue_data, lvalue_data, result_data;
Chris@16:           rvalue_data.reserve(rvalue.data_.size());
Chris@16:           lvalue_data.reserve(data_.size());
Chris@16:           for(std::size_t i = 0 ; i < data_.size(); ++i) {
Chris@16:             const Vertex45Compact& vi = data_[i];
Chris@16:             Vertex45Compact2 ci;
Chris@16:             ci.pt = point_data<Unit2>(x(vi.pt), y(vi.pt));
Chris@16:             ci.count = typename polygon_45_formation<Unit2>::Vertex45Count
Chris@16:               ( vi.count[0], vi.count[1], vi.count[2], vi.count[3]);
Chris@16:             lvalue_data.push_back(ci);
Chris@16:           }
Chris@16:           for(std::size_t i = 0 ; i < rvalue.data_.size(); ++i) {
Chris@16:             const Vertex45Compact& vi = rvalue.data_[i];
Chris@16:             Vertex45Compact2 ci;
Chris@16:             ci.pt = (point_data<Unit2>(x(vi.pt), y(vi.pt)));
Chris@16:             ci.count = typename polygon_45_formation<Unit2>::Vertex45Count
Chris@16:               ( vi.count[0], vi.count[1], vi.count[2], vi.count[3]);
Chris@16:             rvalue_data.push_back(ci);
Chris@16:           }
Chris@16:           scale_up_vertex_45_compact_range(lvalue_data.begin(), lvalue_data.end(), 2);
Chris@16:           scale_up_vertex_45_compact_range(rvalue_data.begin(), rvalue_data.end(), 2);
Chris@16:           bool result_is_manhattan = applyBoolean45OpOnVectors<Unit2, op>(result_data,
Chris@16:                                                                           lvalue_data,
Chris@16:                                                                           rvalue_data );
Chris@16:           if(!result_is_manhattan) {
Chris@16:             typename polygon_45_formation<Unit2>::Polygon45Formation pf(false);
Chris@16:             //std::cout << "FORMING POLYGONS\n";
Chris@16:             std::vector<polygon_45_with_holes_data<Unit2> > container;
Chris@16:             pf.scan(container, result_data.begin(), result_data.end());
Chris@16:             Data2 error_data_out;
Chris@16:             std::vector<rectangle_data<Unit2> > pos_error_rects;
Chris@16:             std::vector<rectangle_data<Unit2> > neg_error_rects;
Chris@16:             for(std::size_t i = 0; i < container.size(); ++i) {
Chris@16:               get_error_rects(pos_error_rects, neg_error_rects, container[i]);
Chris@16:             }
Chris@16:             for(std::size_t i = 0; i < pos_error_rects.size(); ++i) {
Chris@16:               insert_rectangle_into_vector_45(result_data, pos_error_rects[i], false);
Chris@16:               insert_rectangle_into_vector_45(error_data_out, pos_error_rects[i], false);
Chris@16:             }
Chris@16:             for(std::size_t i = 0; i < neg_error_rects.size(); ++i) {
Chris@16:               insert_rectangle_into_vector_45(result_data, neg_error_rects[i], true);
Chris@16:               insert_rectangle_into_vector_45(error_data_out, neg_error_rects[i], false);
Chris@16:             }
Chris@16:             scale_down_vertex_45_compact_range_blindly(error_data_out.begin(), error_data_out.end(), 2);
Chris@16:             for(std::size_t i = 0 ; i < error_data_out.size(); ++i) {
Chris@16:               const Vertex45Compact2& vi = error_data_out[i];
Chris@16:               Vertex45Compact ci;
Chris@16:               ci.pt.x(static_cast<Unit>(x(vi.pt)));
Chris@16:               ci.pt.y(static_cast<Unit>(y(vi.pt)));
Chris@16:               ci.count = typename polygon_45_formation<Unit>::Vertex45Count
Chris@16:               ( vi.count[0], vi.count[1], vi.count[2], vi.count[3]);
Chris@16:               result.error_data_.push_back(ci);
Chris@16:             }
Chris@16:             Data2 new_result_data;
Chris@16:             polygon_sort(result_data.begin(), result_data.end());
Chris@16:             applyUnary45OpOnVectors<Unit2, 0>(new_result_data, result_data); //OR operation
Chris@16:             result_data.swap(new_result_data);
Chris@16:           }
Chris@16:           scale_down_vertex_45_compact_range_blindly(result_data.begin(), result_data.end(), 2);
Chris@16:           //result.data_.reserve(result_data.size());
Chris@16:           for(std::size_t i = 0 ; i < result_data.size(); ++i) {
Chris@16:             const Vertex45Compact2& vi = result_data[i];
Chris@16:             Vertex45Compact ci;
Chris@16:             ci.pt.x(static_cast<Unit>(x(vi.pt)));
Chris@16:             ci.pt.y(static_cast<Unit>(y(vi.pt)));
Chris@16:             ci.count = typename polygon_45_formation<Unit>::Vertex45Count
Chris@16:               ( vi.count[0], vi.count[1], vi.count[2], vi.count[3]);
Chris@16:             result.data_.push_back(ci);
Chris@16:           }
Chris@16:           result.is_manhattan_ = result_is_manhattan;
Chris@16:           result.dirty_ = false;
Chris@16:           result.unsorted_ = false;
Chris@16:         } else { throw str; }
Chris@16:       }
Chris@16:       //std::cout << "DONE SCANNING\n";
Chris@16:     }
Chris@16:   }
Chris@16: 
Chris@16:   template <typename Unit>
Chris@16:   template <int op>
Chris@16:   inline void polygon_45_set_data<Unit>::applyAdaptiveUnary_() const {
Chris@16:     polygon_45_set_data<Unit> result;
Chris@16:     result.error_data_ = error_data_;
Chris@16:     if(is_manhattan()) {
Chris@16:       //convert each into polygon_90_set data and call boolean operations
Chris@16:       polygon_90_set_data<Unit> l90sd(VERTICAL);
Chris@16:       for(typename value_type::const_iterator itr = data_.begin(); itr != data_.end(); ++itr) {
Chris@16:         if((*itr).count[3] == 0) continue; //skip all non vertical edges
Chris@16:         l90sd.insert(std::make_pair((*itr).pt.x(), std::make_pair<Unit, int>((*itr).pt.y(), (*itr).count[3])), false, VERTICAL);
Chris@16:       }
Chris@16:       l90sd.sort();
Chris@16: #ifdef BOOST_POLYGON_MSVC
Chris@16: #pragma warning (push)
Chris@16: #pragma warning (disable: 4127)
Chris@16: #endif
Chris@16:       if(op == 0) {
Chris@16:         l90sd.clean();
Chris@16:       } else if (op == 1) {
Chris@16:         l90sd.self_intersect();
Chris@16:       } else if (op == 3) {
Chris@16:         l90sd.self_xor();
Chris@16:       }
Chris@16: #ifdef BOOST_POLYGON_MSVC
Chris@16: #pragma warning (pop)
Chris@16: #endif
Chris@16:       result.data_.clear();
Chris@16:       result.insert(l90sd);
Chris@16:       result.is_manhattan_ = true;
Chris@16:       result.dirty_ = false;
Chris@16:       result.unsorted_ = false;
Chris@16:     } else {
Chris@16:       sort();
Chris@16:       try {
Chris@16:         result.is_manhattan_ = applyUnary45OpOnVectors<Unit, op>(result.data_, data_);
Chris@16:       } catch (std::string str) {
Chris@16:         std::string msg = "GTL 45 Boolean error, precision insufficient to represent edge intersection coordinate value.";
Chris@16:         if(str == msg) {
Chris@16:           result.clear();
Chris@16:           typedef typename coordinate_traits<Unit>::manhattan_area_type Unit2;
Chris@16:           typedef typename polygon_45_formation<Unit2>::Vertex45Compact Vertex45Compact2;
Chris@16:           typedef std::vector<Vertex45Compact2> Data2;
Chris@16:           Data2 lvalue_data, result_data;
Chris@16:           lvalue_data.reserve(data_.size());
Chris@16:           for(std::size_t i = 0 ; i < data_.size(); ++i) {
Chris@16:             const Vertex45Compact& vi = data_[i];
Chris@16:             Vertex45Compact2 ci;
Chris@16:             ci.pt.x(static_cast<Unit>(x(vi.pt)));
Chris@16:             ci.pt.y(static_cast<Unit>(y(vi.pt)));
Chris@16:             ci.count = typename polygon_45_formation<Unit2>::Vertex45Count
Chris@16:               ( vi.count[0], vi.count[1], vi.count[2], vi.count[3]);
Chris@16:             lvalue_data.push_back(ci);
Chris@16:           }
Chris@16:           scale_up_vertex_45_compact_range(lvalue_data.begin(), lvalue_data.end(), 2);
Chris@16:           bool result_is_manhattan = applyUnary45OpOnVectors<Unit2, op>(result_data,
Chris@16:                                                                         lvalue_data );
Chris@16:           if(!result_is_manhattan) {
Chris@16:             typename polygon_45_formation<Unit2>::Polygon45Formation pf(false);
Chris@16:             //std::cout << "FORMING POLYGONS\n";
Chris@16:             std::vector<polygon_45_with_holes_data<Unit2> > container;
Chris@16:             pf.scan(container, result_data.begin(), result_data.end());
Chris@16:             Data2 error_data_out;
Chris@16:             std::vector<rectangle_data<Unit2> > pos_error_rects;
Chris@16:             std::vector<rectangle_data<Unit2> > neg_error_rects;
Chris@16:             for(std::size_t i = 0; i < container.size(); ++i) {
Chris@16:               get_error_rects(pos_error_rects, neg_error_rects, container[i]);
Chris@16:             }
Chris@16:             for(std::size_t i = 0; i < pos_error_rects.size(); ++i) {
Chris@16:               insert_rectangle_into_vector_45(result_data, pos_error_rects[i], false);
Chris@16:               insert_rectangle_into_vector_45(error_data_out, pos_error_rects[i], false);
Chris@16:             }
Chris@16:             for(std::size_t i = 0; i < neg_error_rects.size(); ++i) {
Chris@16:               insert_rectangle_into_vector_45(result_data, neg_error_rects[i], true);
Chris@16:               insert_rectangle_into_vector_45(error_data_out, neg_error_rects[i], false);
Chris@16:             }
Chris@16:             scale_down_vertex_45_compact_range_blindly(error_data_out.begin(), error_data_out.end(), 2);
Chris@16:             for(std::size_t i = 0 ; i < error_data_out.size(); ++i) {
Chris@16:               const Vertex45Compact2& vi = error_data_out[i];
Chris@16:               Vertex45Compact ci;
Chris@16:               ci.pt.x(static_cast<Unit>(x(vi.pt)));
Chris@16:               ci.pt.y(static_cast<Unit>(y(vi.pt)));
Chris@16:               ci.count = typename polygon_45_formation<Unit>::Vertex45Count
Chris@16:               ( vi.count[0], vi.count[1], vi.count[2], vi.count[3]);
Chris@16:               result.error_data_.push_back(ci);
Chris@16:             }
Chris@16:             Data2 new_result_data;
Chris@16:             polygon_sort(result_data.begin(), result_data.end());
Chris@16:             applyUnary45OpOnVectors<Unit2, 0>(new_result_data, result_data); //OR operation
Chris@16:             result_data.swap(new_result_data);
Chris@16:           }
Chris@16:           scale_down_vertex_45_compact_range_blindly(result_data.begin(), result_data.end(), 2);
Chris@16:           //result.data_.reserve(result_data.size());
Chris@16:           for(std::size_t i = 0 ; i < result_data.size(); ++i) {
Chris@16:             const Vertex45Compact2& vi = result_data[i];
Chris@16:             Vertex45Compact ci;
Chris@16:             ci.pt.x(static_cast<Unit>(x(vi.pt)));
Chris@16:             ci.pt.y(static_cast<Unit>(y(vi.pt)));
Chris@16:             ci.count = typename polygon_45_formation<Unit>::Vertex45Count
Chris@16:               ( vi.count[0], vi.count[1], vi.count[2], vi.count[3]);
Chris@16:             result.data_.push_back(ci);
Chris@16:           }
Chris@16:           result.is_manhattan_ = result_is_manhattan;
Chris@16:           result.dirty_ = false;
Chris@16:           result.unsorted_ = false;
Chris@16:         } else { throw str; }
Chris@16:       }
Chris@16:       //std::cout << "DONE SCANNING\n";
Chris@16:     }
Chris@16:     data_.swap(result.data_);
Chris@16:     error_data_.swap(result.error_data_);
Chris@16:     dirty_ = result.dirty_;
Chris@16:     unsorted_ = result.unsorted_;
Chris@16:     is_manhattan_ = result.is_manhattan_;
Chris@16:   }
Chris@16: 
Chris@16:   template <typename coordinate_type, typename property_type>
Chris@16:   class property_merge_45 {
Chris@16:   private:
Chris@16:     typedef typename coordinate_traits<coordinate_type>::manhattan_area_type big_coord;
Chris@16:     typedef typename polygon_45_property_merge<big_coord, property_type>::MergeSetData tsd;
Chris@16:     tsd tsd_;
Chris@16:   public:
Chris@16:     inline property_merge_45() : tsd_() {}
Chris@16:     inline property_merge_45(const property_merge_45& that) : tsd_(that.tsd_) {}
Chris@16:     inline property_merge_45& operator=(const property_merge_45& that) {
Chris@16:       tsd_ = that.tsd_;
Chris@16:       return *this;
Chris@16:     }
Chris@16: 
Chris@16:     inline void insert(const polygon_45_set_data<coordinate_type>& ps, property_type property) {
Chris@16:       ps.clean();
Chris@16:       polygon_45_property_merge<big_coord, property_type>::populateMergeSetData(tsd_, ps.begin(), ps.end(), property);
Chris@16:     }
Chris@16:     template <class GeoObjT>
Chris@16:     inline void insert(const GeoObjT& geoObj, property_type property) {
Chris@16:       polygon_45_set_data<coordinate_type> ps;
Chris@16:       ps.insert(geoObj);
Chris@16:       insert(ps, property);
Chris@16:     }
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_45_set_data<coordiante_type> > or
Chris@16:     // T = std::map<std::vector<property_type>, polygon_45_set_data<coordiante_type> >
Chris@16:     template <class result_type>
Chris@16:     inline void merge(result_type& result) {
Chris@16:       typedef typename result_type::key_type keytype;
Chris@16:       typedef std::map<keytype, polygon_45_set_data<big_coord> > bigtype;
Chris@16:       bigtype result_big;
Chris@16:       polygon_45_property_merge<big_coord, property_type>::performMerge(result_big, tsd_);
Chris@16:       std::vector<polygon_45_with_holes_data<big_coord> > polys;
Chris@16:       std::vector<rectangle_data<big_coord> > pos_error_rects;
Chris@16:       std::vector<rectangle_data<big_coord> > neg_error_rects;
Chris@16:       for(typename std::map<keytype, polygon_45_set_data<big_coord> >::iterator itr = result_big.begin();
Chris@16:           itr != result_big.end(); ++itr) {
Chris@16:         polys.clear();
Chris@16:         (*itr).second.get(polys);
Chris@16:         for(std::size_t i = 0; i < polys.size(); ++i) {
Chris@16:           get_error_rects(pos_error_rects, neg_error_rects, polys[i]);
Chris@16:         }
Chris@16:         (*itr).second += pos_error_rects;
Chris@16:         (*itr).second -= neg_error_rects;
Chris@16:         (*itr).second.scale_down(2);
Chris@16:         result[(*itr).first].insert((*itr).second);
Chris@16:       }
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_45 {
Chris@16:   private:
Chris@16:     typedef typename coordinate_traits<coordinate_type>::manhattan_area_type big_coord;
Chris@16:     typedef typename polygon_45_touch<big_coord>::TouchSetData tsd;
Chris@16:     tsd tsd_;
Chris@16:     unsigned int nodeCount_;
Chris@16:   public:
Chris@16:     inline connectivity_extraction_45() : tsd_(), nodeCount_(0) {}
Chris@16:     inline connectivity_extraction_45(const connectivity_extraction_45& that) : tsd_(that.tsd_),
Chris@16:                                                                           nodeCount_(that.nodeCount_) {}
Chris@16:     inline connectivity_extraction_45& operator=(const connectivity_extraction_45& 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_45_set_data<coordinate_type>& ps) {
Chris@16:       ps.clean();
Chris@16:       polygon_45_touch<big_coord>::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_45_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:       polygon_45_touch<big_coord>::performTouch(graph, tsd_);
Chris@16:     }
Chris@16:   };
Chris@16: }
Chris@16: }
Chris@16: #endif
Chris@16: