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