boost/geometry/algorithms/within.hpp

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