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>
applyboost::geometry::detail::within::use_point_in_geometry69 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>
applyboost::geometry::detail::within::use_relate78 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>
applyboost::geometry::dispatch::within107 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>
applyboost::geometry::dispatch::within118 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>
applyboost::geometry::resolve_strategy::within283 static inline bool apply(Geometry1 const& geometry1,
284 Geometry2 const& geometry2,
285 Strategy const& strategy)
286 {
287 concept::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>
applyboost::geometry::resolve_strategy::within299 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>
applyboost::geometry::resolve_variant::within338 static inline bool apply(Geometry1 const& geometry1,
339 Geometry2 const& geometry2,
340 Strategy const& strategy)
341 {
342 concept::check<Geometry1 const>();
343 concept::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
visitorboost::geometry::resolve_variant::within::visitor361 visitor(Geometry2 const& geometry2, Strategy const& strategy)
362 : m_geometry2(geometry2)
363 , m_strategy(strategy)
364 {}
365
366 template <typename Geometry1>
operator ()boost::geometry::resolve_variant::within::visitor367 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
applyboost::geometry::resolve_variant::within377 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
visitorboost::geometry::resolve_variant::within::visitor395 visitor(Geometry1 const& geometry1, Strategy const& strategy)
396 : m_geometry1(geometry1)
397 , m_strategy(strategy)
398 {}
399
400 template <typename Geometry2>
operator ()boost::geometry::resolve_variant::within::visitor401 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
applyboost::geometry::resolve_variant::within411 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
visitorboost::geometry::resolve_variant::within::visitor435 visitor(Strategy const& strategy): m_strategy(strategy) {}
436
437 template <typename Geometry1, typename Geometry2>
operator ()boost::geometry::resolve_variant::within::visitor438 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
applyboost::geometry::resolve_variant::within449 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>
within(Geometry1 const & geometry1,Geometry2 const & 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>
within(Geometry1 const & geometry1,Geometry2 const & geometry2,Strategy const & 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
533