Chris@16: /*
Chris@16:   Copyright 2008 Intel Corporation
Chris@16: 
Chris@16:   Use, modification and distribution are subject to the Boost Software License,
Chris@16:   Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
Chris@16:   http://www.boost.org/LICENSE_1_0.txt).
Chris@16: */
Chris@16: namespace boost { namespace polygon { namespace detail {
Chris@16: 
Chris@16: template <typename coordinate_type>
Chris@16: struct minkowski_offset {
Chris@16:   typedef point_data<coordinate_type> point;
Chris@16:   typedef polygon_set_data<coordinate_type> polygon_set;
Chris@16:   typedef polygon_with_holes_data<coordinate_type> polygon;
Chris@16:   typedef std::pair<point, point> edge;
Chris@16: 
Chris@16:   static void convolve_two_segments(std::vector<point>& figure, const edge& a, const edge& b) {
Chris@16:     figure.clear();
Chris@16:     figure.push_back(point(a.first));
Chris@16:     figure.push_back(point(a.first));
Chris@16:     figure.push_back(point(a.second));
Chris@16:     figure.push_back(point(a.second));
Chris@16:     convolve(figure[0], b.second);
Chris@16:     convolve(figure[1], b.first);
Chris@16:     convolve(figure[2], b.first);
Chris@16:     convolve(figure[3], b.second);
Chris@16:   }
Chris@16: 
Chris@16:   template <typename itrT1, typename itrT2>
Chris@16:   static void convolve_two_point_sequences(polygon_set& result, itrT1 ab, itrT1 ae, itrT2 bb, itrT2 be) {
Chris@16:     if(ab == ae || bb == be)
Chris@16:       return;
Chris@16:     point first_a = *ab;
Chris@16:     point prev_a = *ab;
Chris@16:     std::vector<point> vec;
Chris@16:     polygon poly;
Chris@16:     ++ab;
Chris@16:     for( ; ab != ae; ++ab) {
Chris@16:       point first_b = *bb;
Chris@16:       point prev_b = *bb;
Chris@16:       itrT2 tmpb = bb;
Chris@16:       ++tmpb;
Chris@16:       for( ; tmpb != be; ++tmpb) {
Chris@16:         convolve_two_segments(vec, std::make_pair(prev_b, *tmpb), std::make_pair(prev_a, *ab));
Chris@16:         set_points(poly, vec.begin(), vec.end());
Chris@16:         result.insert(poly);
Chris@16:         prev_b = *tmpb;
Chris@16:       }
Chris@16:       prev_a = *ab;
Chris@16:     }
Chris@16:   }
Chris@16: 
Chris@16:   template <typename itrT>
Chris@16:   static void convolve_point_sequence_with_polygons(polygon_set& result, itrT b, itrT e, const std::vector<polygon>& polygons) {
Chris@16:     for(std::size_t i = 0; i < polygons.size(); ++i) {
Chris@16:       convolve_two_point_sequences(result, b, e, begin_points(polygons[i]), end_points(polygons[i]));
Chris@16:       for(typename polygon_with_holes_traits<polygon>::iterator_holes_type itrh = begin_holes(polygons[i]);
Chris@16:           itrh != end_holes(polygons[i]); ++itrh) {
Chris@16:         convolve_two_point_sequences(result, b, e, begin_points(*itrh), end_points(*itrh));
Chris@16:       }
Chris@16:     }
Chris@16:   }
Chris@16: 
Chris@16:   static void convolve_two_polygon_sets(polygon_set& result, const polygon_set& a, const polygon_set& b) {
Chris@16:     result.clear();
Chris@16:     std::vector<polygon> a_polygons;
Chris@16:     std::vector<polygon> b_polygons;
Chris@16:     a.get(a_polygons);
Chris@16:     b.get(b_polygons);
Chris@16:     for(std::size_t ai = 0; ai < a_polygons.size(); ++ai) {
Chris@16:       convolve_point_sequence_with_polygons(result, begin_points(a_polygons[ai]),
Chris@16:                                             end_points(a_polygons[ai]), b_polygons);
Chris@16:       for(typename polygon_with_holes_traits<polygon>::iterator_holes_type itrh = begin_holes(a_polygons[ai]);
Chris@16:           itrh != end_holes(a_polygons[ai]); ++itrh) {
Chris@16:         convolve_point_sequence_with_polygons(result, begin_points(*itrh),
Chris@16:                                               end_points(*itrh), b_polygons);
Chris@16:       }
Chris@16:       for(std::size_t bi = 0; bi < b_polygons.size(); ++bi) {
Chris@16:         polygon tmp_poly = a_polygons[ai];
Chris@16:         result.insert(convolve(tmp_poly, *(begin_points(b_polygons[bi]))));
Chris@16:         tmp_poly = b_polygons[bi];
Chris@16:         result.insert(convolve(tmp_poly, *(begin_points(a_polygons[ai]))));
Chris@16:       }
Chris@16:     }
Chris@16:   }
Chris@16: };
Chris@16: 
Chris@16: }
Chris@16:   template<typename T>
Chris@16:   inline polygon_set_data<T>&
Chris@16:   polygon_set_data<T>::resize(coordinate_type resizing, bool corner_fill_arc, unsigned int num_circle_segments) {
Chris@16:     using namespace ::boost::polygon::operators;
Chris@16:     if(!corner_fill_arc) {
Chris@16:       if(resizing < 0)
Chris@16:         return shrink(-resizing);
Chris@16:       if(resizing > 0)
Chris@16:         return bloat(resizing);
Chris@16:       return *this;
Chris@16:     }
Chris@16:     if(resizing == 0) return *this;
Chris@16:     if(empty()) return *this;
Chris@16:     if(num_circle_segments < 3) num_circle_segments = 4;
Chris@16:     rectangle_data<coordinate_type> rect;
Chris@16:     extents(rect);
Chris@16:     if(resizing < 0) {
Chris@16:       ::boost::polygon::bloat(rect, 10);
Chris@16:       (*this) = rect - (*this); //invert
Chris@16:     }
Chris@16:     //make_arc(std::vector<point_data< T> >& return_points,
Chris@16:     //point_data< double> start, point_data< double>  end,
Chris@16:     //point_data< double> center,  double r, unsigned int num_circle_segments)
Chris@16:     std::vector<point_data<coordinate_type> > circle;
Chris@16:     point_data<double> center(0.0, 0.0), start(0.0, (double)resizing);
Chris@16:     make_arc(circle, start, start, center, std::abs((double)resizing),
Chris@16:              num_circle_segments);
Chris@16:     polygon_data<coordinate_type> poly;
Chris@16:     set_points(poly, circle.begin(), circle.end());
Chris@16:     polygon_set_data<coordinate_type> offset_set;
Chris@16:     offset_set += poly;
Chris@16:     polygon_set_data<coordinate_type> result;
Chris@16:     detail::minkowski_offset<coordinate_type>::convolve_two_polygon_sets
Chris@16:       (result, *this, offset_set);
Chris@16:     if(resizing < 0) {
Chris@16:       result = result & rect;//eliminate overhang
Chris@16:       result = result ^ rect;//invert
Chris@16:     }
Chris@16:     *this = result;
Chris@16:     return *this;
Chris@16:   }
Chris@16: 
Chris@16: }}