boost/polygon/polygon_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_SET_DATA_HPP
   9 #define BOOST_POLYGON_POLYGON_SET_DATA_HPP
  10 #include "polygon_45_set_data.hpp"
  11 #include "polygon_45_set_concept.hpp"
  12 #include "polygon_traits.hpp"
  13 #include "detail/polygon_arbitrary_formation.hpp"
  14 #include <iostream>
  15
  16 namespace boost { namespace polygon {
  17
  18
  19   // utility function to round coordinate types down
  20   // rounds down for both negative and positive numbers
  21   // intended really for integer type T (does not make sense for float)
  22   template <typename T>
  23   static inline T round_down(double val) {
  24      T rounded_val = (T)(val);
  25      if(val < (double)rounded_val)
  26         --rounded_val;
  27      return rounded_val;
  28   }
  29   template <typename T>
  30   static inline point_data<T> round_down(point_data<double> v) {
  31      return point_data<T>(round_down<T>(v.x()),round_down<T>(v.y()));
  32   }
  33
  34
  35
  36   //foward declare view
  37   template <typename ltype, typename rtype, int op_type> class polygon_set_view;
  38
  39   template <typename T>
  40   class polygon_set_data {
  41   public:
  42     typedef T coordinate_type;
  43     typedef point_data<T> point_type;
  44     typedef std::pair<point_type, point_type> edge_type;
  45     typedef std::pair<edge_type, int> element_type;
  46     typedef std::vector<element_type> value_type;
  47     typedef typename value_type::const_iterator iterator_type;
  48     typedef polygon_set_data operator_arg_type;
  49
  50     // default constructor
  51     inline polygon_set_data() : data_(), dirty_(false), unsorted_(false), is_45_(true) {}
  52
  53     // constructor from an iterator pair over edge data
  54     template <typename iT>
  55     inline polygon_set_data(iT input_begin, iT input_end) : data_(), dirty_(false), unsorted_(false), is_45_(true) {
  56       for( ; input_begin != input_end; ++input_begin) { insert(*input_begin); }
  57     }
  58
  59     // copy constructor
  60     inline polygon_set_data(const polygon_set_data& that) :
  61       data_(that.data_), dirty_(that.dirty_), unsorted_(that.unsorted_), is_45_(that.is_45_) {}
  62
  63     // copy constructor
  64     template <typename ltype, typename rtype, int op_type>
  65     inline polygon_set_data(const polygon_set_view<ltype, rtype, op_type>& that);
  66
  67     // destructor
  68     inline ~polygon_set_data() {}
  69
  70     // assignement operator
  71     inline polygon_set_data& operator=(const polygon_set_data& that) {
  72       if(this == &that) return *this;
  73       data_ = that.data_;
  74       dirty_ = that.dirty_;
  75       unsorted_ = that.unsorted_;
  76       is_45_ = that.is_45_;
  77       return *this;
  78     }
  79
  80     template <typename ltype, typename rtype, int op_type>
  81     inline polygon_set_data& operator=(const polygon_set_view<ltype, rtype, op_type>& geometry) {
  82       (*this) = geometry.value();
  83       dirty_ = false;
  84       unsorted_ = false;
  85       return *this;
  86     }
  87
  88     template <typename geometry_object>
  89     inline polygon_set_data& operator=(const geometry_object& geometry) {
  90       data_.clear();
  91       insert(geometry);
  92       return *this;
  93     }
  94
  95
  96     // insert iterator range
  97     inline void insert(iterator_type input_begin, iterator_type input_end, bool is_hole = false) {
  98       if(input_begin == input_end || (!data_.empty() && &(*input_begin) == &(*(data_.begin())))) return;
  99       dirty_ = true;
 100       unsorted_ = true;
 101       while(input_begin != input_end) {
 102         insert(*input_begin, is_hole);
 103         ++input_begin;
 104       }
 105     }
 106
 107     // insert iterator range
 108     template <typename iT>
 109     inline void insert(iT input_begin, iT input_end, bool is_hole = false) {
 110       if(input_begin == input_end) return;
 111       for(; input_begin != input_end; ++input_begin) {
 112         insert(*input_begin, is_hole);
 113       }
 114     }
 115
 116     template <typename geometry_type>
 117     inline void insert(const geometry_type& geometry_object, bool is_hole = false) {
 118       insert(geometry_object, is_hole, typename geometry_concept<geometry_type>::type());
 119     }
 120
 121     template <typename polygon_type>
 122     inline void insert(const polygon_type& polygon_object, bool is_hole, polygon_concept ) {
 123       insert_vertex_sequence(begin_points(polygon_object), end_points(polygon_object), winding(polygon_object), is_hole);
 124     }
 125
 126     inline void insert(const polygon_set_data& ps, bool is_hole = false) {
 127       insert(ps.data_.begin(), ps.data_.end(), is_hole);
 128     }
 129
 130     template <typename polygon_45_set_type>
 131     inline void insert(const polygon_45_set_type& ps, bool is_hole, polygon_45_set_concept) {
 132       std::vector<polygon_45_with_holes_data<typename polygon_45_set_traits<polygon_45_set_type>::coordinate_type> > polys;
 133       assign(polys, ps);
 134       insert(polys.begin(), polys.end(), is_hole);
 135     }
 136
 137     template <typename polygon_90_set_type>
 138     inline void insert(const polygon_90_set_type& ps, bool is_hole, polygon_90_set_concept) {
 139       std::vector<polygon_90_with_holes_data<typename polygon_90_set_traits<polygon_90_set_type>::coordinate_type> > polys;
 140       assign(polys, ps);
 141       insert(polys.begin(), polys.end(), is_hole);
 142     }
 143
 144     template <typename polygon_type>
 145     inline void insert(const polygon_type& polygon_object, bool is_hole, polygon_45_concept ) {
 146       insert(polygon_object, is_hole, polygon_concept()); }
 147
 148     template <typename polygon_type>
 149     inline void insert(const polygon_type& polygon_object, bool is_hole, polygon_90_concept ) {
 150       insert(polygon_object, is_hole, polygon_concept()); }
 151
 152     template <typename polygon_with_holes_type>
 153     inline void insert(const polygon_with_holes_type& polygon_with_holes_object, bool is_hole,
 154                        polygon_with_holes_concept ) {
 155       insert(polygon_with_holes_object, is_hole, polygon_concept());
 156       for(typename polygon_with_holes_traits<polygon_with_holes_type>::iterator_holes_type itr =
 157             begin_holes(polygon_with_holes_object);
 158           itr != end_holes(polygon_with_holes_object); ++itr) {
 159         insert(*itr, !is_hole, polygon_concept());
 160       }
 161     }
 162
 163     template <typename polygon_with_holes_type>
 164     inline void insert(const polygon_with_holes_type& polygon_with_holes_object, bool is_hole,
 165                        polygon_45_with_holes_concept ) {
 166       insert(polygon_with_holes_object, is_hole, polygon_with_holes_concept()); }
 167
 168     template <typename polygon_with_holes_type>
 169     inline void insert(const polygon_with_holes_type& polygon_with_holes_object, bool is_hole,
 170                        polygon_90_with_holes_concept ) {
 171       insert(polygon_with_holes_object, is_hole, polygon_with_holes_concept()); }
 172
 173     template <typename rectangle_type>
 174     inline void insert(const rectangle_type& rectangle_object, bool is_hole, rectangle_concept ) {
 175       polygon_90_data<coordinate_type> poly;
 176       assign(poly, rectangle_object);
 177       insert(poly, is_hole, polygon_concept());
 178     }
 179
 180     inline void insert_clean(const element_type& edge, bool is_hole = false) {
 181       if( ! scanline_base<coordinate_type>::is_45_degree(edge.first) &&
 182           ! scanline_base<coordinate_type>::is_horizontal(edge.first) &&
 183           ! scanline_base<coordinate_type>::is_vertical(edge.first) ) is_45_ = false;
 184       data_.push_back(edge);
 185       if(data_.back().first.second < data_.back().first.first) {
 186         std::swap(data_.back().first.second, data_.back().first.first);
 187         data_.back().second *= -1;
 188       }
 189       if(is_hole)
 190         data_.back().second *= -1;
 191     }
 192
 193     inline void insert(const element_type& edge, bool is_hole = false) {
 194       insert_clean(edge, is_hole);
 195       dirty_ = true;
 196       unsorted_ = true;
 197     }
 198
 199     template <class iT>
 200     inline void insert_vertex_sequence(iT begin_vertex, iT end_vertex, direction_1d winding, bool is_hole) {
 201       bool first_iteration = true;
 202       point_type first_point;
 203       point_type previous_point;
 204       point_type current_point;
 205       direction_1d winding_dir = winding;
 206       int multiplier = winding_dir == COUNTERCLOCKWISE ? 1 : -1;
 207       if(is_hole) multiplier *= -1;
 208       for( ; begin_vertex != end_vertex; ++begin_vertex) {
 209         assign(current_point, *begin_vertex);
 210         if(first_iteration) {
 211           first_iteration = false;
 212           first_point = previous_point = current_point;
 213         } else {
 214           if(previous_point != current_point) {
 215             element_type elem(edge_type(previous_point, current_point),
 216                               ( previous_point.get(HORIZONTAL) == current_point.get(HORIZONTAL) ? -1 : 1) * multiplier);
 217             insert_clean(elem);
 218           }
 219         }
 220         previous_point = current_point;
 221       }
 222       current_point = first_point;
 223       if(!first_iteration) {
 224         if(previous_point != current_point) {
 225           element_type elem(edge_type(previous_point, current_point),
 226                             ( previous_point.get(HORIZONTAL) == current_point.get(HORIZONTAL) ? -1 : 1) * multiplier);
 227           insert_clean(elem);
 228         }
 229         dirty_ = true;
 230         unsorted_ = true;
 231       }
 232     }
 233
 234     template <typename output_container>
 235     inline void get(output_container& output) const {
 236       get_dispatch(output, typename geometry_concept<typename output_container::value_type>::type());
 237     }
 238
 239     // append to the container cT with polygons of three or four verticies
 240     // slicing orientation is vertical
 241     template <class cT>
 242     void get_trapezoids(cT& container) const {
 243       clean();
 244       trapezoid_arbitrary_formation<coordinate_type> pf;
 245       typedef typename polygon_arbitrary_formation<coordinate_type>::vertex_half_edge vertex_half_edge;
 246       std::vector<vertex_half_edge> data;
 247       for(iterator_type itr = data_.begin(); itr != data_.end(); ++itr){
 248         data.push_back(vertex_half_edge((*itr).first.first, (*itr).first.second, (*itr).second));
 249         data.push_back(vertex_half_edge((*itr).first.second, (*itr).first.first, -1 * (*itr).second));
 250       }
 251       gtlsort(data.begin(), data.end());
 252       pf.scan(container, data.begin(), data.end());
 253       //std::cout << "DONE FORMING POLYGONS\n";
 254     }
 255
 256     // append to the container cT with polygons of three or four verticies
 257     template <class cT>
 258     void get_trapezoids(cT& container, orientation_2d slicing_orientation) const {
 259       if(slicing_orientation == VERTICAL) {
 260         get_trapezoids(container);
 261       } else {
 262         polygon_set_data<T> ps(*this);
 263         ps.transform(axis_transformation(axis_transformation::SWAP_XY));
 264         cT result;
 265         ps.get_trapezoids(result);
 266         for(typename cT::iterator itr = result.begin(); itr != result.end(); ++itr) {
 267           ::boost::polygon::transform(*itr, axis_transformation(axis_transformation::SWAP_XY));
 268         }
 269         container.insert(container.end(), result.begin(), result.end());
 270       }
 271     }
 272
 273     // equivalence operator
 274     inline bool operator==(const polygon_set_data& p) const {
 275       clean();
 276       p.clean();
 277       return data_ == p.data_;
 278     }
 279
 280     // inequivalence operator
 281     inline bool operator!=(const polygon_set_data& p) const {
 282       return !((*this) == p);
 283     }
 284
 285     // get iterator to begin vertex data
 286     inline iterator_type begin() const {
 287       return data_.begin();
 288     }
 289
 290     // get iterator to end vertex data
 291     inline iterator_type end() const {
 292       return data_.end();
 293     }
 294
 295     const value_type& value() const {
 296       return data_;
 297     }
 298
 299     // clear the contents of the polygon_set_data
 300     inline void clear() { data_.clear(); dirty_ = unsorted_ = false; }
 301
 302     // find out if Polygon set is empty
 303     inline bool empty() const { return data_.empty(); }
 304
 305     // get the Polygon set size in vertices
 306     inline std::size_t size() const { clean(); return data_.size(); }
 307
 308     // get the current Polygon set capacity in vertices
 309     inline std::size_t capacity() const { return data_.capacity(); }
 310
 311     // reserve size of polygon set in vertices
 312     inline void reserve(std::size_t size) { return data_.reserve(size); }
 313
 314     // find out if Polygon set is sorted
 315     inline bool sorted() const { return !unsorted_; }
 316
 317     // find out if Polygon set is clean
 318     inline bool dirty() const { return dirty_; }
 319
 320     void clean() const;
 321
 322     void sort() const{
 323       if(unsorted_) {
 324         gtlsort(data_.begin(), data_.end());
 325         unsorted_ = false;
 326       }
 327     }
 328
 329     template <typename input_iterator_type>
 330     void set(input_iterator_type input_begin, input_iterator_type input_end) {
 331       clear();
 332       insert(input_begin, input_end);
 333       dirty_ = true;
 334       unsorted_ = true;
 335     }
 336
 337     void set(const value_type& value) {
 338       data_ = value;
 339       dirty_ = true;
 340       unsorted_ = true;
 341     }
 342
 343     template <typename rectangle_type>
 344     bool extents(rectangle_type& rect) {
 345       clean();
 346       if(empty()) return false;
 347       bool first_iteration = true;
 348       for(iterator_type itr = begin();
 349           itr != end(); ++itr) {
 350         rectangle_type edge_box;
 351         set_points(edge_box, (*itr).first.first, (*itr).first.second);
 352         if(first_iteration)
 353           rect = edge_box;
 354         else
 355           encompass(rect, edge_box);
 356         first_iteration = false;
 357       }
 358       return true;
 359     }
 360
 361     inline polygon_set_data&
 362     resize(coordinate_type resizing, bool corner_fill_arc = false, unsigned int num_circle_segments=0);
 363
 364     template <typename transform_type>
 365     inline polygon_set_data&
 366     transform(const transform_type& tr) {
 367       std::vector<polygon_with_holes_data<T> > polys;
 368       get(polys);
 369       clear();
 370       for(std::size_t i = 0 ; i < polys.size(); ++i) {
 371         ::boost::polygon::transform(polys[i], tr);
 372         insert(polys[i]);
 373       }
 374       unsorted_ = true;
 375       dirty_ = true;
 376       return *this;
 377     }
 378
 379     inline polygon_set_data&
 380     scale_up(typename coordinate_traits<coordinate_type>::unsigned_area_type factor) {
 381       for(typename value_type::iterator itr = data_.begin(); itr != data_.end(); ++itr) {
 382         ::boost::polygon::scale_up((*itr).first.first, factor);
 383         ::boost::polygon::scale_up((*itr).first.second, factor);
 384       }
 385       return *this;
 386     }
 387
 388     inline polygon_set_data&
 389     scale_down(typename coordinate_traits<coordinate_type>::unsigned_area_type factor) {
 390       for(typename value_type::iterator itr = data_.begin(); itr != data_.end(); ++itr) {
 391         ::boost::polygon::scale_down((*itr).first.first, factor);
 392         ::boost::polygon::scale_down((*itr).first.second, factor);
 393       }
 394       unsorted_ = true;
 395       dirty_ = true;
 396       return *this;
 397     }
 398
 399     template <typename scaling_type>
 400     inline polygon_set_data& scale(polygon_set_data& polygon_set,
 401                                    const scaling_type& scaling) {
 402       for(typename value_type::iterator itr = begin(); itr != end(); ++itr) {
 403         ::boost::polygon::scale((*itr).first.first, scaling);
 404         ::boost::polygon::scale((*itr).first.second, scaling);
 405       }
 406       unsorted_ = true;
 407       dirty_ = true;
 408       return *this;
 409     }
 410
 411     static inline void compute_offset_edge(point_data<long double>& pt1, point_data<long double>& pt2,
 412                                            const point_data<long double>&  prev_pt,
 413                                            const point_data<long double>&  current_pt,
 414                                            long double distance, int multiplier) {
 415       long double dx = current_pt.x() - prev_pt.x();
 416       long double dy = current_pt.y() - prev_pt.y();
 417       long double edge_length = std::sqrt(dx*dx + dy*dy);
 418       long double dnx = dy;
 419       long double dny = -dx;
 420       dnx = dnx * (long double)distance / edge_length;
 421       dny = dny * (long double)distance / edge_length;
 422       pt1.x(prev_pt.x() + (long double)dnx * (long double)multiplier);
 423       pt2.x(current_pt.x() + (long double)dnx * (long double)multiplier);
 424       pt1.y(prev_pt.y() + (long double)dny * (long double)multiplier);
 425       pt2.y(current_pt.y() + (long double)dny * (long double)multiplier);
 426     }
 427
 428     static inline void modify_pt(point_data<coordinate_type>& pt, const point_data<coordinate_type>&  prev_pt,
 429                                  const point_data<coordinate_type>&  current_pt,  const point_data<coordinate_type>&  next_pt,
 430                                  coordinate_type distance, coordinate_type multiplier) {
 431       std::pair<point_data<long double>, point_data<long double> > he1, he2;
 432       he1.first.x((long double)(prev_pt.x()));
 433       he1.first.y((long double)(prev_pt.y()));
 434       he1.second.x((long double)(current_pt.x()));
 435       he1.second.y((long double)(current_pt.y()));
 436       he2.first.x((long double)(current_pt.x()));
 437       he2.first.y((long double)(current_pt.y()));
 438       he2.second.x((long double)(next_pt.x()));
 439       he2.second.y((long double)(next_pt.y()));
 440       compute_offset_edge(he1.first, he1.second, prev_pt, current_pt, distance, multiplier);
 441       compute_offset_edge(he2.first, he2.second, current_pt, next_pt, distance, multiplier);
 442       typename scanline_base<long double>::compute_intersection_pack pack;
 443       point_data<long double> rpt;
 444       point_data<long double> bisectorpt((he1.second.x()+he2.first.x())/2,
 445                                          (he1.second.y()+he2.first.y())/2);
 446       point_data<long double> orig_pt((long double)pt.x(), (long double)pt.y());
 447       if(euclidean_distance(bisectorpt, orig_pt) < distance/2) {
 448         if(!pack.compute_lazy_intersection(rpt, he1, he2, true, false)) {
 449           rpt = he1.second; //colinear offset edges use shared point
 450         }
 451       } else {
 452         if(!pack.compute_lazy_intersection(rpt, he1, std::pair<point_data<long double>, point_data<long double> >(orig_pt, bisectorpt), true, false)) {
 453           rpt = he1.second; //colinear offset edges use shared point
 454         }
 455       }
 456       pt.x((coordinate_type)(std::floor(rpt.x()+0.5)));
 457       pt.y((coordinate_type)(std::floor(rpt.y()+0.5)));
 458     }
 459
 460     static void resize_poly_up(std::vector<point_data<coordinate_type> >& poly, coordinate_type distance, coordinate_type multiplier) {
 461       point_data<coordinate_type> first_pt = poly[0];
 462       point_data<coordinate_type> second_pt = poly[1];
 463       point_data<coordinate_type> prev_pt = poly[0];
 464       point_data<coordinate_type> current_pt = poly[1];
 465       for(std::size_t i = 2; i < poly.size()-1; ++i) {
 466         point_data<coordinate_type> next_pt = poly[i];
 467         modify_pt(poly[i-1], prev_pt, current_pt, next_pt, distance, multiplier);
 468         prev_pt = current_pt;
 469         current_pt = next_pt;
 470       }
 471       point_data<coordinate_type> next_pt = first_pt;
 472       modify_pt(poly[poly.size()-2], prev_pt, current_pt, next_pt, distance, multiplier);
 473       prev_pt = current_pt;
 474       current_pt = next_pt;
 475       next_pt = second_pt;
 476       modify_pt(poly[0], prev_pt, current_pt, next_pt, distance, multiplier);
 477       poly.back() = poly.front();
 478     }
 479     static bool resize_poly_down(std::vector<point_data<coordinate_type> >& poly, coordinate_type distance, coordinate_type multiplier) {
 480       std::vector<point_data<coordinate_type> > orig_poly(poly);
 481       rectangle_data<coordinate_type> extents_rectangle;
 482       set_points(extents_rectangle, poly[0], poly[0]);
 483       point_data<coordinate_type> first_pt = poly[0];
 484       point_data<coordinate_type> second_pt = poly[1];
 485       point_data<coordinate_type> prev_pt = poly[0];
 486       point_data<coordinate_type> current_pt = poly[1];
 487       encompass(extents_rectangle, current_pt);
 488       for(std::size_t i = 2; i < poly.size()-1; ++i) {
 489         point_data<coordinate_type> next_pt = poly[i];
 490         encompass(extents_rectangle, next_pt);
 491         modify_pt(poly[i-1], prev_pt, current_pt, next_pt, distance, multiplier);
 492         prev_pt = current_pt;
 493         current_pt = next_pt;
 494       }
 495       if(delta(extents_rectangle, HORIZONTAL) <= std::abs(2*distance))
 496         return false;
 497       if(delta(extents_rectangle, VERTICAL) <= std::abs(2*distance))
 498         return false;
 499       point_data<coordinate_type> next_pt = first_pt;
 500       modify_pt(poly[poly.size()-2], prev_pt, current_pt, next_pt, distance, multiplier);
 501       prev_pt = current_pt;
 502       current_pt = next_pt;
 503       next_pt = second_pt;
 504       modify_pt(poly[0], prev_pt, current_pt, next_pt, distance, multiplier);
 505       poly.back() = poly.front();
 506       //if the line segments formed between orignial and new points cross for an edge that edge inverts
 507       //if all edges invert the polygon should be discarded
 508       //if even one edge does not invert return true because the polygon is valid
 509       bool non_inverting_edge = false;
 510       for(std::size_t i = 1; i < poly.size(); ++i) {
 511         std::pair<point_data<coordinate_type>, point_data<coordinate_type> >
 512           he1(poly[i], orig_poly[i]),
 513           he2(poly[i-1], orig_poly[i-1]);
 514         if(!scanline_base<coordinate_type>::intersects(he1, he2)) {
 515           non_inverting_edge = true;
 516           break;
 517         }
 518       }
 519       return non_inverting_edge;
 520     }
 521
 522     polygon_set_data&
 523     bloat(typename coordinate_traits<coordinate_type>::unsigned_area_type distance) {
 524       std::list<polygon_with_holes_data<coordinate_type> > polys;
 525       get(polys);
 526       clear();
 527       for(typename std::list<polygon_with_holes_data<coordinate_type> >::iterator itr = polys.begin();
 528           itr != polys.end(); ++itr) {
 529         resize_poly_up((*itr).self_.coords_, (coordinate_type)distance, (coordinate_type)1);
 530         insert_vertex_sequence((*itr).self_.begin(), (*itr).self_.end(), COUNTERCLOCKWISE, false); //inserts without holes
 531         for(typename std::list<polygon_data<coordinate_type> >::iterator itrh = (*itr).holes_.begin();
 532             itrh != (*itr).holes_.end(); ++itrh) {
 533           if(resize_poly_down((*itrh).coords_, (coordinate_type)distance, (coordinate_type)1)) {
 534             insert_vertex_sequence((*itrh).coords_.begin(), (*itrh).coords_.end(), CLOCKWISE, true);
 535           }
 536         }
 537       }
 538       return *this;
 539     }
 540
 541     polygon_set_data&
 542     shrink(typename coordinate_traits<coordinate_type>::unsigned_area_type distance) {
 543       std::list<polygon_with_holes_data<coordinate_type> > polys;
 544       get(polys);
 545       clear();
 546       for(typename std::list<polygon_with_holes_data<coordinate_type> >::iterator itr = polys.begin();
 547           itr != polys.end(); ++itr) {
 548         if(resize_poly_down((*itr).self_.coords_, (coordinate_type)distance, (coordinate_type)-1)) {
 549           insert_vertex_sequence((*itr).self_.begin(), (*itr).self_.end(), COUNTERCLOCKWISE, false); //inserts without holes
 550           for(typename std::list<polygon_data<coordinate_type> >::iterator itrh = (*itr).holes_.begin();
 551               itrh != (*itr).holes_.end(); ++itrh) {
 552             resize_poly_up((*itrh).coords_, (coordinate_type)distance, (coordinate_type)-1);
 553             insert_vertex_sequence((*itrh).coords_.begin(), (*itrh).coords_.end(), CLOCKWISE, true);
 554           }
 555         }
 556       }
 557       return *this;
 558     }
 559
 560     // TODO:: should be private
 561     template <typename geometry_type>
 562     inline polygon_set_data&
 563     insert_with_resize(const geometry_type& poly, coordinate_type resizing, bool corner_fill_arc=false, unsigned int num_circle_segments=0, bool hole = false) {
 564       return insert_with_resize_dispatch(poly, resizing,  corner_fill_arc, num_circle_segments, hole, typename geometry_concept<geometry_type>::type());
 565     }
 566
 567     template <typename geometry_type>
 568     inline polygon_set_data&
 569     insert_with_resize_dispatch(const geometry_type& poly, coordinate_type resizing, bool corner_fill_arc, unsigned int num_circle_segments, bool hole,
 570                                polygon_with_holes_concept tag) {
 571       insert_with_resize_dispatch(poly, resizing, corner_fill_arc, num_circle_segments, hole, polygon_concept());
 572       for(typename polygon_with_holes_traits<geometry_type>::iterator_holes_type itr =
 573             begin_holes(poly); itr != end_holes(poly);
 574           ++itr) {
 575         insert_with_resize_dispatch(*itr, resizing,  corner_fill_arc, num_circle_segments, !hole, polygon_concept());
 576       }
 577       return *this;
 578     }
 579
 580     template <typename geometry_type>
 581     inline polygon_set_data&
 582     insert_with_resize_dispatch(const geometry_type& poly, coordinate_type resizing, bool corner_fill_arc, unsigned int num_circle_segments, bool hole,
 583                           polygon_concept tag) {
 584
 585       if (resizing==0)
 586          return *this;
 587
 588
 589       // one dimensional used to store CCW/CW flag
 590       //direction_1d wdir = winding(poly);
 591       // LOW==CLOCKWISE just faster to type
 592       // so > 0 is CCW
 593       //int multiplier = wdir == LOW ? -1 : 1;
 594       //std::cout<<" multiplier : "<<multiplier<<std::endl;
 595       //if(hole) resizing *= -1;
 596       direction_1d resize_wdir = resizing>0?COUNTERCLOCKWISE:CLOCKWISE;
 597
 598       typedef typename polygon_data<T>::iterator_type piterator;
 599       piterator first, second, third, end, real_end;
 600       real_end = end_points(poly);
 601       third = begin_points(poly);
 602       first = third;
 603       if(first == real_end) return *this;
 604       ++third;
 605       if(third == real_end) return *this;
 606       second = end = third;
 607       ++third;
 608       if(third == real_end) return *this;
 609
 610         // for 1st corner
 611       std::vector<point_data<T> > first_pts;
 612       std::vector<point_data<T> > all_pts;
 613       direction_1d first_wdir = CLOCKWISE;
 614
 615       // for all corners
 616       polygon_set_data<T> sizingSet;
 617       bool sizing_sign = resizing<0;
 618       bool prev_concave = true;
 619       point_data<T> prev_point;
 620       //int iCtr=0;
 621
 622
 623       //insert minkofski shapes on edges and corners
 624       do { // REAL WORK IS HERE
 625
 626
 627         //first, second and third point to points in correct CCW order
 628         // check if convex or concave case
 629         point_data<coordinate_type> normal1( second->y()-first->y(), first->x()-second->x());
 630         point_data<coordinate_type> normal2( third->y()-second->y(), second->x()-third->x());
 631         double direction = normal1.x()*normal2.y()- normal2.x()*normal1.y();
 632         bool convex = direction>0;
 633
 634         bool treat_as_concave = !convex;
 635         if(sizing_sign)
 636           treat_as_concave = convex;
 637         point_data<double> v;
 638         assign(v, normal1);
 639         double s2 = (v.x()*v.x()+v.y()*v.y());
 640         double s = sqrt(s2)/resizing;
 641         v = point_data<double>(v.x()/s,v.y()/s);
 642         point_data<T> curr_prev;
 643         if (prev_concave)
 644           //TODO missing round_down()
 645           curr_prev = point_data<T>(first->x()+v.x(),first->y()+v.y());
 646         else
 647           curr_prev = prev_point;
 648
 649            // around concave corners - insert rectangle
 650            // if previous corner is concave it's point info may be ignored
 651         if ( treat_as_concave) {
 652            std::vector<point_data<T> > pts;
 653
 654            pts.push_back(point_data<T>(second->x()+v.x(),second->y()+v.y()));
 655            pts.push_back(*second);
 656            pts.push_back(*first);
 657            pts.push_back(point_data<T>(curr_prev));
 658            if (first_pts.size()){
 659               sizingSet.insert_vertex_sequence(pts.begin(),pts.end(), resize_wdir,false);
 660            }else {
 661                first_pts=pts;
 662                first_wdir = resize_wdir;
 663            }
 664         } else {
 665
 666             // add either intersection_quad or pie_shape, based on corner_fill_arc option
 667            // for convex corner (convexity depends on sign of resizing, whether we shrink or grow)
 668            std::vector< std::vector<point_data<T> > > pts;
 669            direction_1d winding;
 670            winding = convex?COUNTERCLOCKWISE:CLOCKWISE;
 671            if (make_resizing_vertex_list(pts, curr_prev, prev_concave, *first, *second, *third, resizing
 672                                          , num_circle_segments, corner_fill_arc))
 673            {
 674                if (first_pts.size()) {
 675                   for (int i=0; i<pts.size(); i++) {
 676                     sizingSet.insert_vertex_sequence(pts[i].begin(),pts[i].end(),winding,false);
 677                   }
 678
 679                } else {
 680                   first_pts = pts[0];
 681                   first_wdir = resize_wdir;
 682                   for (int i=1; i<pts.size(); i++) {
 683                     sizingSet.insert_vertex_sequence(pts[i].begin(),pts[i].end(),winding,false);
 684                   }
 685                }
 686                prev_point = curr_prev;
 687
 688            } else {
 689               treat_as_concave = true;
 690            }
 691         }
 692
 693         prev_concave = treat_as_concave;
 694         first = second;
 695         second = third;
 696         ++third;
 697         if(third == real_end) {
 698           third = begin_points(poly);
 699           if(*second == *third) {
 700             ++third; //skip first point if it is duplicate of last point
 701           }
 702         }
 703       } while(second != end);
 704
 705       // handle insertion of first point
 706       if (!prev_concave) {
 707           first_pts[first_pts.size()-1]=prev_point;
 708       }
 709       sizingSet.insert_vertex_sequence(first_pts.begin(),first_pts.end(),first_wdir,false);
 710
 711       polygon_set_data<coordinate_type> tmp;
 712
 713       //insert original shape
 714       tmp.insert(poly, false, polygon_concept());
 715       if((resizing < 0) ^ hole) tmp -= sizingSet;
 716       else tmp += sizingSet;
 717       //tmp.clean();
 718       insert(tmp, hole);
 719       return (*this);
 720     }
 721
 722
 723     inline polygon_set_data&
 724     interact(const polygon_set_data& that);
 725
 726     inline bool downcast(polygon_45_set_data<coordinate_type>& result) const {
 727       if(!is_45_) return false;
 728       for(iterator_type itr = begin(); itr != end(); ++itr) {
 729         const element_type& elem = *itr;
 730         int count = elem.second;
 731         int rise = 1; //up sloping 45
 732         if(scanline_base<coordinate_type>::is_horizontal(elem.first)) rise = 0;
 733         else if(scanline_base<coordinate_type>::is_vertical(elem.first)) rise = 2;
 734         else {
 735           if(!scanline_base<coordinate_type>::is_45_degree(elem.first)) {
 736             is_45_ = false;
 737             return false; //consider throwing because is_45_ has be be wrong
 738           }
 739           if(elem.first.first.y() > elem.first.second.y()) rise = -1; //down sloping 45
 740         }
 741         typename polygon_45_set_data<coordinate_type>::Vertex45Compact vertex(elem.first.first, rise, count);
 742         result.insert(vertex);
 743         typename polygon_45_set_data<coordinate_type>::Vertex45Compact vertex2(elem.first.second, rise, -count);
 744         result.insert(vertex2);
 745       }
 746       return true;
 747     }
 748
 749     inline GEOMETRY_CONCEPT_ID concept_downcast() const {
 750       typedef typename coordinate_traits<coordinate_type>::coordinate_difference delta_type;
 751       bool is_45 = false;
 752       for(iterator_type itr = begin(); itr != end(); ++itr) {
 753         const element_type& elem = *itr;
 754         delta_type h_delta = euclidean_distance(elem.first.first, elem.first.second, HORIZONTAL);
 755         delta_type v_delta = euclidean_distance(elem.first.first, elem.first.second, VERTICAL);
 756         if(h_delta != 0 || v_delta != 0) {
 757           //neither delta is zero and the edge is not MANHATTAN
 758           if(v_delta != h_delta && v_delta != -h_delta) return POLYGON_SET_CONCEPT;
 759           else is_45 = true;
 760         }
 761       }
 762       if(is_45) return POLYGON_45_SET_CONCEPT;
 763       return POLYGON_90_SET_CONCEPT;
 764     }
 765
 766   private:
 767     mutable value_type data_;
 768     mutable bool dirty_;
 769     mutable bool unsorted_;
 770     mutable bool is_45_;
 771
 772   private:
 773     //functions
 774
 775     template <typename output_container>
 776     void get_dispatch(output_container& output, polygon_concept tag) const {
 777       get_fracture(output, true, tag);
 778     }
 779     template <typename output_container>
 780     void get_dispatch(output_container& output, polygon_with_holes_concept tag) const {
 781       get_fracture(output, false, tag);
 782     }
 783     template <typename output_container, typename concept_type>
 784     void get_fracture(output_container& container, bool fracture_holes, concept_type ) const {
 785       clean();
 786       polygon_arbitrary_formation<coordinate_type> pf(fracture_holes);
 787       typedef typename polygon_arbitrary_formation<coordinate_type>::vertex_half_edge vertex_half_edge;
 788       std::vector<vertex_half_edge> data;
 789       for(iterator_type itr = data_.begin(); itr != data_.end(); ++itr){
 790         data.push_back(vertex_half_edge((*itr).first.first, (*itr).first.second, (*itr).second));
 791         data.push_back(vertex_half_edge((*itr).first.second, (*itr).first.first, -1 * (*itr).second));
 792       }
 793       gtlsort(data.begin(), data.end());
 794       pf.scan(container, data.begin(), data.end());
 795     }
 796   };
 797
 798   struct polygon_set_concept;
 799   template <typename T>
 800   struct geometry_concept<polygon_set_data<T> > {
 801     typedef polygon_set_concept type;
 802   };
 803
 804 //   template <typename  T>
 805 //   inline double compute_area(point_data<T>& a, point_data<T>& b, point_data<T>& c) {
 806
 807 //      return (double)(b.x()-a.x())*(double)(c.y()-a.y())- (double)(c.x()-a.x())*(double)(b.y()-a.y());
 808
 809
 810 //   }
 811
 812   template <typename  T>
 813   inline int make_resizing_vertex_list(std::vector<std::vector<point_data< T> > >& return_points,
 814                        point_data<T>& curr_prev, bool ignore_prev_point,
 815                        point_data< T> start, point_data<T> middle, point_data< T>  end,
 816                        double sizing_distance, unsigned int num_circle_segments, bool corner_fill_arc) {
 817
 818       // handle the case of adding an intersection point
 819       point_data<double> dn1( middle.y()-start.y(), start.x()-middle.x());
 820       double size = sizing_distance/sqrt( dn1.x()*dn1.x()+dn1.y()*dn1.y());
 821       dn1 = point_data<double>( dn1.x()*size, dn1.y()* size);
 822       point_data<double> dn2( end.y()-middle.y(), middle.x()-end.x());
 823       size = sizing_distance/sqrt( dn2.x()*dn2.x()+dn2.y()*dn2.y());
 824       dn2 = point_data<double>( dn2.x()*size, dn2.y()* size);
 825       point_data<double> start_offset((start.x()+dn1.x()),(start.y()+dn1.y()));
 826       point_data<double> mid1_offset((middle.x()+dn1.x()),(middle.y()+dn1.y()));
 827       point_data<double> end_offset((end.x()+dn2.x()),(end.y()+dn2.y()));
 828       point_data<double> mid2_offset((middle.x()+dn2.x()),(middle.y()+dn2.y()));
 829       if (ignore_prev_point)
 830             curr_prev = round_down<T>(start_offset);
 831
 832
 833       if (corner_fill_arc) {
 834          std::vector<point_data< T> > return_points1;
 835          return_points.push_back(return_points1);
 836          std::vector<point_data< T> >& return_points_back = return_points[return_points.size()-1];
 837          return_points_back.push_back(round_down<T>(mid1_offset));
 838          return_points_back.push_back(middle);
 839          return_points_back.push_back(start);
 840          return_points_back.push_back(curr_prev);
 841          point_data<double> dmid(middle.x(),middle.y());
 842          return_points.push_back(return_points1);
 843          int num = make_arc(return_points[return_points.size()-1],mid1_offset,mid2_offset,dmid,sizing_distance,num_circle_segments);
 844          curr_prev = round_down<T>(mid2_offset);
 845          return num;
 846
 847       }
 848
 849       std::pair<point_data<double>,point_data<double> > he1(start_offset,mid1_offset);
 850       std::pair<point_data<double>,point_data<double> > he2(mid2_offset ,end_offset);
 851       //typedef typename high_precision_type<double>::type high_precision;
 852
 853       point_data<T> intersect;
 854       typename scanline_base<T>::compute_intersection_pack pack;
 855       bool res = pack.compute_intersection(intersect,he1,he2,true);
 856       if( res ) {
 857          std::vector<point_data< T> > return_points1;
 858          return_points.push_back(return_points1);
 859          std::vector<point_data< T> >& return_points_back = return_points[return_points.size()-1];
 860          return_points_back.push_back(intersect);
 861          return_points_back.push_back(middle);
 862          return_points_back.push_back(start);
 863          return_points_back.push_back(curr_prev);
 864
 865          //double d1= compute_area(intersect,middle,start);
 866          //double d2= compute_area(start,curr_prev,intersect);
 867
 868          curr_prev = intersect;
 869
 870
 871          return return_points.size();
 872       }
 873       return 0;
 874
 875   }
 876
 877   // this routine should take in start and end point s.t. end point is CCW from start
 878   // it sould make a pie slice polygon  that is an intersection of that arc
 879   // with an ngon segments approximation of the circle centered at center with radius r
 880   // point start is gauaranteed to be on the segmentation
 881   // returnPoints will start with the first point after start
 882   // returnPoints vector  may be empty
 883   template <typename  T>
 884   inline int  make_arc(std::vector<point_data< T> >& return_points,
 885                        point_data< double> start, point_data< double>  end,
 886                        point_data< double> center,  double r, unsigned int num_circle_segments) {
 887       const double our_pi=3.1415926535897932384626433832795028841971;
 888
 889       // derive start and end angles
 890       double ps = atan2(start.y()-center.y(), start.x()-center.x());
 891       double pe = atan2(end.y()-center.y(), end.x()-center.x());
 892       if (ps <  0.0)
 893          ps += 2.0 * our_pi;
 894       if (pe <= 0.0)
 895          pe += 2.0 * our_pi;
 896       if (ps >= 2.0 * our_pi)
 897          ps -= 2.0 * our_pi;
 898       while (pe <= ps)
 899          pe += 2.0 * our_pi;
 900       double delta_angle = (2.0 * our_pi) / (double)num_circle_segments;
 901       if ( start==end) // full circle?
 902       {
 903           ps = delta_angle*0.5;
 904           pe = ps + our_pi * 2.0;
 905           double x,y;
 906           x =  center.x() + r * cos(ps);
 907           y = center.y() + r * sin(ps);
 908           start = point_data<double>(x,y);
 909           end = start;
 910       }
 911       return_points.push_back(round_down<T>(center));
 912       return_points.push_back(round_down<T>(start));
 913       unsigned int i=0;
 914       double curr_angle = ps+delta_angle;
 915       while( curr_angle < pe - 0.01 && i < 2 * num_circle_segments) {
 916          i++;
 917          double x = center.x() + r * cos( curr_angle);
 918          double y = center.y() + r * sin( curr_angle);
 919          return_points.push_back( round_down<T>((point_data<double>(x,y))));
 920          curr_angle+=delta_angle;
 921       }
 922       return_points.push_back(round_down<T>(end));
 923       return return_points.size();
 924   }
 925
 926 }// close namespace
 927 }// close name space
 928
 929 #include "detail/scan_arbitrary.hpp"
 930
 931 namespace boost { namespace polygon {
 932   //ConnectivityExtraction computes the graph of connectivity between rectangle, polygon and
 933   //polygon set graph nodes where an edge is created whenever the geometry in two nodes overlap
 934   template <typename coordinate_type>
 935   class connectivity_extraction{
 936   private:
 937     typedef arbitrary_connectivity_extraction<coordinate_type, int> ce;
 938     ce ce_;
 939     unsigned int nodeCount_;
 940   public:
 941     inline connectivity_extraction() : ce_(), nodeCount_(0) {}
 942     inline connectivity_extraction(const connectivity_extraction& that) : ce_(that.ce_),
 943                                                                           nodeCount_(that.nodeCount_) {}
 944     inline connectivity_extraction& operator=(const connectivity_extraction& that) {
 945       ce_ = that.ce_;
 946       nodeCount_ = that.nodeCount_; {}
 947       return *this;
 948     }
 949
 950     //insert a polygon set graph node, the value returned is the id of the graph node
 951     inline unsigned int insert(const polygon_set_data<coordinate_type>& ps) {
 952       ps.clean();
 953       ce_.populateTouchSetData(ps.begin(), ps.end(), nodeCount_);
 954       return nodeCount_++;
 955     }
 956     template <class GeoObjT>
 957     inline unsigned int insert(const GeoObjT& geoObj) {
 958       polygon_set_data<coordinate_type> ps;
 959       ps.insert(geoObj);
 960       return insert(ps);
 961     }
 962
 963     //extract connectivity and store the edges in the graph
 964     //graph must be indexable by graph node id and the indexed value must be a std::set of
 965     //graph node id
 966     template <class GraphT>
 967     inline void extract(GraphT& graph) {
 968       ce_.execute(graph);
 969     }
 970   };
 971
 972   template <typename T>
 973   polygon_set_data<T>&
 974   polygon_set_data<T>::interact(const polygon_set_data<T>& that) {
 975     connectivity_extraction<coordinate_type> ce;
 976     std::vector<polygon_with_holes_data<T> > polys;
 977     get(polys);
 978     clear();
 979     for(std::size_t i = 0; i < polys.size(); ++i) {
 980       ce.insert(polys[i]);
 981     }
 982     int id = ce.insert(that);
 983     std::vector<std::set<int> > graph(id+1);
 984     ce.extract(graph);
 985     for(std::set<int>::iterator itr = graph[id].begin();
 986         itr != graph[id].end(); ++itr) {
 987       insert(polys[*itr]);
 988     }
 989     return *this;
 990   }
 991 }
 992 }
 993
 994 #include "polygon_set_traits.hpp"
 995 #include "detail/polygon_set_view.hpp"
 996
 997 #include "polygon_set_concept.hpp"
 998 #include "detail/minkowski.hpp"
 999 #endif
1000