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