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>
check_edge(CoordinateType const & p,CoordinateType const & q,CalcType & t1,CalcType & t2) const55 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
clip_segment(Box const & b,segment_type & s,bool & sp1_clipped,bool & sp2_clipped) const86 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>
apply(Linestring & line_out,OutputIterator out) const134 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 >
clip_range_with_box(Box const & b,Range const & range,RobustPolicy const &,OutputIterator out,Strategy const & strategy)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
251