ceph/src/boost/libs/polygon/include/boost/polygon/detail/minkowski.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 namespace boost { namespace polygon { namespace detail {
   9
  10 template <typename coordinate_type>
  11 struct minkowski_offset {
  12   typedef point_data<coordinate_type> point;
  13   typedef polygon_set_data<coordinate_type> polygon_set;
  14   typedef polygon_with_holes_data<coordinate_type> polygon;
  15   typedef std::pair<point, point> edge;
  16
  17   static void convolve_two_segments(std::vector<point>& figure, const edge& a, const edge& b) {
  18     figure.clear();
  19     figure.push_back(point(a.first));
  20     figure.push_back(point(a.first));
  21     figure.push_back(point(a.second));
  22     figure.push_back(point(a.second));
  23     convolve(figure[0], b.second);
  24     convolve(figure[1], b.first);
  25     convolve(figure[2], b.first);
  26     convolve(figure[3], b.second);
  27   }
  28
  29   template <typename itrT1, typename itrT2>
  30   static void convolve_two_point_sequences(polygon_set& result, itrT1 ab, itrT1 ae, itrT2 bb, itrT2 be) {
  31     if(ab == ae || bb == be)
  32       return;
  33     point first_a = *ab;
  34     point prev_a = *ab;
  35     std::vector<point> vec;
  36     polygon poly;
  37     ++ab;
  38     for( ; ab != ae; ++ab) {
  39       point first_b = *bb;
  40       point prev_b = *bb;
  41       itrT2 tmpb = bb;
  42       ++tmpb;
  43       for( ; tmpb != be; ++tmpb) {
  44         convolve_two_segments(vec, std::make_pair(prev_b, *tmpb), std::make_pair(prev_a, *ab));
  45         set_points(poly, vec.begin(), vec.end());
  46         result.insert(poly);
  47         prev_b = *tmpb;
  48       }
  49       prev_a = *ab;
  50     }
  51   }
  52
  53   template <typename itrT>
  54   static void convolve_point_sequence_with_polygons(polygon_set& result, itrT b, itrT e, const std::vector<polygon>& polygons) {
  55     for(std::size_t i = 0; i < polygons.size(); ++i) {
  56       convolve_two_point_sequences(result, b, e, begin_points(polygons[i]), end_points(polygons[i]));
  57       for(typename polygon_with_holes_traits<polygon>::iterator_holes_type itrh = begin_holes(polygons[i]);
  58           itrh != end_holes(polygons[i]); ++itrh) {
  59         convolve_two_point_sequences(result, b, e, begin_points(*itrh), end_points(*itrh));
  60       }
  61     }
  62   }
  63
  64   static void convolve_two_polygon_sets(polygon_set& result, const polygon_set& a, const polygon_set& b) {
  65     result.clear();
  66     std::vector<polygon> a_polygons;
  67     std::vector<polygon> b_polygons;
  68     a.get(a_polygons);
  69     b.get(b_polygons);
  70     for(std::size_t ai = 0; ai < a_polygons.size(); ++ai) {
  71       convolve_point_sequence_with_polygons(result, begin_points(a_polygons[ai]),
  72                                             end_points(a_polygons[ai]), b_polygons);
  73       for(typename polygon_with_holes_traits<polygon>::iterator_holes_type itrh = begin_holes(a_polygons[ai]);
  74           itrh != end_holes(a_polygons[ai]); ++itrh) {
  75         convolve_point_sequence_with_polygons(result, begin_points(*itrh),
  76                                               end_points(*itrh), b_polygons);
  77       }
  78       for(std::size_t bi = 0; bi < b_polygons.size(); ++bi) {
  79         polygon tmp_poly = a_polygons[ai];
  80         result.insert(convolve(tmp_poly, *(begin_points(b_polygons[bi]))));
  81         tmp_poly = b_polygons[bi];
  82         result.insert(convolve(tmp_poly, *(begin_points(a_polygons[ai]))));
  83       }
  84     }
  85   }
  86 };
  87
  88 }
  89   template<typename T>
  90   inline polygon_set_data<T>&
  91   polygon_set_data<T>::resize(coordinate_type resizing, bool corner_fill_arc, unsigned int num_circle_segments) {
  92     using namespace ::boost::polygon::operators;
  93     if(!corner_fill_arc) {
  94       if(resizing < 0)
  95         return shrink(-resizing);
  96       if(resizing > 0)
  97         return bloat(resizing);
  98       return *this;
  99     }
 100     if(resizing == 0) return *this;
 101     if(empty()) return *this;
 102     if(num_circle_segments < 3) num_circle_segments = 4;
 103     rectangle_data<coordinate_type> rect;
 104     extents(rect);
 105     if(resizing < 0) {
 106       ::boost::polygon::bloat(rect, 10);
 107       (*this) = rect - (*this); //invert
 108     }
 109     //make_arc(std::vector<point_data< T> >& return_points,
 110     //point_data< double> start, point_data< double>  end,
 111     //point_data< double> center,  double r, unsigned int num_circle_segments)
 112     std::vector<point_data<coordinate_type> > circle;
 113     point_data<double> center(0.0, 0.0), start(0.0, (double)resizing);
 114     make_arc(circle, start, start, center, std::abs((double)resizing),
 115              num_circle_segments);
 116     polygon_data<coordinate_type> poly;
 117     set_points(poly, circle.begin(), circle.end());
 118     polygon_set_data<coordinate_type> offset_set;
 119     offset_set += poly;
 120     polygon_set_data<coordinate_type> result;
 121     detail::minkowski_offset<coordinate_type>::convolve_two_polygon_sets
 122       (result, *this, offset_set);
 123     if(resizing < 0) {
 124       result = result & rect;//eliminate overhang
 125       result = result ^ rect;//invert
 126     }
 127     *this = result;
 128     return *this;
 129   }
 130
 131 }}