ceph/src/boost/boost/geometry/algorithms/detail/overlay/clip_linestring.hpp

   1 // Boost.Geometry (aka GGL, Generic Geometry Library)
   2
   3 // Copyright (c) 2007-2015 Barend Gehrels, Amsterdam, the Netherlands.
   4
   5 // This file was modified by Oracle on 2015.
   6 // Modifications copyright (c) 2015 Oracle and/or its affiliates.
   7
   8 // Contributed and/or modified by Menelaos Karavelas, on behalf of Oracle
   9
  10 // Use, modification and distribution is subject to the Boost Software License,
  11 // Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
  12 // http://www.boost.org/LICENSE_1_0.txt)
  13
  14 #ifndef BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_CLIP_LINESTRING_HPP
  15 #define BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_CLIP_LINESTRING_HPP
  16
  17 #include <boost/range.hpp>
  18
  19 #include <boost/geometry/algorithms/clear.hpp>
  20 #include <boost/geometry/algorithms/convert.hpp>
  21
  22 #include <boost/geometry/algorithms/detail/overlay/append_no_duplicates.hpp>
  23
  24 #include <boost/geometry/util/select_coordinate_type.hpp>
  25 #include <boost/geometry/geometries/segment.hpp>
  26
  27 namespace boost { namespace geometry
  28 {
  29
  30 namespace strategy { namespace intersection
  31 {
  32
  33 /*!
  34     \brief Strategy: line clipping algorithm after Liang Barsky
  35     \ingroup overlay
  36     \details The Liang-Barsky line clipping algorithm clips a line with a clipping box.
  37     It is slightly adapted in the sense that it returns which points are clipped
  38     \tparam B input box type of clipping box
  39     \tparam P input/output point-type of segments to be clipped
  40     \note The algorithm is currently only implemented for 2D Cartesian points
  41     \note Though it is implemented in namespace strategy, and theoretically another
  42         strategy could be used, it is not (yet) updated to the general strategy concepts,
  43         and not (yet) splitted into a file in folder strategies
  44     \author Barend Gehrels, and the following recourses
  45     - A tutorial: http://www.skytopia.com/project/articles/compsci/clipping.html
  46     - a German applet (link broken): http://ls7-www.cs.uni-dortmund.de/students/projectgroups/acit/lineclip.shtml
  47 */
  48 template<typename Box, typename Point>
  49 class liang_barsky
  50 {
  51 private:
  52     typedef model::referring_segment<Point> segment_type;
  53
  54     template <typename CoordinateType, typename CalcType>
  55     inline bool check_edge(CoordinateType const& p, CoordinateType const& q, CalcType& t1, CalcType& t2) const
  56     {
  57         bool visible = true;
  58
  59         if(p < 0)
  60         {
  61             CalcType const r = static_cast<CalcType>(q) / p;
  62             if (r > t2)
  63                 visible = false;
  64             else if (r > t1)
  65                 t1 = r;
  66         }
  67         else if(p > 0)
  68         {
  69             CalcType const r = static_cast<CalcType>(q) / p;
  70             if (r < t1)
  71                 visible = false;
  72             else if (r < t2)
  73                 t2 = r;
  74         }
  75         else
  76         {
  77             if (q < 0)
  78                 visible = false;
  79         }
  80
  81         return visible;
  82     }
  83
  84 public:
  85
  86     inline bool clip_segment(Box const& b, segment_type& s, bool& sp1_clipped, bool& sp2_clipped) const
  87     {
  88         typedef typename select_coordinate_type<Box, Point>::type coordinate_type;
  89         typedef typename select_most_precise<coordinate_type, double>::type calc_type;
  90
  91         calc_type t1 = 0;
  92         calc_type t2 = 1;
  93
  94         coordinate_type const dx = get<1, 0>(s) - get<0, 0>(s);
  95         coordinate_type const dy = get<1, 1>(s) - get<0, 1>(s);
  96
  97         coordinate_type const p1 = -dx;
  98         coordinate_type const p2 = dx;
  99         coordinate_type const p3 = -dy;
 100         coordinate_type const p4 = dy;
 101
 102         coordinate_type const q1 = get<0, 0>(s) - get<min_corner, 0>(b);
 103         coordinate_type const q2 = get<max_corner, 0>(b) - get<0, 0>(s);
 104         coordinate_type const q3 = get<0, 1>(s) - get<min_corner, 1>(b);
 105         coordinate_type const q4 = get<max_corner, 1>(b) - get<0, 1>(s);
 106
 107         if (check_edge(p1, q1, t1, t2)      // left
 108             && check_edge(p2, q2, t1, t2)   // right
 109             && check_edge(p3, q3, t1, t2)   // bottom
 110             && check_edge(p4, q4, t1, t2))   // top
 111         {
 112             sp1_clipped = t1 > 0;
 113             sp2_clipped = t2 < 1;
 114
 115             if (sp2_clipped)
 116             {
 117                 set<1, 0>(s, get<0, 0>(s) + t2 * dx);
 118                 set<1, 1>(s, get<0, 1>(s) + t2 * dy);
 119             }
 120
 121             if(sp1_clipped)
 122             {
 123                 set<0, 0>(s, get<0, 0>(s) + t1 * dx);
 124                 set<0, 1>(s, get<0, 1>(s) + t1 * dy);
 125             }
 126
 127             return true;
 128         }
 129
 130         return false;
 131     }
 132
 133     template<typename Linestring, typename OutputIterator>
 134     inline void apply(Linestring& line_out, OutputIterator out) const
 135     {
 136         if (!boost::empty(line_out))
 137         {
 138             *out = line_out;
 139             ++out;
 140             geometry::clear(line_out);
 141         }
 142     }
 143 };
 144
 145
 146 }} // namespace strategy::intersection
 147
 148
 149 #ifndef DOXYGEN_NO_DETAIL
 150 namespace detail { namespace intersection
 151 {
 152
 153 /*!
 154     \brief Clips a linestring with a box
 155     \details A linestring is intersected (clipped) by the specified box
 156     and the resulting linestring, or pieces of linestrings, are sent to the specified output operator.
 157     \tparam OutputLinestring type of the output linestrings
 158     \tparam OutputIterator an output iterator which outputs linestrings
 159     \tparam Linestring linestring-type, for example a vector of points, matching the output-iterator type,
 160          the points should also match the input-iterator type
 161     \tparam Box box type
 162     \tparam Strategy strategy, a clipping strategy which should implement the methods "clip_segment" and "apply"
 163 */
 164 template
 165 <
 166     typename OutputLinestring,
 167     typename OutputIterator,
 168     typename Range,
 169     typename RobustPolicy,
 170     typename Box,
 171     typename Strategy
 172 >
 173 OutputIterator clip_range_with_box(Box const& b, Range const& range,
 174             RobustPolicy const&,
 175             OutputIterator out, Strategy const& strategy)
 176 {
 177     if (boost::begin(range) == boost::end(range))
 178     {
 179         return out;
 180     }
 181
 182     typedef typename point_type<OutputLinestring>::type point_type;
 183
 184     OutputLinestring line_out;
 185
 186     typedef typename boost::range_iterator<Range const>::type iterator_type;
 187     iterator_type vertex = boost::begin(range);
 188     for(iterator_type previous = vertex++;
 189             vertex != boost::end(range);
 190             ++previous, ++vertex)
 191     {
 192         point_type p1, p2;
 193         geometry::convert(*previous, p1);
 194         geometry::convert(*vertex, p2);
 195
 196         // Clip the segment. Five situations:
 197         // 1. Segment is invisible, finish line if any (shouldn't occur)
 198         // 2. Segment is completely visible. Add (p1)-p2 to line
 199         // 3. Point 1 is invisible (clipped), point 2 is visible. Start new line from p1-p2...
 200         // 4. Point 1 is visible, point 2 is invisible (clipped). End the line with ...p2
 201         // 5. Point 1 and point 2 are both invisible (clipped). Start/finish an independant line p1-p2
 202         //
 203         // This results in:
 204         // a. if p1 is clipped, start new line
 205         // b. if segment is partly or completely visible, add the segment
 206         // c. if p2 is clipped, end the line
 207
 208         bool c1 = false;
 209         bool c2 = false;
 210         model::referring_segment<point_type> s(p1, p2);
 211
 212         if (!strategy.clip_segment(b, s, c1, c2))
 213         {
 214             strategy.apply(line_out, out);
 215         }
 216         else
 217         {
 218             // a. If necessary, finish the line and add a start a new one
 219             if (c1)
 220             {
 221                 strategy.apply(line_out, out);
 222             }
 223
 224             // b. Add p1 only if it is the first point, then add p2
 225             if (boost::empty(line_out))
 226             {
 227                 detail::overlay::append_no_duplicates(line_out, p1, true);
 228             }
 229             detail::overlay::append_no_duplicates(line_out, p2);
 230
 231             // c. If c2 is clipped, finish the line
 232             if (c2)
 233             {
 234                 strategy.apply(line_out, out);
 235             }
 236         }
 237
 238     }
 239
 240     // Add last part
 241     strategy.apply(line_out, out);
 242     return out;
 243 }
 244
 245 }} // namespace detail::intersection
 246 #endif // DOXYGEN_NO_DETAIL
 247
 248 }} // namespace boost::geometry
 249
 250 #endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_CLIP_LINESTRING_HPP