detail/overlay/clip_linestring.hpp

0001 // Boost.Geometry (aka GGL, Generic Geometry Library)
0002
0003 // Copyright (c) 2007-2015 Barend Gehrels, Amsterdam, the Netherlands.
0004
0005 // This file was modified by Oracle on 2015-2020.
0006 // Modifications copyright (c) 2015-2020 Oracle and/or its affiliates.
0007
0008 // Contributed and/or modified by Menelaos Karavelas, on behalf of Oracle
0009 // Contributed and/or modified by Adam Wulkiewicz, on behalf of Oracle
0010
0011 // Use, modification and distribution is subject to the Boost Software License,
0012 // Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
0013 // http://www.boost.org/LICENSE_1_0.txt)
0014
0015 #ifndef BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_CLIP_LINESTRING_HPP
0016 #define BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_CLIP_LINESTRING_HPP
0017
0018 #include <boost/range/begin.hpp>
0019 #include <boost/range/empty.hpp>
0020 #include <boost/range/end.hpp>
0021
0022 #include <boost/geometry/algorithms/clear.hpp>
0023 #include <boost/geometry/algorithms/convert.hpp>
0024
0025 #include <boost/geometry/algorithms/detail/overlay/append_no_duplicates.hpp>
0026
0027 #include <boost/geometry/util/select_coordinate_type.hpp>
0028 #include <boost/geometry/geometries/segment.hpp>
0029
0030 #include <boost/geometry/strategies/cartesian/point_in_point.hpp>
0031
0032 namespace boost { namespace geometry
0033 {
0034
0035 namespace strategy { namespace intersection
0036 {
0037
0038 /*!
0039     \brief Strategy: line clipping algorithm after Liang Barsky
0040     \ingroup overlay
0041     \details The Liang-Barsky line clipping algorithm clips a line with a clipping box.
0042     It is slightly adapted in the sense that it returns which points are clipped
0043     \tparam B input box type of clipping box
0044     \tparam P input/output point-type of segments to be clipped
0045     \note The algorithm is currently only implemented for 2D Cartesian points
0046     \note Though it is implemented in namespace strategy, and theoretically another
0047         strategy could be used, it is not (yet) updated to the general strategy concepts,
0048         and not (yet) splitted into a file in folder strategies
0049     \author Barend Gehrels, and the following recourses
0050     - A tutorial: http://www.skytopia.com/project/articles/compsci/clipping.html
0051     - a German applet (link broken): http://ls7-www.cs.uni-dortmund.de/students/projectgroups/acit/lineclip.shtml
0052 */
0053 template<typename Box, typename Point>
0054 class liang_barsky
0055 {
0056 private:
0057     typedef model::referring_segment<Point> segment_type;
0058
0059     template <typename CoordinateType, typename CalcType>
0060     inline bool check_edge(CoordinateType const& p, CoordinateType const& q, CalcType& t1, CalcType& t2) const
0061     {
0062         bool visible = true;
0063
0064         if(p < 0)
0065         {
0066             CalcType const r = static_cast<CalcType>(q) / p;
0067             if (r > t2)
0068                 visible = false;
0069             else if (r > t1)
0070                 t1 = r;
0071         }
0072         else if(p > 0)
0073         {
0074             CalcType const r = static_cast<CalcType>(q) / p;
0075             if (r < t1)
0076                 visible = false;
0077             else if (r < t2)
0078                 t2 = r;
0079         }
0080         else
0081         {
0082             if (q < 0)
0083                 visible = false;
0084         }
0085
0086         return visible;
0087     }
0088
0089 public:
0090
0091 // TODO: Temporary, this strategy should be moved, it is cartesian-only
0092
0093     typedef strategy::within::cartesian_point_point equals_point_point_strategy_type;
0094
0095     static inline equals_point_point_strategy_type get_equals_point_point_strategy()
0096     {
0097         return equals_point_point_strategy_type();
0098     }
0099
0100     inline bool clip_segment(Box const& b, segment_type& s, bool& sp1_clipped, bool& sp2_clipped) const
0101     {
0102         typedef typename select_coordinate_type<Box, Point>::type coordinate_type;
0103         typedef typename select_most_precise<coordinate_type, double>::type calc_type;
0104
0105         calc_type t1 = 0;
0106         calc_type t2 = 1;
0107
0108         coordinate_type const dx = get<1, 0>(s) - get<0, 0>(s);
0109         coordinate_type const dy = get<1, 1>(s) - get<0, 1>(s);
0110
0111         coordinate_type const p1 = -dx;
0112         coordinate_type const p2 = dx;
0113         coordinate_type const p3 = -dy;
0114         coordinate_type const p4 = dy;
0115
0116         coordinate_type const q1 = get<0, 0>(s) - get<min_corner, 0>(b);
0117         coordinate_type const q2 = get<max_corner, 0>(b) - get<0, 0>(s);
0118         coordinate_type const q3 = get<0, 1>(s) - get<min_corner, 1>(b);
0119         coordinate_type const q4 = get<max_corner, 1>(b) - get<0, 1>(s);
0120
0121         if (check_edge(p1, q1, t1, t2)      // left
0122             && check_edge(p2, q2, t1, t2)   // right
0123             && check_edge(p3, q3, t1, t2)   // bottom
0124             && check_edge(p4, q4, t1, t2))   // top
0125         {
0126             sp1_clipped = t1 > 0;
0127             sp2_clipped = t2 < 1;
0128
0129             if (sp2_clipped)
0130             {
0131                 set<1, 0>(s, get<0, 0>(s) + t2 * dx);
0132                 set<1, 1>(s, get<0, 1>(s) + t2 * dy);
0133             }
0134
0135             if(sp1_clipped)
0136             {
0137                 set<0, 0>(s, get<0, 0>(s) + t1 * dx);
0138                 set<0, 1>(s, get<0, 1>(s) + t1 * dy);
0139             }
0140
0141             return true;
0142         }
0143
0144         return false;
0145     }
0146
0147     template<typename Linestring, typename OutputIterator>
0148     inline void apply(Linestring& line_out, OutputIterator out) const
0149     {
0150         if (!boost::empty(line_out))
0151         {
0152             *out = line_out;
0153             ++out;
0154             geometry::clear(line_out);
0155         }
0156     }
0157 };
0158
0159
0160 }} // namespace strategy::intersection
0161
0162
0163 #ifndef DOXYGEN_NO_DETAIL
0164 namespace detail { namespace intersection
0165 {
0166
0167 /*!
0168     \brief Clips a linestring with a box
0169     \details A linestring is intersected (clipped) by the specified box
0170     and the resulting linestring, or pieces of linestrings, are sent to the specified output operator.
0171     \tparam OutputLinestring type of the output linestrings
0172     \tparam OutputIterator an output iterator which outputs linestrings
0173     \tparam Linestring linestring-type, for example a vector of points, matching the output-iterator type,
0174          the points should also match the input-iterator type
0175     \tparam Box box type
0176     \tparam Strategy strategy, a clipping strategy which should implement the methods "clip_segment" and "apply"
0177 */
0178 template
0179 <
0180     typename OutputLinestring,
0181     typename OutputIterator,
0182     typename Range,
0183     typename RobustPolicy,
0184     typename Box,
0185     typename Strategy
0186 >
0187 OutputIterator clip_range_with_box(Box const& b, Range const& range,
0188             RobustPolicy const&,
0189             OutputIterator out, Strategy const& strategy)
0190 {
0191     if (boost::begin(range) == boost::end(range))
0192     {
0193         return out;
0194     }
0195
0196     typedef typename point_type<OutputLinestring>::type point_type;
0197
0198     OutputLinestring line_out;
0199
0200     auto vertex = boost::begin(range);
0201     for (auto previous = vertex++;
0202             vertex != boost::end(range);
0203             ++previous, ++vertex)
0204     {
0205         point_type p1, p2;
0206         geometry::convert(*previous, p1);
0207         geometry::convert(*vertex, p2);
0208
0209         // Clip the segment. Five situations:
0210         // 1. Segment is invisible, finish line if any (shouldn't occur)
0211         // 2. Segment is completely visible. Add (p1)-p2 to line
0212         // 3. Point 1 is invisible (clipped), point 2 is visible. Start new line from p1-p2...
0213         // 4. Point 1 is visible, point 2 is invisible (clipped). End the line with ...p2
0214         // 5. Point 1 and point 2 are both invisible (clipped). Start/finish an independant line p1-p2
0215         //
0216         // This results in:
0217         // a. if p1 is clipped, start new line
0218         // b. if segment is partly or completely visible, add the segment
0219         // c. if p2 is clipped, end the line
0220
0221         bool c1 = false;
0222         bool c2 = false;
0223         model::referring_segment<point_type> s(p1, p2);
0224
0225         if (!strategy.clip_segment(b, s, c1, c2))
0226         {
0227             strategy.apply(line_out, out);
0228         }
0229         else
0230         {
0231             // a. If necessary, finish the line and add a start a new one
0232             if (c1)
0233             {
0234                 strategy.apply(line_out, out);
0235             }
0236
0237             // b. Add p1 only if it is the first point, then add p2
0238             if (boost::empty(line_out))
0239             {
0240                 detail::overlay::append_with_duplicates(line_out, p1);
0241             }
0242             detail::overlay::append_no_duplicates(line_out, p2,
0243                                                   strategy.get_equals_point_point_strategy());
0244
0245             // c. If c2 is clipped, finish the line
0246             if (c2)
0247             {
0248                 strategy.apply(line_out, out);
0249             }
0250         }
0251
0252     }
0253
0254     // Add last part
0255     strategy.apply(line_out, out);
0256     return out;
0257 }
0258
0259 }} // namespace detail::intersection
0260 #endif // DOXYGEN_NO_DETAIL
0261
0262 }} // namespace boost::geometry
0263
0264 #endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_CLIP_LINESTRING_HPP