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