]>
Commit | Line | Data |
---|---|---|
7c673cae FG |
1 | // Boost.Geometry (aka GGL, Generic Geometry Library) |
2 | ||
3 | // Copyright (c) 2007-2012 Barend Gehrels, Amsterdam, the Netherlands. | |
4 | // Copyright (c) 2008-2012 Bruno Lalande, Paris, France. | |
5 | // Copyright (c) 2009-2012 Mateusz Loskot, London, UK. | |
6 | ||
7 | // This file was modified by Oracle on 2013, 2014. | |
8 | // Modifications copyright (c) 2013, 2014 Oracle and/or its affiliates. | |
9 | ||
10 | // Parts of Boost.Geometry are redesigned from Geodan's Geographic Library | |
11 | // (geolib/GGL), copyright (c) 1995-2010 Geodan, Amsterdam, the Netherlands. | |
12 | ||
13 | // Use, modification and distribution is subject to the Boost Software License, | |
14 | // Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at | |
15 | // http://www.boost.org/LICENSE_1_0.txt) | |
16 | ||
17 | // Contributed and/or modified by Adam Wulkiewicz, on behalf of Oracle | |
18 | ||
19 | #ifndef BOOST_GEOMETRY_ALGORITHMS_WITHIN_HPP | |
20 | #define BOOST_GEOMETRY_ALGORITHMS_WITHIN_HPP | |
21 | ||
22 | ||
23 | #include <cstddef> | |
24 | ||
25 | #include <boost/concept_check.hpp> | |
26 | #include <boost/range.hpp> | |
27 | ||
28 | #include <boost/variant/apply_visitor.hpp> | |
29 | #include <boost/variant/static_visitor.hpp> | |
30 | #include <boost/variant/variant_fwd.hpp> | |
31 | ||
32 | #include <boost/geometry/algorithms/make.hpp> | |
33 | #include <boost/geometry/algorithms/not_implemented.hpp> | |
34 | ||
35 | #include <boost/geometry/core/access.hpp> | |
36 | #include <boost/geometry/core/closure.hpp> | |
37 | #include <boost/geometry/core/cs.hpp> | |
38 | #include <boost/geometry/core/exterior_ring.hpp> | |
39 | #include <boost/geometry/core/interior_rings.hpp> | |
40 | #include <boost/geometry/core/point_order.hpp> | |
41 | #include <boost/geometry/core/ring_type.hpp> | |
42 | #include <boost/geometry/core/interior_rings.hpp> | |
43 | #include <boost/geometry/core/tags.hpp> | |
44 | ||
45 | #include <boost/geometry/geometries/concepts/check.hpp> | |
46 | #include <boost/geometry/strategies/concepts/within_concept.hpp> | |
47 | #include <boost/geometry/strategies/default_strategy.hpp> | |
48 | #include <boost/geometry/strategies/within.hpp> | |
49 | #include <boost/geometry/util/math.hpp> | |
50 | #include <boost/geometry/util/order_as_direction.hpp> | |
51 | #include <boost/geometry/views/closeable_view.hpp> | |
52 | #include <boost/geometry/views/reversible_view.hpp> | |
53 | ||
54 | #include <boost/geometry/algorithms/detail/within/point_in_geometry.hpp> | |
55 | ||
56 | #include <boost/geometry/algorithms/detail/overlay/get_turns.hpp> | |
57 | #include <boost/geometry/algorithms/detail/overlay/do_reverse.hpp> | |
58 | #include <deque> | |
59 | ||
60 | namespace boost { namespace geometry | |
61 | { | |
62 | ||
63 | #ifndef DOXYGEN_NO_DETAIL | |
64 | namespace detail { namespace within { | |
65 | ||
66 | struct use_point_in_geometry | |
67 | { | |
68 | template <typename Geometry1, typename Geometry2, typename Strategy> | |
69 | static inline bool apply(Geometry1 const& geometry1, Geometry2 const& geometry2, Strategy const& strategy) | |
70 | { | |
71 | return detail::within::point_in_geometry(geometry1, geometry2, strategy) == 1; | |
72 | } | |
73 | }; | |
74 | ||
75 | struct use_relate | |
76 | { | |
77 | template <typename Geometry1, typename Geometry2, typename Strategy> | |
78 | static inline bool apply(Geometry1 const& geometry1, Geometry2 const& geometry2, Strategy const& /*strategy*/) | |
79 | { | |
80 | return Strategy::apply(geometry1, geometry2); | |
81 | } | |
82 | }; | |
83 | ||
84 | }} // namespace detail::within | |
85 | #endif // DOXYGEN_NO_DETAIL | |
86 | ||
87 | #ifndef DOXYGEN_NO_DISPATCH | |
88 | namespace dispatch | |
89 | { | |
90 | ||
91 | template | |
92 | < | |
93 | typename Geometry1, | |
94 | typename Geometry2, | |
95 | typename Tag1 = typename tag<Geometry1>::type, | |
96 | typename Tag2 = typename tag<Geometry2>::type | |
97 | > | |
98 | struct within | |
99 | : not_implemented<Tag1, Tag2> | |
100 | {}; | |
101 | ||
102 | ||
103 | template <typename Point, typename Box> | |
104 | struct within<Point, Box, point_tag, box_tag> | |
105 | { | |
106 | template <typename Strategy> | |
107 | static inline bool apply(Point const& point, Box const& box, Strategy const& strategy) | |
108 | { | |
109 | boost::ignore_unused_variable_warning(strategy); | |
110 | return strategy.apply(point, box); | |
111 | } | |
112 | }; | |
113 | ||
114 | template <typename Box1, typename Box2> | |
115 | struct within<Box1, Box2, box_tag, box_tag> | |
116 | { | |
117 | template <typename Strategy> | |
118 | static inline bool apply(Box1 const& box1, Box2 const& box2, Strategy const& strategy) | |
119 | { | |
120 | assert_dimension_equal<Box1, Box2>(); | |
121 | boost::ignore_unused_variable_warning(strategy); | |
122 | return strategy.apply(box1, box2); | |
123 | } | |
124 | }; | |
125 | ||
126 | // P/P | |
127 | ||
128 | template <typename Point1, typename Point2> | |
129 | struct within<Point1, Point2, point_tag, point_tag> | |
130 | : public detail::within::use_point_in_geometry | |
131 | {}; | |
132 | ||
133 | template <typename Point, typename MultiPoint> | |
134 | struct within<Point, MultiPoint, point_tag, multi_point_tag> | |
135 | : public detail::within::use_point_in_geometry | |
136 | {}; | |
137 | ||
138 | // P/L | |
139 | ||
140 | template <typename Point, typename Segment> | |
141 | struct within<Point, Segment, point_tag, segment_tag> | |
142 | : public detail::within::use_point_in_geometry | |
143 | {}; | |
144 | ||
145 | template <typename Point, typename Linestring> | |
146 | struct within<Point, Linestring, point_tag, linestring_tag> | |
147 | : public detail::within::use_point_in_geometry | |
148 | {}; | |
149 | ||
150 | template <typename Point, typename MultiLinestring> | |
151 | struct within<Point, MultiLinestring, point_tag, multi_linestring_tag> | |
152 | : public detail::within::use_point_in_geometry | |
153 | {}; | |
154 | ||
155 | // P/A | |
156 | ||
157 | template <typename Point, typename Ring> | |
158 | struct within<Point, Ring, point_tag, ring_tag> | |
159 | : public detail::within::use_point_in_geometry | |
160 | {}; | |
161 | ||
162 | template <typename Point, typename Polygon> | |
163 | struct within<Point, Polygon, point_tag, polygon_tag> | |
164 | : public detail::within::use_point_in_geometry | |
165 | {}; | |
166 | ||
167 | template <typename Point, typename MultiPolygon> | |
168 | struct within<Point, MultiPolygon, point_tag, multi_polygon_tag> | |
169 | : public detail::within::use_point_in_geometry | |
170 | {}; | |
171 | ||
172 | // L/L | |
173 | ||
174 | template <typename Linestring1, typename Linestring2> | |
175 | struct within<Linestring1, Linestring2, linestring_tag, linestring_tag> | |
176 | : public detail::within::use_relate | |
177 | {}; | |
178 | ||
179 | template <typename Linestring, typename MultiLinestring> | |
180 | struct within<Linestring, MultiLinestring, linestring_tag, multi_linestring_tag> | |
181 | : public detail::within::use_relate | |
182 | {}; | |
183 | ||
184 | template <typename MultiLinestring, typename Linestring> | |
185 | struct within<MultiLinestring, Linestring, multi_linestring_tag, linestring_tag> | |
186 | : public detail::within::use_relate | |
187 | {}; | |
188 | ||
189 | template <typename MultiLinestring1, typename MultiLinestring2> | |
190 | struct within<MultiLinestring1, MultiLinestring2, multi_linestring_tag, multi_linestring_tag> | |
191 | : public detail::within::use_relate | |
192 | {}; | |
193 | ||
194 | // L/A | |
195 | ||
196 | template <typename Linestring, typename Ring> | |
197 | struct within<Linestring, Ring, linestring_tag, ring_tag> | |
198 | : public detail::within::use_relate | |
199 | {}; | |
200 | ||
201 | template <typename MultiLinestring, typename Ring> | |
202 | struct within<MultiLinestring, Ring, multi_linestring_tag, ring_tag> | |
203 | : public detail::within::use_relate | |
204 | {}; | |
205 | ||
206 | template <typename Linestring, typename Polygon> | |
207 | struct within<Linestring, Polygon, linestring_tag, polygon_tag> | |
208 | : public detail::within::use_relate | |
209 | {}; | |
210 | ||
211 | template <typename MultiLinestring, typename Polygon> | |
212 | struct within<MultiLinestring, Polygon, multi_linestring_tag, polygon_tag> | |
213 | : public detail::within::use_relate | |
214 | {}; | |
215 | ||
216 | template <typename Linestring, typename MultiPolygon> | |
217 | struct within<Linestring, MultiPolygon, linestring_tag, multi_polygon_tag> | |
218 | : public detail::within::use_relate | |
219 | {}; | |
220 | ||
221 | template <typename MultiLinestring, typename MultiPolygon> | |
222 | struct within<MultiLinestring, MultiPolygon, multi_linestring_tag, multi_polygon_tag> | |
223 | : public detail::within::use_relate | |
224 | {}; | |
225 | ||
226 | // A/A | |
227 | ||
228 | template <typename Ring1, typename Ring2> | |
229 | struct within<Ring1, Ring2, ring_tag, ring_tag> | |
230 | : public detail::within::use_relate | |
231 | {}; | |
232 | ||
233 | template <typename Ring, typename Polygon> | |
234 | struct within<Ring, Polygon, ring_tag, polygon_tag> | |
235 | : public detail::within::use_relate | |
236 | {}; | |
237 | ||
238 | template <typename Polygon, typename Ring> | |
239 | struct within<Polygon, Ring, polygon_tag, ring_tag> | |
240 | : public detail::within::use_relate | |
241 | {}; | |
242 | ||
243 | template <typename Polygon1, typename Polygon2> | |
244 | struct within<Polygon1, Polygon2, polygon_tag, polygon_tag> | |
245 | : public detail::within::use_relate | |
246 | {}; | |
247 | ||
248 | template <typename Ring, typename MultiPolygon> | |
249 | struct within<Ring, MultiPolygon, ring_tag, multi_polygon_tag> | |
250 | : public detail::within::use_relate | |
251 | {}; | |
252 | ||
253 | template <typename MultiPolygon, typename Ring> | |
254 | struct within<MultiPolygon, Ring, multi_polygon_tag, ring_tag> | |
255 | : public detail::within::use_relate | |
256 | {}; | |
257 | ||
258 | template <typename Polygon, typename MultiPolygon> | |
259 | struct within<Polygon, MultiPolygon, polygon_tag, multi_polygon_tag> | |
260 | : public detail::within::use_relate | |
261 | {}; | |
262 | ||
263 | template <typename MultiPolygon, typename Polygon> | |
264 | struct within<MultiPolygon, Polygon, multi_polygon_tag, polygon_tag> | |
265 | : public detail::within::use_relate | |
266 | {}; | |
267 | ||
268 | template <typename MultiPolygon1, typename MultiPolygon2> | |
269 | struct within<MultiPolygon1, MultiPolygon2, multi_polygon_tag, multi_polygon_tag> | |
270 | : public detail::within::use_relate | |
271 | {}; | |
272 | ||
273 | } // namespace dispatch | |
274 | #endif // DOXYGEN_NO_DISPATCH | |
275 | ||
276 | ||
277 | namespace resolve_strategy | |
278 | { | |
279 | ||
280 | struct within | |
281 | { | |
282 | template <typename Geometry1, typename Geometry2, typename Strategy> | |
283 | static inline bool apply(Geometry1 const& geometry1, | |
284 | Geometry2 const& geometry2, | |
285 | Strategy const& strategy) | |
286 | { | |
287 | concepts::within::check | |
288 | < | |
289 | typename tag<Geometry1>::type, | |
290 | typename tag<Geometry2>::type, | |
291 | typename tag_cast<typename tag<Geometry2>::type, areal_tag>::type, | |
292 | Strategy | |
293 | >(); | |
294 | ||
295 | return dispatch::within<Geometry1, Geometry2>::apply(geometry1, geometry2, strategy); | |
296 | } | |
297 | ||
298 | template <typename Geometry1, typename Geometry2> | |
299 | static inline bool apply(Geometry1 const& geometry1, | |
300 | Geometry2 const& geometry2, | |
301 | default_strategy) | |
302 | { | |
303 | typedef typename point_type<Geometry1>::type point_type1; | |
304 | typedef typename point_type<Geometry2>::type point_type2; | |
305 | ||
306 | typedef typename strategy::within::services::default_strategy | |
307 | < | |
308 | typename tag<Geometry1>::type, | |
309 | typename tag<Geometry2>::type, | |
310 | typename tag<Geometry1>::type, | |
311 | typename tag_cast<typename tag<Geometry2>::type, areal_tag>::type, | |
312 | typename tag_cast | |
313 | < | |
314 | typename cs_tag<point_type1>::type, spherical_tag | |
315 | >::type, | |
316 | typename tag_cast | |
317 | < | |
318 | typename cs_tag<point_type2>::type, spherical_tag | |
319 | >::type, | |
320 | Geometry1, | |
321 | Geometry2 | |
322 | >::type strategy_type; | |
323 | ||
324 | return apply(geometry1, geometry2, strategy_type()); | |
325 | } | |
326 | }; | |
327 | ||
328 | } // namespace resolve_strategy | |
329 | ||
330 | ||
331 | namespace resolve_variant | |
332 | { | |
333 | ||
334 | template <typename Geometry1, typename Geometry2> | |
335 | struct within | |
336 | { | |
337 | template <typename Strategy> | |
338 | static inline bool apply(Geometry1 const& geometry1, | |
339 | Geometry2 const& geometry2, | |
340 | Strategy const& strategy) | |
341 | { | |
342 | concepts::check<Geometry1 const>(); | |
343 | concepts::check<Geometry2 const>(); | |
344 | assert_dimension_equal<Geometry1, Geometry2>(); | |
345 | ||
346 | return resolve_strategy::within::apply(geometry1, | |
347 | geometry2, | |
348 | strategy); | |
349 | } | |
350 | }; | |
351 | ||
352 | template <BOOST_VARIANT_ENUM_PARAMS(typename T), typename Geometry2> | |
353 | struct within<boost::variant<BOOST_VARIANT_ENUM_PARAMS(T)>, Geometry2> | |
354 | { | |
355 | template <typename Strategy> | |
356 | struct visitor: boost::static_visitor<bool> | |
357 | { | |
358 | Geometry2 const& m_geometry2; | |
359 | Strategy const& m_strategy; | |
360 | ||
361 | visitor(Geometry2 const& geometry2, Strategy const& strategy) | |
362 | : m_geometry2(geometry2) | |
363 | , m_strategy(strategy) | |
364 | {} | |
365 | ||
366 | template <typename Geometry1> | |
367 | bool operator()(Geometry1 const& geometry1) const | |
368 | { | |
369 | return within<Geometry1, Geometry2>::apply(geometry1, | |
370 | m_geometry2, | |
371 | m_strategy); | |
372 | } | |
373 | }; | |
374 | ||
375 | template <typename Strategy> | |
376 | static inline bool | |
377 | apply(boost::variant<BOOST_VARIANT_ENUM_PARAMS(T)> const& geometry1, | |
378 | Geometry2 const& geometry2, | |
379 | Strategy const& strategy) | |
380 | { | |
381 | return boost::apply_visitor(visitor<Strategy>(geometry2, strategy), | |
382 | geometry1); | |
383 | } | |
384 | }; | |
385 | ||
386 | template <typename Geometry1, BOOST_VARIANT_ENUM_PARAMS(typename T)> | |
387 | struct within<Geometry1, boost::variant<BOOST_VARIANT_ENUM_PARAMS(T)> > | |
388 | { | |
389 | template <typename Strategy> | |
390 | struct visitor: boost::static_visitor<bool> | |
391 | { | |
392 | Geometry1 const& m_geometry1; | |
393 | Strategy const& m_strategy; | |
394 | ||
395 | visitor(Geometry1 const& geometry1, Strategy const& strategy) | |
396 | : m_geometry1(geometry1) | |
397 | , m_strategy(strategy) | |
398 | {} | |
399 | ||
400 | template <typename Geometry2> | |
401 | bool operator()(Geometry2 const& geometry2) const | |
402 | { | |
403 | return within<Geometry1, Geometry2>::apply(m_geometry1, | |
404 | geometry2, | |
405 | m_strategy); | |
406 | } | |
407 | }; | |
408 | ||
409 | template <typename Strategy> | |
410 | static inline bool | |
411 | apply(Geometry1 const& geometry1, | |
412 | boost::variant<BOOST_VARIANT_ENUM_PARAMS(T)> const& geometry2, | |
413 | Strategy const& strategy) | |
414 | { | |
415 | return boost::apply_visitor(visitor<Strategy>(geometry1, strategy), | |
416 | geometry2 | |
417 | ); | |
418 | } | |
419 | }; | |
420 | ||
421 | template < | |
422 | BOOST_VARIANT_ENUM_PARAMS(typename T1), | |
423 | BOOST_VARIANT_ENUM_PARAMS(typename T2) | |
424 | > | |
425 | struct within< | |
426 | boost::variant<BOOST_VARIANT_ENUM_PARAMS(T1)>, | |
427 | boost::variant<BOOST_VARIANT_ENUM_PARAMS(T2)> | |
428 | > | |
429 | { | |
430 | template <typename Strategy> | |
431 | struct visitor: boost::static_visitor<bool> | |
432 | { | |
433 | Strategy const& m_strategy; | |
434 | ||
435 | visitor(Strategy const& strategy): m_strategy(strategy) {} | |
436 | ||
437 | template <typename Geometry1, typename Geometry2> | |
438 | bool operator()(Geometry1 const& geometry1, | |
439 | Geometry2 const& geometry2) const | |
440 | { | |
441 | return within<Geometry1, Geometry2>::apply(geometry1, | |
442 | geometry2, | |
443 | m_strategy); | |
444 | } | |
445 | }; | |
446 | ||
447 | template <typename Strategy> | |
448 | static inline bool | |
449 | apply(boost::variant<BOOST_VARIANT_ENUM_PARAMS(T1)> const& geometry1, | |
450 | boost::variant<BOOST_VARIANT_ENUM_PARAMS(T2)> const& geometry2, | |
451 | Strategy const& strategy) | |
452 | { | |
453 | return boost::apply_visitor(visitor<Strategy>(strategy), | |
454 | geometry1, | |
455 | geometry2); | |
456 | } | |
457 | }; | |
458 | ||
459 | } | |
460 | ||
461 | ||
462 | /*! | |
463 | \brief \brief_check12{is completely inside} | |
464 | \ingroup within | |
465 | \details \details_check12{within, is completely inside}. | |
466 | \tparam Geometry1 \tparam_geometry | |
467 | \tparam Geometry2 \tparam_geometry | |
468 | \param geometry1 \param_geometry which might be within the second geometry | |
469 | \param geometry2 \param_geometry which might contain the first geometry | |
470 | \return true if geometry1 is completely contained within geometry2, | |
471 | else false | |
472 | \note The default strategy is used for within detection | |
473 | ||
474 | ||
475 | \qbk{[include reference/algorithms/within.qbk]} | |
476 | ||
477 | \qbk{ | |
478 | [heading Example] | |
479 | [within] | |
480 | [within_output] | |
481 | } | |
482 | */ | |
483 | template<typename Geometry1, typename Geometry2> | |
484 | inline bool within(Geometry1 const& geometry1, Geometry2 const& geometry2) | |
485 | { | |
486 | return resolve_variant::within | |
487 | < | |
488 | Geometry1, | |
489 | Geometry2 | |
490 | >::apply(geometry1, geometry2, default_strategy()); | |
491 | } | |
492 | ||
493 | /*! | |
494 | \brief \brief_check12{is completely inside} \brief_strategy | |
495 | \ingroup within | |
496 | \details \details_check12{within, is completely inside}, \brief_strategy. \details_strategy_reasons | |
497 | \tparam Geometry1 \tparam_geometry | |
498 | \tparam Geometry2 \tparam_geometry | |
499 | \param geometry1 \param_geometry which might be within the second geometry | |
500 | \param geometry2 \param_geometry which might contain the first geometry | |
501 | \param strategy strategy to be used | |
502 | \return true if geometry1 is completely contained within geometry2, | |
503 | else false | |
504 | ||
505 | \qbk{distinguish,with strategy} | |
506 | \qbk{[include reference/algorithms/within.qbk]} | |
507 | \qbk{ | |
508 | [heading Available Strategies] | |
509 | \* [link geometry.reference.strategies.strategy_within_winding Winding (coordinate system agnostic)] | |
510 | \* [link geometry.reference.strategies.strategy_within_franklin Franklin (cartesian)] | |
511 | \* [link geometry.reference.strategies.strategy_within_crossings_multiply Crossings Multiply (cartesian)] | |
512 | ||
513 | [heading Example] | |
514 | [within_strategy] | |
515 | [within_strategy_output] | |
516 | ||
517 | } | |
518 | */ | |
519 | template<typename Geometry1, typename Geometry2, typename Strategy> | |
520 | inline bool within(Geometry1 const& geometry1, Geometry2 const& geometry2, | |
521 | Strategy const& strategy) | |
522 | { | |
523 | return resolve_variant::within | |
524 | < | |
525 | Geometry1, | |
526 | Geometry2 | |
527 | >::apply(geometry1, geometry2, strategy); | |
528 | } | |
529 | ||
530 | }} // namespace boost::geometry | |
531 | ||
532 | #endif // BOOST_GEOMETRY_ALGORITHMS_WITHIN_HPP |