ceph/src/boost/boost/geometry/algorithms/detail/relate/de9im.hpp

   1 // Boost.Geometry (aka GGL, Generic Geometry Library)
   2
   3 // Copyright (c) 2007-2015 Barend Gehrels, Amsterdam, the Netherlands.
   4
   5 // This file was modified by Oracle on 2013, 2014, 2015, 2019.
   6 // Modifications copyright (c) 2013-2019 Oracle and/or its affiliates.
   7
   8 // Contributed and/or modified by Adam Wulkiewicz, on behalf of Oracle
   9
  10 // Use, modification and distribution is subject to the Boost Software License,
  11 // Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
  12 // http://www.boost.org/LICENSE_1_0.txt)
  13
  14 #ifndef BOOST_GEOMETRY_ALGORITHMS_DETAIL_RELATE_DE9IM_HPP
  15 #define BOOST_GEOMETRY_ALGORITHMS_DETAIL_RELATE_DE9IM_HPP
  16
  17 #include <boost/mpl/is_sequence.hpp>
  18 #include <boost/mpl/push_back.hpp>
  19 #include <boost/mpl/vector.hpp>
  20 #include <boost/mpl/vector_c.hpp>
  21 #include <boost/static_assert.hpp>
  22 #include <boost/tuple/tuple.hpp>
  23
  24 #include <boost/geometry/algorithms/detail/relate/result.hpp>
  25 #include <boost/geometry/core/topological_dimension.hpp>
  26 #include <boost/geometry/core/tag.hpp>
  27
  28 #include <boost/geometry/util/tuples.hpp>
  29
  30 namespace boost { namespace geometry
  31 {
  32
  33 namespace de9im
  34 {
  35
  36 /*!
  37 \brief DE-9IM model intersection matrix.
  38 \ingroup de9im
  39 \details This matrix can be used to express spatial relations as defined in
  40          Dimensionally Extended 9-Intersection Model.
  41
  42 \qbk{[heading See also]}
  43 \qbk{* [link geometry.reference.algorithms.relation relation]}
  44  */
  45 class matrix
  46     : public detail::relate::matrix<3, 3>
  47 {
  48 #ifdef DOXYGEN_INVOKED
  49 public:
  50     /*!
  51     \brief Initializes all of the matrix elements to F
  52      */
  53     matrix();
  54     /*!
  55     \brief Subscript operator
  56     \param index The index of the element
  57     \return The element
  58      */
  59     char operator[](std::size_t index) const;
  60     /*!
  61     \brief Returns the iterator to the first element
  62     \return const RandomAccessIterator
  63      */
  64     const_iterator begin() const;
  65     /*!
  66     \brief Returns the iterator past the last element
  67     \return const RandomAccessIterator
  68      */
  69     const_iterator end() const;
  70     /*!
  71     \brief Returns the number of elements
  72     \return 9
  73      */
  74     static std::size_t size();
  75     /*!
  76     \brief Returns raw pointer to elements
  77     \return const pointer to array of elements
  78      */
  79     inline const char * data() const;
  80     /*!
  81     \brief Returns std::string containing elements
  82     \return string containing elements
  83      */
  84     inline std::string str() const;
  85 #endif
  86 };
  87
  88 /*!
  89 \brief DE-9IM model intersection mask.
  90 \ingroup de9im
  91 \details This mask can be used to check spatial relations as defined in
  92          Dimensionally Extended 9-Intersection Model.
  93
  94 \qbk{[heading See also]}
  95 \qbk{* [link geometry.reference.algorithms.relate relate]}
  96  */
  97 class mask
  98     : public detail::relate::mask<3, 3>
  99 {
 100     typedef detail::relate::mask<3, 3> base_type;
 101
 102 public:
 103     /*!
 104     \brief The constructor.
 105     \param code The mask pattern.
 106     */
 107     inline explicit mask(const char* code)
 108         : base_type(code)
 109     {}
 110
 111     /*!
 112     \brief The constructor.
 113     \param code The mask pattern.
 114     */
 115     inline explicit mask(std::string const& code)
 116         : base_type(code.c_str(), code.size())
 117     {}
 118 };
 119
 120 // static_mask
 121
 122 /*!
 123 \brief DE-9IM model intersection mask (static version).
 124 \ingroup de9im
 125 \details This mask can be used to check spatial relations as defined in
 126          Dimensionally Extended 9-Intersection Model.
 127 \tparam II Interior/Interior intersection mask element
 128 \tparam IB Interior/Boundary intersection mask element
 129 \tparam IE Interior/Exterior intersection mask element
 130 \tparam BI Boundary/Interior intersection mask element
 131 \tparam BB Boundary/Boundary intersection mask element
 132 \tparam BE Boundary/Exterior intersection mask element
 133 \tparam EI Exterior/Interior intersection mask element
 134 \tparam EB Exterior/Boundary intersection mask element
 135 \tparam EE Exterior/Exterior intersection mask element
 136
 137 \qbk{[heading See also]}
 138 \qbk{* [link geometry.reference.algorithms.relate relate]}
 139  */
 140 template
 141 <
 142     char II = '*', char IB = '*', char IE = '*',
 143     char BI = '*', char BB = '*', char BE = '*',
 144     char EI = '*', char EB = '*', char EE = '*'
 145 >
 146 class static_mask
 147     : public detail::relate::static_mask
 148         <
 149             boost::mpl::vector_c
 150                 <
 151                     char, II, IB, IE, BI, BB, BE, EI, EB, EE
 152                 >,
 153             3, 3
 154         >
 155 {};
 156
 157 } // namespace de9im
 158
 159 namespace detail { namespace de9im
 160 {
 161
 162 // a small helper util for ORing static masks
 163
 164 template
 165 <
 166     typename Seq,
 167     typename T,
 168     bool IsSeq = boost::mpl::is_sequence<Seq>::value
 169 >
 170 struct push_back
 171 {
 172     typedef typename boost::mpl::push_back
 173         <
 174             Seq,
 175             T
 176         >::type type;
 177 };
 178
 179 template <typename Seq, typename T>
 180 struct push_back<Seq, T, false>
 181 {};
 182
 183 }} // namespace detail::de9im
 184
 185 namespace de9im
 186 {
 187
 188 inline
 189 boost::tuples::cons
 190     <
 191         mask,
 192         boost::tuples::cons<mask, boost::tuples::null_type>
 193     >
 194 operator||(mask const& m1, mask const& m2)
 195 {
 196     namespace bt = boost::tuples;
 197
 198     return bt::cons<mask, bt::cons<mask, bt::null_type> >
 199         ( m1, bt::cons<mask, bt::null_type>(m2, bt::null_type()) );
 200 }
 201
 202 template <typename Tail>
 203 inline
 204 typename geometry::tuples::push_back
 205     <
 206         boost::tuples::cons<mask, Tail>,
 207         mask
 208     >::type
 209 operator||(boost::tuples::cons<mask, Tail> const& t, mask const& m)
 210 {
 211     namespace bt = boost::tuples;
 212
 213     return geometry::tuples::push_back
 214             <
 215                 bt::cons<mask, Tail>,
 216                 mask
 217             >::apply(t, m);
 218 }
 219
 220 template
 221 <
 222     char II1, char IB1, char IE1,
 223     char BI1, char BB1, char BE1,
 224     char EI1, char EB1, char EE1,
 225     char II2, char IB2, char IE2,
 226     char BI2, char BB2, char BE2,
 227     char EI2, char EB2, char EE2
 228 >
 229 inline
 230 boost::mpl::vector<
 231     static_mask<II1, IB1, IE1, BI1, BB1, BE1, EI1, EB1, EE1>,
 232     static_mask<II2, IB2, IE2, BI2, BB2, BE2, EI2, EB2, EE2>
 233 >
 234 operator||(static_mask<II1, IB1, IE1, BI1, BB1, BE1, EI1, EB1, EE1> const& ,
 235            static_mask<II2, IB2, IE2, BI2, BB2, BE2, EI2, EB2, EE2> const& )
 236 {
 237     return boost::mpl::vector
 238             <
 239                 static_mask<II1, IB1, IE1, BI1, BB1, BE1, EI1, EB1, EE1>,
 240                 static_mask<II2, IB2, IE2, BI2, BB2, BE2, EI2, EB2, EE2>
 241             >();
 242 }
 243
 244 template
 245 <
 246     typename Seq,
 247     char II, char IB, char IE,
 248     char BI, char BB, char BE,
 249     char EI, char EB, char EE
 250 >
 251 inline
 252 typename detail::de9im::push_back
 253     <
 254         Seq,
 255         static_mask<II, IB, IE, BI, BB, BE, EI, EB, EE>
 256     >::type
 257 operator||(Seq const& ,
 258            static_mask<II, IB, IE, BI, BB, BE, EI, EB, EE> const& )
 259 {
 260     return typename detail::de9im::push_back
 261             <
 262                 Seq,
 263                 static_mask<II, IB, IE, BI, BB, BE, EI, EB, EE>
 264             >::type();
 265 }
 266
 267 } // namespace de9im
 268
 269
 270 #ifndef DOXYGEN_NO_DETAIL
 271 namespace detail { namespace de9im
 272 {
 273
 274 // PREDEFINED MASKS
 275
 276 // TODO:
 277 // 1. specialize for simplified masks if available
 278 // e.g. for TOUCHES use 1 mask for A/A
 279 // 2. Think about dimensions > 2 e.g. should TOUCHES be true
 280 // if the interior of the Areal overlaps the boundary of the Volumetric
 281 // like it's true for Linear/Areal
 282
 283 // EQUALS
 284 template <typename Geometry1, typename Geometry2>
 285 struct static_mask_equals_type
 286 {
 287     typedef geometry::de9im::static_mask<'T', '*', 'F', '*', '*', 'F', 'F', 'F', '*'> type; // wikipedia
 288     //typedef geometry::de9im::static_mask<'T', 'F', 'F', 'F', 'T', 'F', 'F', 'F', 'T'> type; // OGC
 289 };
 290
 291 // DISJOINT
 292 template <typename Geometry1, typename Geometry2>
 293 struct static_mask_disjoint_type
 294 {
 295     typedef geometry::de9im::static_mask<'F', 'F', '*', 'F', 'F', '*', '*', '*', '*'> type;
 296 };
 297
 298 // TOUCHES - NOT P/P
 299 template
 300 <
 301     typename Geometry1,
 302     typename Geometry2,
 303     std::size_t Dim1 = geometry::topological_dimension<Geometry1>::value,
 304     std::size_t Dim2 = geometry::topological_dimension<Geometry2>::value
 305 >
 306 struct static_mask_touches_impl
 307 {
 308     typedef boost::mpl::vector
 309         <
 310             geometry::de9im::static_mask<'F', 'T', '*', '*', '*', '*', '*', '*', '*'>,
 311             geometry::de9im::static_mask<'F', '*', '*', 'T', '*', '*', '*', '*', '*'>,
 312             geometry::de9im::static_mask<'F', '*', '*', '*', 'T', '*', '*', '*', '*'>
 313         > type;
 314 };
 315 // According to OGC, doesn't apply to P/P
 316 // Using the above mask the result would be always false
 317 template <typename Geometry1, typename Geometry2>
 318 struct static_mask_touches_impl<Geometry1, Geometry2, 0, 0>
 319 {
 320     typedef geometry::detail::relate::false_mask type;
 321 };
 322
 323 template <typename Geometry1, typename Geometry2>
 324 struct static_mask_touches_type
 325     : static_mask_touches_impl<Geometry1, Geometry2>
 326 {};
 327
 328 // WITHIN
 329 template <typename Geometry1, typename Geometry2>
 330 struct static_mask_within_type
 331 {
 332     typedef geometry::de9im::static_mask<'T', '*', 'F', '*', '*', 'F', '*', '*', '*'> type;
 333 };
 334
 335 // COVERED_BY (non OGC)
 336 template <typename Geometry1, typename Geometry2>
 337 struct static_mask_covered_by_type
 338 {
 339     typedef boost::mpl::vector
 340         <
 341             geometry::de9im::static_mask<'T', '*', 'F', '*', '*', 'F', '*', '*', '*'>,
 342             geometry::de9im::static_mask<'*', 'T', 'F', '*', '*', 'F', '*', '*', '*'>,
 343             geometry::de9im::static_mask<'*', '*', 'F', 'T', '*', 'F', '*', '*', '*'>,
 344             geometry::de9im::static_mask<'*', '*', 'F', '*', 'T', 'F', '*', '*', '*'>
 345         > type;
 346 };
 347
 348 // CROSSES
 349 // dim(G1) < dim(G2) - P/L P/A L/A
 350 template
 351 <
 352     typename Geometry1,
 353     typename Geometry2,
 354     std::size_t Dim1 = geometry::topological_dimension<Geometry1>::value,
 355     std::size_t Dim2 = geometry::topological_dimension<Geometry2>::value,
 356     bool D1LessD2 = (Dim1 < Dim2)
 357 >
 358 struct static_mask_crosses_impl
 359 {
 360     typedef geometry::de9im::static_mask<'T', '*', 'T', '*', '*', '*', '*', '*', '*'> type;
 361 };
 362 // TODO: I'm not sure if this one below should be available!
 363 // dim(G1) > dim(G2) - L/P A/P A/L
 364 template
 365 <
 366     typename Geometry1, typename Geometry2, std::size_t Dim1, std::size_t Dim2
 367 >
 368 struct static_mask_crosses_impl<Geometry1, Geometry2, Dim1, Dim2, false>
 369 {
 370     typedef geometry::de9im::static_mask<'T', '*', '*', '*', '*', '*', 'T', '*', '*'> type;
 371 };
 372 // dim(G1) == dim(G2) - P/P A/A
 373 template
 374 <
 375     typename Geometry1, typename Geometry2, std::size_t Dim
 376 >
 377 struct static_mask_crosses_impl<Geometry1, Geometry2, Dim, Dim, false>
 378 {
 379     typedef geometry::detail::relate::false_mask type;
 380 };
 381 // dim(G1) == 1 && dim(G2) == 1 - L/L
 382 template <typename Geometry1, typename Geometry2>
 383 struct static_mask_crosses_impl<Geometry1, Geometry2, 1, 1, false>
 384 {
 385     typedef geometry::de9im::static_mask<'0', '*', '*', '*', '*', '*', '*', '*', '*'> type;
 386 };
 387
 388 template <typename Geometry1, typename Geometry2>
 389 struct static_mask_crosses_type
 390     : static_mask_crosses_impl<Geometry1, Geometry2>
 391 {};
 392
 393 // OVERLAPS
 394
 395 // dim(G1) != dim(G2) - NOT P/P, L/L, A/A
 396 template
 397 <
 398     typename Geometry1,
 399     typename Geometry2,
 400     std::size_t Dim1 = geometry::topological_dimension<Geometry1>::value,
 401     std::size_t Dim2 = geometry::topological_dimension<Geometry2>::value
 402 >
 403 struct static_mask_overlaps_impl
 404 {
 405     typedef geometry::detail::relate::false_mask type;
 406 };
 407 // dim(G1) == D && dim(G2) == D - P/P A/A
 408 template <typename Geometry1, typename Geometry2, std::size_t Dim>
 409 struct static_mask_overlaps_impl<Geometry1, Geometry2, Dim, Dim>
 410 {
 411     typedef geometry::de9im::static_mask<'T', '*', 'T', '*', '*', '*', 'T', '*', '*'> type;
 412 };
 413 // dim(G1) == 1 && dim(G2) == 1 - L/L
 414 template <typename Geometry1, typename Geometry2>
 415 struct static_mask_overlaps_impl<Geometry1, Geometry2, 1, 1>
 416 {
 417     typedef geometry::de9im::static_mask<'1', '*', 'T', '*', '*', '*', 'T', '*', '*'> type;
 418 };
 419
 420 template <typename Geometry1, typename Geometry2>
 421 struct static_mask_overlaps_type
 422     : static_mask_overlaps_impl<Geometry1, Geometry2>
 423 {};
 424
 425 }} // namespace detail::de9im
 426 #endif // DOXYGEN_NO_DETAIL
 427
 428
 429 }} // namespace boost::geometry
 430
 431 #endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_RELATE_DE9IM_HPP