ceph/src/boost/libs/geometry/include/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
  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