boost/polygon/polygon_90_set_data.hpp

0001 /*
0002   Copyright 2008 Intel Corporation
0003
0004   Use, modification and distribution are subject to the Boost Software License,
0005   Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
0006   http://www.boost.org/LICENSE_1_0.txt).
0007 */
0008 #ifndef BOOST_POLYGON_POLYGON_90_SET_DATA_HPP
0009 #define BOOST_POLYGON_POLYGON_90_SET_DATA_HPP
0010 #include "isotropy.hpp"
0011 #include "point_concept.hpp"
0012 #include "transform.hpp"
0013 #include "interval_concept.hpp"
0014 #include "rectangle_concept.hpp"
0015 #include "segment_concept.hpp"
0016 #include "detail/iterator_points_to_compact.hpp"
0017 #include "detail/iterator_compact_to_points.hpp"
0018 #include "polygon_traits.hpp"
0019
0020 //manhattan boolean algorithms
0021 #include "detail/boolean_op.hpp"
0022 #include "detail/polygon_formation.hpp"
0023 #include "detail/rectangle_formation.hpp"
0024 #include "detail/max_cover.hpp"
0025 #include "detail/property_merge.hpp"
0026 #include "detail/polygon_90_touch.hpp"
0027 #include "detail/iterator_geometry_to_set.hpp"
0028
0029 namespace boost { namespace polygon{
0030   template <typename ltype, typename rtype, typename op_type>
0031   class polygon_90_set_view;
0032
0033   template <typename T>
0034   class polygon_90_set_data {
0035   public:
0036     typedef T coordinate_type;
0037     typedef std::vector<std::pair<coordinate_type, std::pair<coordinate_type, int> > > value_type;
0038     typedef typename std::vector<std::pair<coordinate_type, std::pair<coordinate_type, int> > >::const_iterator iterator_type;
0039     typedef polygon_90_set_data operator_arg_type;
0040
0041     // default constructor
0042     inline polygon_90_set_data() : orient_(HORIZONTAL), data_(), dirty_(false), unsorted_(false) {}
0043
0044     // constructor
0045     inline polygon_90_set_data(orientation_2d orient) : orient_(orient), data_(), dirty_(false), unsorted_(false) {}
0046
0047     // constructor from an iterator pair over vertex data
0048     template <typename iT>
0049     inline polygon_90_set_data(orientation_2d, iT input_begin, iT input_end) :
0050       orient_(HORIZONTAL), data_(), dirty_(false), unsorted_(false) {
0051       dirty_ = true;
0052       unsorted_ = true;
0053       for( ; input_begin != input_end; ++input_begin) { insert(*input_begin); }
0054     }
0055
0056     // copy constructor
0057     inline polygon_90_set_data(const polygon_90_set_data& that) :
0058       orient_(that.orient_), data_(that.data_), dirty_(that.dirty_), unsorted_(that.unsorted_) {}
0059
0060     template <typename ltype, typename rtype, typename op_type>
0061     inline polygon_90_set_data(const polygon_90_set_view<ltype, rtype, op_type>& that);
0062
0063     // copy with orientation change constructor
0064     inline polygon_90_set_data(orientation_2d orient, const polygon_90_set_data& that) :
0065       orient_(orient), data_(), dirty_(false), unsorted_(false) {
0066       insert(that, false, that.orient_);
0067     }
0068
0069     // destructor
0070     inline ~polygon_90_set_data() {}
0071
0072     // assignement operator
0073     inline polygon_90_set_data& operator=(const polygon_90_set_data& that) {
0074       if(this == &that) return *this;
0075       orient_ = that.orient_;
0076       data_ = that.data_;
0077       dirty_ = that.dirty_;
0078       unsorted_ = that.unsorted_;
0079       return *this;
0080     }
0081
0082     template <typename ltype, typename rtype, typename op_type>
0083     inline polygon_90_set_data& operator=(const polygon_90_set_view<ltype, rtype, op_type>& that);
0084
0085     template <typename geometry_object>
0086     inline polygon_90_set_data& operator=(const geometry_object& geometry) {
0087       data_.clear();
0088       insert(geometry);
0089       return *this;
0090     }
0091
0092     // insert iterator range
0093     inline void insert(iterator_type input_begin, iterator_type input_end, orientation_2d orient = HORIZONTAL) {
0094       if(input_begin == input_end || (!data_.empty() && &(*input_begin) == &(*(data_.begin())))) return;
0095       dirty_ = true;
0096       unsorted_ = true;
0097       if(orient == orient_)
0098         data_.insert(data_.end(), input_begin, input_end);
0099       else {
0100         for( ; input_begin != input_end; ++input_begin) {
0101           insert(*input_begin, false, orient);
0102         }
0103       }
0104     }
0105
0106     // insert iterator range
0107     template <typename iT>
0108     inline void insert(iT input_begin, iT input_end, orientation_2d orient = HORIZONTAL) {
0109       if(input_begin == input_end) return;
0110       dirty_ = true;
0111       unsorted_ = true;
0112       for( ; input_begin != input_end; ++input_begin) {
0113         insert(*input_begin, false, orient);
0114       }
0115     }
0116
0117     inline void insert(const polygon_90_set_data& polygon_set) {
0118       insert(polygon_set.begin(), polygon_set.end(), polygon_set.orient());
0119     }
0120
0121     inline void insert(const std::pair<std::pair<point_data<coordinate_type>, point_data<coordinate_type> >, int>& edge, bool is_hole = false,
0122                        orientation_2d = HORIZONTAL) {
0123       std::pair<coordinate_type, std::pair<coordinate_type, int> > vertex;
0124       vertex.first = edge.first.first.x();
0125       vertex.second.first = edge.first.first.y();
0126       vertex.second.second = edge.second * (is_hole ? -1 : 1);
0127       insert(vertex, false, VERTICAL);
0128       vertex.first = edge.first.second.x();
0129       vertex.second.first = edge.first.second.y();
0130       vertex.second.second *= -1;
0131       insert(vertex, false, VERTICAL);
0132     }
0133
0134     template <typename geometry_type>
0135     inline void insert(const geometry_type& geometry_object, bool is_hole = false, orientation_2d = HORIZONTAL) {
0136       iterator_geometry_to_set<typename geometry_concept<geometry_type>::type, geometry_type>
0137         begin_input(geometry_object, LOW, orient_, is_hole), end_input(geometry_object, HIGH, orient_, is_hole);
0138       insert(begin_input, end_input, orient_);
0139     }
0140
0141     inline void insert(const std::pair<coordinate_type, std::pair<coordinate_type, int> >& vertex, bool is_hole = false,
0142                        orientation_2d orient = HORIZONTAL) {
0143       data_.push_back(vertex);
0144       if(orient != orient_) std::swap(data_.back().first, data_.back().second.first);
0145       if(is_hole) data_.back().second.second *= -1;
0146       dirty_ = true;
0147       unsorted_ = true;
0148     }
0149
0150     inline void insert(coordinate_type major_coordinate, const std::pair<interval_data<coordinate_type>, int>& edge) {
0151       std::pair<coordinate_type, std::pair<coordinate_type, int> > vertex;
0152       vertex.first = major_coordinate;
0153       vertex.second.first = edge.first.get(LOW);
0154       vertex.second.second = edge.second;
0155       insert(vertex, false, orient_);
0156       vertex.second.first = edge.first.get(HIGH);
0157       vertex.second.second *= -1;
0158       insert(vertex, false, orient_);
0159     }
0160
0161     template <typename output_container>
0162     inline void get(output_container& output) const {
0163       get_dispatch(output, typename geometry_concept<typename output_container::value_type>::type());
0164     }
0165
0166     template <typename output_container>
0167     inline void get(output_container& output, size_t vthreshold) const {
0168       get_dispatch(output, typename geometry_concept<typename output_container::value_type>::type(), vthreshold);
0169     }
0170
0171
0172     template <typename output_container>
0173     inline void get_polygons(output_container& output) const {
0174       get_dispatch(output, polygon_90_concept());
0175     }
0176
0177     template <typename output_container>
0178     inline void get_rectangles(output_container& output) const {
0179       clean();
0180       form_rectangles(output, data_.begin(), data_.end(), orient_, rectangle_concept());
0181     }
0182
0183     template <typename output_container>
0184     inline void get_rectangles(output_container& output, orientation_2d slicing_orientation) const {
0185       if(slicing_orientation == orient_) {
0186         get_rectangles(output);
0187       } else {
0188         polygon_90_set_data<coordinate_type> ps(*this);
0189         ps.transform(axis_transformation(axis_transformation::SWAP_XY));
0190         output_container result;
0191         ps.get_rectangles(result);
0192         for(typename output_container::iterator itr = result.begin(); itr != result.end(); ++itr) {
0193           ::boost::polygon::transform(*itr, axis_transformation(axis_transformation::SWAP_XY));
0194         }
0195         output.insert(output.end(), result.begin(), result.end());
0196       }
0197     }
0198
0199     // equivalence operator
0200     inline bool operator==(const polygon_90_set_data& p) const {
0201       if(orient_ == p.orient()) {
0202         clean();
0203         p.clean();
0204         return data_ == p.data_;
0205       } else {
0206         return false;
0207       }
0208     }
0209
0210     // inequivalence operator
0211     inline bool operator!=(const polygon_90_set_data& p) const {
0212       return !((*this) == p);
0213     }
0214
0215     // get iterator to begin vertex data
0216     inline iterator_type begin() const {
0217       return data_.begin();
0218     }
0219
0220     // get iterator to end vertex data
0221     inline iterator_type end() const {
0222       return data_.end();
0223     }
0224
0225     const value_type& value() const {
0226       return data_;
0227     }
0228
0229     // clear the contents of the polygon_90_set_data
0230     inline void clear() { data_.clear(); dirty_ = unsorted_ = false; }
0231
0232     // find out if Polygon set is empty
0233     inline bool empty() const { clean(); return data_.empty(); }
0234
0235     // get the Polygon set size in vertices
0236     inline std::size_t size() const { clean(); return data_.size(); }
0237
0238     // get the current Polygon set capacity in vertices
0239     inline std::size_t capacity() const { return data_.capacity(); }
0240
0241     // reserve size of polygon set in vertices
0242     inline void reserve(std::size_t size) { return data_.reserve(size); }
0243
0244     // find out if Polygon set is sorted
0245     inline bool sorted() const { return !unsorted_; }
0246
0247     // find out if Polygon set is clean
0248     inline bool dirty() const { return dirty_; }
0249
0250     // get the scanline orientation of the polygon set
0251     inline orientation_2d orient() const { return orient_; }
0252
0253     // Start BM
0254     // The problem: If we have two polygon sets with two different scanline orientations:
0255     // I tried changing the orientation of one to coincide with other (If not, resulting boolean operation
0256     // produces spurious results).
0257     // First I tried copying polygon data from one of the sets into another set with corrected orientation
0258     // using one of the copy constructor that takes in orientation (see somewhere above in this file) --> copy constructor throws error
0259     // Then I tried another approach:(see below). This approach also fails to produce the desired results when test case is run.
0260     // Here is the part that beats me: If I comment out the whole section, I can do all the operations (^=, -=, &= )these commented out
0261     // operations perform. So then why do we need them?. Hence, I commented out this whole section.
0262     // End BM
0263     // polygon_90_set_data<coordinate_type>& operator-=(const polygon_90_set_data& that) {
0264     //   sort();
0265     //   that.sort();
0266     //   value_type data;
0267     //   std::swap(data, data_);
0268     //   applyBooleanBinaryOp(data.begin(), data.end(),
0269     //                        that.begin(), that.end(), boolean_op::BinaryCount<boolean_op::BinaryNot>());
0270     //   return *this;
0271     // }
0272     // polygon_90_set_data<coordinate_type>& operator^=(const polygon_90_set_data& that) {
0273     //   sort();
0274     //   that.sort();
0275     //   value_type data;
0276     //   std::swap(data, data_);
0277     //   applyBooleanBinaryOp(data.begin(), data.end(),
0278     //                        that.begin(), that.end(),  boolean_op::BinaryCount<boolean_op::BinaryXor>());
0279     //   return *this;
0280     // }
0281     // polygon_90_set_data<coordinate_type>& operator&=(const polygon_90_set_data& that) {
0282     //   sort();
0283     //   that.sort();
0284     //   value_type data;
0285     //   std::swap(data, data_);
0286     //   applyBooleanBinaryOp(data.begin(), data.end(),
0287     //                        that.begin(), that.end(), boolean_op::BinaryCount<boolean_op::BinaryAnd>());
0288     //   return *this;
0289     // }
0290     // polygon_90_set_data<coordinate_type>& operator|=(const polygon_90_set_data& that) {
0291     //   insert(that);
0292     //   return *this;
0293     // }
0294
0295     void clean() const {
0296       sort();
0297       if(dirty_) {
0298         boolean_op::default_arg_workaround<int>::applyBooleanOr(data_);
0299         dirty_ = false;
0300       }
0301     }
0302
0303     void sort() const{
0304       if(unsorted_) {
0305         polygon_sort(data_.begin(), data_.end());
0306         unsorted_ = false;
0307       }
0308     }
0309
0310     template <typename input_iterator_type>
0311     void set(input_iterator_type input_begin, input_iterator_type input_end, orientation_2d orient) {
0312       data_.clear();
0313       reserve(std::distance(input_begin, input_end));
0314       data_.insert(data_.end(), input_begin, input_end);
0315       orient_ = orient;
0316       dirty_ = true;
0317       unsorted_ = true;
0318     }
0319
0320     void set(const value_type& value, orientation_2d orient) {
0321       data_ = value;
0322       orient_ = orient;
0323       dirty_ = true;
0324       unsorted_ = true;
0325     }
0326
0327     //extents
0328     template <typename rectangle_type>
0329     bool
0330     extents(rectangle_type& extents_rectangle) const {
0331       clean();
0332       if(data_.empty()) return false;
0333       if(orient_ == HORIZONTAL)
0334         set_points(extents_rectangle, point_data<coordinate_type>(data_[0].second.first, data_[0].first),
0335                    point_data<coordinate_type>(data_[data_.size() - 1].second.first, data_[data_.size() - 1].first));
0336       else
0337         set_points(extents_rectangle, point_data<coordinate_type>(data_[0].first, data_[0].second.first),
0338                    point_data<coordinate_type>(data_[data_.size() - 1].first, data_[data_.size() - 1].second.first));
0339       for(std::size_t i = 1; i < data_.size() - 1; ++i) {
0340         if(orient_ == HORIZONTAL)
0341           encompass(extents_rectangle, point_data<coordinate_type>(data_[i].second.first, data_[i].first));
0342         else
0343           encompass(extents_rectangle, point_data<coordinate_type>(data_[i].first, data_[i].second.first));
0344       }
0345       return true;
0346     }
0347
0348     polygon_90_set_data&
0349     bloat2(typename coordinate_traits<coordinate_type>::unsigned_area_type west_bloating,
0350           typename coordinate_traits<coordinate_type>::unsigned_area_type east_bloating,
0351           typename coordinate_traits<coordinate_type>::unsigned_area_type south_bloating,
0352           typename coordinate_traits<coordinate_type>::unsigned_area_type north_bloating) {
0353       std::vector<rectangle_data<coordinate_type> > rects;
0354       clean();
0355       rects.reserve(data_.size() / 2);
0356       get(rects);
0357       rectangle_data<coordinate_type> convolutionRectangle(interval_data<coordinate_type>(-((coordinate_type)west_bloating),
0358                                                                                           (coordinate_type)east_bloating),
0359                                                            interval_data<coordinate_type>(-((coordinate_type)south_bloating),
0360                                                                                           (coordinate_type)north_bloating));
0361       for(typename std::vector<rectangle_data<coordinate_type> >::iterator itr = rects.begin();
0362           itr != rects.end(); ++itr) {
0363         convolve(*itr, convolutionRectangle);
0364       }
0365       clear();
0366       insert(rects.begin(), rects.end());
0367       return *this;
0368     }
0369
0370     static void modify_pt(point_data<coordinate_type>& pt, const point_data<coordinate_type>&  prev_pt,
0371                           const point_data<coordinate_type>&  current_pt,  const point_data<coordinate_type>&  next_pt,
0372                           coordinate_type west_bloating,
0373                           coordinate_type east_bloating,
0374                           coordinate_type south_bloating,
0375                           coordinate_type north_bloating) {
0376       bool pxl = prev_pt.x() < current_pt.x();
0377       bool pyl = prev_pt.y() < current_pt.y();
0378       bool nxl = next_pt.x() < current_pt.x();
0379       bool nyl = next_pt.y() < current_pt.y();
0380       bool pxg = prev_pt.x() > current_pt.x();
0381       bool pyg = prev_pt.y() > current_pt.y();
0382       bool nxg = next_pt.x() > current_pt.x();
0383       bool nyg = next_pt.y() > current_pt.y();
0384       //two of the four if statements will execute
0385       if(pxl)
0386         pt.y(current_pt.y() - south_bloating);
0387       if(pxg)
0388         pt.y(current_pt.y() + north_bloating);
0389       if(nxl)
0390         pt.y(current_pt.y() + north_bloating);
0391       if(nxg)
0392         pt.y(current_pt.y() - south_bloating);
0393       if(pyl)
0394         pt.x(current_pt.x() + east_bloating);
0395       if(pyg)
0396         pt.x(current_pt.x() - west_bloating);
0397       if(nyl)
0398         pt.x(current_pt.x() - west_bloating);
0399       if(nyg)
0400         pt.x(current_pt.x() + east_bloating);
0401     }
0402     static void resize_poly_up(std::vector<point_data<coordinate_type> >& poly,
0403                                coordinate_type west_bloating,
0404                                coordinate_type east_bloating,
0405                                coordinate_type south_bloating,
0406                                coordinate_type north_bloating) {
0407       point_data<coordinate_type> first_pt = poly[0];
0408       point_data<coordinate_type> second_pt = poly[1];
0409       point_data<coordinate_type> prev_pt = poly[0];
0410       point_data<coordinate_type> current_pt = poly[1];
0411       for(std::size_t i = 2; i < poly.size(); ++i) {
0412         point_data<coordinate_type> next_pt = poly[i];
0413         modify_pt(poly[i-1], prev_pt, current_pt, next_pt, west_bloating, east_bloating, south_bloating, north_bloating);
0414         prev_pt = current_pt;
0415         current_pt = next_pt;
0416       }
0417       point_data<coordinate_type> next_pt = first_pt;
0418       modify_pt(poly.back(), prev_pt, current_pt, next_pt, west_bloating, east_bloating, south_bloating, north_bloating);
0419       prev_pt = current_pt;
0420       current_pt = next_pt;
0421       next_pt = second_pt;
0422       modify_pt(poly[0], prev_pt, current_pt, next_pt, west_bloating, east_bloating, south_bloating, north_bloating);
0423       remove_colinear_pts(poly);
0424     }
0425     static bool resize_poly_down(std::vector<point_data<coordinate_type> >& poly,
0426                                  coordinate_type west_shrinking,
0427                                  coordinate_type east_shrinking,
0428                                  coordinate_type south_shrinking,
0429                                  coordinate_type north_shrinking) {
0430       rectangle_data<coordinate_type> extents_rectangle;
0431       set_points(extents_rectangle, poly[0], poly[0]);
0432       point_data<coordinate_type> first_pt = poly[0];
0433       point_data<coordinate_type> second_pt = poly[1];
0434       point_data<coordinate_type> prev_pt = poly[0];
0435       point_data<coordinate_type> current_pt = poly[1];
0436       encompass(extents_rectangle, current_pt);
0437       for(std::size_t i = 2; i < poly.size(); ++i) {
0438         point_data<coordinate_type> next_pt = poly[i];
0439         encompass(extents_rectangle, next_pt);
0440         modify_pt(poly[i-1], prev_pt, current_pt, next_pt, west_shrinking, east_shrinking, south_shrinking, north_shrinking);
0441         prev_pt = current_pt;
0442         current_pt = next_pt;
0443       }
0444       if(delta(extents_rectangle, HORIZONTAL) < std::abs(west_shrinking + east_shrinking))
0445         return false;
0446       if(delta(extents_rectangle, VERTICAL) < std::abs(north_shrinking + south_shrinking))
0447         return false;
0448       point_data<coordinate_type> next_pt = first_pt;
0449       modify_pt(poly.back(), prev_pt, current_pt, next_pt, west_shrinking, east_shrinking, south_shrinking, north_shrinking);
0450       prev_pt = current_pt;
0451       current_pt = next_pt;
0452       next_pt = second_pt;
0453       modify_pt(poly[0], prev_pt, current_pt, next_pt, west_shrinking, east_shrinking, south_shrinking, north_shrinking);
0454       return remove_colinear_pts(poly);
0455     }
0456
0457     static bool remove_colinear_pts(std::vector<point_data<coordinate_type> >& poly) {
0458       bool found_colinear = true;
0459       while(found_colinear && poly.size() >= 4) {
0460         found_colinear = false;
0461         typename std::vector<point_data<coordinate_type> >::iterator itr = poly.begin();
0462         itr += poly.size() - 1; //get last element position
0463         typename std::vector<point_data<coordinate_type> >::iterator itr2 = poly.begin();
0464         typename std::vector<point_data<coordinate_type> >::iterator itr3 = itr2;
0465         ++itr3;
0466         std::size_t count = 0;
0467         for( ; itr3 < poly.end(); ++itr3) {
0468           if(((*itr).x() == (*itr2).x() && (*itr).x() == (*itr3).x()) ||
0469              ((*itr).y() == (*itr2).y() && (*itr).y() == (*itr3).y()) ) {
0470             ++count;
0471             found_colinear = true;
0472           } else {
0473             itr = itr2;
0474             ++itr2;
0475           }
0476           *itr2 = *itr3;
0477         }
0478         itr3 = poly.begin();
0479         if(((*itr).x() == (*itr2).x() && (*itr).x() == (*itr3).x()) ||
0480            ((*itr).y() == (*itr2).y() && (*itr).y() == (*itr3).y()) ) {
0481           ++count;
0482           found_colinear = true;
0483         }
0484         poly.erase(poly.end() - count, poly.end());
0485       }
0486       return poly.size() >= 4;
0487     }
0488
0489     polygon_90_set_data&
0490     bloat(typename coordinate_traits<coordinate_type>::unsigned_area_type west_bloating,
0491            typename coordinate_traits<coordinate_type>::unsigned_area_type east_bloating,
0492            typename coordinate_traits<coordinate_type>::unsigned_area_type south_bloating,
0493            typename coordinate_traits<coordinate_type>::unsigned_area_type north_bloating) {
0494       std::list<polygon_45_with_holes_data<coordinate_type> > polys;
0495       get(polys);
0496       clear();
0497       for(typename std::list<polygon_45_with_holes_data<coordinate_type> >::iterator itr = polys.begin();
0498           itr != polys.end(); ++itr) {
0499         //polygon_90_set_data<coordinate_type> psref;
0500         //psref.insert(view_as<polygon_90_concept>((*itr).self_));
0501         //rectangle_data<coordinate_type> prerect;
0502         //psref.extents(prerect);
0503         resize_poly_up((*itr).self_.coords_, (coordinate_type)west_bloating, (coordinate_type)east_bloating,
0504                        (coordinate_type)south_bloating, (coordinate_type)north_bloating);
0505         iterator_geometry_to_set<polygon_90_concept, view_of<polygon_90_concept, polygon_45_data<coordinate_type> > >
0506           begin_input(view_as<polygon_90_concept>((*itr).self_), LOW, orient_, false, true, COUNTERCLOCKWISE),
0507           end_input(view_as<polygon_90_concept>((*itr).self_), HIGH, orient_, false, true, COUNTERCLOCKWISE);
0508         insert(begin_input, end_input, orient_);
0509         //polygon_90_set_data<coordinate_type> pstest;
0510         //pstest.insert(view_as<polygon_90_concept>((*itr).self_));
0511         //psref.bloat2(west_bloating, east_bloating, south_bloating, north_bloating);
0512         //if(!equivalence(psref, pstest)) {
0513         // std::cout << "test failed\n";
0514         //}
0515         for(typename std::list<polygon_45_data<coordinate_type> >::iterator itrh = (*itr).holes_.begin();
0516             itrh != (*itr).holes_.end(); ++itrh) {
0517           //rectangle_data<coordinate_type> rect;
0518           //psref.extents(rect);
0519           //polygon_90_set_data<coordinate_type> psrefhole;
0520           //psrefhole.insert(prerect);
0521           //psrefhole.insert(view_as<polygon_90_concept>(*itrh), true);
0522           //polygon_45_data<coordinate_type> testpoly(*itrh);
0523           if(resize_poly_down((*itrh).coords_,(coordinate_type)west_bloating, (coordinate_type)east_bloating,
0524                               (coordinate_type)south_bloating, (coordinate_type)north_bloating)) {
0525             iterator_geometry_to_set<polygon_90_concept, view_of<polygon_90_concept, polygon_45_data<coordinate_type> > >
0526               begin_input2(view_as<polygon_90_concept>(*itrh), LOW, orient_, true, true),
0527               end_input2(view_as<polygon_90_concept>(*itrh), HIGH, orient_, true, true);
0528             insert(begin_input2, end_input2, orient_);
0529             //polygon_90_set_data<coordinate_type> pstesthole;
0530             //pstesthole.insert(rect);
0531             //iterator_geometry_to_set<polygon_90_concept, view_of<polygon_90_concept, polygon_45_data<coordinate_type> > >
0532             // begin_input2(view_as<polygon_90_concept>(*itrh), LOW, orient_, true, true);
0533             //pstesthole.insert(begin_input2, end_input, orient_);
0534             //psrefhole.bloat2(west_bloating, east_bloating, south_bloating, north_bloating);
0535             //if(!equivalence(psrefhole, pstesthole)) {
0536             // std::cout << (winding(testpoly) == CLOCKWISE) << std::endl;
0537             // std::cout << (winding(*itrh) == CLOCKWISE) << std::endl;
0538             // polygon_90_set_data<coordinate_type> c(psrefhole);
0539             // c.clean();
0540             // polygon_90_set_data<coordinate_type> a(pstesthole);
0541             // polygon_90_set_data<coordinate_type> b(pstesthole);
0542             // a.sort();
0543             // b.clean();
0544             // std::cout << "test hole failed\n";
0545             // //std::cout << testpoly << std::endl;
0546             //}
0547           }
0548         }
0549       }
0550       return *this;
0551     }
0552
0553     polygon_90_set_data&
0554     shrink(typename coordinate_traits<coordinate_type>::unsigned_area_type west_shrinking,
0555            typename coordinate_traits<coordinate_type>::unsigned_area_type east_shrinking,
0556            typename coordinate_traits<coordinate_type>::unsigned_area_type south_shrinking,
0557            typename coordinate_traits<coordinate_type>::unsigned_area_type north_shrinking) {
0558       std::list<polygon_45_with_holes_data<coordinate_type> > polys;
0559       get(polys);
0560       clear();
0561       for(typename std::list<polygon_45_with_holes_data<coordinate_type> >::iterator itr = polys.begin();
0562           itr != polys.end(); ++itr) {
0563         //polygon_90_set_data<coordinate_type> psref;
0564         //psref.insert(view_as<polygon_90_concept>((*itr).self_));
0565         //rectangle_data<coordinate_type> prerect;
0566         //psref.extents(prerect);
0567         //polygon_45_data<coordinate_type> testpoly((*itr).self_);
0568         if(resize_poly_down((*itr).self_.coords_, -(coordinate_type)west_shrinking, -(coordinate_type)east_shrinking,
0569                             -(coordinate_type)south_shrinking, -(coordinate_type)north_shrinking)) {
0570           iterator_geometry_to_set<polygon_90_concept, view_of<polygon_90_concept, polygon_45_data<coordinate_type> > >
0571             begin_input(view_as<polygon_90_concept>((*itr).self_), LOW, orient_, false, true, COUNTERCLOCKWISE),
0572             end_input(view_as<polygon_90_concept>((*itr).self_), HIGH, orient_, false, true, COUNTERCLOCKWISE);
0573           insert(begin_input, end_input, orient_);
0574           //iterator_geometry_to_set<polygon_90_concept, view_of<polygon_90_concept, polygon_45_data<coordinate_type> > >
0575           //  begin_input2(view_as<polygon_90_concept>((*itr).self_), LOW, orient_, false, true, COUNTERCLOCKWISE);
0576           //polygon_90_set_data<coordinate_type> pstest;
0577           //pstest.insert(begin_input2, end_input, orient_);
0578           //psref.shrink2(west_shrinking, east_shrinking, south_shrinking, north_shrinking);
0579           //if(!equivalence(psref, pstest)) {
0580           //  std::cout << "test failed\n";
0581           //}
0582           for(typename std::list<polygon_45_data<coordinate_type> >::iterator itrh = (*itr).holes_.begin();
0583               itrh != (*itr).holes_.end(); ++itrh) {
0584             //rectangle_data<coordinate_type> rect;
0585             //psref.extents(rect);
0586             //polygon_90_set_data<coordinate_type> psrefhole;
0587             //psrefhole.insert(prerect);
0588             //psrefhole.insert(view_as<polygon_90_concept>(*itrh), true);
0589             //polygon_45_data<coordinate_type> testpoly(*itrh);
0590             resize_poly_up((*itrh).coords_, -(coordinate_type)west_shrinking, -(coordinate_type)east_shrinking,
0591                             -(coordinate_type)south_shrinking, -(coordinate_type)north_shrinking);
0592             iterator_geometry_to_set<polygon_90_concept, view_of<polygon_90_concept, polygon_45_data<coordinate_type> > >
0593               begin_input2(view_as<polygon_90_concept>(*itrh), LOW, orient_, true, true),
0594               end_input2(view_as<polygon_90_concept>(*itrh), HIGH, orient_, true, true);
0595             insert(begin_input2, end_input2, orient_);
0596             //polygon_90_set_data<coordinate_type> pstesthole;
0597             //pstesthole.insert(rect);
0598             //iterator_geometry_to_set<polygon_90_concept, view_of<polygon_90_concept, polygon_45_data<coordinate_type> > >
0599             //  begin_input2(view_as<polygon_90_concept>(*itrh), LOW, orient_, true, true);
0600             //pstesthole.insert(begin_input2, end_input, orient_);
0601             //psrefhole.shrink2(west_shrinking, east_shrinking, south_shrinking, north_shrinking);
0602             //if(!equivalence(psrefhole, pstesthole)) {
0603             //  std::cout << (winding(testpoly) == CLOCKWISE) << std::endl;
0604             //  std::cout << (winding(*itrh) == CLOCKWISE) << std::endl;
0605             //  polygon_90_set_data<coordinate_type> c(psrefhole);
0606             //  c.clean();
0607             //  polygon_90_set_data<coordinate_type> a(pstesthole);
0608             //  polygon_90_set_data<coordinate_type> b(pstesthole);
0609             //  a.sort();
0610             //  b.clean();
0611             //  std::cout << "test hole failed\n";
0612             //  //std::cout << testpoly << std::endl;
0613             //}
0614           }
0615         }
0616       }
0617       return *this;
0618     }
0619
0620     polygon_90_set_data&
0621     shrink2(typename coordinate_traits<coordinate_type>::unsigned_area_type west_shrinking,
0622             typename coordinate_traits<coordinate_type>::unsigned_area_type east_shrinking,
0623             typename coordinate_traits<coordinate_type>::unsigned_area_type south_shrinking,
0624             typename coordinate_traits<coordinate_type>::unsigned_area_type north_shrinking) {
0625       rectangle_data<coordinate_type> externalBoundary;
0626       if(!extents(externalBoundary)) return *this;
0627       ::boost::polygon::bloat(externalBoundary, 10); //bloat by diferential ammount
0628       //insert a hole that encompasses the data
0629       insert(externalBoundary, true); //note that the set is in a dirty state now
0630       sort();  //does not apply implicit OR operation
0631       std::vector<rectangle_data<coordinate_type> > rects;
0632       rects.reserve(data_.size() / 2);
0633       //begin does not apply implicit or operation, this is a dirty range
0634       form_rectangles(rects, data_.begin(), data_.end(), orient_, rectangle_concept());
0635       clear();
0636       rectangle_data<coordinate_type> convolutionRectangle(interval_data<coordinate_type>(-((coordinate_type)east_shrinking),
0637                                                                                           (coordinate_type)west_shrinking),
0638                                                            interval_data<coordinate_type>(-((coordinate_type)north_shrinking),
0639                                                                                           (coordinate_type)south_shrinking));
0640       for(typename std::vector<rectangle_data<coordinate_type> >::iterator itr = rects.begin();
0641           itr != rects.end(); ++itr) {
0642         rectangle_data<coordinate_type>& rect = *itr;
0643         convolve(rect, convolutionRectangle);
0644         //insert rectangle as a hole
0645         insert(rect, true);
0646       }
0647       convolve(externalBoundary, convolutionRectangle);
0648       //insert duplicate of external boundary as solid to cancel out the external hole boundaries
0649       insert(externalBoundary);
0650       clean(); //we have negative values in the set, so we need to apply an OR operation to make it valid input to a boolean
0651       return *this;
0652     }
0653
0654     polygon_90_set_data&
0655     shrink(direction_2d dir, typename coordinate_traits<coordinate_type>::unsigned_area_type shrinking) {
0656       if(dir == WEST)
0657         return shrink(shrinking, 0, 0, 0);
0658       if(dir == EAST)
0659         return shrink(0, shrinking, 0, 0);
0660       if(dir == SOUTH)
0661         return shrink(0, 0, shrinking, 0);
0662       return shrink(0, 0, 0, shrinking);
0663     }
0664
0665     polygon_90_set_data&
0666     bloat(direction_2d dir, typename coordinate_traits<coordinate_type>::unsigned_area_type shrinking) {
0667       if(dir == WEST)
0668         return bloat(shrinking, 0, 0, 0);
0669       if(dir == EAST)
0670         return bloat(0, shrinking, 0, 0);
0671       if(dir == SOUTH)
0672         return bloat(0, 0, shrinking, 0);
0673       return bloat(0, 0, 0, shrinking);
0674     }
0675
0676     polygon_90_set_data&
0677     resize(coordinate_type west, coordinate_type east, coordinate_type south, coordinate_type north);
0678
0679     polygon_90_set_data& move(coordinate_type x_delta, coordinate_type y_delta) {
0680       for(typename std::vector<std::pair<coordinate_type, std::pair<coordinate_type, int> > >::iterator
0681             itr = data_.begin(); itr != data_.end(); ++itr) {
0682         if(orient_ == orientation_2d(VERTICAL)) {
0683           (*itr).first += x_delta;
0684           (*itr).second.first += y_delta;
0685         } else {
0686           (*itr).second.first += x_delta;
0687           (*itr).first += y_delta;
0688         }
0689       }
0690       return *this;
0691     }
0692
0693     // transform set
0694     template <typename transformation_type>
0695     polygon_90_set_data& transform(const transformation_type& transformation) {
0696       direction_2d dir1, dir2;
0697       transformation.get_directions(dir1, dir2);
0698       int sign = dir1.get_sign() * dir2.get_sign();
0699       for(typename std::vector<std::pair<coordinate_type, std::pair<coordinate_type, int> > >::iterator
0700             itr = data_.begin(); itr != data_.end(); ++itr) {
0701         if(orient_ == orientation_2d(VERTICAL)) {
0702           transformation.transform((*itr).first, (*itr).second.first);
0703         } else {
0704           transformation.transform((*itr).second.first, (*itr).first);
0705         }
0706         (*itr).second.second *= sign;
0707       }
0708       if(dir1 != EAST || dir2 != NORTH)
0709         unsorted_ = true; //some mirroring or rotation must have happened
0710       return *this;
0711     }
0712
0713     // scale set
0714     polygon_90_set_data& scale_up(typename coordinate_traits<coordinate_type>::unsigned_area_type factor) {
0715       for(typename std::vector<std::pair<coordinate_type, std::pair<coordinate_type, int> > >::iterator
0716             itr = data_.begin(); itr != data_.end(); ++itr) {
0717         (*itr).first *= (coordinate_type)factor;
0718         (*itr).second.first *= (coordinate_type)factor;
0719       }
0720       return *this;
0721     }
0722     polygon_90_set_data& scale_down(typename coordinate_traits<coordinate_type>::unsigned_area_type factor) {
0723       typedef typename coordinate_traits<coordinate_type>::coordinate_distance dt;
0724       for(typename std::vector<std::pair<coordinate_type, std::pair<coordinate_type, int> > >::iterator
0725             itr = data_.begin(); itr != data_.end(); ++itr) {
0726         (*itr).first = scaling_policy<coordinate_type>::round((dt)((*itr).first) / (dt)factor);
0727         (*itr).second.first = scaling_policy<coordinate_type>::round((dt)((*itr).second.first) / (dt)factor);
0728       }
0729       unsorted_ = true; //scaling down can make coordinates equal that were not previously equal
0730       return *this;
0731     }
0732     template <typename scaling_type>
0733     polygon_90_set_data& scale(const anisotropic_scale_factor<scaling_type>& scaling) {
0734       for(typename std::vector<std::pair<coordinate_type, std::pair<coordinate_type, int> > >::iterator
0735             itr = data_.begin(); itr != data_.end(); ++itr) {
0736         if(orient_ == orientation_2d(VERTICAL)) {
0737           scaling.scale((*itr).first, (*itr).second.first);
0738         } else {
0739           scaling.scale((*itr).second.first, (*itr).first);
0740         }
0741       }
0742       unsorted_ = true;
0743       return *this;
0744     }
0745     template <typename scaling_type>
0746     polygon_90_set_data& scale_with(const scaling_type& scaling) {
0747       for(typename std::vector<std::pair<coordinate_type, std::pair<coordinate_type, int> > >::iterator
0748             itr = data_.begin(); itr != data_.end(); ++itr) {
0749         if(orient_ == orientation_2d(VERTICAL)) {
0750           scaling.scale((*itr).first, (*itr).second.first);
0751         } else {
0752           scaling.scale((*itr).second.first, (*itr).first);
0753         }
0754       }
0755       unsorted_ = true;
0756       return *this;
0757     }
0758     polygon_90_set_data& scale(double factor) {
0759       typedef typename coordinate_traits<coordinate_type>::coordinate_distance dt;
0760       for(typename std::vector<std::pair<coordinate_type, std::pair<coordinate_type, int> > >::iterator
0761             itr = data_.begin(); itr != data_.end(); ++itr) {
0762         (*itr).first = scaling_policy<coordinate_type>::round((dt)((*itr).first) * (dt)factor);
0763         (*itr).second.first = scaling_policy<coordinate_type>::round((dt)((*itr).second.first) * (dt)factor);
0764       }
0765       unsorted_ = true; //scaling make coordinates equal that were not previously equal
0766       return *this;
0767     }
0768
0769     polygon_90_set_data& self_xor() {
0770       sort();
0771       if(dirty_) { //if it is clean it is a no-op
0772         boolean_op::default_arg_workaround<boolean_op::UnaryCount>::applyBooleanOr(data_);
0773         dirty_ = false;
0774       }
0775       return *this;
0776     }
0777
0778     polygon_90_set_data& self_intersect() {
0779       sort();
0780       if(dirty_) { //if it is clean it is a no-op
0781         interval_data<coordinate_type> ivl((std::numeric_limits<coordinate_type>::min)(), (std::numeric_limits<coordinate_type>::max)());
0782         rectangle_data<coordinate_type> rect(ivl, ivl);
0783         insert(rect, true);
0784         clean();
0785       }
0786       return *this;
0787     }
0788
0789     inline polygon_90_set_data& interact(const polygon_90_set_data& that) {
0790       typedef coordinate_type Unit;
0791       if(that.dirty_) that.clean();
0792       typename touch_90_operation<Unit>::TouchSetData tsd;
0793       touch_90_operation<Unit>::populateTouchSetData(tsd, that.data_, 0);
0794       std::vector<polygon_90_data<Unit> > polys;
0795       get(polys);
0796       std::vector<std::set<int> > graph(polys.size()+1, std::set<int>());
0797       for(std::size_t i = 0; i < polys.size(); ++i){
0798         polygon_90_set_data<Unit> psTmp(that.orient_);
0799         psTmp.insert(polys[i]);
0800         psTmp.clean();
0801         touch_90_operation<Unit>::populateTouchSetData(tsd, psTmp.data_, i+1);
0802       }
0803       touch_90_operation<Unit>::performTouch(graph, tsd);
0804       clear();
0805       for(std::set<int>::iterator itr = graph[0].begin(); itr != graph[0].end(); ++itr){
0806         insert(polys[(*itr)-1]);
0807       }
0808       dirty_ = false;
0809       return *this;
0810     }
0811
0812
0813     template <class T2, typename iterator_type_1, typename iterator_type_2>
0814     void applyBooleanBinaryOp(iterator_type_1 itr1, iterator_type_1 itr1_end,
0815                               iterator_type_2 itr2, iterator_type_2 itr2_end,
0816                               T2 defaultCount) {
0817       data_.clear();
0818       boolean_op::applyBooleanBinaryOp(data_, itr1, itr1_end, itr2, itr2_end, defaultCount);
0819     }
0820
0821   private:
0822     orientation_2d orient_;
0823     mutable value_type data_;
0824     mutable bool dirty_;
0825     mutable bool unsorted_;
0826
0827   private:
0828     //functions
0829     template <typename output_container>
0830     void get_dispatch(output_container& output, rectangle_concept ) const {
0831       clean();
0832       form_rectangles(output, data_.begin(), data_.end(), orient_, rectangle_concept());
0833     }
0834     template <typename output_container>
0835     void get_dispatch(output_container& output, polygon_90_concept tag) const {
0836       get_fracture(output, true, tag);
0837     }
0838
0839     template <typename output_container>
0840     void get_dispatch(output_container& output, polygon_90_concept tag,
0841       size_t vthreshold) const {
0842       get_fracture(output, true, tag, vthreshold);
0843     }
0844
0845     template <typename output_container>
0846     void get_dispatch(output_container& output, polygon_90_with_holes_concept tag) const {
0847       get_fracture(output, false, tag);
0848     }
0849
0850     template <typename output_container>
0851     void get_dispatch(output_container& output, polygon_90_with_holes_concept tag,
0852       size_t vthreshold) const {
0853       get_fracture(output, false, tag, vthreshold);
0854     }
0855
0856
0857     template <typename output_container>
0858     void get_dispatch(output_container& output, polygon_45_concept tag) const {
0859       get_fracture(output, true, tag);
0860     }
0861     template <typename output_container>
0862     void get_dispatch(output_container& output, polygon_45_with_holes_concept tag) const {
0863       get_fracture(output, false, tag);
0864     }
0865     template <typename output_container>
0866     void get_dispatch(output_container& output, polygon_concept tag) const {
0867       get_fracture(output, true, tag);
0868     }
0869     template <typename output_container>
0870     void get_dispatch(output_container& output, polygon_with_holes_concept tag) const {
0871       get_fracture(output, false, tag);
0872     }
0873     template <typename output_container, typename concept_type>
0874     void get_fracture(output_container& container, bool fracture_holes, concept_type tag) const {
0875       clean();
0876       ::boost::polygon::get_polygons(container, data_.begin(), data_.end(), orient_, fracture_holes, tag);
0877     }
0878
0879     template <typename output_container, typename concept_type>
0880     void get_fracture(output_container& container, bool fracture_holes, concept_type tag,
0881       size_t vthreshold) const {
0882       clean();
0883       ::boost::polygon::get_polygons(container, data_.begin(), data_.end(), orient_, fracture_holes, tag, vthreshold);
0884     }
0885   };
0886
0887   template <typename coordinate_type>
0888   polygon_90_set_data<coordinate_type>&
0889   polygon_90_set_data<coordinate_type>::resize(coordinate_type west,
0890                                                coordinate_type east,
0891                                                coordinate_type south,
0892                                                coordinate_type north) {
0893     move(-west, -south);
0894     coordinate_type e_total = west + east;
0895     coordinate_type n_total = south + north;
0896     if((e_total < 0) ^ (n_total < 0)) {
0897       //different signs
0898       if(e_total < 0) {
0899         shrink(0, -e_total, 0, 0);
0900         if(n_total != 0)
0901           return bloat(0, 0, 0, n_total);
0902         else
0903           return (*this);
0904       } else {
0905         shrink(0, 0, 0, -n_total); //shrink first
0906         if(e_total != 0)
0907           return bloat(0, e_total, 0, 0);
0908         else
0909           return (*this);
0910       }
0911     } else {
0912       if(e_total < 0) {
0913         return shrink(0, -e_total, 0, -n_total);
0914       }
0915       return bloat(0, e_total, 0, n_total);
0916     }
0917   }
0918
0919   template <typename coordinate_type, typename property_type>
0920   class property_merge_90 {
0921   private:
0922     std::vector<std::pair<property_merge_point<coordinate_type>, std::pair<property_type, int> > > pmd_;
0923   public:
0924     inline property_merge_90() : pmd_() {}
0925     inline property_merge_90(const property_merge_90& that) : pmd_(that.pmd_) {}
0926     inline property_merge_90& operator=(const property_merge_90& that) { pmd_ = that.pmd_; return *this; }
0927     inline void insert(const polygon_90_set_data<coordinate_type>& ps, const property_type& property) {
0928       merge_scanline<coordinate_type, property_type, polygon_90_set_data<coordinate_type> >::
0929         populate_property_merge_data(pmd_, ps.begin(), ps.end(), property, ps.orient());
0930     }
0931     template <class GeoObjT>
0932     inline void insert(const GeoObjT& geoObj, const property_type& property) {
0933       polygon_90_set_data<coordinate_type> ps;
0934       ps.insert(geoObj);
0935       insert(ps, property);
0936     }
0937     //merge properties of input geometries and store the resulting geometries of regions
0938     //with unique sets of merged properties to polygons sets in a map keyed by sets of properties
0939     // T = std::map<std::set<property_type>, polygon_90_set_data<coordiante_type> > or
0940     // T = std::map<std::vector<property_type>, polygon_90_set_data<coordiante_type> >
0941     template <typename ResultType>
0942     inline void merge(ResultType& result) {
0943       merge_scanline<coordinate_type, property_type, polygon_90_set_data<coordinate_type>, typename ResultType::key_type> ms;
0944       ms.perform_merge(result, pmd_);
0945     }
0946   };
0947
0948   //ConnectivityExtraction computes the graph of connectivity between rectangle, polygon and
0949   //polygon set graph nodes where an edge is created whenever the geometry in two nodes overlap
0950   template <typename coordinate_type>
0951   class connectivity_extraction_90 {
0952   private:
0953     typedef typename touch_90_operation<coordinate_type>::TouchSetData tsd;
0954     tsd tsd_;
0955     unsigned int nodeCount_;
0956   public:
0957     inline connectivity_extraction_90() : tsd_(), nodeCount_(0) {}
0958     inline connectivity_extraction_90(const connectivity_extraction_90& that) : tsd_(that.tsd_),
0959                                                                           nodeCount_(that.nodeCount_) {}
0960     inline connectivity_extraction_90& operator=(const connectivity_extraction_90& that) {
0961       tsd_ = that.tsd_;
0962       nodeCount_ = that.nodeCount_; {}
0963       return *this;
0964     }
0965
0966     //insert a polygon set graph node, the value returned is the id of the graph node
0967     inline unsigned int insert(const polygon_90_set_data<coordinate_type>& ps) {
0968       ps.clean();
0969       touch_90_operation<coordinate_type>::populateTouchSetData(tsd_, ps.begin(), ps.end(), nodeCount_);
0970       return nodeCount_++;
0971     }
0972     template <class GeoObjT>
0973     inline unsigned int insert(const GeoObjT& geoObj) {
0974       polygon_90_set_data<coordinate_type> ps;
0975       ps.insert(geoObj);
0976       return insert(ps);
0977     }
0978
0979     //extract connectivity and store the edges in the graph
0980     //graph must be indexable by graph node id and the indexed value must be a std::set of
0981     //graph node id
0982     template <class GraphT>
0983     inline void extract(GraphT& graph) {
0984       touch_90_operation<coordinate_type>::performTouch(graph, tsd_);
0985     }
0986   };
0987 }
0988 }
0989 #endif