boost/polygon/polygon_90_set_data.hpp

   1 /*
   2   Copyright 2008 Intel Corporation
   3
   4   Use, modification and distribution are subject to the Boost Software License,
   5   Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
   6   http://www.boost.org/LICENSE_1_0.txt).
   7 */
   8 #ifndef BOOST_POLYGON_POLYGON_90_SET_DATA_HPP
   9 #define BOOST_POLYGON_POLYGON_90_SET_DATA_HPP
  10 #include "isotropy.hpp"
  11 #include "point_concept.hpp"
  12 #include "point_3d_concept.hpp"
  13 #include "transform.hpp"
  14 #include "interval_concept.hpp"
  15 #include "rectangle_concept.hpp"
  16 #include "detail/iterator_points_to_compact.hpp"
  17 #include "detail/iterator_compact_to_points.hpp"
  18 #include "polygon_traits.hpp"
  19
  20 //manhattan boolean algorithms
  21 #include "detail/boolean_op.hpp"
  22 #include "detail/polygon_formation.hpp"
  23 #include "detail/rectangle_formation.hpp"
  24 #include "detail/max_cover.hpp"
  25 #include "detail/property_merge.hpp"
  26 #include "detail/polygon_90_touch.hpp"
  27 #include "detail/iterator_geometry_to_set.hpp"
  28
  29 namespace boost { namespace polygon{
  30   template <typename ltype, typename rtype, typename op_type>
  31   class polygon_90_set_view;
  32
  33   template <typename T>
  34   class polygon_90_set_data {
  35   public:
  36     typedef T coordinate_type;
  37     typedef std::vector<std::pair<coordinate_type, std::pair<coordinate_type, int> > > value_type;
  38     typedef typename std::vector<std::pair<coordinate_type, std::pair<coordinate_type, int> > >::const_iterator iterator_type;
  39     typedef polygon_90_set_data operator_arg_type;
  40
  41     // default constructor
  42     inline polygon_90_set_data() : orient_(HORIZONTAL), data_(), dirty_(false), unsorted_(false) {}
  43
  44     // constructor
  45     inline polygon_90_set_data(orientation_2d orient) : orient_(orient), data_(), dirty_(false), unsorted_(false) {}
  46
  47     // constructor from an iterator pair over vertex data
  48     template <typename iT>
  49     inline polygon_90_set_data(orientation_2d orient, iT input_begin, iT input_end) :
  50       orient_(HORIZONTAL), data_(), dirty_(false), unsorted_(false) {
  51       dirty_ = true;
  52       unsorted_ = true;
  53       for( ; input_begin != input_end; ++input_begin) { insert(*input_begin); }
  54     }
  55
  56     // copy constructor
  57     inline polygon_90_set_data(const polygon_90_set_data& that) :
  58       orient_(that.orient_), data_(that.data_), dirty_(that.dirty_), unsorted_(that.unsorted_) {}
  59
  60     template <typename ltype, typename rtype, typename op_type>
  61     inline polygon_90_set_data(const polygon_90_set_view<ltype, rtype, op_type>& that);
  62
  63     // copy with orientation change constructor
  64     inline polygon_90_set_data(orientation_2d orient, const polygon_90_set_data& that) :
  65       orient_(orient), data_(), dirty_(false), unsorted_(false) {
  66       insert(that, false, that.orient_);
  67     }
  68
  69     // destructor
  70     inline ~polygon_90_set_data() {}
  71
  72     // assignement operator
  73     inline polygon_90_set_data& operator=(const polygon_90_set_data& that) {
  74       if(this == &that) return *this;
  75       orient_ = that.orient_;
  76       data_ = that.data_;
  77       dirty_ = that.dirty_;
  78       unsorted_ = that.unsorted_;
  79       return *this;
  80     }
  81
  82     template <typename ltype, typename rtype, typename op_type>
  83     inline polygon_90_set_data& operator=(const polygon_90_set_view<ltype, rtype, op_type>& that);
  84
  85     template <typename geometry_object>
  86     inline polygon_90_set_data& operator=(const geometry_object& geometry) {
  87       data_.clear();
  88       insert(geometry);
  89       return *this;
  90     }
  91
  92     // insert iterator range
  93     inline void insert(iterator_type input_begin, iterator_type input_end, orientation_2d orient = HORIZONTAL) {
  94       if(input_begin == input_end || (!data_.empty() && &(*input_begin) == &(*(data_.begin())))) return;
  95       dirty_ = true;
  96       unsorted_ = true;
  97       if(orient == orient_)
  98         data_.insert(data_.end(), input_begin, input_end);
  99       else {
 100         for( ; input_begin != input_end; ++input_begin) {
 101           insert(*input_begin, false, orient);
 102         }
 103       }
 104     }
 105
 106     // insert iterator range
 107     template <typename iT>
 108     inline void insert(iT input_begin, iT input_end, orientation_2d orient = HORIZONTAL) {
 109       if(input_begin == input_end) return;
 110       dirty_ = true;
 111       unsorted_ = true;
 112       for( ; input_begin != input_end; ++input_begin) {
 113         insert(*input_begin, false, orient);
 114       }
 115     }
 116
 117     inline void insert(const polygon_90_set_data& polygon_set) {
 118       insert(polygon_set.begin(), polygon_set.end(), polygon_set.orient());
 119     }
 120
 121     inline void insert(const std::pair<std::pair<point_data<coordinate_type>, point_data<coordinate_type> >, int>& edge, bool is_hole = false,
 122                        orientation_2d orient = HORIZONTAL) {
 123       std::pair<coordinate_type, std::pair<coordinate_type, int> > vertex;
 124       vertex.first = edge.first.first.x();
 125       vertex.second.first = edge.first.first.y();
 126       vertex.second.second = edge.second * (is_hole ? -1 : 1);
 127       insert(vertex, false, VERTICAL);
 128       vertex.first = edge.first.second.x();
 129       vertex.second.first = edge.first.second.y();
 130       vertex.second.second *= -1;
 131       insert(vertex, false, VERTICAL);
 132     }
 133
 134     template <typename geometry_type>
 135     inline void insert(const geometry_type& geometry_object, bool is_hole = false, orientation_2d = HORIZONTAL) {
 136       iterator_geometry_to_set<typename geometry_concept<geometry_type>::type, geometry_type>
 137         begin_input(geometry_object, LOW, orient_, is_hole), end_input(geometry_object, HIGH, orient_, is_hole);
 138       insert(begin_input, end_input, orient_);
 139     }
 140
 141     inline void insert(const std::pair<coordinate_type, std::pair<coordinate_type, int> >& vertex, bool is_hole = false,
 142                        orientation_2d orient = HORIZONTAL) {
 143       data_.push_back(vertex);
 144       if(orient != orient_) std::swap(data_.back().first, data_.back().second.first);
 145       if(is_hole) data_.back().second.second *= -1;
 146       dirty_ = true;
 147       unsorted_ = true;
 148     }
 149
 150     inline void insert(coordinate_type major_coordinate, const std::pair<interval_data<coordinate_type>, int>& edge) {
 151       std::pair<coordinate_type, std::pair<coordinate_type, int> > vertex;
 152       vertex.first = major_coordinate;
 153       vertex.second.first = edge.first.get(LOW);
 154       vertex.second.second = edge.second;
 155       insert(vertex, false, orient_);
 156       vertex.second.first = edge.first.get(HIGH);
 157       vertex.second.second *= -1;
 158       insert(vertex, false, orient_);
 159     }
 160
 161     template <typename output_container>
 162     inline void get(output_container& output) const {
 163       get_dispatch(output, typename geometry_concept<typename output_container::value_type>::type());
 164     }
 165
 166     template <typename output_container>
 167     inline void get_polygons(output_container& output) const {
 168       get_dispatch(output, polygon_90_concept());
 169     }
 170
 171     template <typename output_container>
 172     inline void get_rectangles(output_container& output) const {
 173       clean();
 174       form_rectangles(output, data_.begin(), data_.end(), orient_, rectangle_concept());
 175     }
 176
 177     template <typename output_container>
 178     inline void get_rectangles(output_container& output, orientation_2d slicing_orientation) const {
 179       if(slicing_orientation == orient_) {
 180         get_rectangles(output);
 181       } else {
 182         polygon_90_set_data<coordinate_type> ps(*this);
 183         ps.transform(axis_transformation(axis_transformation::SWAP_XY));
 184         output_container result;
 185         ps.get_rectangles(result);
 186         for(typename output_container::iterator itr = result.begin(); itr != result.end(); ++itr) {
 187           ::boost::polygon::transform(*itr, axis_transformation(axis_transformation::SWAP_XY));
 188         }
 189         output.insert(output.end(), result.begin(), result.end());
 190       }
 191     }
 192
 193     // equivalence operator
 194     inline bool operator==(const polygon_90_set_data& p) const {
 195       if(orient_ == p.orient()) {
 196         clean();
 197         p.clean();
 198         return data_ == p.data_;
 199       } else {
 200         return false;
 201       }
 202     }
 203
 204     // inequivalence operator
 205     inline bool operator!=(const polygon_90_set_data& p) const {
 206       return !((*this) == p);
 207     }
 208
 209     // get iterator to begin vertex data
 210     inline iterator_type begin() const {
 211       return data_.begin();
 212     }
 213
 214     // get iterator to end vertex data
 215     inline iterator_type end() const {
 216       return data_.end();
 217     }
 218
 219     const value_type& value() const {
 220       return data_;
 221     }
 222
 223     // clear the contents of the polygon_90_set_data
 224     inline void clear() { data_.clear(); dirty_ = unsorted_ = false; }
 225
 226     // find out if Polygon set is empty
 227     inline bool empty() const { clean(); return data_.empty(); }
 228
 229     // get the Polygon set size in vertices
 230     inline std::size_t size() const { clean(); return data_.size(); }
 231
 232     // get the current Polygon set capacity in vertices
 233     inline std::size_t capacity() const { return data_.capacity(); }
 234
 235     // reserve size of polygon set in vertices
 236     inline void reserve(std::size_t size) { return data_.reserve(size); }
 237
 238     // find out if Polygon set is sorted
 239     inline bool sorted() const { return !unsorted_; }
 240
 241     // find out if Polygon set is clean
 242     inline bool dirty() const { return dirty_; }
 243
 244     // get the scanline orientation of the polygon set
 245     inline orientation_2d orient() const { return orient_; }
 246
 247     // Start BM
 248     // The problem: If we have two polygon sets with two different scanline orientations:
 249     // I tried changing the orientation of one to coincide with other (If not, resulting boolean operation
 250     // produces spurious results).
 251     // First I tried copying polygon data from one of the sets into another set with corrected orientation
 252     // using one of the copy constructor that takes in orientation (see somewhere above in this file) --> copy constructor throws error
 253     // Then I tried another approach:(see below). This approach also fails to produce the desired results when test case is run.
 254     // Here is the part that beats me: If I comment out the whole section, I can do all the operations (^=, -=, &= )these commented out
 255     // operations perform. So then why do we need them?. Hence, I commented out this whole section.
 256     // End BM
 257     // polygon_90_set_data<coordinate_type>& operator-=(const polygon_90_set_data& that) {
 258     //   sort();
 259     //   that.sort();
 260     //   value_type data;
 261     //   std::swap(data, data_);
 262     //   applyBooleanBinaryOp(data.begin(), data.end(),
 263     //                        that.begin(), that.end(), boolean_op::BinaryCount<boolean_op::BinaryNot>());
 264     //   return *this;
 265     // }
 266     // polygon_90_set_data<coordinate_type>& operator^=(const polygon_90_set_data& that) {
 267     //   sort();
 268     //   that.sort();
 269     //   value_type data;
 270     //   std::swap(data, data_);
 271     //   applyBooleanBinaryOp(data.begin(), data.end(),
 272     //                        that.begin(), that.end(),  boolean_op::BinaryCount<boolean_op::BinaryXor>());
 273     //   return *this;
 274     // }
 275     // polygon_90_set_data<coordinate_type>& operator&=(const polygon_90_set_data& that) {
 276     //   sort();
 277     //   that.sort();
 278     //   value_type data;
 279     //   std::swap(data, data_);
 280     //   applyBooleanBinaryOp(data.begin(), data.end(),
 281     //                        that.begin(), that.end(), boolean_op::BinaryCount<boolean_op::BinaryAnd>());
 282     //   return *this;
 283     // }
 284     // polygon_90_set_data<coordinate_type>& operator|=(const polygon_90_set_data& that) {
 285     //   insert(that);
 286     //   return *this;
 287     // }
 288
 289     void clean() const {
 290       sort();
 291       if(dirty_) {
 292         boolean_op::default_arg_workaround<int>::applyBooleanOr(data_);
 293         dirty_ = false;
 294       }
 295     }
 296
 297     void sort() const{
 298       if(unsorted_) {
 299         gtlsort(data_.begin(), data_.end());
 300         unsorted_ = false;
 301       }
 302     }
 303
 304     template <typename input_iterator_type>
 305     void set(input_iterator_type input_begin, input_iterator_type input_end, orientation_2d orient) {
 306       data_.clear();
 307       data_.insert(data_.end(), input_begin, input_end);
 308       orient_ = orient;
 309       dirty_ = true;
 310       unsorted_ = true;
 311     }
 312
 313     void set(const value_type& value, orientation_2d orient) {
 314       data_ = value;
 315       orient_ = orient;
 316       dirty_ = true;
 317       unsorted_ = true;
 318     }
 319
 320     //extents
 321     template <typename rectangle_type>
 322     bool
 323     extents(rectangle_type& extents_rectangle) const {
 324       clean();
 325       if(data_.empty()) return false;
 326       if(orient_ == HORIZONTAL)
 327         set_points(extents_rectangle, point_data<coordinate_type>(data_[0].second.first, data_[0].first),
 328                    point_data<coordinate_type>(data_[data_.size() - 1].second.first, data_[data_.size() - 1].first));
 329       else
 330         set_points(extents_rectangle, point_data<coordinate_type>(data_[0].first, data_[0].second.first),
 331                    point_data<coordinate_type>(data_[data_.size() - 1].first, data_[data_.size() - 1].second.first));
 332       for(std::size_t i = 1; i < data_.size() - 1; ++i) {
 333         if(orient_ == HORIZONTAL)
 334           encompass(extents_rectangle, point_data<coordinate_type>(data_[i].second.first, data_[i].first));
 335         else
 336           encompass(extents_rectangle, point_data<coordinate_type>(data_[i].first, data_[i].second.first));
 337       }
 338       return true;
 339     }
 340
 341     polygon_90_set_data&
 342     bloat2(typename coordinate_traits<coordinate_type>::unsigned_area_type west_bloating,
 343           typename coordinate_traits<coordinate_type>::unsigned_area_type east_bloating,
 344           typename coordinate_traits<coordinate_type>::unsigned_area_type south_bloating,
 345           typename coordinate_traits<coordinate_type>::unsigned_area_type north_bloating) {
 346       std::vector<rectangle_data<coordinate_type> > rects;
 347       clean();
 348       rects.reserve(data_.size() / 2);
 349       get(rects);
 350       rectangle_data<coordinate_type> convolutionRectangle(interval_data<coordinate_type>(-((coordinate_type)west_bloating),
 351                                                                                           (coordinate_type)east_bloating),
 352                                                            interval_data<coordinate_type>(-((coordinate_type)south_bloating),
 353                                                                                           (coordinate_type)north_bloating));
 354       for(typename std::vector<rectangle_data<coordinate_type> >::iterator itr = rects.begin();
 355           itr != rects.end(); ++itr) {
 356         convolve(*itr, convolutionRectangle);
 357       }
 358       clear();
 359       insert(rects.begin(), rects.end());
 360       return *this;
 361     }
 362
 363     static void modify_pt(point_data<coordinate_type>& pt, const point_data<coordinate_type>&  prev_pt,
 364                           const point_data<coordinate_type>&  current_pt,  const point_data<coordinate_type>&  next_pt,
 365                           coordinate_type west_bloating,
 366                           coordinate_type east_bloating,
 367                           coordinate_type south_bloating,
 368                           coordinate_type north_bloating) {
 369       bool pxl = prev_pt.x() < current_pt.x();
 370       bool pyl = prev_pt.y() < current_pt.y();
 371       bool nxl = next_pt.x() < current_pt.x();
 372       bool nyl = next_pt.y() < current_pt.y();
 373       bool pxg = prev_pt.x() > current_pt.x();
 374       bool pyg = prev_pt.y() > current_pt.y();
 375       bool nxg = next_pt.x() > current_pt.x();
 376       bool nyg = next_pt.y() > current_pt.y();
 377       //two of the four if statements will execute
 378       if(pxl)
 379         pt.y(current_pt.y() - south_bloating);
 380       if(pxg)
 381         pt.y(current_pt.y() + north_bloating);
 382       if(nxl)
 383         pt.y(current_pt.y() + north_bloating);
 384       if(nxg)
 385         pt.y(current_pt.y() - south_bloating);
 386       if(pyl)
 387         pt.x(current_pt.x() + east_bloating);
 388       if(pyg)
 389         pt.x(current_pt.x() - west_bloating);
 390       if(nyl)
 391         pt.x(current_pt.x() - west_bloating);
 392       if(nyg)
 393         pt.x(current_pt.x() + east_bloating);
 394     }
 395     static void resize_poly_up(std::vector<point_data<coordinate_type> >& poly,
 396                                coordinate_type west_bloating,
 397                                coordinate_type east_bloating,
 398                                coordinate_type south_bloating,
 399                                coordinate_type north_bloating) {
 400       point_data<coordinate_type> first_pt = poly[0];
 401       point_data<coordinate_type> second_pt = poly[1];
 402       point_data<coordinate_type> prev_pt = poly[0];
 403       point_data<coordinate_type> current_pt = poly[1];
 404       for(std::size_t i = 2; i < poly.size(); ++i) {
 405         point_data<coordinate_type> next_pt = poly[i];
 406         modify_pt(poly[i-1], prev_pt, current_pt, next_pt, west_bloating, east_bloating, south_bloating, north_bloating);
 407         prev_pt = current_pt;
 408         current_pt = next_pt;
 409       }
 410       point_data<coordinate_type> next_pt = first_pt;
 411       modify_pt(poly.back(), prev_pt, current_pt, next_pt, west_bloating, east_bloating, south_bloating, north_bloating);
 412       prev_pt = current_pt;
 413       current_pt = next_pt;
 414       next_pt = second_pt;
 415       modify_pt(poly[0], prev_pt, current_pt, next_pt, west_bloating, east_bloating, south_bloating, north_bloating);
 416       remove_colinear_pts(poly);
 417     }
 418     static bool resize_poly_down(std::vector<point_data<coordinate_type> >& poly,
 419                                  coordinate_type west_shrinking,
 420                                  coordinate_type east_shrinking,
 421                                  coordinate_type south_shrinking,
 422                                  coordinate_type north_shrinking) {
 423       rectangle_data<coordinate_type> extents_rectangle;
 424       set_points(extents_rectangle, poly[0], poly[0]);
 425       point_data<coordinate_type> first_pt = poly[0];
 426       point_data<coordinate_type> second_pt = poly[1];
 427       point_data<coordinate_type> prev_pt = poly[0];
 428       point_data<coordinate_type> current_pt = poly[1];
 429       encompass(extents_rectangle, current_pt);
 430       for(int i = 2; i < poly.size(); ++i) {
 431         point_data<coordinate_type> next_pt = poly[i];
 432         encompass(extents_rectangle, next_pt);
 433         modify_pt(poly[i-1], prev_pt, current_pt, next_pt, west_shrinking, east_shrinking, south_shrinking, north_shrinking);
 434         prev_pt = current_pt;
 435         current_pt = next_pt;
 436       }
 437       if(delta(extents_rectangle, HORIZONTAL) < std::abs(west_shrinking + east_shrinking))
 438         return false;
 439       if(delta(extents_rectangle, VERTICAL) < std::abs(north_shrinking + south_shrinking))
 440         return false;
 441       point_data<coordinate_type> next_pt = first_pt;
 442       modify_pt(poly.back(), prev_pt, current_pt, next_pt, west_shrinking, east_shrinking, south_shrinking, north_shrinking);
 443       prev_pt = current_pt;
 444       current_pt = next_pt;
 445       next_pt = second_pt;
 446       modify_pt(poly[0], prev_pt, current_pt, next_pt, west_shrinking, east_shrinking, south_shrinking, north_shrinking);
 447       return remove_colinear_pts(poly);
 448     }
 449
 450     static bool remove_colinear_pts(std::vector<point_data<coordinate_type> >& poly) {
 451       bool found_colinear = true;
 452       while(found_colinear && poly.size() >= 4) {
 453         found_colinear = false;
 454         typename std::vector<point_data<coordinate_type> >::iterator itr = poly.begin();
 455         itr += poly.size() - 1; //get last element position
 456         typename std::vector<point_data<coordinate_type> >::iterator itr2 = poly.begin();
 457         typename std::vector<point_data<coordinate_type> >::iterator itr3 = itr2;
 458         ++itr3;
 459         std::size_t count = 0;
 460         for( ; itr3 < poly.end(); ++itr3) {
 461           if(((*itr).x() == (*itr2).x() && (*itr).x() == (*itr3).x()) ||
 462              ((*itr).y() == (*itr2).y() && (*itr).y() == (*itr3).y()) ) {
 463             ++count;
 464             found_colinear = true;
 465           } else {
 466             itr = itr2;
 467             ++itr2;
 468           }
 469           *itr2 = *itr3;
 470         }
 471         itr3 = poly.begin();
 472         if(((*itr).x() == (*itr2).x() && (*itr).x() == (*itr3).x()) ||
 473            ((*itr).y() == (*itr2).y() && (*itr).y() == (*itr3).y()) ) {
 474           ++count;
 475           found_colinear = true;
 476         }
 477         poly.erase(poly.end() - count, poly.end());
 478       }
 479       return poly.size() >= 4;
 480     }
 481
 482     polygon_90_set_data&
 483     bloat(typename coordinate_traits<coordinate_type>::unsigned_area_type west_bloating,
 484            typename coordinate_traits<coordinate_type>::unsigned_area_type east_bloating,
 485            typename coordinate_traits<coordinate_type>::unsigned_area_type south_bloating,
 486            typename coordinate_traits<coordinate_type>::unsigned_area_type north_bloating) {
 487       std::list<polygon_45_with_holes_data<coordinate_type> > polys;
 488       get(polys);
 489       clear();
 490       for(typename std::list<polygon_45_with_holes_data<coordinate_type> >::iterator itr = polys.begin();
 491           itr != polys.end(); ++itr) {
 492         //polygon_90_set_data<coordinate_type> psref;
 493         //psref.insert(view_as<polygon_90_concept>((*itr).self_));
 494         //rectangle_data<coordinate_type> prerect;
 495         //psref.extents(prerect);
 496         resize_poly_up((*itr).self_.coords_, west_bloating, east_bloating, south_bloating, north_bloating);
 497         iterator_geometry_to_set<polygon_90_concept, view_of<polygon_90_concept, polygon_45_data<coordinate_type> > >
 498           begin_input(view_as<polygon_90_concept>((*itr).self_), LOW, orient_, false, true, COUNTERCLOCKWISE),
 499           end_input(view_as<polygon_90_concept>((*itr).self_), HIGH, orient_, false, true, COUNTERCLOCKWISE);
 500         insert(begin_input, end_input, orient_);
 501         //polygon_90_set_data<coordinate_type> pstest;
 502         //pstest.insert(view_as<polygon_90_concept>((*itr).self_));
 503         //psref.bloat2(west_bloating, east_bloating, south_bloating, north_bloating);
 504         //if(!equivalence(psref, pstest)) {
 505         // std::cout << "test failed\n";
 506         //}
 507         for(typename std::list<polygon_45_data<coordinate_type> >::iterator itrh = (*itr).holes_.begin();
 508             itrh != (*itr).holes_.end(); ++itrh) {
 509           //rectangle_data<coordinate_type> rect;
 510           //psref.extents(rect);
 511           //polygon_90_set_data<coordinate_type> psrefhole;
 512           //psrefhole.insert(prerect);
 513           //psrefhole.insert(view_as<polygon_90_concept>(*itrh), true);
 514           //polygon_45_data<coordinate_type> testpoly(*itrh);
 515           if(resize_poly_down((*itrh).coords_, west_bloating, east_bloating, south_bloating, north_bloating)) {
 516             iterator_geometry_to_set<polygon_90_concept, view_of<polygon_90_concept, polygon_45_data<coordinate_type> > >
 517               begin_input2(view_as<polygon_90_concept>(*itrh), LOW, orient_, true, true),
 518               end_input2(view_as<polygon_90_concept>(*itrh), HIGH, orient_, true, true);
 519             insert(begin_input2, end_input2, orient_);
 520             //polygon_90_set_data<coordinate_type> pstesthole;
 521             //pstesthole.insert(rect);
 522             //iterator_geometry_to_set<polygon_90_concept, view_of<polygon_90_concept, polygon_45_data<coordinate_type> > >
 523             // begin_input2(view_as<polygon_90_concept>(*itrh), LOW, orient_, true, true);
 524             //pstesthole.insert(begin_input2, end_input, orient_);
 525             //psrefhole.bloat2(west_bloating, east_bloating, south_bloating, north_bloating);
 526             //if(!equivalence(psrefhole, pstesthole)) {
 527             // std::cout << (winding(testpoly) == CLOCKWISE) << std::endl;
 528             // std::cout << (winding(*itrh) == CLOCKWISE) << std::endl;
 529             // polygon_90_set_data<coordinate_type> c(psrefhole);
 530             // c.clean();
 531             // polygon_90_set_data<coordinate_type> a(pstesthole);
 532             // polygon_90_set_data<coordinate_type> b(pstesthole);
 533             // a.sort();
 534             // b.clean();
 535             // std::cout << "test hole failed\n";
 536             // //std::cout << testpoly << std::endl;
 537             //}
 538           }
 539         }
 540       }
 541       return *this;
 542     }
 543
 544     polygon_90_set_data&
 545     shrink(typename coordinate_traits<coordinate_type>::unsigned_area_type west_shrinking,
 546            typename coordinate_traits<coordinate_type>::unsigned_area_type east_shrinking,
 547            typename coordinate_traits<coordinate_type>::unsigned_area_type south_shrinking,
 548            typename coordinate_traits<coordinate_type>::unsigned_area_type north_shrinking) {
 549       std::list<polygon_45_with_holes_data<coordinate_type> > polys;
 550       get(polys);
 551       clear();
 552       for(typename std::list<polygon_45_with_holes_data<coordinate_type> >::iterator itr = polys.begin();
 553           itr != polys.end(); ++itr) {
 554         //polygon_90_set_data<coordinate_type> psref;
 555         //psref.insert(view_as<polygon_90_concept>((*itr).self_));
 556         //rectangle_data<coordinate_type> prerect;
 557         //psref.extents(prerect);
 558         //polygon_45_data<coordinate_type> testpoly((*itr).self_);
 559         if(resize_poly_down((*itr).self_.coords_, -west_shrinking, -east_shrinking, -south_shrinking, -north_shrinking)) {
 560           iterator_geometry_to_set<polygon_90_concept, view_of<polygon_90_concept, polygon_45_data<coordinate_type> > >
 561             begin_input(view_as<polygon_90_concept>((*itr).self_), LOW, orient_, false, true, COUNTERCLOCKWISE),
 562             end_input(view_as<polygon_90_concept>((*itr).self_), HIGH, orient_, false, true, COUNTERCLOCKWISE);
 563           insert(begin_input, end_input, orient_);
 564           //iterator_geometry_to_set<polygon_90_concept, view_of<polygon_90_concept, polygon_45_data<coordinate_type> > >
 565           //  begin_input2(view_as<polygon_90_concept>((*itr).self_), LOW, orient_, false, true, COUNTERCLOCKWISE);
 566           //polygon_90_set_data<coordinate_type> pstest;
 567           //pstest.insert(begin_input2, end_input, orient_);
 568           //psref.shrink2(west_shrinking, east_shrinking, south_shrinking, north_shrinking);
 569           //if(!equivalence(psref, pstest)) {
 570           //  std::cout << "test failed\n";
 571           //}
 572           for(typename std::list<polygon_45_data<coordinate_type> >::iterator itrh = (*itr).holes_.begin();
 573               itrh != (*itr).holes_.end(); ++itrh) {
 574             //rectangle_data<coordinate_type> rect;
 575             //psref.extents(rect);
 576             //polygon_90_set_data<coordinate_type> psrefhole;
 577             //psrefhole.insert(prerect);
 578             //psrefhole.insert(view_as<polygon_90_concept>(*itrh), true);
 579             //polygon_45_data<coordinate_type> testpoly(*itrh);
 580             resize_poly_up((*itrh).coords_, -west_shrinking, -east_shrinking, -south_shrinking, -north_shrinking);
 581             iterator_geometry_to_set<polygon_90_concept, view_of<polygon_90_concept, polygon_45_data<coordinate_type> > >
 582               begin_input2(view_as<polygon_90_concept>(*itrh), LOW, orient_, true, true),
 583               end_input2(view_as<polygon_90_concept>(*itrh), HIGH, orient_, true, true);
 584             insert(begin_input2, end_input2, orient_);
 585             //polygon_90_set_data<coordinate_type> pstesthole;
 586             //pstesthole.insert(rect);
 587             //iterator_geometry_to_set<polygon_90_concept, view_of<polygon_90_concept, polygon_45_data<coordinate_type> > >
 588             //  begin_input2(view_as<polygon_90_concept>(*itrh), LOW, orient_, true, true);
 589             //pstesthole.insert(begin_input2, end_input, orient_);
 590             //psrefhole.shrink2(west_shrinking, east_shrinking, south_shrinking, north_shrinking);
 591             //if(!equivalence(psrefhole, pstesthole)) {
 592             //  std::cout << (winding(testpoly) == CLOCKWISE) << std::endl;
 593             //  std::cout << (winding(*itrh) == CLOCKWISE) << std::endl;
 594             //  polygon_90_set_data<coordinate_type> c(psrefhole);
 595             //  c.clean();
 596             //  polygon_90_set_data<coordinate_type> a(pstesthole);
 597             //  polygon_90_set_data<coordinate_type> b(pstesthole);
 598             //  a.sort();
 599             //  b.clean();
 600             //  std::cout << "test hole failed\n";
 601             //  //std::cout << testpoly << std::endl;
 602             //}
 603           }
 604         }
 605       }
 606       return *this;
 607     }
 608
 609     polygon_90_set_data&
 610     shrink2(typename coordinate_traits<coordinate_type>::unsigned_area_type west_shrinking,
 611             typename coordinate_traits<coordinate_type>::unsigned_area_type east_shrinking,
 612             typename coordinate_traits<coordinate_type>::unsigned_area_type south_shrinking,
 613             typename coordinate_traits<coordinate_type>::unsigned_area_type north_shrinking) {
 614       rectangle_data<coordinate_type> externalBoundary;
 615       if(!extents(externalBoundary)) return *this;
 616       ::boost::polygon::bloat(externalBoundary, 10); //bloat by diferential ammount
 617       //insert a hole that encompasses the data
 618       insert(externalBoundary, true); //note that the set is in a dirty state now
 619       sort();  //does not apply implicit OR operation
 620       std::vector<rectangle_data<coordinate_type> > rects;
 621       rects.reserve(data_.size() / 2);
 622       //begin does not apply implicit or operation, this is a dirty range
 623       form_rectangles(rects, data_.begin(), data_.end(), orient_, rectangle_concept());
 624       clear();
 625       rectangle_data<coordinate_type> convolutionRectangle(interval_data<coordinate_type>(-((coordinate_type)east_shrinking),
 626                                                                                           (coordinate_type)west_shrinking),
 627                                                            interval_data<coordinate_type>(-((coordinate_type)north_shrinking),
 628                                                                                           (coordinate_type)south_shrinking));
 629       for(typename std::vector<rectangle_data<coordinate_type> >::iterator itr = rects.begin();
 630           itr != rects.end(); ++itr) {
 631         rectangle_data<coordinate_type>& rect = *itr;
 632         convolve(rect, convolutionRectangle);
 633         //insert rectangle as a hole
 634         insert(rect, true);
 635       }
 636       convolve(externalBoundary, convolutionRectangle);
 637       //insert duplicate of external boundary as solid to cancel out the external hole boundaries
 638       insert(externalBoundary);
 639       clean(); //we have negative values in the set, so we need to apply an OR operation to make it valid input to a boolean
 640       return *this;
 641     }
 642
 643     polygon_90_set_data&
 644     shrink(direction_2d dir, typename coordinate_traits<coordinate_type>::unsigned_area_type shrinking) {
 645       if(dir == WEST)
 646         return shrink(shrinking, 0, 0, 0);
 647       if(dir == EAST)
 648         return shrink(0, shrinking, 0, 0);
 649       if(dir == SOUTH)
 650         return shrink(0, 0, shrinking, 0);
 651       return shrink(0, 0, 0, shrinking);
 652     }
 653
 654     polygon_90_set_data&
 655     bloat(direction_2d dir, typename coordinate_traits<coordinate_type>::unsigned_area_type shrinking) {
 656       if(dir == WEST)
 657         return bloat(shrinking, 0, 0, 0);
 658       if(dir == EAST)
 659         return bloat(0, shrinking, 0, 0);
 660       if(dir == SOUTH)
 661         return bloat(0, 0, shrinking, 0);
 662       return bloat(0, 0, 0, shrinking);
 663     }
 664
 665     polygon_90_set_data&
 666     resize(coordinate_type west, coordinate_type east, coordinate_type south, coordinate_type north);
 667
 668     polygon_90_set_data& move(coordinate_type x_delta, coordinate_type y_delta) {
 669       for(typename std::vector<std::pair<coordinate_type, std::pair<coordinate_type, int> > >::iterator
 670             itr = data_.begin(); itr != data_.end(); ++itr) {
 671         if(orient_ == orientation_2d(VERTICAL)) {
 672           (*itr).first += x_delta;
 673           (*itr).second.first += y_delta;
 674         } else {
 675           (*itr).second.first += x_delta;
 676           (*itr).first += y_delta;
 677         }
 678       }
 679       return *this;
 680     }
 681
 682     // transform set
 683     template <typename transformation_type>
 684     polygon_90_set_data& transform(const transformation_type& transformation) {
 685       direction_2d dir1, dir2;
 686       transformation.get_directions(dir1, dir2);
 687       int sign = dir1.get_sign() * dir2.get_sign();
 688       for(typename std::vector<std::pair<coordinate_type, std::pair<coordinate_type, int> > >::iterator
 689             itr = data_.begin(); itr != data_.end(); ++itr) {
 690         if(orient_ == orientation_2d(VERTICAL)) {
 691           transformation.transform((*itr).first, (*itr).second.first);
 692         } else {
 693           transformation.transform((*itr).second.first, (*itr).first);
 694         }
 695         (*itr).second.second *= sign;
 696       }
 697       if(dir1 != EAST || dir2 != NORTH)
 698         unsorted_ = true; //some mirroring or rotation must have happened
 699       return *this;
 700     }
 701
 702     // scale set
 703     polygon_90_set_data& scale_up(typename coordinate_traits<coordinate_type>::unsigned_area_type factor) {
 704       for(typename std::vector<std::pair<coordinate_type, std::pair<coordinate_type, int> > >::iterator
 705             itr = data_.begin(); itr != data_.end(); ++itr) {
 706         (*itr).first *= (coordinate_type)factor;
 707         (*itr).second.first *= (coordinate_type)factor;
 708       }
 709       return *this;
 710     }
 711     polygon_90_set_data& scale_down(typename coordinate_traits<coordinate_type>::unsigned_area_type factor) {
 712       typedef typename coordinate_traits<coordinate_type>::coordinate_distance dt;
 713       for(typename std::vector<std::pair<coordinate_type, std::pair<coordinate_type, int> > >::iterator
 714             itr = data_.begin(); itr != data_.end(); ++itr) {
 715         (*itr).first = scaling_policy<coordinate_type>::round((dt)((*itr).first) / (dt)factor);
 716         (*itr).second.first = scaling_policy<coordinate_type>::round((dt)((*itr).second.first) / (dt)factor);
 717       }
 718       unsorted_ = true; //scaling down can make coordinates equal that were not previously equal
 719       return *this;
 720     }
 721     template <typename scaling_type>
 722     polygon_90_set_data& scale(const anisotropic_scale_factor<scaling_type>& scaling) {
 723       for(typename std::vector<std::pair<coordinate_type, std::pair<coordinate_type, int> > >::iterator
 724             itr = data_.begin(); itr != data_.end(); ++itr) {
 725         if(orient_ == orientation_2d(VERTICAL)) {
 726           scaling.scale((*itr).first, (*itr).second.first);
 727         } else {
 728           scaling.scale((*itr).second.first, (*itr).first);
 729         }
 730       }
 731       unsorted_ = true;
 732       return *this;
 733     }
 734     template <typename scaling_type>
 735     polygon_90_set_data& scale_with(const scaling_type& scaling) {
 736       for(typename std::vector<std::pair<coordinate_type, std::pair<coordinate_type, int> > >::iterator
 737             itr = data_.begin(); itr != data_.end(); ++itr) {
 738         if(orient_ == orientation_2d(VERTICAL)) {
 739           scaling.scale((*itr).first, (*itr).second.first);
 740         } else {
 741           scaling.scale((*itr).second.first, (*itr).first);
 742         }
 743       }
 744       unsorted_ = true;
 745       return *this;
 746     }
 747     polygon_90_set_data& scale(double factor) {
 748       typedef typename coordinate_traits<coordinate_type>::coordinate_distance dt;
 749       for(typename std::vector<std::pair<coordinate_type, std::pair<coordinate_type, int> > >::iterator
 750             itr = data_.begin(); itr != data_.end(); ++itr) {
 751         (*itr).first = scaling_policy<coordinate_type>::round((dt)((*itr).first) * (dt)factor);
 752         (*itr).second.first = scaling_policy<coordinate_type>::round((dt)((*itr).second.first) * (dt)factor);
 753       }
 754       unsorted_ = true; //scaling make coordinates equal that were not previously equal
 755       return *this;
 756     }
 757
 758     polygon_90_set_data& self_xor() {
 759       sort();
 760       if(dirty_) { //if it is clean it is a no-op
 761         boolean_op::default_arg_workaround<boolean_op::UnaryCount>::applyBooleanOr(data_);
 762         dirty_ = false;
 763       }
 764       return *this;
 765     }
 766
 767     polygon_90_set_data& self_intersect() {
 768       sort();
 769       if(dirty_) { //if it is clean it is a no-op
 770         interval_data<coordinate_type> ivl((std::numeric_limits<coordinate_type>::min)(), (std::numeric_limits<coordinate_type>::max)());
 771         rectangle_data<coordinate_type> rect(ivl, ivl);
 772         insert(rect, true);
 773         clean();
 774       }
 775       return *this;
 776     }
 777
 778     inline polygon_90_set_data& interact(const polygon_90_set_data& that) {
 779       typedef coordinate_type Unit;
 780       if(that.dirty_) that.clean();
 781       typename touch_90_operation<Unit>::TouchSetData tsd;
 782       touch_90_operation<Unit>::populateTouchSetData(tsd, that.data_, 0);
 783       std::vector<polygon_90_data<Unit> > polys;
 784       get(polys);
 785       std::vector<std::set<int> > graph(polys.size()+1, std::set<int>());
 786       for(std::size_t i = 0; i < polys.size(); ++i){
 787         polygon_90_set_data<Unit> psTmp(that.orient_);
 788         psTmp.insert(polys[i]);
 789         psTmp.clean();
 790         touch_90_operation<Unit>::populateTouchSetData(tsd, psTmp.data_, i+1);
 791       }
 792       touch_90_operation<Unit>::performTouch(graph, tsd);
 793       clear();
 794       for(std::set<int>::iterator itr = graph[0].begin(); itr != graph[0].end(); ++itr){
 795         insert(polys[(*itr)-1]);
 796       }
 797       dirty_ = false;
 798       return *this;
 799     }
 800
 801
 802     template <class T2, typename iterator_type_1, typename iterator_type_2>
 803     void applyBooleanBinaryOp(iterator_type_1 itr1, iterator_type_1 itr1_end,
 804                               iterator_type_2 itr2, iterator_type_2 itr2_end,
 805                               T2 defaultCount) {
 806       data_.clear();
 807       boolean_op::applyBooleanBinaryOp(data_, itr1, itr1_end, itr2, itr2_end, defaultCount);
 808     }
 809
 810   private:
 811     orientation_2d orient_;
 812     mutable value_type data_;
 813     mutable bool dirty_;
 814     mutable bool unsorted_;
 815
 816   private:
 817     //functions
 818     template <typename output_container>
 819     void get_dispatch(output_container& output, rectangle_concept ) const {
 820       clean();
 821       form_rectangles(output, data_.begin(), data_.end(), orient_, rectangle_concept());
 822     }
 823     template <typename output_container>
 824     void get_dispatch(output_container& output, polygon_90_concept tag) const {
 825       get_fracture(output, true, tag);
 826     }
 827     template <typename output_container>
 828     void get_dispatch(output_container& output, polygon_90_with_holes_concept tag) const {
 829       get_fracture(output, false, tag);
 830     }
 831     template <typename output_container>
 832     void get_dispatch(output_container& output, polygon_45_concept tag) const {
 833       get_fracture(output, true, tag);
 834     }
 835     template <typename output_container>
 836     void get_dispatch(output_container& output, polygon_45_with_holes_concept tag) const {
 837       get_fracture(output, false, tag);
 838     }
 839     template <typename output_container>
 840     void get_dispatch(output_container& output, polygon_concept tag) const {
 841       get_fracture(output, true, tag);
 842     }
 843     template <typename output_container>
 844     void get_dispatch(output_container& output, polygon_with_holes_concept tag) const {
 845       get_fracture(output, false, tag);
 846     }
 847     template <typename output_container, typename concept_type>
 848     void get_fracture(output_container& container, bool fracture_holes, concept_type tag) const {
 849       clean();
 850       ::boost::polygon::get_polygons(container, data_.begin(), data_.end(), orient_, fracture_holes, tag);
 851     }
 852   };
 853
 854   template <typename coordinate_type>
 855   polygon_90_set_data<coordinate_type>&
 856   polygon_90_set_data<coordinate_type>::resize(coordinate_type west,
 857                                                coordinate_type east,
 858                                                coordinate_type south,
 859                                                coordinate_type north) {
 860     move(-west, -south);
 861     coordinate_type e_total = west + east;
 862     coordinate_type n_total = south + north;
 863     if((e_total < 0) ^ (n_total < 0)) {
 864       //different signs
 865       if(e_total < 0) {
 866         shrink(0, -e_total, 0, 0);
 867         if(n_total != 0)
 868           return bloat(0, 0, 0, n_total);
 869         else
 870           return (*this);
 871       } else {
 872         shrink(0, 0, 0, -n_total); //shrink first
 873         if(e_total != 0)
 874           return bloat(0, e_total, 0, 0);
 875         else
 876           return (*this);
 877       }
 878     } else {
 879       if(e_total < 0) {
 880         return shrink(0, -e_total, 0, -n_total);
 881       }
 882       return bloat(0, e_total, 0, n_total);
 883     }
 884   }
 885
 886   template <typename coordinate_type, typename property_type>
 887   class property_merge_90 {
 888   private:
 889     std::vector<std::pair<property_merge_point<coordinate_type>, std::pair<property_type, int> > > pmd_;
 890   public:
 891     inline property_merge_90() : pmd_() {}
 892     inline property_merge_90(const property_merge_90& that) : pmd_(that.pmd_) {}
 893     inline property_merge_90& operator=(const property_merge_90& that) { pmd_ = that.pmd_; return *this; }
 894     inline void insert(const polygon_90_set_data<coordinate_type>& ps, const property_type& property) {
 895       merge_scanline<coordinate_type, property_type, polygon_90_set_data<coordinate_type> >::
 896         populate_property_merge_data(pmd_, ps.begin(), ps.end(), property, ps.orient());
 897     }
 898     template <class GeoObjT>
 899     inline void insert(const GeoObjT& geoObj, const property_type& property) {
 900       polygon_90_set_data<coordinate_type> ps;
 901       ps.insert(geoObj);
 902       insert(ps, property);
 903     }
 904     //merge properties of input geometries and store the resulting geometries of regions
 905     //with unique sets of merged properties to polygons sets in a map keyed by sets of properties
 906     // T = std::map<std::set<property_type>, polygon_90_set_data<coordiante_type> > or
 907     // T = std::map<std::vector<property_type>, polygon_90_set_data<coordiante_type> >
 908     template <typename ResultType>
 909     inline void merge(ResultType& result) {
 910       merge_scanline<coordinate_type, property_type, polygon_90_set_data<coordinate_type>, typename ResultType::key_type> ms;
 911       ms.perform_merge(result, pmd_);
 912     }
 913   };
 914
 915   //ConnectivityExtraction computes the graph of connectivity between rectangle, polygon and
 916   //polygon set graph nodes where an edge is created whenever the geometry in two nodes overlap
 917   template <typename coordinate_type>
 918   class connectivity_extraction_90 {
 919   private:
 920     typedef typename touch_90_operation<coordinate_type>::TouchSetData tsd;
 921     tsd tsd_;
 922     unsigned int nodeCount_;
 923   public:
 924     inline connectivity_extraction_90() : tsd_(), nodeCount_(0) {}
 925     inline connectivity_extraction_90(const connectivity_extraction_90& that) : tsd_(that.tsd_),
 926                                                                           nodeCount_(that.nodeCount_) {}
 927     inline connectivity_extraction_90& operator=(const connectivity_extraction_90& that) {
 928       tsd_ = that.tsd_;
 929       nodeCount_ = that.nodeCount_; {}
 930       return *this;
 931     }
 932
 933     //insert a polygon set graph node, the value returned is the id of the graph node
 934     inline unsigned int insert(const polygon_90_set_data<coordinate_type>& ps) {
 935       ps.clean();
 936       touch_90_operation<coordinate_type>::populateTouchSetData(tsd_, ps.begin(), ps.end(), nodeCount_);
 937       return nodeCount_++;
 938     }
 939     template <class GeoObjT>
 940     inline unsigned int insert(const GeoObjT& geoObj) {
 941       polygon_90_set_data<coordinate_type> ps;
 942       ps.insert(geoObj);
 943       return insert(ps);
 944     }
 945
 946     //extract connectivity and store the edges in the graph
 947     //graph must be indexable by graph node id and the indexed value must be a std::set of
 948     //graph node id
 949     template <class GraphT>
 950     inline void extract(GraphT& graph) {
 951       touch_90_operation<coordinate_type>::performTouch(graph, tsd_);
 952     }
 953   };
 954 }
 955 }
 956 #endif
 957