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