1 // Boost.Geometry (aka GGL, Generic Geometry Library)
2 
3 // Copyright (c) 2007-2015 Barend Gehrels, Amsterdam, the Netherlands.
4 // Copyright (c) 2008-2015 Bruno Lalande, Paris, France.
5 // Copyright (c) 2009-2015 Mateusz Loskot, London, UK.
6 // Copyright (c) 2014-2015 Adam Wulkiewicz, Lodz, Poland.
7 
8 // This file was modified by Oracle on 2014, 2015.
9 // Modifications copyright (c) 2014-2015 Oracle and/or its affiliates.
10 
11 // Contributed and/or modified by Adam Wulkiewicz, on behalf of Oracle
12 // Contributed and/or modified by Menelaos Karavelas, on behalf of Oracle
13 
14 // Parts of Boost.Geometry are redesigned from Geodan's Geographic Library
15 // (geolib/GGL), copyright (c) 1995-2010 Geodan, Amsterdam, the Netherlands.
16 
17 // Use, modification and distribution is subject to the Boost Software License,
18 // Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
19 // http://www.boost.org/LICENSE_1_0.txt)
20 
21 #ifndef BOOST_GEOMETRY_ALGORITHMS_EQUALS_HPP
22 #define BOOST_GEOMETRY_ALGORITHMS_EQUALS_HPP
23 
24 
25 #include <cstddef>
26 #include <vector>
27 
28 #include <boost/range.hpp>
29 
30 #include <boost/variant/apply_visitor.hpp>
31 #include <boost/variant/static_visitor.hpp>
32 #include <boost/variant/variant_fwd.hpp>
33 
34 #include <boost/geometry/core/access.hpp>
35 #include <boost/geometry/core/coordinate_dimension.hpp>
36 #include <boost/geometry/core/geometry_id.hpp>
37 #include <boost/geometry/core/reverse_dispatch.hpp>
38 #include <boost/geometry/core/tags.hpp>
39 
40 #include <boost/geometry/geometries/concepts/check.hpp>
41 
42 #include <boost/geometry/algorithms/detail/equals/point_point.hpp>
43 #include <boost/geometry/algorithms/detail/not.hpp>
44 #include <boost/geometry/algorithms/not_implemented.hpp>
45 
46 // For trivial checks
47 #include <boost/geometry/algorithms/area.hpp>
48 #include <boost/geometry/algorithms/length.hpp>
49 #include <boost/geometry/util/math.hpp>
50 #include <boost/geometry/util/select_coordinate_type.hpp>
51 #include <boost/geometry/util/select_most_precise.hpp>
52 
53 #include <boost/geometry/algorithms/detail/equals/collect_vectors.hpp>
54 #include <boost/geometry/algorithms/relate.hpp>
55 #include <boost/geometry/algorithms/detail/relate/relate_impl.hpp>
56 
57 #include <boost/geometry/views/detail/indexed_point_view.hpp>
58 
59 
60 namespace boost { namespace geometry
61 {
62 
63 #ifndef DOXYGEN_NO_DETAIL
64 namespace detail { namespace equals
65 {
66 
67 
68 template
69 <
70     std::size_t Dimension,
71     std::size_t DimensionCount
72 >
73 struct box_box
74 {
75     template <typename Box1, typename Box2>
applyboost::geometry::detail::equals::box_box76     static inline bool apply(Box1 const& box1, Box2 const& box2)
77     {
78         if (!geometry::math::equals(get<min_corner, Dimension>(box1), get<min_corner, Dimension>(box2))
79             || !geometry::math::equals(get<max_corner, Dimension>(box1), get<max_corner, Dimension>(box2)))
80         {
81             return false;
82         }
83         return box_box<Dimension + 1, DimensionCount>::apply(box1, box2);
84     }
85 };
86 
87 template <std::size_t DimensionCount>
88 struct box_box<DimensionCount, DimensionCount>
89 {
90     template <typename Box1, typename Box2>
applyboost::geometry::detail::equals::box_box91     static inline bool apply(Box1 const& , Box2 const& )
92     {
93         return true;
94     }
95 };
96 
97 
98 struct segment_segment
99 {
100     template <typename Segment1, typename Segment2>
applyboost::geometry::detail::equals::segment_segment101     static inline bool apply(Segment1 const& segment1, Segment2 const& segment2)
102     {
103         return equals::equals_point_point(
104                     indexed_point_view<Segment1 const, 0>(segment1),
105                     indexed_point_view<Segment2 const, 0>(segment2) )
106                 ? equals::equals_point_point(
107                     indexed_point_view<Segment1 const, 1>(segment1),
108                     indexed_point_view<Segment2 const, 1>(segment2) )
109                 : ( equals::equals_point_point(
110                         indexed_point_view<Segment1 const, 0>(segment1),
111                         indexed_point_view<Segment2 const, 1>(segment2) )
112                  && equals::equals_point_point(
113                         indexed_point_view<Segment1 const, 1>(segment1),
114                         indexed_point_view<Segment2 const, 0>(segment2) )
115                   );
116     }
117 };
118 
119 
120 struct area_check
121 {
122     template <typename Geometry1, typename Geometry2>
applyboost::geometry::detail::equals::area_check123     static inline bool apply(Geometry1 const& geometry1, Geometry2 const& geometry2)
124     {
125         return geometry::math::equals(
126                 geometry::area(geometry1),
127                 geometry::area(geometry2));
128     }
129 };
130 
131 
132 struct length_check
133 {
134     template <typename Geometry1, typename Geometry2>
applyboost::geometry::detail::equals::length_check135     static inline bool apply(Geometry1 const& geometry1, Geometry2 const& geometry2)
136     {
137         return geometry::math::equals(
138                 geometry::length(geometry1),
139                 geometry::length(geometry2));
140     }
141 };
142 
143 
144 template <typename TrivialCheck>
145 struct equals_by_collection
146 {
147     template <typename Geometry1, typename Geometry2>
applyboost::geometry::detail::equals::equals_by_collection148     static inline bool apply(Geometry1 const& geometry1, Geometry2 const& geometry2)
149     {
150         if (! TrivialCheck::apply(geometry1, geometry2))
151         {
152             return false;
153         }
154 
155         typedef typename geometry::select_most_precise
156             <
157                 typename select_coordinate_type
158                     <
159                         Geometry1, Geometry2
160                     >::type,
161                 double
162             >::type calculation_type;
163 
164         typedef std::vector<collected_vector<calculation_type> > v;
165         v c1, c2;
166 
167         geometry::collect_vectors(c1, geometry1);
168         geometry::collect_vectors(c2, geometry2);
169 
170         if (boost::size(c1) != boost::size(c2))
171         {
172             return false;
173         }
174 
175         std::sort(c1.begin(), c1.end());
176         std::sort(c2.begin(), c2.end());
177 
178         // Just check if these vectors are equal.
179         return std::equal(c1.begin(), c1.end(), c2.begin());
180     }
181 };
182 
183 template<typename Geometry1, typename Geometry2>
184 struct equals_by_relate
185     : detail::relate::relate_impl
186         <
187             detail::de9im::static_mask_equals_type,
188             Geometry1,
189             Geometry2
190         >
191 {};
192 
193 }} // namespace detail::equals
194 #endif // DOXYGEN_NO_DETAIL
195 
196 
197 #ifndef DOXYGEN_NO_DISPATCH
198 namespace dispatch
199 {
200 
201 template
202 <
203     typename Geometry1,
204     typename Geometry2,
205     typename Tag1 = typename tag<Geometry1>::type,
206     typename Tag2 = typename tag<Geometry2>::type,
207     std::size_t DimensionCount = dimension<Geometry1>::type::value,
208     bool Reverse = reverse_dispatch<Geometry1, Geometry2>::type::value
209 >
210 struct equals: not_implemented<Tag1, Tag2>
211 {};
212 
213 
214 // If reversal is needed, perform it
215 template
216 <
217     typename Geometry1, typename Geometry2,
218     typename Tag1, typename Tag2,
219     std::size_t DimensionCount
220 >
221 struct equals<Geometry1, Geometry2, Tag1, Tag2, DimensionCount, true>
222     : equals<Geometry2, Geometry1, Tag2, Tag1, DimensionCount, false>
223 {
applyboost::geometry::dispatch::equals224     static inline bool apply(Geometry1 const& g1, Geometry2 const& g2)
225     {
226         return equals
227             <
228                 Geometry2, Geometry1,
229                 Tag2, Tag1,
230                 DimensionCount,
231                 false
232             >::apply(g2, g1);
233     }
234 };
235 
236 
237 template <typename P1, typename P2, std::size_t DimensionCount, bool Reverse>
238 struct equals<P1, P2, point_tag, point_tag, DimensionCount, Reverse>
239     : geometry::detail::not_
240         <
241             detail::disjoint::point_point<P1, P2, 0, DimensionCount>
242         >
243 {};
244 
245 
246 template <typename Box1, typename Box2, std::size_t DimensionCount, bool Reverse>
247 struct equals<Box1, Box2, box_tag, box_tag, DimensionCount, Reverse>
248     : detail::equals::box_box<0, DimensionCount>
249 {};
250 
251 
252 template <typename Ring1, typename Ring2, bool Reverse>
253 struct equals<Ring1, Ring2, ring_tag, ring_tag, 2, Reverse>
254     : detail::equals::equals_by_collection<detail::equals::area_check>
255 {};
256 
257 
258 template <typename Polygon1, typename Polygon2, bool Reverse>
259 struct equals<Polygon1, Polygon2, polygon_tag, polygon_tag, 2, Reverse>
260     : detail::equals::equals_by_collection<detail::equals::area_check>
261 {};
262 
263 
264 template <typename Polygon, typename Ring, bool Reverse>
265 struct equals<Polygon, Ring, polygon_tag, ring_tag, 2, Reverse>
266     : detail::equals::equals_by_collection<detail::equals::area_check>
267 {};
268 
269 
270 template <typename Ring, typename Box, bool Reverse>
271 struct equals<Ring, Box, ring_tag, box_tag, 2, Reverse>
272     : detail::equals::equals_by_collection<detail::equals::area_check>
273 {};
274 
275 
276 template <typename Polygon, typename Box, bool Reverse>
277 struct equals<Polygon, Box, polygon_tag, box_tag, 2, Reverse>
278     : detail::equals::equals_by_collection<detail::equals::area_check>
279 {};
280 
281 template <typename Segment1, typename Segment2, std::size_t DimensionCount, bool Reverse>
282 struct equals<Segment1, Segment2, segment_tag, segment_tag, DimensionCount, Reverse>
283     : detail::equals::segment_segment
284 {};
285 
286 template <typename LineString1, typename LineString2, bool Reverse>
287 struct equals<LineString1, LineString2, linestring_tag, linestring_tag, 2, Reverse>
288     //: detail::equals::equals_by_collection<detail::equals::length_check>
289     : detail::equals::equals_by_relate<LineString1, LineString2>
290 {};
291 
292 template <typename LineString, typename MultiLineString, bool Reverse>
293 struct equals<LineString, MultiLineString, linestring_tag, multi_linestring_tag, 2, Reverse>
294     : detail::equals::equals_by_relate<LineString, MultiLineString>
295 {};
296 
297 template <typename MultiLineString1, typename MultiLineString2, bool Reverse>
298 struct equals<MultiLineString1, MultiLineString2, multi_linestring_tag, multi_linestring_tag, 2, Reverse>
299     : detail::equals::equals_by_relate<MultiLineString1, MultiLineString2>
300 {};
301 
302 
303 template <typename MultiPolygon1, typename MultiPolygon2, bool Reverse>
304 struct equals
305     <
306         MultiPolygon1, MultiPolygon2,
307         multi_polygon_tag, multi_polygon_tag,
308         2,
309         Reverse
310     >
311     : detail::equals::equals_by_collection<detail::equals::area_check>
312 {};
313 
314 
315 template <typename Polygon, typename MultiPolygon, bool Reverse>
316 struct equals
317     <
318         Polygon, MultiPolygon,
319         polygon_tag, multi_polygon_tag,
320         2,
321         Reverse
322     >
323     : detail::equals::equals_by_collection<detail::equals::area_check>
324 {};
325 
326 
327 } // namespace dispatch
328 #endif // DOXYGEN_NO_DISPATCH
329 
330 
331 namespace resolve_variant {
332 
333 template <typename Geometry1, typename Geometry2>
334 struct equals
335 {
applyboost::geometry::resolve_variant::equals336     static inline bool apply(Geometry1 const& geometry1,
337                              Geometry2 const& geometry2)
338     {
339         concept::check_concepts_and_equal_dimensions
340         <
341             Geometry1 const,
342             Geometry2 const
343         >();
344 
345         return dispatch::equals<Geometry1, Geometry2>
346                        ::apply(geometry1, geometry2);
347     }
348 };
349 
350 template <BOOST_VARIANT_ENUM_PARAMS(typename T), typename Geometry2>
351 struct equals<boost::variant<BOOST_VARIANT_ENUM_PARAMS(T)>, Geometry2>
352 {
353     struct visitor: static_visitor<bool>
354     {
355         Geometry2 const& m_geometry2;
356 
visitorboost::geometry::resolve_variant::equals::visitor357         visitor(Geometry2 const& geometry2)
358             : m_geometry2(geometry2)
359         {}
360 
361         template <typename Geometry1>
operator ()boost::geometry::resolve_variant::equals::visitor362         inline bool operator()(Geometry1 const& geometry1) const
363         {
364             return equals<Geometry1, Geometry2>
365                    ::apply(geometry1, m_geometry2);
366         }
367 
368     };
369 
applyboost::geometry::resolve_variant::equals370     static inline bool apply(
371         boost::variant<BOOST_VARIANT_ENUM_PARAMS(T)> const& geometry1,
372         Geometry2 const& geometry2
373     )
374     {
375         return boost::apply_visitor(visitor(geometry2), geometry1);
376     }
377 };
378 
379 template <typename Geometry1, BOOST_VARIANT_ENUM_PARAMS(typename T)>
380 struct equals<Geometry1, boost::variant<BOOST_VARIANT_ENUM_PARAMS(T)> >
381 {
382     struct visitor: static_visitor<bool>
383     {
384         Geometry1 const& m_geometry1;
385 
visitorboost::geometry::resolve_variant::equals::visitor386         visitor(Geometry1 const& geometry1)
387             : m_geometry1(geometry1)
388         {}
389 
390         template <typename Geometry2>
operator ()boost::geometry::resolve_variant::equals::visitor391         inline bool operator()(Geometry2 const& geometry2) const
392         {
393             return equals<Geometry1, Geometry2>
394                    ::apply(m_geometry1, geometry2);
395         }
396 
397     };
398 
applyboost::geometry::resolve_variant::equals399     static inline bool apply(
400         Geometry1 const& geometry1,
401         boost::variant<BOOST_VARIANT_ENUM_PARAMS(T)> const& geometry2
402     )
403     {
404         return boost::apply_visitor(visitor(geometry1), geometry2);
405     }
406 };
407 
408 template <
409     BOOST_VARIANT_ENUM_PARAMS(typename T1),
410     BOOST_VARIANT_ENUM_PARAMS(typename T2)
411 >
412 struct equals<
413     boost::variant<BOOST_VARIANT_ENUM_PARAMS(T1)>,
414     boost::variant<BOOST_VARIANT_ENUM_PARAMS(T2)>
415 >
416 {
417     struct visitor: static_visitor<bool>
418     {
419         template <typename Geometry1, typename Geometry2>
operator ()boost::geometry::resolve_variant::equals::visitor420         inline bool operator()(Geometry1 const& geometry1,
421                                Geometry2 const& geometry2) const
422         {
423             return equals<Geometry1, Geometry2>
424                    ::apply(geometry1, geometry2);
425         }
426 
427     };
428 
applyboost::geometry::resolve_variant::equals429     static inline bool apply(
430         boost::variant<BOOST_VARIANT_ENUM_PARAMS(T1)> const& geometry1,
431         boost::variant<BOOST_VARIANT_ENUM_PARAMS(T2)> const& geometry2
432     )
433     {
434         return boost::apply_visitor(visitor(), geometry1, geometry2);
435     }
436 };
437 
438 } // namespace resolve_variant
439 
440 
441 /*!
442 \brief \brief_check{are spatially equal}
443 \details \details_check12{equals, is spatially equal}. Spatially equal means
444     that the same point set is included. A box can therefore be spatially equal
445     to a ring or a polygon, or a linestring can be spatially equal to a
446     multi-linestring or a segment. This only works theoretically, not all
447     combinations are implemented yet.
448 \ingroup equals
449 \tparam Geometry1 \tparam_geometry
450 \tparam Geometry2 \tparam_geometry
451 \param geometry1 \param_geometry
452 \param geometry2 \param_geometry
453 \return \return_check2{are spatially equal}
454 
455 \qbk{[include reference/algorithms/equals.qbk]}
456 
457  */
458 template <typename Geometry1, typename Geometry2>
equals(Geometry1 const & geometry1,Geometry2 const & geometry2)459 inline bool equals(Geometry1 const& geometry1, Geometry2 const& geometry2)
460 {
461     return resolve_variant::equals<Geometry1, Geometry2>
462                           ::apply(geometry1, geometry2);
463 }
464 
465 
466 }} // namespace boost::geometry
467 
468 
469 #endif // BOOST_GEOMETRY_ALGORITHMS_EQUALS_HPP
470 
471