]>
Commit | Line | Data |
---|---|---|
7c673cae FG |
1 | // Boost.Geometry (aka GGL, Generic Geometry Library) |
2 | ||
3 | // Copyright (c) 2007-2015 Barend Gehrels, Amsterdam, the Netherlands. | |
4 | // Copyright (c) 2008-2015 Bruno Lalande, Paris, France. | |
5 | // Copyright (c) 2009-2015 Mateusz Loskot, London, UK. | |
6 | // Copyright (c) 2013-2015 Adam Wulkiewicz, Lodz, Poland. | |
7 | ||
92f5a8d4 TL |
8 | // This file was modified by Oracle on 2013, 2014, 2015, 2017, 2019. |
9 | // Modifications copyright (c) 2013-2019, Oracle and/or its affiliates. | |
7c673cae FG |
10 | |
11 | // Contributed and/or modified by Adam Wulkiewicz, on behalf of Oracle | |
12 | ||
13 | // Parts of Boost.Geometry are redesigned from Geodan's Geographic Library | |
14 | // (geolib/GGL), copyright (c) 1995-2010 Geodan, Amsterdam, the Netherlands. | |
15 | ||
16 | // Use, modification and distribution is subject to the Boost Software License, | |
17 | // Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at | |
18 | // http://www.boost.org/LICENSE_1_0.txt) | |
19 | ||
b32b8144 FG |
20 | #ifndef BOOST_GEOMETRY_ALGORITHMS_DETAIL_TOUCHES_IMPLEMENTATION_HPP |
21 | #define BOOST_GEOMETRY_ALGORITHMS_DETAIL_TOUCHES_IMPLEMENTATION_HPP | |
7c673cae FG |
22 | |
23 | ||
7c673cae FG |
24 | #include <boost/geometry/algorithms/detail/for_each_range.hpp> |
25 | #include <boost/geometry/algorithms/detail/overlay/overlay.hpp> | |
26 | #include <boost/geometry/algorithms/detail/overlay/self_turn_points.hpp> | |
b32b8144 FG |
27 | #include <boost/geometry/algorithms/detail/sub_range.hpp> |
28 | #include <boost/geometry/algorithms/detail/relate/relate_impl.hpp> | |
29 | #include <boost/geometry/algorithms/detail/touches/interface.hpp> | |
7c673cae FG |
30 | #include <boost/geometry/algorithms/disjoint.hpp> |
31 | #include <boost/geometry/algorithms/intersects.hpp> | |
32 | #include <boost/geometry/algorithms/num_geometries.hpp> | |
7c673cae | 33 | #include <boost/geometry/algorithms/relate.hpp> |
b32b8144 FG |
34 | |
35 | #include <boost/geometry/policies/robustness/no_rescale_policy.hpp> | |
7c673cae FG |
36 | |
37 | ||
38 | namespace boost { namespace geometry | |
39 | { | |
40 | ||
41 | #ifndef DOXYGEN_NO_DETAIL | |
42 | namespace detail { namespace touches | |
43 | { | |
44 | ||
45 | // Box/Box | |
46 | ||
47 | template | |
48 | < | |
49 | std::size_t Dimension, | |
50 | std::size_t DimensionCount | |
51 | > | |
52 | struct box_box_loop | |
53 | { | |
54 | template <typename Box1, typename Box2> | |
55 | static inline bool apply(Box1 const& b1, Box2 const& b2, bool & touch) | |
56 | { | |
57 | typedef typename coordinate_type<Box1>::type coordinate_type1; | |
58 | typedef typename coordinate_type<Box2>::type coordinate_type2; | |
59 | ||
60 | coordinate_type1 const& min1 = get<min_corner, Dimension>(b1); | |
61 | coordinate_type1 const& max1 = get<max_corner, Dimension>(b1); | |
62 | coordinate_type2 const& min2 = get<min_corner, Dimension>(b2); | |
63 | coordinate_type2 const& max2 = get<max_corner, Dimension>(b2); | |
64 | ||
65 | // TODO assert or exception? | |
66 | //BOOST_GEOMETRY_ASSERT(min1 <= max1 && min2 <= max2); | |
67 | ||
68 | if (max1 < min2 || max2 < min1) | |
69 | { | |
70 | return false; | |
71 | } | |
72 | ||
73 | if (max1 == min2 || max2 == min1) | |
74 | { | |
75 | touch = true; | |
76 | } | |
77 | ||
78 | return box_box_loop | |
79 | < | |
80 | Dimension + 1, | |
81 | DimensionCount | |
82 | >::apply(b1, b2, touch); | |
83 | } | |
84 | }; | |
85 | ||
86 | template | |
87 | < | |
88 | std::size_t DimensionCount | |
89 | > | |
90 | struct box_box_loop<DimensionCount, DimensionCount> | |
91 | { | |
92 | template <typename Box1, typename Box2> | |
93 | static inline bool apply(Box1 const& , Box2 const&, bool &) | |
94 | { | |
95 | return true; | |
96 | } | |
97 | }; | |
98 | ||
99 | struct box_box | |
100 | { | |
b32b8144 FG |
101 | template <typename Box1, typename Box2, typename Strategy> |
102 | static inline bool apply(Box1 const& b1, Box2 const& b2, Strategy const& /*strategy*/) | |
7c673cae FG |
103 | { |
104 | BOOST_STATIC_ASSERT((boost::is_same | |
105 | < | |
106 | typename geometry::coordinate_system<Box1>::type, | |
107 | typename geometry::coordinate_system<Box2>::type | |
108 | >::value | |
109 | )); | |
110 | assert_dimension_equal<Box1, Box2>(); | |
111 | ||
112 | bool touches = false; | |
113 | bool ok = box_box_loop | |
114 | < | |
115 | 0, | |
116 | dimension<Box1>::type::value | |
117 | >::apply(b1, b2, touches); | |
118 | ||
119 | return ok && touches; | |
120 | } | |
121 | }; | |
122 | ||
123 | // Areal/Areal | |
124 | ||
125 | struct areal_interrupt_policy | |
126 | { | |
127 | static bool const enabled = true; | |
128 | bool found_touch; | |
129 | bool found_not_touch; | |
130 | ||
131 | // dummy variable required by self_get_turn_points::get_turns | |
132 | static bool const has_intersections = false; | |
133 | ||
134 | inline bool result() | |
135 | { | |
136 | return found_touch && !found_not_touch; | |
137 | } | |
138 | ||
139 | inline areal_interrupt_policy() | |
140 | : found_touch(false), found_not_touch(false) | |
141 | {} | |
142 | ||
143 | template <typename Range> | |
144 | inline bool apply(Range const& range) | |
145 | { | |
146 | // if already rejected (temp workaround?) | |
147 | if ( found_not_touch ) | |
148 | return true; | |
149 | ||
150 | typedef typename boost::range_iterator<Range const>::type iterator; | |
151 | for ( iterator it = boost::begin(range) ; it != boost::end(range) ; ++it ) | |
152 | { | |
153 | if ( it->has(overlay::operation_intersection) ) | |
154 | { | |
155 | found_not_touch = true; | |
156 | return true; | |
157 | } | |
158 | ||
159 | switch(it->method) | |
160 | { | |
161 | case overlay::method_crosses: | |
162 | found_not_touch = true; | |
163 | return true; | |
164 | case overlay::method_equal: | |
165 | // Segment spatially equal means: at the right side | |
166 | // the polygon internally overlaps. So return false. | |
167 | found_not_touch = true; | |
168 | return true; | |
169 | case overlay::method_touch: | |
170 | case overlay::method_touch_interior: | |
171 | case overlay::method_collinear: | |
172 | if ( ok_for_touch(*it) ) | |
173 | { | |
174 | found_touch = true; | |
175 | } | |
176 | else | |
177 | { | |
178 | found_not_touch = true; | |
179 | return true; | |
180 | } | |
181 | break; | |
182 | case overlay::method_none : | |
183 | case overlay::method_disjoint : | |
184 | case overlay::method_error : | |
185 | break; | |
186 | } | |
187 | } | |
188 | ||
189 | return false; | |
190 | } | |
191 | ||
192 | template <typename Turn> | |
193 | inline bool ok_for_touch(Turn const& turn) | |
194 | { | |
195 | return turn.both(overlay::operation_union) | |
196 | || turn.both(overlay::operation_blocked) | |
197 | || turn.combination(overlay::operation_union, overlay::operation_blocked) | |
198 | ; | |
199 | } | |
200 | }; | |
201 | ||
b32b8144 | 202 | template<typename Geometry, typename PointInRingStrategy> |
7c673cae FG |
203 | struct check_each_ring_for_within |
204 | { | |
205 | bool has_within; | |
206 | Geometry const& m_geometry; | |
b32b8144 | 207 | PointInRingStrategy const& m_strategy; |
7c673cae | 208 | |
b32b8144 | 209 | inline check_each_ring_for_within(Geometry const& g, PointInRingStrategy const& strategy) |
7c673cae FG |
210 | : has_within(false) |
211 | , m_geometry(g) | |
b32b8144 | 212 | , m_strategy(strategy) |
7c673cae FG |
213 | {} |
214 | ||
215 | template <typename Range> | |
216 | inline void apply(Range const& range) | |
217 | { | |
218 | typename geometry::point_type<Range>::type p; | |
219 | geometry::point_on_border(p, range); | |
b32b8144 | 220 | if ( !has_within && geometry::within(p, m_geometry, m_strategy) ) |
7c673cae FG |
221 | { |
222 | has_within = true; | |
223 | } | |
224 | } | |
225 | }; | |
226 | ||
b32b8144 | 227 | template <typename FirstGeometry, typename SecondGeometry, typename IntersectionStrategy> |
7c673cae | 228 | inline bool rings_containing(FirstGeometry const& geometry1, |
b32b8144 FG |
229 | SecondGeometry const& geometry2, |
230 | IntersectionStrategy const& strategy) | |
7c673cae | 231 | { |
b32b8144 FG |
232 | // NOTE: This strategy could be defined inside IntersectionStrategy |
233 | typedef typename IntersectionStrategy::template point_in_geometry_strategy | |
234 | < | |
235 | FirstGeometry, SecondGeometry | |
236 | >::type point_in_ring_strategy_type; | |
237 | ||
238 | point_in_ring_strategy_type point_in_ring_strategy | |
239 | = strategy.template get_point_in_geometry_strategy<FirstGeometry, SecondGeometry>(); | |
240 | ||
241 | check_each_ring_for_within | |
242 | < | |
243 | FirstGeometry, point_in_ring_strategy_type | |
244 | > checker(geometry1, point_in_ring_strategy); | |
7c673cae FG |
245 | geometry::detail::for_each_range(geometry2, checker); |
246 | return checker.has_within; | |
247 | } | |
248 | ||
249 | template <typename Geometry1, typename Geometry2> | |
250 | struct areal_areal | |
251 | { | |
b32b8144 FG |
252 | template <typename IntersectionStrategy> |
253 | static inline bool apply(Geometry1 const& geometry1, | |
254 | Geometry2 const& geometry2, | |
255 | IntersectionStrategy const& strategy) | |
7c673cae | 256 | { |
7c673cae | 257 | typedef typename geometry::point_type<Geometry1>::type point_type; |
92f5a8d4 | 258 | typedef detail::overlay::turn_info<point_type> turn_info; |
7c673cae FG |
259 | |
260 | std::deque<turn_info> turns; | |
261 | detail::touches::areal_interrupt_policy policy; | |
7c673cae FG |
262 | boost::geometry::get_turns |
263 | < | |
264 | detail::overlay::do_reverse<geometry::point_order<Geometry1>::value>::value, | |
265 | detail::overlay::do_reverse<geometry::point_order<Geometry2>::value>::value, | |
266 | detail::overlay::assign_null_policy | |
92f5a8d4 | 267 | >(geometry1, geometry2, strategy, detail::no_rescale_policy(), turns, policy); |
7c673cae FG |
268 | |
269 | return policy.result() | |
b32b8144 FG |
270 | && ! geometry::detail::touches::rings_containing(geometry1, geometry2, strategy) |
271 | && ! geometry::detail::touches::rings_containing(geometry2, geometry1, strategy); | |
7c673cae FG |
272 | } |
273 | }; | |
274 | ||
275 | // P/* | |
276 | ||
277 | struct use_point_in_geometry | |
278 | { | |
b32b8144 FG |
279 | template <typename Point, typename Geometry, typename Strategy> |
280 | static inline bool apply(Point const& point, Geometry const& geometry, Strategy const& strategy) | |
7c673cae | 281 | { |
b32b8144 | 282 | return detail::within::point_in_geometry(point, geometry, strategy) == 0; |
7c673cae FG |
283 | } |
284 | }; | |
285 | ||
b32b8144 | 286 | |
7c673cae FG |
287 | }} |
288 | #endif // DOXYGEN_NO_DETAIL | |
289 | ||
290 | #ifndef DOXYGEN_NO_DISPATCH | |
291 | namespace dispatch { | |
292 | ||
b32b8144 | 293 | // P/P |
7c673cae | 294 | |
92f5a8d4 TL |
295 | template <typename Geometry1, typename Geometry2> |
296 | struct touches<Geometry1, Geometry2, point_tag, point_tag, pointlike_tag, pointlike_tag, false> | |
7c673cae | 297 | { |
b32b8144 FG |
298 | template <typename Strategy> |
299 | static inline bool apply(Geometry1 const& , Geometry2 const& , Strategy const&) | |
7c673cae | 300 | { |
b32b8144 | 301 | return false; |
7c673cae FG |
302 | } |
303 | }; | |
304 | ||
92f5a8d4 TL |
305 | template <typename Geometry1, typename Geometry2> |
306 | struct touches<Geometry1, Geometry2, point_tag, multi_point_tag, pointlike_tag, pointlike_tag, false> | |
307 | { | |
308 | template <typename Strategy> | |
309 | static inline bool apply(Geometry1 const& , Geometry2 const& , Strategy const&) | |
310 | { | |
311 | return false; | |
312 | } | |
313 | }; | |
314 | ||
315 | template <typename Geometry1, typename Geometry2> | |
316 | struct touches<Geometry1, Geometry2, multi_point_tag, multi_point_tag, pointlike_tag, pointlike_tag, false> | |
7c673cae | 317 | { |
b32b8144 FG |
318 | template <typename Strategy> |
319 | static inline bool apply(Geometry1 const&, Geometry2 const&, Strategy const&) | |
7c673cae FG |
320 | { |
321 | return false; | |
322 | } | |
323 | }; | |
324 | ||
92f5a8d4 | 325 | // P/L P/A |
7c673cae FG |
326 | |
327 | template <typename Point, typename Geometry, typename Tag2, typename CastedTag2> | |
328 | struct touches<Point, Geometry, point_tag, Tag2, pointlike_tag, CastedTag2, false> | |
329 | : detail::touches::use_point_in_geometry | |
330 | {}; | |
331 | ||
b32b8144 FG |
332 | template <typename MultiPoint, typename MultiGeometry, typename Tag2, typename CastedTag2> |
333 | struct touches<MultiPoint, MultiGeometry, multi_point_tag, Tag2, pointlike_tag, CastedTag2, false> | |
334 | : detail::relate::relate_impl | |
335 | < | |
336 | detail::de9im::static_mask_touches_type, | |
337 | MultiPoint, | |
338 | MultiGeometry | |
339 | > | |
340 | {}; | |
341 | ||
92f5a8d4 TL |
342 | // L/P A/P |
343 | ||
b32b8144 FG |
344 | template <typename Geometry, typename MultiPoint, typename Tag1, typename CastedTag1> |
345 | struct touches<Geometry, MultiPoint, Tag1, multi_point_tag, CastedTag1, pointlike_tag, false> | |
346 | : detail::relate::relate_impl | |
347 | < | |
348 | detail::de9im::static_mask_touches_type, | |
349 | Geometry, | |
350 | MultiPoint | |
351 | > | |
352 | {}; | |
7c673cae FG |
353 | |
354 | // Box/Box | |
355 | ||
356 | template <typename Box1, typename Box2, typename CastedTag1, typename CastedTag2> | |
357 | struct touches<Box1, Box2, box_tag, box_tag, CastedTag1, CastedTag2, false> | |
358 | : detail::touches::box_box | |
359 | {}; | |
360 | ||
361 | template <typename Box1, typename Box2> | |
362 | struct touches<Box1, Box2, box_tag, box_tag, areal_tag, areal_tag, false> | |
363 | : detail::touches::box_box | |
364 | {}; | |
365 | ||
366 | // L/L | |
367 | ||
368 | template <typename Linear1, typename Linear2, typename Tag1, typename Tag2> | |
369 | struct touches<Linear1, Linear2, Tag1, Tag2, linear_tag, linear_tag, false> | |
370 | : detail::relate::relate_impl | |
371 | < | |
372 | detail::de9im::static_mask_touches_type, | |
373 | Linear1, | |
374 | Linear2 | |
375 | > | |
376 | {}; | |
377 | ||
378 | // L/A | |
379 | ||
380 | template <typename Linear, typename Areal, typename Tag1, typename Tag2> | |
381 | struct touches<Linear, Areal, Tag1, Tag2, linear_tag, areal_tag, false> | |
382 | : detail::relate::relate_impl | |
383 | < | |
384 | detail::de9im::static_mask_touches_type, | |
385 | Linear, | |
386 | Areal | |
387 | > | |
388 | {}; | |
389 | ||
390 | // A/L | |
391 | template <typename Linear, typename Areal, typename Tag1, typename Tag2> | |
392 | struct touches<Areal, Linear, Tag1, Tag2, areal_tag, linear_tag, false> | |
393 | : detail::relate::relate_impl | |
394 | < | |
395 | detail::de9im::static_mask_touches_type, | |
396 | Areal, | |
397 | Linear | |
398 | > | |
399 | {}; | |
400 | ||
401 | // A/A | |
402 | ||
403 | template <typename Areal1, typename Areal2, typename Tag1, typename Tag2> | |
404 | struct touches<Areal1, Areal2, Tag1, Tag2, areal_tag, areal_tag, false> | |
405 | : detail::relate::relate_impl | |
406 | < | |
407 | detail::de9im::static_mask_touches_type, | |
408 | Areal1, | |
409 | Areal2 | |
410 | > | |
411 | {}; | |
412 | ||
413 | template <typename Areal1, typename Areal2> | |
414 | struct touches<Areal1, Areal2, ring_tag, ring_tag, areal_tag, areal_tag, false> | |
415 | : detail::touches::areal_areal<Areal1, Areal2> | |
416 | {}; | |
417 | ||
418 | } // namespace dispatch | |
419 | #endif // DOXYGEN_NO_DISPATCH | |
420 | ||
421 | ||
b32b8144 | 422 | namespace resolve_variant |
7c673cae | 423 | { |
7c673cae FG |
424 | |
425 | template <typename Geometry> | |
426 | struct self_touches | |
427 | { | |
428 | static bool apply(Geometry const& geometry) | |
429 | { | |
430 | concepts::check<Geometry const>(); | |
431 | ||
b32b8144 FG |
432 | typedef typename strategy::relate::services::default_strategy |
433 | < | |
434 | Geometry, Geometry | |
435 | >::type strategy_type; | |
7c673cae | 436 | typedef typename geometry::point_type<Geometry>::type point_type; |
92f5a8d4 | 437 | typedef detail::overlay::turn_info<point_type> turn_info; |
7c673cae FG |
438 | |
439 | typedef detail::overlay::get_turn_info | |
440 | < | |
441 | detail::overlay::assign_null_policy | |
442 | > policy_type; | |
443 | ||
444 | std::deque<turn_info> turns; | |
445 | detail::touches::areal_interrupt_policy policy; | |
b32b8144 | 446 | strategy_type strategy; |
b32b8144 | 447 | // TODO: skip_adjacent should be set to false |
7c673cae FG |
448 | detail::self_get_turn_points::get_turns |
449 | < | |
b32b8144 | 450 | false, policy_type |
92f5a8d4 | 451 | >::apply(geometry, strategy, detail::no_rescale_policy(), turns, policy, 0, true); |
7c673cae FG |
452 | |
453 | return policy.result(); | |
454 | } | |
455 | }; | |
456 | ||
7c673cae FG |
457 | } |
458 | ||
7c673cae FG |
459 | }} // namespace boost::geometry |
460 | ||
b32b8144 | 461 | #endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_TOUCHES_IMPLEMENTATION_HPP |