1 // Boost.Geometry (aka GGL, Generic Geometry Library)
2 
3 // Copyright (c) 2015, Oracle and/or its affiliates.
4 
5 // Licensed under the Boost Software License version 1.0.
6 // http://www.boost.org/users/license.html
7 
8 // Contributed and/or modified by Menelaos Karavelas, on behalf of Oracle
9 
10 
11 #ifndef BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_POINTLIKE_LINEAR_HPP
12 #define BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_POINTLIKE_LINEAR_HPP
13 
14 #include <iterator>
15 #include <vector>
16 
17 #include <boost/range.hpp>
18 
19 #include <boost/geometry/core/tags.hpp>
20 
21 #include <boost/geometry/geometries/box.hpp>
22 
23 #include <boost/geometry/iterators/segment_iterator.hpp>
24 
25 #include <boost/geometry/algorithms/disjoint.hpp>
26 #include <boost/geometry/algorithms/envelope.hpp>
27 #include <boost/geometry/algorithms/expand.hpp>
28 #include <boost/geometry/algorithms/not_implemented.hpp>
29 
30 #include <boost/geometry/algorithms/detail/not.hpp>
31 #include <boost/geometry/algorithms/detail/partition.hpp>
32 #include <boost/geometry/algorithms/detail/relate/less.hpp>
33 #include <boost/geometry/algorithms/detail/disjoint/point_geometry.hpp>
34 #include <boost/geometry/algorithms/detail/equals/point_point.hpp>
35 #include <boost/geometry/algorithms/detail/overlay/overlay_type.hpp>
36 #include <boost/geometry/algorithms/detail/overlay/pointlike_pointlike.hpp>
37 
38 
39 namespace boost { namespace geometry
40 {
41 
42 
43 #ifndef DOXYGEN_NO_DETAIL
44 namespace detail { namespace overlay
45 {
46 
47 
48 // action struct for pointlike-linear difference/intersection
49 // it works the same as its pointlike-pointlike counterpart, hence the
50 // derivation
51 template <typename PointOut, overlay_type OverlayType>
52 struct action_selector_pl_l
53     : action_selector_pl_pl<PointOut, OverlayType>
54 {};
55 
56 // difference/intersection of point-linear
57 template
58 <
59     typename Point,
60     typename Linear,
61     typename PointOut,
62     overlay_type OverlayType,
63     typename Policy
64 >
65 struct point_linear_point
66 {
67     template <typename RobustPolicy, typename OutputIterator, typename Strategy>
applyboost::geometry::detail::overlay::point_linear_point68     static inline OutputIterator apply(Point const& point,
69                                        Linear const& linear,
70                                        RobustPolicy const&,
71                                        OutputIterator oit,
72                                        Strategy const&)
73     {
74         action_selector_pl_l
75             <
76                 PointOut, OverlayType
77             >::apply(point, Policy::apply(point, linear), oit);
78         return oit;
79     }
80 };
81 
82 // difference/intersection of multipoint-segment
83 template
84 <
85     typename MultiPoint,
86     typename Segment,
87     typename PointOut,
88     overlay_type OverlayType,
89     typename Policy
90 >
91 struct multipoint_segment_point
92 {
93     template <typename RobustPolicy, typename OutputIterator, typename Strategy>
applyboost::geometry::detail::overlay::multipoint_segment_point94     static inline OutputIterator apply(MultiPoint const& multipoint,
95                                        Segment const& segment,
96                                        RobustPolicy const&,
97                                        OutputIterator oit,
98                                        Strategy const&)
99     {
100         for (typename boost::range_iterator<MultiPoint const>::type
101                  it = boost::begin(multipoint);
102              it != boost::end(multipoint);
103              ++it)
104         {
105             action_selector_pl_l
106                 <
107                     PointOut, OverlayType
108                 >::apply(*it, Policy::apply(*it, segment), oit);
109         }
110 
111         return oit;
112     }
113 };
114 
115 
116 // difference/intersection of multipoint-linear
117 template
118 <
119     typename MultiPoint,
120     typename Linear,
121     typename PointOut,
122     overlay_type OverlayType,
123     typename Policy
124 >
125 class multipoint_linear_point
126 {
127 private:
128     // structs for partition -- start
129     struct expand_box
130     {
131         template <typename Box, typename Geometry>
applyboost::geometry::detail::overlay::multipoint_linear_point::expand_box132         static inline void apply(Box& total, Geometry const& geometry)
133         {
134             geometry::expand(total, geometry::return_envelope<Box>(geometry));
135         }
136 
137     };
138 
139     struct overlaps_box
140     {
141         template <typename Box, typename Geometry>
applyboost::geometry::detail::overlay::multipoint_linear_point::overlaps_box142         static inline bool apply(Box const& box, Geometry const& geometry)
143         {
144             return ! geometry::disjoint(geometry, box);
145         }
146     };
147 
148     template <typename OutputIterator>
149     class item_visitor_type
150     {
151     public:
item_visitor_type(OutputIterator & oit)152         item_visitor_type(OutputIterator& oit) : m_oit(oit) {}
153 
154         template <typename Item1, typename Item2>
apply(Item1 const & item1,Item2 const & item2)155         inline void apply(Item1 const& item1, Item2 const& item2)
156         {
157             action_selector_pl_l
158                 <
159                     PointOut, overlay_intersection
160                 >::apply(item1, Policy::apply(item1, item2), m_oit);
161         }
162 
163     private:
164         OutputIterator& m_oit;
165     };
166     // structs for partition -- end
167 
168     class segment_range
169     {
170     public:
171         typedef geometry::segment_iterator<Linear const> const_iterator;
172         typedef const_iterator iterator;
173 
segment_range(Linear const & linear)174         segment_range(Linear const& linear)
175             : m_linear(linear)
176         {}
177 
begin() const178         const_iterator begin() const
179         {
180             return geometry::segments_begin(m_linear);
181         }
182 
end() const183         const_iterator end() const
184         {
185             return geometry::segments_end(m_linear);
186         }
187 
188     private:
189         Linear const& m_linear;
190     };
191 
192     template <typename OutputIterator>
get_common_points(MultiPoint const & multipoint,Linear const & linear,OutputIterator oit)193     static inline OutputIterator get_common_points(MultiPoint const& multipoint,
194                                                    Linear const& linear,
195                                                    OutputIterator oit)
196     {
197         item_visitor_type<OutputIterator> item_visitor(oit);
198 
199         segment_range rng(linear);
200 
201         geometry::partition
202             <
203                 geometry::model::box
204                     <
205                         typename boost::range_value<MultiPoint>::type
206                     >,
207                 expand_box,
208                 overlaps_box
209             >::apply(multipoint, rng, item_visitor);
210 
211         return oit;
212     }
213 
214 public:
215     template <typename RobustPolicy, typename OutputIterator, typename Strategy>
apply(MultiPoint const & multipoint,Linear const & linear,RobustPolicy const & robust_policy,OutputIterator oit,Strategy const & strategy)216     static inline OutputIterator apply(MultiPoint const& multipoint,
217                                        Linear const& linear,
218                                        RobustPolicy const& robust_policy,
219                                        OutputIterator oit,
220                                        Strategy const& strategy)
221     {
222         typedef std::vector
223             <
224                 typename boost::range_value<MultiPoint>::type
225             > point_vector_type;
226 
227         point_vector_type common_points;
228 
229         // compute the common points
230         get_common_points(multipoint, linear,
231                           std::back_inserter(common_points));
232 
233         return multipoint_multipoint_point
234             <
235                 MultiPoint, point_vector_type, PointOut, OverlayType
236             >::apply(multipoint, common_points, robust_policy, oit, strategy);
237     }
238 };
239 
240 
241 }} // namespace detail::overlay
242 #endif // DOXYGEN_NO_DETAIL
243 
244 
245 #ifndef DOXYGEN_NO_DISPATCH
246 namespace detail_dispatch { namespace overlay
247 {
248 
249 // dispatch struct for pointlike-linear difference/intersection computation
250 template
251 <
252     typename PointLike,
253     typename Linear,
254     typename PointOut,
255     overlay_type OverlayType,
256     typename Tag1,
257     typename Tag2
258 >
259 struct pointlike_linear_point
260     : not_implemented<PointLike, Linear, PointOut>
261 {};
262 
263 
264 template
265 <
266     typename Point,
267     typename Linear,
268     typename PointOut,
269     overlay_type OverlayType
270 >
271 struct pointlike_linear_point
272     <
273         Point, Linear, PointOut, OverlayType, point_tag, linear_tag
274     > : detail::overlay::point_linear_point
275         <
276             Point, Linear, PointOut, OverlayType,
277             detail::not_<detail::disjoint::reverse_covered_by>
278         >
279 {};
280 
281 
282 template
283 <
284     typename Point,
285     typename Segment,
286     typename PointOut,
287     overlay_type OverlayType
288 >
289 struct pointlike_linear_point
290     <
291         Point, Segment, PointOut, OverlayType, point_tag, segment_tag
292     > : detail::overlay::point_linear_point
293         <
294             Point, Segment, PointOut, OverlayType,
295             detail::not_<detail::disjoint::reverse_covered_by>
296         >
297 {};
298 
299 
300 template
301 <
302     typename MultiPoint,
303     typename Linear,
304     typename PointOut,
305     overlay_type OverlayType
306 >
307 struct pointlike_linear_point
308     <
309         MultiPoint, Linear, PointOut, OverlayType, multi_point_tag, linear_tag
310     > : detail::overlay::multipoint_linear_point
311         <
312             MultiPoint, Linear, PointOut, OverlayType,
313             detail::not_<detail::disjoint::reverse_covered_by>
314         >
315 {};
316 
317 
318 template
319 <
320     typename MultiPoint,
321     typename Segment,
322     typename PointOut,
323     overlay_type OverlayType
324 >
325 struct pointlike_linear_point
326     <
327         MultiPoint, Segment, PointOut, OverlayType, multi_point_tag, segment_tag
328     > : detail::overlay::multipoint_segment_point
329         <
330             MultiPoint, Segment, PointOut, OverlayType,
331             detail::not_<detail::disjoint::reverse_covered_by>
332         >
333 {};
334 
335 
336 }} // namespace detail_dispatch::overlay
337 #endif // DOXYGEN_NO_DISPATCH
338 
339 
340 }} // namespace boost::geometry
341 
342 
343 #endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_POINTLIKE_LINEAR_HPP
344