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 */
mask(const char * code)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 */
mask(std::string const & code)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 >
operator ||(mask const & m1,mask const & m2)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
operator ||(boost::tuples::cons<mask,Tail> const & t,mask const & m)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 >
operator ||(static_mask<II1,IB1,IE1,BI1,BB1,BE1,EI1,EB1,EE1> const &,static_mask<II2,IB2,IE2,BI2,BB2,BE2,EI2,EB2,EE2> const &)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
operator ||(Seq const &,static_mask<II,IB,IE,BI,BB,BE,EI,EB,EE> const &)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
432