1 // Boost.Geometry (aka GGL, Generic Geometry Library)
2 
3 // Copyright (c) 2017 Adam Wulkiewicz, Lodz, Poland.
4 
5 // Copyright (c) 2015-2019, Oracle and/or its affiliates.
6 
7 // Contributed and/or modified by Menelaos Karavelas, on behalf of Oracle
8 // Contributed and/or modified by Adam Wulkiewicz, on behalf of Oracle
9 
10 // Licensed under the Boost Software License version 1.0.
11 // http://www.boost.org/users/license.html
12 
13 
14 #ifndef BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_POINTLIKE_LINEAR_HPP
15 #define BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_POINTLIKE_LINEAR_HPP
16 
17 #include <iterator>
18 #include <vector>
19 
20 #include <boost/range.hpp>
21 
22 #include <boost/geometry/core/tags.hpp>
23 
24 #include <boost/geometry/geometries/box.hpp>
25 
26 #include <boost/geometry/iterators/segment_iterator.hpp>
27 
28 #include <boost/geometry/algorithms/disjoint.hpp>
29 #include <boost/geometry/algorithms/envelope.hpp>
30 #include <boost/geometry/algorithms/expand.hpp>
31 #include <boost/geometry/algorithms/not_implemented.hpp>
32 
33 #include <boost/geometry/algorithms/detail/not.hpp>
34 #include <boost/geometry/algorithms/detail/partition.hpp>
35 #include <boost/geometry/algorithms/detail/disjoint/point_geometry.hpp>
36 #include <boost/geometry/algorithms/detail/equals/point_point.hpp>
37 #include <boost/geometry/algorithms/detail/overlay/overlay_type.hpp>
38 #include <boost/geometry/algorithms/detail/overlay/pointlike_pointlike.hpp>
39 
40 
41 namespace boost { namespace geometry
42 {
43 
44 
45 #ifndef DOXYGEN_NO_DETAIL
46 namespace detail { namespace overlay
47 {
48 
49 
50 // action struct for pointlike-linear difference/intersection
51 // it works the same as its pointlike-pointlike counterpart, hence the
52 // derivation
53 template <typename PointOut, overlay_type OverlayType>
54 struct action_selector_pl_l
55     : action_selector_pl_pl<PointOut, OverlayType>
56 {};
57 
58 // difference/intersection of point-linear
59 template
60 <
61     typename Point,
62     typename Linear,
63     typename PointOut,
64     overlay_type OverlayType,
65     typename Policy
66 >
67 struct point_linear_point
68 {
69     template <typename RobustPolicy, typename OutputIterator, typename Strategy>
applyboost::geometry::detail::overlay::point_linear_point70     static inline OutputIterator apply(Point const& point,
71                                        Linear const& linear,
72                                        RobustPolicy const&,
73                                        OutputIterator oit,
74                                        Strategy const& strategy)
75     {
76         action_selector_pl_l
77             <
78                 PointOut, OverlayType
79             >::apply(point, Policy::apply(point, linear, strategy), oit);
80         return oit;
81     }
82 };
83 
84 // difference/intersection of multipoint-segment
85 template
86 <
87     typename MultiPoint,
88     typename Segment,
89     typename PointOut,
90     overlay_type OverlayType,
91     typename Policy
92 >
93 struct multipoint_segment_point
94 {
95     template <typename RobustPolicy, typename OutputIterator, typename Strategy>
applyboost::geometry::detail::overlay::multipoint_segment_point96     static inline OutputIterator apply(MultiPoint const& multipoint,
97                                        Segment const& segment,
98                                        RobustPolicy const&,
99                                        OutputIterator oit,
100                                        Strategy const& strategy)
101     {
102         for (typename boost::range_iterator<MultiPoint const>::type
103                  it = boost::begin(multipoint);
104              it != boost::end(multipoint);
105              ++it)
106         {
107             action_selector_pl_l
108                 <
109                     PointOut, OverlayType
110                 >::apply(*it, Policy::apply(*it, segment, strategy), oit);
111         }
112 
113         return oit;
114     }
115 };
116 
117 
118 // difference/intersection of multipoint-linear
119 template
120 <
121     typename MultiPoint,
122     typename Linear,
123     typename PointOut,
124     overlay_type OverlayType,
125     typename Policy
126 >
127 class multipoint_linear_point
128 {
129 private:
130     // structs for partition -- start
131     template <typename ExpandPointStrategy>
132     struct expand_box_point
133     {
134         template <typename Box, typename Point>
applyboost::geometry::detail::overlay::multipoint_linear_point::expand_box_point135         static inline void apply(Box& total, Point const& point)
136         {
137             geometry::expand(total, point, ExpandPointStrategy());
138         }
139     };
140 
141     template <typename EnvelopeStrategy>
142     struct expand_box_segment
143     {
expand_box_segmentboost::geometry::detail::overlay::multipoint_linear_point::expand_box_segment144         explicit expand_box_segment(EnvelopeStrategy const& strategy)
145             : m_strategy(strategy)
146         {}
147 
148         template <typename Box, typename Segment>
applyboost::geometry::detail::overlay::multipoint_linear_point::expand_box_segment149         inline void apply(Box& total, Segment const& segment) const
150         {
151             geometry::expand(total,
152                              geometry::return_envelope<Box>(segment, m_strategy),
153                              m_strategy.get_box_expand_strategy());
154         }
155 
156         EnvelopeStrategy const& m_strategy;
157     };
158 
159     template <typename DisjointPointBoxStrategy>
160     struct overlaps_box_point
161     {
162         template <typename Box, typename Point>
applyboost::geometry::detail::overlay::multipoint_linear_point::overlaps_box_point163         static inline bool apply(Box const& box, Point const& point)
164         {
165             return ! geometry::disjoint(point, box, DisjointPointBoxStrategy());
166         }
167     };
168 
169     template <typename DisjointStrategy>
170     struct overlaps_box_segment
171     {
overlaps_box_segmentboost::geometry::detail::overlay::multipoint_linear_point::overlaps_box_segment172         explicit overlaps_box_segment(DisjointStrategy const& strategy)
173             : m_strategy(strategy)
174         {}
175 
176         template <typename Box, typename Segment>
applyboost::geometry::detail::overlay::multipoint_linear_point::overlaps_box_segment177         inline bool apply(Box const& box, Segment const& segment) const
178         {
179             return ! geometry::disjoint(segment, box, m_strategy);
180         }
181 
182         DisjointStrategy const& m_strategy;
183     };
184 
185     template <typename OutputIterator, typename Strategy>
186     class item_visitor_type
187     {
188     public:
item_visitor_type(OutputIterator & oit,Strategy const & strategy)189         item_visitor_type(OutputIterator& oit, Strategy const& strategy)
190             : m_oit(oit)
191             , m_strategy(strategy)
192         {}
193 
194         template <typename Item1, typename Item2>
apply(Item1 const & item1,Item2 const & item2)195         inline bool apply(Item1 const& item1, Item2 const& item2)
196         {
197             action_selector_pl_l
198                 <
199                     PointOut, overlay_intersection
200                 >::apply(item1, Policy::apply(item1, item2, m_strategy), m_oit);
201 
202             return true;
203         }
204 
205     private:
206         OutputIterator& m_oit;
207         Strategy const& m_strategy;
208     };
209     // structs for partition -- end
210 
211     class segment_range
212     {
213     public:
214         typedef geometry::segment_iterator<Linear const> const_iterator;
215         typedef const_iterator iterator;
216 
segment_range(Linear const & linear)217         segment_range(Linear const& linear)
218             : m_linear(linear)
219         {}
220 
begin() const221         const_iterator begin() const
222         {
223             return geometry::segments_begin(m_linear);
224         }
225 
end() const226         const_iterator end() const
227         {
228             return geometry::segments_end(m_linear);
229         }
230 
231     private:
232         Linear const& m_linear;
233     };
234 
235     template <typename OutputIterator, typename Strategy>
get_common_points(MultiPoint const & multipoint,Linear const & linear,OutputIterator oit,Strategy const & strategy)236     static inline OutputIterator get_common_points(MultiPoint const& multipoint,
237                                                    Linear const& linear,
238                                                    OutputIterator oit,
239                                                    Strategy const& strategy)
240     {
241         item_visitor_type<OutputIterator, Strategy> item_visitor(oit, strategy);
242 
243         typedef typename Strategy::envelope_strategy_type envelope_strategy_type;
244         typedef typename Strategy::disjoint_strategy_type disjoint_strategy_type;
245         typedef typename Strategy::disjoint_point_box_strategy_type disjoint_point_box_strategy_type;
246         typedef typename Strategy::expand_point_strategy_type expand_point_strategy_type;
247 
248         // TODO: disjoint Segment/Box may be called in partition multiple times
249         // possibly for non-cartesian segments which could be slow. We should consider
250         // passing a range of bounding boxes of segments after calculating them once.
251         // Alternatively instead of a range of segments a range of Segment/Envelope pairs
252         // should be passed, where envelope would be lazily calculated when needed the first time
253         geometry::partition
254             <
255                 geometry::model::box
256                     <
257                         typename boost::range_value<MultiPoint>::type
258                     >
259             >::apply(multipoint, segment_range(linear), item_visitor,
260                      expand_box_point<expand_point_strategy_type>(),
261                      overlaps_box_point<disjoint_point_box_strategy_type>(),
262                      expand_box_segment<envelope_strategy_type>(strategy.get_envelope_strategy()),
263                      overlaps_box_segment<disjoint_strategy_type>(strategy.get_disjoint_strategy()));
264 
265         return oit;
266     }
267 
268 public:
269     template <typename RobustPolicy, typename OutputIterator, typename Strategy>
apply(MultiPoint const & multipoint,Linear const & linear,RobustPolicy const & robust_policy,OutputIterator oit,Strategy const & strategy)270     static inline OutputIterator apply(MultiPoint const& multipoint,
271                                        Linear const& linear,
272                                        RobustPolicy const& robust_policy,
273                                        OutputIterator oit,
274                                        Strategy const& strategy)
275     {
276         typedef std::vector
277             <
278                 typename boost::range_value<MultiPoint>::type
279             > point_vector_type;
280 
281         point_vector_type common_points;
282 
283         // compute the common points
284         get_common_points(multipoint, linear,
285                           std::back_inserter(common_points),
286                           strategy);
287 
288         return multipoint_multipoint_point
289             <
290                 MultiPoint, point_vector_type, PointOut, OverlayType
291             >::apply(multipoint, common_points, robust_policy, oit, strategy);
292     }
293 };
294 
295 
296 }} // namespace detail::overlay
297 #endif // DOXYGEN_NO_DETAIL
298 
299 
300 #ifndef DOXYGEN_NO_DISPATCH
301 namespace detail_dispatch { namespace overlay
302 {
303 
304 // dispatch struct for pointlike-linear difference/intersection computation
305 template
306 <
307     typename PointLike,
308     typename Linear,
309     typename PointOut,
310     overlay_type OverlayType,
311     typename Tag1,
312     typename Tag2
313 >
314 struct pointlike_linear_point
315     : not_implemented<PointLike, Linear, PointOut>
316 {};
317 
318 
319 template
320 <
321     typename Point,
322     typename Linear,
323     typename PointOut,
324     overlay_type OverlayType
325 >
326 struct pointlike_linear_point
327     <
328         Point, Linear, PointOut, OverlayType, point_tag, linear_tag
329     > : detail::overlay::point_linear_point
330         <
331             Point, Linear, PointOut, OverlayType,
332             detail::not_<detail::disjoint::reverse_covered_by>
333         >
334 {};
335 
336 
337 template
338 <
339     typename Point,
340     typename Segment,
341     typename PointOut,
342     overlay_type OverlayType
343 >
344 struct pointlike_linear_point
345     <
346         Point, Segment, PointOut, OverlayType, point_tag, segment_tag
347     > : detail::overlay::point_linear_point
348         <
349             Point, Segment, PointOut, OverlayType,
350             detail::not_<detail::disjoint::reverse_covered_by>
351         >
352 {};
353 
354 
355 template
356 <
357     typename MultiPoint,
358     typename Linear,
359     typename PointOut,
360     overlay_type OverlayType
361 >
362 struct pointlike_linear_point
363     <
364         MultiPoint, Linear, PointOut, OverlayType, multi_point_tag, linear_tag
365     > : detail::overlay::multipoint_linear_point
366         <
367             MultiPoint, Linear, PointOut, OverlayType,
368             detail::not_<detail::disjoint::reverse_covered_by>
369         >
370 {};
371 
372 
373 template
374 <
375     typename MultiPoint,
376     typename Segment,
377     typename PointOut,
378     overlay_type OverlayType
379 >
380 struct pointlike_linear_point
381     <
382         MultiPoint, Segment, PointOut, OverlayType, multi_point_tag, segment_tag
383     > : detail::overlay::multipoint_segment_point
384         <
385             MultiPoint, Segment, PointOut, OverlayType,
386             detail::not_<detail::disjoint::reverse_covered_by>
387         >
388 {};
389 
390 
391 }} // namespace detail_dispatch::overlay
392 #endif // DOXYGEN_NO_DISPATCH
393 
394 
395 }} // namespace boost::geometry
396 
397 
398 #endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_POINTLIKE_LINEAR_HPP
399