boost/polygon/polygon_set_data.hpp

0001 /*
0002   Copyright 2008 Intel Corporation
0003
0004   Use, modification and distribution are subject to the Boost Software License,
0005   Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
0006   http://www.boost.org/LICENSE_1_0.txt).
0007 */
0008 #ifndef BOOST_POLYGON_POLYGON_SET_DATA_HPP
0009 #define BOOST_POLYGON_POLYGON_SET_DATA_HPP
0010 #include "polygon_45_set_data.hpp"
0011 #include "polygon_45_set_concept.hpp"
0012 #include "polygon_traits.hpp"
0013 #include "detail/polygon_arbitrary_formation.hpp"
0014
0015 namespace boost { namespace polygon {
0016
0017
0018   // utility function to round coordinate types down
0019   // rounds down for both negative and positive numbers
0020   // intended really for integer type T (does not make sense for float)
0021   template <typename T>
0022   static inline T round_down(double val) {
0023      T rounded_val = (T)(val);
0024      if(val < (double)rounded_val)
0025         --rounded_val;
0026      return rounded_val;
0027   }
0028   template <typename T>
0029   static inline point_data<T> round_down(point_data<double> v) {
0030      return point_data<T>(round_down<T>(v.x()),round_down<T>(v.y()));
0031   }
0032
0033
0034
0035   //foward declare view
0036   template <typename ltype, typename rtype, int op_type> class polygon_set_view;
0037
0038   template <typename T>
0039   class polygon_set_data {
0040   public:
0041     typedef T coordinate_type;
0042     typedef point_data<T> point_type;
0043     typedef std::pair<point_type, point_type> edge_type;
0044     typedef std::pair<edge_type, int> element_type;
0045     typedef std::vector<element_type> value_type;
0046     typedef typename value_type::const_iterator iterator_type;
0047     typedef polygon_set_data operator_arg_type;
0048
0049     // default constructor
0050     inline polygon_set_data() : data_(), dirty_(false), unsorted_(false), is_45_(true) {}
0051
0052     // constructor from an iterator pair over edge data
0053     template <typename iT>
0054     inline polygon_set_data(iT input_begin, iT input_end) : data_(), dirty_(false), unsorted_(false), is_45_(true) {
0055       for( ; input_begin != input_end; ++input_begin) { insert(*input_begin); }
0056     }
0057
0058     // copy constructor
0059     inline polygon_set_data(const polygon_set_data& that) :
0060       data_(that.data_), dirty_(that.dirty_), unsorted_(that.unsorted_), is_45_(that.is_45_) {}
0061
0062     // copy constructor
0063     template <typename ltype, typename rtype, int op_type>
0064     inline polygon_set_data(const polygon_set_view<ltype, rtype, op_type>& that);
0065
0066     // destructor
0067     inline ~polygon_set_data() {}
0068
0069     // assignement operator
0070     inline polygon_set_data& operator=(const polygon_set_data& that) {
0071       if(this == &that) return *this;
0072       data_ = that.data_;
0073       dirty_ = that.dirty_;
0074       unsorted_ = that.unsorted_;
0075       is_45_ = that.is_45_;
0076       return *this;
0077     }
0078
0079     template <typename ltype, typename rtype, int op_type>
0080     inline polygon_set_data& operator=(const polygon_set_view<ltype, rtype, op_type>& geometry) {
0081       (*this) = geometry.value();
0082       dirty_ = false;
0083       unsorted_ = false;
0084       return *this;
0085     }
0086
0087     template <typename geometry_object>
0088     inline polygon_set_data& operator=(const geometry_object& geometry) {
0089       data_.clear();
0090       insert(geometry);
0091       return *this;
0092     }
0093
0094
0095     // insert iterator range
0096     inline void insert(iterator_type input_begin, iterator_type input_end, bool is_hole = false) {
0097       if(input_begin == input_end || (!data_.empty() && &(*input_begin) == &(*(data_.begin())))) return;
0098       dirty_ = true;
0099       unsorted_ = true;
0100       while(input_begin != input_end) {
0101         insert(*input_begin, is_hole);
0102         ++input_begin;
0103       }
0104     }
0105
0106     // insert iterator range
0107     template <typename iT>
0108     inline void insert(iT input_begin, iT input_end, bool is_hole = false) {
0109       if(input_begin == input_end) return;
0110       for(; input_begin != input_end; ++input_begin) {
0111         insert(*input_begin, is_hole);
0112       }
0113     }
0114
0115     template <typename geometry_type>
0116     inline void insert(const geometry_type& geometry_object, bool is_hole = false) {
0117       insert(geometry_object, is_hole, typename geometry_concept<geometry_type>::type());
0118     }
0119
0120     template <typename polygon_type>
0121     inline void insert(const polygon_type& polygon_object, bool is_hole, polygon_concept ) {
0122       insert_vertex_sequence(begin_points(polygon_object), end_points(polygon_object), winding(polygon_object), is_hole);
0123     }
0124
0125     inline void insert(const polygon_set_data& ps, bool is_hole = false) {
0126       insert(ps.data_.begin(), ps.data_.end(), is_hole);
0127     }
0128
0129     template <typename polygon_45_set_type>
0130     inline void insert(const polygon_45_set_type& ps, bool is_hole, polygon_45_set_concept) {
0131       std::vector<polygon_45_with_holes_data<typename polygon_45_set_traits<polygon_45_set_type>::coordinate_type> > polys;
0132       assign(polys, ps);
0133       insert(polys.begin(), polys.end(), is_hole);
0134     }
0135
0136     template <typename polygon_90_set_type>
0137     inline void insert(const polygon_90_set_type& ps, bool is_hole, polygon_90_set_concept) {
0138       std::vector<polygon_90_with_holes_data<typename polygon_90_set_traits<polygon_90_set_type>::coordinate_type> > polys;
0139       assign(polys, ps);
0140       insert(polys.begin(), polys.end(), is_hole);
0141     }
0142
0143     template <typename polygon_type>
0144     inline void insert(const polygon_type& polygon_object, bool is_hole, polygon_45_concept ) {
0145       insert(polygon_object, is_hole, polygon_concept()); }
0146
0147     template <typename polygon_type>
0148     inline void insert(const polygon_type& polygon_object, bool is_hole, polygon_90_concept ) {
0149       insert(polygon_object, is_hole, polygon_concept()); }
0150
0151     template <typename polygon_with_holes_type>
0152     inline void insert(const polygon_with_holes_type& polygon_with_holes_object, bool is_hole,
0153                        polygon_with_holes_concept ) {
0154       insert(polygon_with_holes_object, is_hole, polygon_concept());
0155       for(typename polygon_with_holes_traits<polygon_with_holes_type>::iterator_holes_type itr =
0156             begin_holes(polygon_with_holes_object);
0157           itr != end_holes(polygon_with_holes_object); ++itr) {
0158         insert(*itr, !is_hole, polygon_concept());
0159       }
0160     }
0161
0162     template <typename polygon_with_holes_type>
0163     inline void insert(const polygon_with_holes_type& polygon_with_holes_object, bool is_hole,
0164                        polygon_45_with_holes_concept ) {
0165       insert(polygon_with_holes_object, is_hole, polygon_with_holes_concept()); }
0166
0167     template <typename polygon_with_holes_type>
0168     inline void insert(const polygon_with_holes_type& polygon_with_holes_object, bool is_hole,
0169                        polygon_90_with_holes_concept ) {
0170       insert(polygon_with_holes_object, is_hole, polygon_with_holes_concept()); }
0171
0172     template <typename rectangle_type>
0173     inline void insert(const rectangle_type& rectangle_object, bool is_hole, rectangle_concept ) {
0174       polygon_90_data<coordinate_type> poly;
0175       assign(poly, rectangle_object);
0176       insert(poly, is_hole, polygon_concept());
0177     }
0178
0179     inline void insert_clean(const element_type& edge, bool is_hole = false) {
0180       if( ! scanline_base<coordinate_type>::is_45_degree(edge.first) &&
0181           ! scanline_base<coordinate_type>::is_horizontal(edge.first) &&
0182           ! scanline_base<coordinate_type>::is_vertical(edge.first) ) is_45_ = false;
0183       data_.push_back(edge);
0184       if(data_.back().first.second < data_.back().first.first) {
0185         std::swap(data_.back().first.second, data_.back().first.first);
0186         data_.back().second *= -1;
0187       }
0188       if(is_hole)
0189         data_.back().second *= -1;
0190     }
0191
0192     inline void insert(const element_type& edge, bool is_hole = false) {
0193       insert_clean(edge, is_hole);
0194       dirty_ = true;
0195       unsorted_ = true;
0196     }
0197
0198     template <class iT>
0199     inline void insert_vertex_sequence(iT begin_vertex, iT end_vertex, direction_1d winding, bool is_hole) {
0200       if (begin_vertex == end_vertex) {
0201         // No edges to insert.
0202         return;
0203       }
0204       // Current edge endpoints.
0205       iT vertex0 = begin_vertex;
0206       iT vertex1 = begin_vertex;
0207       if (++vertex1 == end_vertex) {
0208         // No edges to insert.
0209         return;
0210       }
0211       int wmultiplier = (winding == COUNTERCLOCKWISE) ? 1 : -1;
0212       if (is_hole) {
0213         wmultiplier = -wmultiplier;
0214       }
0215       dirty_ = true;
0216       unsorted_ = true;
0217       while (vertex0 != end_vertex) {
0218         point_type p0, p1;
0219         assign(p0, *vertex0);
0220         assign(p1, *vertex1);
0221         if (p0 != p1) {
0222           int hmultiplier = (p0.get(HORIZONTAL) == p1.get(HORIZONTAL)) ? -1 : 1;
0223           element_type elem(edge_type(p0, p1), hmultiplier * wmultiplier);
0224           insert_clean(elem);
0225         }
0226         ++vertex0;
0227         ++vertex1;
0228         if (vertex1 == end_vertex) {
0229           vertex1 = begin_vertex;
0230         }
0231       }
0232     }
0233
0234     template <typename output_container>
0235     inline void get(output_container& output) const {
0236       get_dispatch(output, typename geometry_concept<typename output_container::value_type>::type());
0237     }
0238
0239     // append to the container cT with polygons of three or four verticies
0240     // slicing orientation is vertical
0241     template <class cT>
0242     void get_trapezoids(cT& container) const {
0243       clean();
0244       trapezoid_arbitrary_formation<coordinate_type> pf;
0245       typedef typename polygon_arbitrary_formation<coordinate_type>::vertex_half_edge vertex_half_edge;
0246       std::vector<vertex_half_edge> data;
0247       for(iterator_type itr = data_.begin(); itr != data_.end(); ++itr){
0248         data.push_back(vertex_half_edge((*itr).first.first, (*itr).first.second, (*itr).second));
0249         data.push_back(vertex_half_edge((*itr).first.second, (*itr).first.first, -1 * (*itr).second));
0250       }
0251       polygon_sort(data.begin(), data.end());
0252       pf.scan(container, data.begin(), data.end());
0253       //std::cout << "DONE FORMING POLYGONS\n";
0254     }
0255
0256     // append to the container cT with polygons of three or four verticies
0257     template <class cT>
0258     void get_trapezoids(cT& container, orientation_2d slicing_orientation) const {
0259       if(slicing_orientation == VERTICAL) {
0260         get_trapezoids(container);
0261       } else {
0262         polygon_set_data<T> ps(*this);
0263         ps.transform(axis_transformation(axis_transformation::SWAP_XY));
0264         cT result;
0265         ps.get_trapezoids(result);
0266         for(typename cT::iterator itr = result.begin(); itr != result.end(); ++itr) {
0267           ::boost::polygon::transform(*itr, axis_transformation(axis_transformation::SWAP_XY));
0268         }
0269         container.insert(container.end(), result.begin(), result.end());
0270       }
0271     }
0272
0273     // equivalence operator
0274     inline bool operator==(const polygon_set_data& p) const;
0275
0276     // inequivalence operator
0277     inline bool operator!=(const polygon_set_data& p) const {
0278       return !((*this) == p);
0279     }
0280
0281     // get iterator to begin vertex data
0282     inline iterator_type begin() const {
0283       return data_.begin();
0284     }
0285
0286     // get iterator to end vertex data
0287     inline iterator_type end() const {
0288       return data_.end();
0289     }
0290
0291     const value_type& value() const {
0292       return data_;
0293     }
0294
0295     // clear the contents of the polygon_set_data
0296     inline void clear() { data_.clear(); dirty_ = unsorted_ = false; }
0297
0298     // find out if Polygon set is empty
0299     inline bool empty() const { return data_.empty(); }
0300
0301     // get the Polygon set size in vertices
0302     inline std::size_t size() const { clean(); return data_.size(); }
0303
0304     // get the current Polygon set capacity in vertices
0305     inline std::size_t capacity() const { return data_.capacity(); }
0306
0307     // reserve size of polygon set in vertices
0308     inline void reserve(std::size_t size) { return data_.reserve(size); }
0309
0310     // find out if Polygon set is sorted
0311     inline bool sorted() const { return !unsorted_; }
0312
0313     // find out if Polygon set is clean
0314     inline bool dirty() const { return dirty_; }
0315
0316     void clean() const;
0317
0318     void sort() const{
0319       if(unsorted_) {
0320         polygon_sort(data_.begin(), data_.end());
0321         unsorted_ = false;
0322       }
0323     }
0324
0325     template <typename input_iterator_type>
0326     void set(input_iterator_type input_begin, input_iterator_type input_end) {
0327       clear();
0328       reserve(std::distance(input_begin,input_end));
0329       insert(input_begin, input_end);
0330       dirty_ = true;
0331       unsorted_ = true;
0332     }
0333
0334     void set(const value_type& value) {
0335       data_ = value;
0336       dirty_ = true;
0337       unsorted_ = true;
0338     }
0339
0340     template <typename rectangle_type>
0341     bool extents(rectangle_type& rect) {
0342       clean();
0343       if(empty()) return false;
0344       bool first_iteration = true;
0345       for(iterator_type itr = begin();
0346           itr != end(); ++itr) {
0347         rectangle_type edge_box;
0348         set_points(edge_box, (*itr).first.first, (*itr).first.second);
0349         if(first_iteration)
0350           rect = edge_box;
0351         else
0352           encompass(rect, edge_box);
0353         first_iteration = false;
0354       }
0355       return true;
0356     }
0357
0358     inline polygon_set_data&
0359     resize(coordinate_type resizing, bool corner_fill_arc = false, unsigned int num_circle_segments=0);
0360
0361     template <typename transform_type>
0362     inline polygon_set_data&
0363     transform(const transform_type& tr) {
0364       std::vector<polygon_with_holes_data<T> > polys;
0365       get(polys);
0366       clear();
0367       for(std::size_t i = 0 ; i < polys.size(); ++i) {
0368         ::boost::polygon::transform(polys[i], tr);
0369         insert(polys[i]);
0370       }
0371       unsorted_ = true;
0372       dirty_ = true;
0373       return *this;
0374     }
0375
0376     inline polygon_set_data&
0377     scale_up(typename coordinate_traits<coordinate_type>::unsigned_area_type factor) {
0378       for(typename value_type::iterator itr = data_.begin(); itr != data_.end(); ++itr) {
0379         ::boost::polygon::scale_up((*itr).first.first, factor);
0380         ::boost::polygon::scale_up((*itr).first.second, factor);
0381       }
0382       return *this;
0383     }
0384
0385     inline polygon_set_data&
0386     scale_down(typename coordinate_traits<coordinate_type>::unsigned_area_type factor) {
0387       for(typename value_type::iterator itr = data_.begin(); itr != data_.end(); ++itr) {
0388         bool vb = (*itr).first.first.x() == (*itr).first.second.x();
0389         ::boost::polygon::scale_down((*itr).first.first, factor);
0390         ::boost::polygon::scale_down((*itr).first.second, factor);
0391         bool va = (*itr).first.first.x() == (*itr).first.second.x();
0392         if(!vb && va) {
0393           (*itr).second *= -1;
0394         }
0395       }
0396       unsorted_ = true;
0397       dirty_ = true;
0398       return *this;
0399     }
0400
0401     template <typename scaling_type>
0402     inline polygon_set_data& scale(polygon_set_data&,
0403                                    const scaling_type& scaling) {
0404       for(typename value_type::iterator itr = begin(); itr != end(); ++itr) {
0405         bool vb = (*itr).first.first.x() == (*itr).first.second.x();
0406         ::boost::polygon::scale((*itr).first.first, scaling);
0407         ::boost::polygon::scale((*itr).first.second, scaling);
0408         bool va = (*itr).first.first.x() == (*itr).first.second.x();
0409         if(!vb && va) {
0410           (*itr).second *= -1;
0411         }
0412       }
0413       unsorted_ = true;
0414       dirty_ = true;
0415       return *this;
0416     }
0417
0418     static inline void compute_offset_edge(point_data<long double>& pt1, point_data<long double>& pt2,
0419                                            const point_data<long double>&  prev_pt,
0420                                            const point_data<long double>&  current_pt,
0421                                            long double distance, int multiplier) {
0422       long double dx = current_pt.x() - prev_pt.x();
0423       long double dy = current_pt.y() - prev_pt.y();
0424       long double edge_length = std::sqrt(dx*dx + dy*dy);
0425       long double dnx = dy;
0426       long double dny = -dx;
0427       dnx = dnx * (long double)distance / edge_length;
0428       dny = dny * (long double)distance / edge_length;
0429       pt1.x(prev_pt.x() + (long double)dnx * (long double)multiplier);
0430       pt2.x(current_pt.x() + (long double)dnx * (long double)multiplier);
0431       pt1.y(prev_pt.y() + (long double)dny * (long double)multiplier);
0432       pt2.y(current_pt.y() + (long double)dny * (long double)multiplier);
0433     }
0434
0435     static inline void modify_pt(point_data<coordinate_type>& pt, const point_data<coordinate_type>&  prev_pt,
0436                                  const point_data<coordinate_type>&  current_pt,  const point_data<coordinate_type>&  next_pt,
0437                                  coordinate_type distance, coordinate_type multiplier) {
0438       std::pair<point_data<long double>, point_data<long double> > he1, he2;
0439       he1.first.x((long double)(prev_pt.x()));
0440       he1.first.y((long double)(prev_pt.y()));
0441       he1.second.x((long double)(current_pt.x()));
0442       he1.second.y((long double)(current_pt.y()));
0443       he2.first.x((long double)(current_pt.x()));
0444       he2.first.y((long double)(current_pt.y()));
0445       he2.second.x((long double)(next_pt.x()));
0446       he2.second.y((long double)(next_pt.y()));
0447       compute_offset_edge(he1.first, he1.second, prev_pt, current_pt, distance, multiplier);
0448       compute_offset_edge(he2.first, he2.second, current_pt, next_pt, distance, multiplier);
0449       typedef scanline_base<long double>::compute_intersection_pack pack;
0450       point_data<long double> rpt;
0451       point_data<long double> bisectorpt((he1.second.x()+he2.first.x())/2,
0452                                          (he1.second.y()+he2.first.y())/2);
0453       point_data<long double> orig_pt((long double)pt.x(), (long double)pt.y());
0454       if(euclidean_distance(bisectorpt, orig_pt) < distance/2) {
0455         if(!pack::compute_lazy_intersection(rpt, he1, he2, true, false)) {
0456           rpt = he1.second; //colinear offset edges use shared point
0457         }
0458       } else {
0459         if(!pack::compute_lazy_intersection(rpt, he1, std::pair<point_data<long double>, point_data<long double> >(orig_pt, bisectorpt), true, false)) {
0460           rpt = he1.second; //colinear offset edges use shared point
0461         }
0462       }
0463       pt.x((coordinate_type)(std::floor(rpt.x()+0.5)));
0464       pt.y((coordinate_type)(std::floor(rpt.y()+0.5)));
0465     }
0466
0467     static void resize_poly_up(std::vector<point_data<coordinate_type> >& poly, coordinate_type distance, coordinate_type multiplier) {
0468       point_data<coordinate_type> first_pt = poly[0];
0469       point_data<coordinate_type> second_pt = poly[1];
0470       point_data<coordinate_type> prev_pt = poly[0];
0471       point_data<coordinate_type> current_pt = poly[1];
0472       for(std::size_t i = 2; i < poly.size()-1; ++i) {
0473         point_data<coordinate_type> next_pt = poly[i];
0474         modify_pt(poly[i-1], prev_pt, current_pt, next_pt, distance, multiplier);
0475         prev_pt = current_pt;
0476         current_pt = next_pt;
0477       }
0478       point_data<coordinate_type> next_pt = first_pt;
0479       modify_pt(poly[poly.size()-2], prev_pt, current_pt, next_pt, distance, multiplier);
0480       prev_pt = current_pt;
0481       current_pt = next_pt;
0482       next_pt = second_pt;
0483       modify_pt(poly[0], prev_pt, current_pt, next_pt, distance, multiplier);
0484       poly.back() = poly.front();
0485     }
0486     static bool resize_poly_down(std::vector<point_data<coordinate_type> >& poly, coordinate_type distance, coordinate_type multiplier) {
0487       std::vector<point_data<coordinate_type> > orig_poly(poly);
0488       rectangle_data<coordinate_type> extents_rectangle;
0489       set_points(extents_rectangle, poly[0], poly[0]);
0490       point_data<coordinate_type> first_pt = poly[0];
0491       point_data<coordinate_type> second_pt = poly[1];
0492       point_data<coordinate_type> prev_pt = poly[0];
0493       point_data<coordinate_type> current_pt = poly[1];
0494       encompass(extents_rectangle, current_pt);
0495       for(std::size_t i = 2; i < poly.size()-1; ++i) {
0496         point_data<coordinate_type> next_pt = poly[i];
0497         encompass(extents_rectangle, next_pt);
0498         modify_pt(poly[i-1], prev_pt, current_pt, next_pt, distance, multiplier);
0499         prev_pt = current_pt;
0500         current_pt = next_pt;
0501       }
0502       if(delta(extents_rectangle, HORIZONTAL) <= std::abs(2*distance))
0503         return false;
0504       if(delta(extents_rectangle, VERTICAL) <= std::abs(2*distance))
0505         return false;
0506       point_data<coordinate_type> next_pt = first_pt;
0507       modify_pt(poly[poly.size()-2], prev_pt, current_pt, next_pt, distance, multiplier);
0508       prev_pt = current_pt;
0509       current_pt = next_pt;
0510       next_pt = second_pt;
0511       modify_pt(poly[0], prev_pt, current_pt, next_pt, distance, multiplier);
0512       poly.back() = poly.front();
0513       //if the line segments formed between orignial and new points cross for an edge that edge inverts
0514       //if all edges invert the polygon should be discarded
0515       //if even one edge does not invert return true because the polygon is valid
0516       bool non_inverting_edge = false;
0517       for(std::size_t i = 1; i < poly.size(); ++i) {
0518         std::pair<point_data<coordinate_type>, point_data<coordinate_type> >
0519           he1(poly[i], orig_poly[i]),
0520           he2(poly[i-1], orig_poly[i-1]);
0521         if(!scanline_base<coordinate_type>::intersects(he1, he2)) {
0522           non_inverting_edge = true;
0523           break;
0524         }
0525       }
0526       return non_inverting_edge;
0527     }
0528
0529     polygon_set_data&
0530     bloat(typename coordinate_traits<coordinate_type>::unsigned_area_type distance) {
0531       std::list<polygon_with_holes_data<coordinate_type> > polys;
0532       get(polys);
0533       clear();
0534       for(typename std::list<polygon_with_holes_data<coordinate_type> >::iterator itr = polys.begin();
0535           itr != polys.end(); ++itr) {
0536         resize_poly_up((*itr).self_.coords_, (coordinate_type)distance, (coordinate_type)1);
0537         insert_vertex_sequence((*itr).self_.begin(), (*itr).self_.end(), COUNTERCLOCKWISE, false); //inserts without holes
0538         for(typename std::list<polygon_data<coordinate_type> >::iterator itrh = (*itr).holes_.begin();
0539             itrh != (*itr).holes_.end(); ++itrh) {
0540           if(resize_poly_down((*itrh).coords_, (coordinate_type)distance, (coordinate_type)1)) {
0541             insert_vertex_sequence((*itrh).coords_.begin(), (*itrh).coords_.end(), CLOCKWISE, true);
0542           }
0543         }
0544       }
0545       return *this;
0546     }
0547
0548     polygon_set_data&
0549     shrink(typename coordinate_traits<coordinate_type>::unsigned_area_type distance) {
0550       std::list<polygon_with_holes_data<coordinate_type> > polys;
0551       get(polys);
0552       clear();
0553       for(typename std::list<polygon_with_holes_data<coordinate_type> >::iterator itr = polys.begin();
0554           itr != polys.end(); ++itr) {
0555         if(resize_poly_down((*itr).self_.coords_, (coordinate_type)distance, (coordinate_type)-1)) {
0556           insert_vertex_sequence((*itr).self_.begin(), (*itr).self_.end(), COUNTERCLOCKWISE, false); //inserts without holes
0557           for(typename std::list<polygon_data<coordinate_type> >::iterator itrh = (*itr).holes_.begin();
0558               itrh != (*itr).holes_.end(); ++itrh) {
0559             resize_poly_up((*itrh).coords_, (coordinate_type)distance, (coordinate_type)-1);
0560             insert_vertex_sequence((*itrh).coords_.begin(), (*itrh).coords_.end(), CLOCKWISE, true);
0561           }
0562         }
0563       }
0564       return *this;
0565     }
0566
0567     // TODO:: should be private
0568     template <typename geometry_type>
0569     inline polygon_set_data&
0570     insert_with_resize(const geometry_type& poly, coordinate_type resizing, bool corner_fill_arc=false, unsigned int num_circle_segments=0, bool hole = false) {
0571       return insert_with_resize_dispatch(poly, resizing,  corner_fill_arc, num_circle_segments, hole, typename geometry_concept<geometry_type>::type());
0572     }
0573
0574     template <typename geometry_type>
0575     inline polygon_set_data&
0576     insert_with_resize_dispatch(const geometry_type& poly, coordinate_type resizing, bool corner_fill_arc, unsigned int num_circle_segments, bool hole,
0577                                polygon_with_holes_concept) {
0578       insert_with_resize_dispatch(poly, resizing, corner_fill_arc, num_circle_segments, hole, polygon_concept());
0579       for(typename polygon_with_holes_traits<geometry_type>::iterator_holes_type itr =
0580             begin_holes(poly); itr != end_holes(poly);
0581           ++itr) {
0582         insert_with_resize_dispatch(*itr, resizing,  corner_fill_arc, num_circle_segments, !hole, polygon_concept());
0583       }
0584       return *this;
0585     }
0586
0587     template <typename geometry_type>
0588     inline polygon_set_data&
0589     insert_with_resize_dispatch(const geometry_type& poly, coordinate_type resizing, bool corner_fill_arc, unsigned int num_circle_segments, bool hole,
0590                           polygon_concept) {
0591
0592       if (resizing==0)
0593          return *this;
0594
0595
0596       // one dimensional used to store CCW/CW flag
0597       //direction_1d wdir = winding(poly);
0598       // LOW==CLOCKWISE just faster to type
0599       // so > 0 is CCW
0600       //int multiplier = wdir == LOW ? -1 : 1;
0601       //std::cout<<" multiplier : "<<multiplier<<std::endl;
0602       //if(hole) resizing *= -1;
0603       direction_1d resize_wdir = resizing>0?COUNTERCLOCKWISE:CLOCKWISE;
0604
0605       typedef typename polygon_data<T>::iterator_type piterator;
0606       piterator first, second, third, end, real_end;
0607       real_end = end_points(poly);
0608       third = begin_points(poly);
0609       first = third;
0610       if(first == real_end) return *this;
0611       ++third;
0612       if(third == real_end) return *this;
0613       second = end = third;
0614       ++third;
0615       if(third == real_end) return *this;
0616
0617         // for 1st corner
0618       std::vector<point_data<T> > first_pts;
0619       std::vector<point_data<T> > all_pts;
0620       direction_1d first_wdir = CLOCKWISE;
0621
0622       // for all corners
0623       polygon_set_data<T> sizingSet;
0624       bool sizing_sign = resizing<0;
0625       bool prev_concave = true;
0626       point_data<T> prev_point;
0627       //int iCtr=0;
0628
0629
0630       //insert minkofski shapes on edges and corners
0631       do { // REAL WORK IS HERE
0632
0633
0634         //first, second and third point to points in correct CCW order
0635         // check if convex or concave case
0636         point_data<coordinate_type> normal1( second->y()-first->y(), first->x()-second->x());
0637         point_data<coordinate_type> normal2( third->y()-second->y(), second->x()-third->x());
0638         double direction = normal1.x()*normal2.y()- normal2.x()*normal1.y();
0639         bool convex = direction>0;
0640
0641         bool treat_as_concave = !convex;
0642         if(sizing_sign)
0643           treat_as_concave = convex;
0644         point_data<double> v;
0645         assign(v, normal1);
0646         double s2 = (v.x()*v.x()+v.y()*v.y());
0647         double s = std::sqrt(s2)/resizing;
0648         v = point_data<double>(v.x()/s,v.y()/s);
0649         point_data<T> curr_prev;
0650         if (prev_concave)
0651           //TODO missing round_down()
0652           curr_prev = point_data<T>(first->x()+v.x(),first->y()+v.y());
0653         else
0654           curr_prev = prev_point;
0655
0656            // around concave corners - insert rectangle
0657            // if previous corner is concave it's point info may be ignored
0658         if ( treat_as_concave) {
0659            std::vector<point_data<T> > pts;
0660
0661            pts.push_back(point_data<T>(second->x()+v.x(),second->y()+v.y()));
0662            pts.push_back(*second);
0663            pts.push_back(*first);
0664            pts.push_back(point_data<T>(curr_prev));
0665            if (first_pts.size()){
0666               sizingSet.insert_vertex_sequence(pts.begin(),pts.end(), resize_wdir,false);
0667            }else {
0668                first_pts=pts;
0669                first_wdir = resize_wdir;
0670            }
0671         } else {
0672
0673             // add either intersection_quad or pie_shape, based on corner_fill_arc option
0674            // for convex corner (convexity depends on sign of resizing, whether we shrink or grow)
0675            std::vector< std::vector<point_data<T> > > pts;
0676            direction_1d winding;
0677            winding = convex?COUNTERCLOCKWISE:CLOCKWISE;
0678            if (make_resizing_vertex_list(pts, curr_prev, prev_concave, *first, *second, *third, resizing
0679                                          , num_circle_segments, corner_fill_arc))
0680            {
0681                if (first_pts.size()) {
0682                   for (int i=0; i<pts.size(); i++) {
0683                     sizingSet.insert_vertex_sequence(pts[i].begin(),pts[i].end(),winding,false);
0684                   }
0685
0686                } else {
0687                   first_pts = pts[0];
0688                   first_wdir = resize_wdir;
0689                   for (int i=1; i<pts.size(); i++) {
0690                     sizingSet.insert_vertex_sequence(pts[i].begin(),pts[i].end(),winding,false);
0691                   }
0692                }
0693                prev_point = curr_prev;
0694
0695            } else {
0696               treat_as_concave = true;
0697            }
0698         }
0699
0700         prev_concave = treat_as_concave;
0701         first = second;
0702         second = third;
0703         ++third;
0704         if(third == real_end) {
0705           third = begin_points(poly);
0706           if(*second == *third) {
0707             ++third; //skip first point if it is duplicate of last point
0708           }
0709         }
0710       } while(second != end);
0711
0712       // handle insertion of first point
0713       if (!prev_concave) {
0714           first_pts[first_pts.size()-1]=prev_point;
0715       }
0716       sizingSet.insert_vertex_sequence(first_pts.begin(),first_pts.end(),first_wdir,false);
0717
0718       polygon_set_data<coordinate_type> tmp;
0719
0720       //insert original shape
0721       tmp.insert(poly, false, polygon_concept());
0722       if((resizing < 0) ^ hole) tmp -= sizingSet;
0723       else tmp += sizingSet;
0724       //tmp.clean();
0725       insert(tmp, hole);
0726       return (*this);
0727     }
0728
0729
0730     inline polygon_set_data&
0731     interact(const polygon_set_data& that);
0732
0733     inline bool downcast(polygon_45_set_data<coordinate_type>& result) const {
0734       if(!is_45_) return false;
0735       for(iterator_type itr = begin(); itr != end(); ++itr) {
0736         const element_type& elem = *itr;
0737         int count = elem.second;
0738         int rise = 1; //up sloping 45
0739         if(scanline_base<coordinate_type>::is_horizontal(elem.first)) rise = 0;
0740         else if(scanline_base<coordinate_type>::is_vertical(elem.first)) rise = 2;
0741         else {
0742           if(!scanline_base<coordinate_type>::is_45_degree(elem.first)) {
0743             is_45_ = false;
0744             return false; //consider throwing because is_45_ has be be wrong
0745           }
0746           if(elem.first.first.y() > elem.first.second.y()) rise = -1; //down sloping 45
0747         }
0748         typename polygon_45_set_data<coordinate_type>::Vertex45Compact vertex(elem.first.first, rise, count);
0749         result.insert(vertex);
0750         typename polygon_45_set_data<coordinate_type>::Vertex45Compact vertex2(elem.first.second, rise, -count);
0751         result.insert(vertex2);
0752       }
0753       return true;
0754     }
0755
0756     inline GEOMETRY_CONCEPT_ID concept_downcast() const {
0757       typedef typename coordinate_traits<coordinate_type>::coordinate_difference delta_type;
0758       bool is_45 = false;
0759       for(iterator_type itr = begin(); itr != end(); ++itr) {
0760         const element_type& elem = *itr;
0761         delta_type h_delta = euclidean_distance(elem.first.first, elem.first.second, HORIZONTAL);
0762         delta_type v_delta = euclidean_distance(elem.first.first, elem.first.second, VERTICAL);
0763         if(h_delta != 0 || v_delta != 0) {
0764           //neither delta is zero and the edge is not MANHATTAN
0765           if(v_delta != h_delta && v_delta != -h_delta) return POLYGON_SET_CONCEPT;
0766           else is_45 = true;
0767         }
0768       }
0769       if(is_45) return POLYGON_45_SET_CONCEPT;
0770       return POLYGON_90_SET_CONCEPT;
0771     }
0772
0773   private:
0774     mutable value_type data_;
0775     mutable bool dirty_;
0776     mutable bool unsorted_;
0777     mutable bool is_45_;
0778
0779   private:
0780     //functions
0781
0782     template <typename output_container>
0783     void get_dispatch(output_container& output, polygon_concept tag) const {
0784       get_fracture(output, true, tag);
0785     }
0786     template <typename output_container>
0787     void get_dispatch(output_container& output, polygon_with_holes_concept tag) const {
0788       get_fracture(output, false, tag);
0789     }
0790     template <typename output_container, typename concept_type>
0791     void get_fracture(output_container& container, bool fracture_holes, concept_type ) const {
0792       clean();
0793       polygon_arbitrary_formation<coordinate_type> pf(fracture_holes);
0794       typedef typename polygon_arbitrary_formation<coordinate_type>::vertex_half_edge vertex_half_edge;
0795       std::vector<vertex_half_edge> data;
0796       for(iterator_type itr = data_.begin(); itr != data_.end(); ++itr){
0797         data.push_back(vertex_half_edge((*itr).first.first, (*itr).first.second, (*itr).second));
0798         data.push_back(vertex_half_edge((*itr).first.second, (*itr).first.first, -1 * (*itr).second));
0799       }
0800       polygon_sort(data.begin(), data.end());
0801       pf.scan(container, data.begin(), data.end());
0802     }
0803   };
0804
0805   struct polygon_set_concept;
0806   template <typename T>
0807   struct geometry_concept<polygon_set_data<T> > {
0808     typedef polygon_set_concept type;
0809   };
0810
0811 //   template <typename  T>
0812 //   inline double compute_area(point_data<T>& a, point_data<T>& b, point_data<T>& c) {
0813
0814 //      return (double)(b.x()-a.x())*(double)(c.y()-a.y())- (double)(c.x()-a.x())*(double)(b.y()-a.y());
0815
0816
0817 //   }
0818
0819   template <typename  T>
0820   inline int make_resizing_vertex_list(std::vector<std::vector<point_data< T> > >& return_points,
0821                        point_data<T>& curr_prev, bool ignore_prev_point,
0822                        point_data< T> start, point_data<T> middle, point_data< T>  end,
0823                        double sizing_distance, unsigned int num_circle_segments, bool corner_fill_arc) {
0824
0825       // handle the case of adding an intersection point
0826       point_data<double> dn1( middle.y()-start.y(), start.x()-middle.x());
0827       double size = sizing_distance/std::sqrt( dn1.x()*dn1.x()+dn1.y()*dn1.y());
0828       dn1 = point_data<double>( dn1.x()*size, dn1.y()* size);
0829       point_data<double> dn2( end.y()-middle.y(), middle.x()-end.x());
0830       size = sizing_distance/std::sqrt( dn2.x()*dn2.x()+dn2.y()*dn2.y());
0831       dn2 = point_data<double>( dn2.x()*size, dn2.y()* size);
0832       point_data<double> start_offset((start.x()+dn1.x()),(start.y()+dn1.y()));
0833       point_data<double> mid1_offset((middle.x()+dn1.x()),(middle.y()+dn1.y()));
0834       point_data<double> end_offset((end.x()+dn2.x()),(end.y()+dn2.y()));
0835       point_data<double> mid2_offset((middle.x()+dn2.x()),(middle.y()+dn2.y()));
0836       if (ignore_prev_point)
0837             curr_prev = round_down<T>(start_offset);
0838
0839
0840       if (corner_fill_arc) {
0841          std::vector<point_data< T> > return_points1;
0842          return_points.push_back(return_points1);
0843          std::vector<point_data< T> >& return_points_back = return_points[return_points.size()-1];
0844          return_points_back.push_back(round_down<T>(mid1_offset));
0845          return_points_back.push_back(middle);
0846          return_points_back.push_back(start);
0847          return_points_back.push_back(curr_prev);
0848          point_data<double> dmid(middle.x(),middle.y());
0849          return_points.push_back(return_points1);
0850          int num = make_arc(return_points[return_points.size()-1],mid1_offset,mid2_offset,dmid,sizing_distance,num_circle_segments);
0851          curr_prev = round_down<T>(mid2_offset);
0852          return num;
0853
0854       }
0855
0856       std::pair<point_data<double>,point_data<double> > he1(start_offset,mid1_offset);
0857       std::pair<point_data<double>,point_data<double> > he2(mid2_offset ,end_offset);
0858       //typedef typename high_precision_type<double>::type high_precision;
0859
0860       point_data<T> intersect;
0861       typename scanline_base<T>::compute_intersection_pack pack;
0862       bool res = pack.compute_intersection(intersect,he1,he2,true);
0863       if( res ) {
0864          std::vector<point_data< T> > return_points1;
0865          return_points.push_back(return_points1);
0866          std::vector<point_data< T> >& return_points_back = return_points[return_points.size()-1];
0867          return_points_back.push_back(intersect);
0868          return_points_back.push_back(middle);
0869          return_points_back.push_back(start);
0870          return_points_back.push_back(curr_prev);
0871
0872          //double d1= compute_area(intersect,middle,start);
0873          //double d2= compute_area(start,curr_prev,intersect);
0874
0875          curr_prev = intersect;
0876
0877
0878          return return_points.size();
0879       }
0880       return 0;
0881
0882   }
0883
0884   // this routine should take in start and end point s.t. end point is CCW from start
0885   // it sould make a pie slice polygon  that is an intersection of that arc
0886   // with an ngon segments approximation of the circle centered at center with radius r
0887   // point start is gauaranteed to be on the segmentation
0888   // returnPoints will start with the first point after start
0889   // returnPoints vector  may be empty
0890   template <typename  T>
0891   inline int  make_arc(std::vector<point_data< T> >& return_points,
0892                        point_data< double> start, point_data< double>  end,
0893                        point_data< double> center,  double r, unsigned int num_circle_segments) {
0894       const double our_pi=3.1415926535897932384626433832795028841971;
0895
0896       // derive start and end angles
0897       double ps = atan2(start.y()-center.y(), start.x()-center.x());
0898       double pe = atan2(end.y()-center.y(), end.x()-center.x());
0899       if (ps <  0.0)
0900          ps += 2.0 * our_pi;
0901       if (pe <= 0.0)
0902          pe += 2.0 * our_pi;
0903       if (ps >= 2.0 * our_pi)
0904          ps -= 2.0 * our_pi;
0905       while (pe <= ps)
0906          pe += 2.0 * our_pi;
0907       double delta_angle = (2.0 * our_pi) / (double)num_circle_segments;
0908       if ( start==end) // full circle?
0909       {
0910           ps = delta_angle*0.5;
0911           pe = ps + our_pi * 2.0;
0912           double x,y;
0913           x =  center.x() + r * cos(ps);
0914           y = center.y() + r * sin(ps);
0915           start = point_data<double>(x,y);
0916           end = start;
0917       }
0918       return_points.push_back(round_down<T>(center));
0919       return_points.push_back(round_down<T>(start));
0920       unsigned int i=0;
0921       double curr_angle = ps+delta_angle;
0922       while( curr_angle < pe - 0.01 && i < 2 * num_circle_segments) {
0923          i++;
0924          double x = center.x() + r * cos( curr_angle);
0925          double y = center.y() + r * sin( curr_angle);
0926          return_points.push_back( round_down<T>((point_data<double>(x,y))));
0927          curr_angle+=delta_angle;
0928       }
0929       return_points.push_back(round_down<T>(end));
0930       return return_points.size();
0931   }
0932
0933 }// close namespace
0934 }// close name space
0935
0936 #include "detail/scan_arbitrary.hpp"
0937
0938 namespace boost { namespace polygon {
0939   //ConnectivityExtraction computes the graph of connectivity between rectangle, polygon and
0940   //polygon set graph nodes where an edge is created whenever the geometry in two nodes overlap
0941   template <typename coordinate_type>
0942   class connectivity_extraction{
0943   private:
0944     typedef arbitrary_connectivity_extraction<coordinate_type, int> ce;
0945     ce ce_;
0946     unsigned int nodeCount_;
0947   public:
0948     inline connectivity_extraction() : ce_(), nodeCount_(0) {}
0949     inline connectivity_extraction(const connectivity_extraction& that) : ce_(that.ce_),
0950                                                                           nodeCount_(that.nodeCount_) {}
0951     inline connectivity_extraction& operator=(const connectivity_extraction& that) {
0952       ce_ = that.ce_;
0953       nodeCount_ = that.nodeCount_; {}
0954       return *this;
0955     }
0956
0957     //insert a polygon set graph node, the value returned is the id of the graph node
0958     inline unsigned int insert(const polygon_set_data<coordinate_type>& ps) {
0959       ps.clean();
0960       ce_.populateTouchSetData(ps.begin(), ps.end(), nodeCount_);
0961       return nodeCount_++;
0962     }
0963     template <class GeoObjT>
0964     inline unsigned int insert(const GeoObjT& geoObj) {
0965       polygon_set_data<coordinate_type> ps;
0966       ps.insert(geoObj);
0967       return insert(ps);
0968     }
0969
0970     //extract connectivity and store the edges in the graph
0971     //graph must be indexable by graph node id and the indexed value must be a std::set of
0972     //graph node id
0973     template <class GraphT>
0974     inline void extract(GraphT& graph) {
0975       ce_.execute(graph);
0976     }
0977   };
0978
0979   template <typename T>
0980   polygon_set_data<T>&
0981   polygon_set_data<T>::interact(const polygon_set_data<T>& that) {
0982     connectivity_extraction<coordinate_type> ce;
0983     std::vector<polygon_with_holes_data<T> > polys;
0984     get(polys);
0985     clear();
0986     for(std::size_t i = 0; i < polys.size(); ++i) {
0987       ce.insert(polys[i]);
0988     }
0989     int id = ce.insert(that);
0990     std::vector<std::set<int> > graph(id+1);
0991     ce.extract(graph);
0992     for(std::set<int>::iterator itr = graph[id].begin();
0993         itr != graph[id].end(); ++itr) {
0994       insert(polys[*itr]);
0995     }
0996     return *this;
0997   }
0998 }
0999 }
1000
1001 #include "polygon_set_traits.hpp"
1002 #include "detail/polygon_set_view.hpp"
1003
1004 #include "polygon_set_concept.hpp"
1005 #include "detail/minkowski.hpp"
1006 #endif