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

source code of boost/libs/geometry/include/boost/geometry/algorithms/detail/overlay/pointlike_linear.hpp