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