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