]>
Commit | Line | Data |
---|---|---|
7c673cae FG |
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> | |
68 | 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> | |
94 | 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> | |
132 | 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> | |
142 | 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: | |
152 | item_visitor_type(OutputIterator& oit) : m_oit(oit) {} | |
153 | ||
154 | template <typename Item1, typename 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 | ||
174 | segment_range(Linear const& linear) | |
175 | : m_linear(linear) | |
176 | {} | |
177 | ||
178 | const_iterator begin() const | |
179 | { | |
180 | return geometry::segments_begin(m_linear); | |
181 | } | |
182 | ||
183 | 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> | |
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> | |
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 |