boost/geometry/algorithms/equals.hpp

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