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-2024.
0006 // Modifications copyright (c) 2015-2024 Oracle and/or its affiliates.
0007 // Contributed and/or modified by Vissarion Fysikopoulos, on behalf of Oracle
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     using segment_type = model::referring_segment<Point>;
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     using equals_point_point_strategy_type = strategy::within::cartesian_point_point;
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         using coordinate_type = typename select_coordinate_type<Box, Point>::type;
0103         using calc_type = typename select_most_precise<coordinate_type, double>::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 Box,
0184     typename Strategy
0185 >
0186 OutputIterator clip_range_with_box(Box const& b, Range const& range,
0187                                    OutputIterator out, Strategy const& strategy)
0188 {
0189     if (boost::begin(range) == boost::end(range))
0190     {
0191         return out;
0192     }
0193
0194     using point_type = point_type_t<OutputLinestring>;
0195
0196     OutputLinestring line_out;
0197
0198     auto vertex = boost::begin(range);
0199     for (auto previous = vertex++;
0200             vertex != boost::end(range);
0201             ++previous, ++vertex)
0202     {
0203         point_type p1, p2;
0204         geometry::convert(*previous, p1);
0205         geometry::convert(*vertex, p2);
0206
0207         // Clip the segment. Five situations:
0208         // 1. Segment is invisible, finish line if any (shouldn't occur)
0209         // 2. Segment is completely visible. Add (p1)-p2 to line
0210         // 3. Point 1 is invisible (clipped), point 2 is visible. Start new line from p1-p2...
0211         // 4. Point 1 is visible, point 2 is invisible (clipped). End the line with ...p2
0212         // 5. Point 1 and point 2 are both invisible (clipped). Start/finish an independant line p1-p2
0213         //
0214         // This results in:
0215         // a. if p1 is clipped, start new line
0216         // b. if segment is partly or completely visible, add the segment
0217         // c. if p2 is clipped, end the line
0218
0219         bool c1 = false;
0220         bool c2 = false;
0221         model::referring_segment<point_type> s(p1, p2);
0222
0223         if (!strategy.clip_segment(b, s, c1, c2))
0224         {
0225             strategy.apply(line_out, out);
0226         }
0227         else
0228         {
0229             // a. If necessary, finish the line and add a start a new one
0230             if (c1)
0231             {
0232                 strategy.apply(line_out, out);
0233             }
0234
0235             // b. Add p1 only if it is the first point, then add p2
0236             if (boost::empty(line_out))
0237             {
0238                 detail::overlay::append_with_duplicates(line_out, p1);
0239             }
0240             detail::overlay::append_no_duplicates(line_out, p2,
0241                                                   strategy.get_equals_point_point_strategy());
0242
0243             // c. If c2 is clipped, finish the line
0244             if (c2)
0245             {
0246                 strategy.apply(line_out, out);
0247             }
0248         }
0249
0250     }
0251
0252     // Add last part
0253     strategy.apply(line_out, out);
0254     return out;
0255 }
0256
0257 }} // namespace detail::intersection
0258 #endif // DOXYGEN_NO_DETAIL
0259
0260 }} // namespace boost::geometry
0261
0262 #endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_CLIP_LINESTRING_HPP