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