detail/relate/de9im.hpp

0001 // Boost.Geometry (aka GGL, Generic Geometry Library)
0002
0003 // Copyright (c) 2007-2015 Barend Gehrels, Amsterdam, the Netherlands.
0004 // Copyright (c) 2022 Adam Wulkiewicz, Lodz, Poland.
0005
0006 // This file was modified by Oracle on 2013-2022.
0007 // Modifications copyright (c) 2013-2022 Oracle and/or its affiliates.
0008
0009 // Contributed and/or modified by Adam Wulkiewicz, on behalf of Oracle
0010
0011 // Use, modification and distribution is subject to the Boost Software License,
0012 // Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
0013 // http://www.boost.org/LICENSE_1_0.txt)
0014
0015 #ifndef BOOST_GEOMETRY_ALGORITHMS_DETAIL_RELATE_DE9IM_HPP
0016 #define BOOST_GEOMETRY_ALGORITHMS_DETAIL_RELATE_DE9IM_HPP
0017
0018 #include <tuple>
0019
0020 #include <boost/geometry/algorithms/detail/relate/result.hpp>
0021 #include <boost/geometry/core/topological_dimension.hpp>
0022 #include <boost/geometry/core/tag.hpp>
0023
0024 #include <boost/geometry/util/sequence.hpp>
0025 #include <boost/geometry/util/tuples.hpp>
0026
0027 namespace boost { namespace geometry
0028 {
0029
0030 namespace de9im
0031 {
0032
0033 /*!
0034 \brief DE-9IM model intersection matrix.
0035 \ingroup de9im
0036 \details This matrix can be used to express spatial relations as defined in
0037          Dimensionally Extended 9-Intersection Model.
0038
0039 \qbk{[heading See also]}
0040 \qbk{* [link geometry.reference.algorithms.relation relation]}
0041  */
0042 class matrix
0043     : public detail::relate::matrix<3, 3>
0044 {
0045 #ifdef DOXYGEN_INVOKED
0046 public:
0047     /*!
0048     \brief Initializes all of the matrix elements to F
0049      */
0050     matrix();
0051     /*!
0052     \brief Subscript operator
0053     \param index The index of the element
0054     \return The element
0055      */
0056     char operator[](std::size_t index) const;
0057     /*!
0058     \brief Returns the iterator to the first element
0059     \return const RandomAccessIterator
0060      */
0061     const_iterator begin() const;
0062     /*!
0063     \brief Returns the iterator past the last element
0064     \return const RandomAccessIterator
0065      */
0066     const_iterator end() const;
0067     /*!
0068     \brief Returns the number of elements
0069     \return 9
0070      */
0071     static std::size_t size();
0072     /*!
0073     \brief Returns raw pointer to elements
0074     \return const pointer to array of elements
0075      */
0076     inline const char * data() const;
0077     /*!
0078     \brief Returns std::string containing elements
0079     \return string containing elements
0080      */
0081     inline std::string str() const;
0082 #endif
0083 };
0084
0085 /*!
0086 \brief DE-9IM model intersection mask.
0087 \ingroup de9im
0088 \details This mask can be used to check spatial relations as defined in
0089          Dimensionally Extended 9-Intersection Model.
0090
0091 \qbk{[heading See also]}
0092 \qbk{* [link geometry.reference.algorithms.relate relate]}
0093  */
0094 class mask
0095     : public detail::relate::mask<3, 3>
0096 {
0097     typedef detail::relate::mask<3, 3> base_type;
0098
0099 public:
0100     /*!
0101     \brief The constructor.
0102     \param code The mask pattern.
0103     */
0104     inline explicit mask(const char* code)
0105         : base_type(code)
0106     {}
0107
0108     /*!
0109     \brief The constructor.
0110     \param code The mask pattern.
0111     */
0112     inline explicit mask(std::string const& code)
0113         : base_type(code.c_str(), code.size())
0114     {}
0115 };
0116
0117 // static_mask
0118
0119 /*!
0120 \brief DE-9IM model intersection mask (static version).
0121 \ingroup de9im
0122 \details This mask can be used to check spatial relations as defined in
0123          Dimensionally Extended 9-Intersection Model.
0124 \tparam II Interior/Interior intersection mask element
0125 \tparam IB Interior/Boundary intersection mask element
0126 \tparam IE Interior/Exterior intersection mask element
0127 \tparam BI Boundary/Interior intersection mask element
0128 \tparam BB Boundary/Boundary intersection mask element
0129 \tparam BE Boundary/Exterior intersection mask element
0130 \tparam EI Exterior/Interior intersection mask element
0131 \tparam EB Exterior/Boundary intersection mask element
0132 \tparam EE Exterior/Exterior intersection mask element
0133
0134 \qbk{[heading See also]}
0135 \qbk{* [link geometry.reference.algorithms.relate relate]}
0136  */
0137 template
0138 <
0139     char II = '*', char IB = '*', char IE = '*',
0140     char BI = '*', char BB = '*', char BE = '*',
0141     char EI = '*', char EB = '*', char EE = '*'
0142 >
0143 class static_mask
0144     : public detail::relate::static_mask
0145         <
0146             std::integer_sequence
0147                 <
0148                     char, II, IB, IE, BI, BB, BE, EI, EB, EE
0149                 >,
0150             3, 3
0151         >
0152 {};
0153
0154
0155 inline
0156 std::tuple<mask, mask>
0157 operator||(mask const& m1, mask const& m2)
0158 {
0159     return std::tuple<mask, mask>(m1, m2);
0160 }
0161
0162 template <typename ...Masks>
0163 inline
0164 std::tuple<Masks..., mask>
0165 operator||(std::tuple<Masks...> const& t, mask const& m)
0166 {
0167     return geometry::tuples::push_back
0168             <
0169                 std::tuple<Masks...>,
0170                 mask
0171             >::apply(t, m);
0172 }
0173
0174 template
0175 <
0176     char II1, char IB1, char IE1,
0177     char BI1, char BB1, char BE1,
0178     char EI1, char EB1, char EE1,
0179     char II2, char IB2, char IE2,
0180     char BI2, char BB2, char BE2,
0181     char EI2, char EB2, char EE2
0182 >
0183 inline
0184 util::type_sequence
0185     <
0186         static_mask<II1, IB1, IE1, BI1, BB1, BE1, EI1, EB1, EE1>,
0187         static_mask<II2, IB2, IE2, BI2, BB2, BE2, EI2, EB2, EE2>
0188     >
0189 operator||(static_mask<II1, IB1, IE1, BI1, BB1, BE1, EI1, EB1, EE1> const& ,
0190            static_mask<II2, IB2, IE2, BI2, BB2, BE2, EI2, EB2, EE2> const& )
0191 {
0192     return util::type_sequence
0193             <
0194                 static_mask<II1, IB1, IE1, BI1, BB1, BE1, EI1, EB1, EE1>,
0195                 static_mask<II2, IB2, IE2, BI2, BB2, BE2, EI2, EB2, EE2>
0196             >();
0197 }
0198
0199 template
0200 <
0201     typename ...StaticMasks,
0202     char II, char IB, char IE,
0203     char BI, char BB, char BE,
0204     char EI, char EB, char EE
0205 >
0206 inline
0207 util::type_sequence
0208 <
0209     StaticMasks...,
0210     static_mask<II, IB, IE, BI, BB, BE, EI, EB, EE>
0211 >
0212 operator||(util::type_sequence<StaticMasks...> const& ,
0213            static_mask<II, IB, IE, BI, BB, BE, EI, EB, EE> const& )
0214 {
0215     return util::type_sequence
0216             <
0217                 StaticMasks...,
0218                 static_mask<II, IB, IE, BI, BB, BE, EI, EB, EE>
0219             >();
0220 }
0221
0222 } // namespace de9im
0223
0224
0225 #ifndef DOXYGEN_NO_DETAIL
0226 namespace detail { namespace de9im
0227 {
0228
0229 // PREDEFINED MASKS
0230
0231 // TODO:
0232 // 1. specialize for simplified masks if available
0233 // e.g. for TOUCHES use 1 mask for A/A
0234 // 2. Think about dimensions > 2 e.g. should TOUCHES be true
0235 // if the interior of the Areal overlaps the boundary of the Volumetric
0236 // like it's true for Linear/Areal
0237
0238 // EQUALS
0239 template <typename Geometry1, typename Geometry2>
0240 struct static_mask_equals_type
0241 {
0242     typedef geometry::de9im::static_mask<'T', '*', 'F', '*', '*', 'F', 'F', 'F', '*'> type; // wikipedia
0243     //typedef geometry::de9im::static_mask<'T', 'F', 'F', 'F', 'T', 'F', 'F', 'F', 'T'> type; // OGC
0244 };
0245
0246 // DISJOINT
0247 template <typename Geometry1, typename Geometry2>
0248 struct static_mask_disjoint_type
0249 {
0250     typedef geometry::de9im::static_mask<'F', 'F', '*', 'F', 'F', '*', '*', '*', '*'> type;
0251 };
0252
0253 // TOUCHES - NOT P/P
0254 template
0255 <
0256     typename Geometry1,
0257     typename Geometry2,
0258     std::size_t Dim1 = geometry::topological_dimension<Geometry1>::value,
0259     std::size_t Dim2 = geometry::topological_dimension<Geometry2>::value
0260 >
0261 struct static_mask_touches_impl
0262 {
0263     typedef util::type_sequence
0264         <
0265             geometry::de9im::static_mask<'F', 'T', '*', '*', '*', '*', '*', '*', '*'>,
0266             geometry::de9im::static_mask<'F', '*', '*', 'T', '*', '*', '*', '*', '*'>,
0267             geometry::de9im::static_mask<'F', '*', '*', '*', 'T', '*', '*', '*', '*'>
0268         > type;
0269 };
0270 // According to OGC, doesn't apply to P/P
0271 // Using the above mask the result would be always false
0272 template <typename Geometry1, typename Geometry2>
0273 struct static_mask_touches_impl<Geometry1, Geometry2, 0, 0>
0274 {
0275     typedef geometry::detail::relate::false_mask type;
0276 };
0277
0278 template <typename Geometry1, typename Geometry2>
0279 struct static_mask_touches_not_pp_type
0280     : static_mask_touches_impl<Geometry1, Geometry2, 2, 2> // dummy dimensions
0281 {};
0282
0283 template <typename Geometry1, typename Geometry2>
0284 struct static_mask_touches_type
0285     : static_mask_touches_impl<Geometry1, Geometry2>
0286 {};
0287
0288 // WITHIN
0289 template <typename Geometry1, typename Geometry2>
0290 struct static_mask_within_type
0291 {
0292     typedef geometry::de9im::static_mask<'T', '*', 'F', '*', '*', 'F', '*', '*', '*'> type;
0293 };
0294
0295 // COVERED_BY (non OGC)
0296 template <typename Geometry1, typename Geometry2>
0297 struct static_mask_covered_by_type
0298 {
0299     typedef util::type_sequence
0300         <
0301             geometry::de9im::static_mask<'T', '*', 'F', '*', '*', 'F', '*', '*', '*'>,
0302             geometry::de9im::static_mask<'*', 'T', 'F', '*', '*', 'F', '*', '*', '*'>,
0303             geometry::de9im::static_mask<'*', '*', 'F', 'T', '*', 'F', '*', '*', '*'>,
0304             geometry::de9im::static_mask<'*', '*', 'F', '*', 'T', 'F', '*', '*', '*'>
0305         > type;
0306 };
0307
0308 // CROSSES
0309 // dim(G1) < dim(G2) - P/L P/A L/A
0310 template
0311 <
0312     typename Geometry1,
0313     typename Geometry2,
0314     std::size_t Dim1 = geometry::topological_dimension<Geometry1>::value,
0315     std::size_t Dim2 = geometry::topological_dimension<Geometry2>::value,
0316     bool D1LessD2 = (Dim1 < Dim2)
0317 >
0318 struct static_mask_crosses_impl
0319 {
0320     typedef geometry::de9im::static_mask<'T', '*', 'T', '*', '*', '*', '*', '*', '*'> type;
0321 };
0322 // TODO: I'm not sure if this one below should be available!
0323 // dim(G1) > dim(G2) - L/P A/P A/L
0324 template
0325 <
0326     typename Geometry1, typename Geometry2, std::size_t Dim1, std::size_t Dim2
0327 >
0328 struct static_mask_crosses_impl<Geometry1, Geometry2, Dim1, Dim2, false>
0329 {
0330     typedef geometry::de9im::static_mask<'T', '*', '*', '*', '*', '*', 'T', '*', '*'> type;
0331 };
0332 // dim(G1) == dim(G2) - P/P A/A
0333 template
0334 <
0335     typename Geometry1, typename Geometry2, std::size_t Dim
0336 >
0337 struct static_mask_crosses_impl<Geometry1, Geometry2, Dim, Dim, false>
0338 {
0339     typedef geometry::detail::relate::false_mask type;
0340 };
0341 // dim(G1) == 1 && dim(G2) == 1 - L/L
0342 template <typename Geometry1, typename Geometry2>
0343 struct static_mask_crosses_impl<Geometry1, Geometry2, 1, 1, false>
0344 {
0345     typedef geometry::de9im::static_mask<'0', '*', '*', '*', '*', '*', '*', '*', '*'> type;
0346 };
0347
0348 template <typename Geometry1, typename Geometry2>
0349 struct static_mask_crosses_type
0350     : static_mask_crosses_impl<Geometry1, Geometry2>
0351 {};
0352
0353 template <typename Geometry1, typename Geometry2>
0354 struct static_mask_crosses_d1_le_d2_type // specific dimensions are not important here
0355     : static_mask_crosses_impl<Geometry1, Geometry2, 0, 1>
0356 {};
0357
0358 template <typename Geometry1, typename Geometry2>
0359 struct static_mask_crosses_d2_le_d1_type // specific dimensions are not important here
0360     : static_mask_crosses_impl<Geometry1, Geometry2, 1, 0>
0361 {};
0362
0363 template <typename Geometry1, typename Geometry2>
0364 struct static_mask_crosses_d1_1_d2_1_type
0365     : static_mask_crosses_impl<Geometry1, Geometry2, 1, 1>
0366 {};
0367
0368 // OVERLAPS
0369
0370 // dim(G1) != dim(G2) - NOT P/P, L/L, A/A
0371 template
0372 <
0373     typename Geometry1,
0374     typename Geometry2,
0375     std::size_t Dim1 = geometry::topological_dimension<Geometry1>::value,
0376     std::size_t Dim2 = geometry::topological_dimension<Geometry2>::value
0377 >
0378 struct static_mask_overlaps_impl
0379 {
0380     typedef geometry::detail::relate::false_mask type;
0381 };
0382 // dim(G1) == D && dim(G2) == D - P/P A/A
0383 template <typename Geometry1, typename Geometry2, std::size_t Dim>
0384 struct static_mask_overlaps_impl<Geometry1, Geometry2, Dim, Dim>
0385 {
0386     typedef geometry::de9im::static_mask<'T', '*', 'T', '*', '*', '*', 'T', '*', '*'> type;
0387 };
0388 // dim(G1) == 1 && dim(G2) == 1 - L/L
0389 template <typename Geometry1, typename Geometry2>
0390 struct static_mask_overlaps_impl<Geometry1, Geometry2, 1, 1>
0391 {
0392     typedef geometry::de9im::static_mask<'1', '*', 'T', '*', '*', '*', 'T', '*', '*'> type;
0393 };
0394
0395 template <typename Geometry1, typename Geometry2>
0396 struct static_mask_overlaps_type
0397     : static_mask_overlaps_impl<Geometry1, Geometry2>
0398 {};
0399
0400 template <typename Geometry1, typename Geometry2>
0401 struct static_mask_overlaps_d1_eq_d2_type
0402     : static_mask_overlaps_impl<Geometry1, Geometry2, 2, 2>
0403 {};
0404
0405 template <typename Geometry1, typename Geometry2>
0406 struct static_mask_overlaps_d1_1_d2_1_type
0407     : static_mask_overlaps_impl<Geometry1, Geometry2, 1, 1>
0408 {};
0409
0410 }} // namespace detail::de9im
0411 #endif // DOXYGEN_NO_DETAIL
0412
0413
0414 }} // namespace boost::geometry
0415
0416 #endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_RELATE_DE9IM_HPP