ceph/src/boost/libs/geometry/include/boost/geometry/algorithms/equals.hpp

   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, 2016.
   9 // Modifications copyright (c) 2014-2016 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>
  76     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>
  91     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>
 101     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>
 123     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>
 135     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>
 148     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 geometry::collected_vector
 165             <
 166                 calculation_type,
 167                 Geometry1
 168             > collected_vector;
 169
 170         std::vector<collected_vector> c1, c2;
 171
 172         geometry::collect_vectors(c1, geometry1);
 173         geometry::collect_vectors(c2, geometry2);
 174
 175         if (boost::size(c1) != boost::size(c2))
 176         {
 177             return false;
 178         }
 179
 180         std::sort(c1.begin(), c1.end());
 181         std::sort(c2.begin(), c2.end());
 182
 183         // Just check if these vectors are equal.
 184         return std::equal(c1.begin(), c1.end(), c2.begin());
 185     }
 186 };
 187
 188 template<typename Geometry1, typename Geometry2>
 189 struct equals_by_relate
 190     : detail::relate::relate_impl
 191         <
 192             detail::de9im::static_mask_equals_type,
 193             Geometry1,
 194             Geometry2
 195         >
 196 {};
 197
 198 }} // namespace detail::equals
 199 #endif // DOXYGEN_NO_DETAIL
 200
 201
 202 #ifndef DOXYGEN_NO_DISPATCH
 203 namespace dispatch
 204 {
 205
 206 template
 207 <
 208     typename Geometry1,
 209     typename Geometry2,
 210     typename Tag1 = typename tag<Geometry1>::type,
 211     typename Tag2 = typename tag<Geometry2>::type,
 212     std::size_t DimensionCount = dimension<Geometry1>::type::value,
 213     bool Reverse = reverse_dispatch<Geometry1, Geometry2>::type::value
 214 >
 215 struct equals: not_implemented<Tag1, Tag2>
 216 {};
 217
 218
 219 // If reversal is needed, perform it
 220 template
 221 <
 222     typename Geometry1, typename Geometry2,
 223     typename Tag1, typename Tag2,
 224     std::size_t DimensionCount
 225 >
 226 struct equals<Geometry1, Geometry2, Tag1, Tag2, DimensionCount, true>
 227     : equals<Geometry2, Geometry1, Tag2, Tag1, DimensionCount, false>
 228 {
 229     static inline bool apply(Geometry1 const& g1, Geometry2 const& g2)
 230     {
 231         return equals
 232             <
 233                 Geometry2, Geometry1,
 234                 Tag2, Tag1,
 235                 DimensionCount,
 236                 false
 237             >::apply(g2, g1);
 238     }
 239 };
 240
 241
 242 template <typename P1, typename P2, std::size_t DimensionCount, bool Reverse>
 243 struct equals<P1, P2, point_tag, point_tag, DimensionCount, Reverse>
 244     : geometry::detail::not_
 245         <
 246             detail::disjoint::point_point<P1, P2, 0, DimensionCount>
 247         >
 248 {};
 249
 250
 251 template <typename Box1, typename Box2, std::size_t DimensionCount, bool Reverse>
 252 struct equals<Box1, Box2, box_tag, box_tag, DimensionCount, Reverse>
 253     : detail::equals::box_box<0, DimensionCount>
 254 {};
 255
 256
 257 template <typename Ring1, typename Ring2, bool Reverse>
 258 struct equals<Ring1, Ring2, ring_tag, ring_tag, 2, Reverse>
 259     : detail::equals::equals_by_collection<detail::equals::area_check>
 260 {};
 261
 262
 263 template <typename Polygon1, typename Polygon2, bool Reverse>
 264 struct equals<Polygon1, Polygon2, polygon_tag, polygon_tag, 2, Reverse>
 265     : detail::equals::equals_by_collection<detail::equals::area_check>
 266 {};
 267
 268
 269 template <typename Polygon, typename Ring, bool Reverse>
 270 struct equals<Polygon, Ring, polygon_tag, ring_tag, 2, Reverse>
 271     : detail::equals::equals_by_collection<detail::equals::area_check>
 272 {};
 273
 274
 275 template <typename Ring, typename Box, bool Reverse>
 276 struct equals<Ring, Box, ring_tag, box_tag, 2, Reverse>
 277     : detail::equals::equals_by_collection<detail::equals::area_check>
 278 {};
 279
 280
 281 template <typename Polygon, typename Box, bool Reverse>
 282 struct equals<Polygon, Box, polygon_tag, box_tag, 2, Reverse>
 283     : detail::equals::equals_by_collection<detail::equals::area_check>
 284 {};
 285
 286 template <typename Segment1, typename Segment2, std::size_t DimensionCount, bool Reverse>
 287 struct equals<Segment1, Segment2, segment_tag, segment_tag, DimensionCount, Reverse>
 288     : detail::equals::segment_segment
 289 {};
 290
 291 template <typename LineString1, typename LineString2, bool Reverse>
 292 struct equals<LineString1, LineString2, linestring_tag, linestring_tag, 2, Reverse>
 293     //: detail::equals::equals_by_collection<detail::equals::length_check>
 294     : detail::equals::equals_by_relate<LineString1, LineString2>
 295 {};
 296
 297 template <typename LineString, typename MultiLineString, bool Reverse>
 298 struct equals<LineString, MultiLineString, linestring_tag, multi_linestring_tag, 2, Reverse>
 299     : detail::equals::equals_by_relate<LineString, MultiLineString>
 300 {};
 301
 302 template <typename MultiLineString1, typename MultiLineString2, bool Reverse>
 303 struct equals<MultiLineString1, MultiLineString2, multi_linestring_tag, multi_linestring_tag, 2, Reverse>
 304     : detail::equals::equals_by_relate<MultiLineString1, MultiLineString2>
 305 {};
 306
 307
 308 template <typename MultiPolygon1, typename MultiPolygon2, bool Reverse>
 309 struct equals
 310     <
 311         MultiPolygon1, MultiPolygon2,
 312         multi_polygon_tag, multi_polygon_tag,
 313         2,
 314         Reverse
 315     >
 316     : detail::equals::equals_by_collection<detail::equals::area_check>
 317 {};
 318
 319
 320 template <typename Polygon, typename MultiPolygon, bool Reverse>
 321 struct equals
 322     <
 323         Polygon, MultiPolygon,
 324         polygon_tag, multi_polygon_tag,
 325         2,
 326         Reverse
 327     >
 328     : detail::equals::equals_by_collection<detail::equals::area_check>
 329 {};
 330
 331 template <typename MultiPolygon, typename Ring, bool Reverse>
 332 struct equals
 333     <
 334         MultiPolygon, Ring,
 335         multi_polygon_tag, ring_tag,
 336         2,
 337         Reverse
 338     >
 339     : detail::equals::equals_by_collection<detail::equals::area_check>
 340 {};
 341
 342
 343 } // namespace dispatch
 344 #endif // DOXYGEN_NO_DISPATCH
 345
 346
 347 namespace resolve_variant {
 348
 349 template <typename Geometry1, typename Geometry2>
 350 struct equals
 351 {
 352     static inline bool apply(Geometry1 const& geometry1,
 353                              Geometry2 const& geometry2)
 354     {
 355         concepts::check_concepts_and_equal_dimensions
 356         <
 357             Geometry1 const,
 358             Geometry2 const
 359         >();
 360
 361         return dispatch::equals<Geometry1, Geometry2>
 362                        ::apply(geometry1, geometry2);
 363     }
 364 };
 365
 366 template <BOOST_VARIANT_ENUM_PARAMS(typename T), typename Geometry2>
 367 struct equals<boost::variant<BOOST_VARIANT_ENUM_PARAMS(T)>, Geometry2>
 368 {
 369     struct visitor: static_visitor<bool>
 370     {
 371         Geometry2 const& m_geometry2;
 372
 373         visitor(Geometry2 const& geometry2)
 374             : m_geometry2(geometry2)
 375         {}
 376
 377         template <typename Geometry1>
 378         inline bool operator()(Geometry1 const& geometry1) const
 379         {
 380             return equals<Geometry1, Geometry2>
 381                    ::apply(geometry1, m_geometry2);
 382         }
 383
 384     };
 385
 386     static inline bool apply(
 387         boost::variant<BOOST_VARIANT_ENUM_PARAMS(T)> const& geometry1,
 388         Geometry2 const& geometry2
 389     )
 390     {
 391         return boost::apply_visitor(visitor(geometry2), geometry1);
 392     }
 393 };
 394
 395 template <typename Geometry1, BOOST_VARIANT_ENUM_PARAMS(typename T)>
 396 struct equals<Geometry1, boost::variant<BOOST_VARIANT_ENUM_PARAMS(T)> >
 397 {
 398     struct visitor: static_visitor<bool>
 399     {
 400         Geometry1 const& m_geometry1;
 401
 402         visitor(Geometry1 const& geometry1)
 403             : m_geometry1(geometry1)
 404         {}
 405
 406         template <typename Geometry2>
 407         inline bool operator()(Geometry2 const& geometry2) const
 408         {
 409             return equals<Geometry1, Geometry2>
 410                    ::apply(m_geometry1, geometry2);
 411         }
 412
 413     };
 414
 415     static inline bool apply(
 416         Geometry1 const& geometry1,
 417         boost::variant<BOOST_VARIANT_ENUM_PARAMS(T)> const& geometry2
 418     )
 419     {
 420         return boost::apply_visitor(visitor(geometry1), geometry2);
 421     }
 422 };
 423
 424 template <
 425     BOOST_VARIANT_ENUM_PARAMS(typename T1),
 426     BOOST_VARIANT_ENUM_PARAMS(typename T2)
 427 >
 428 struct equals<
 429     boost::variant<BOOST_VARIANT_ENUM_PARAMS(T1)>,
 430     boost::variant<BOOST_VARIANT_ENUM_PARAMS(T2)>
 431 >
 432 {
 433     struct visitor: static_visitor<bool>
 434     {
 435         template <typename Geometry1, typename Geometry2>
 436         inline bool operator()(Geometry1 const& geometry1,
 437                                Geometry2 const& geometry2) const
 438         {
 439             return equals<Geometry1, Geometry2>
 440                    ::apply(geometry1, geometry2);
 441         }
 442
 443     };
 444
 445     static inline bool apply(
 446         boost::variant<BOOST_VARIANT_ENUM_PARAMS(T1)> const& geometry1,
 447         boost::variant<BOOST_VARIANT_ENUM_PARAMS(T2)> const& geometry2
 448     )
 449     {
 450         return boost::apply_visitor(visitor(), geometry1, geometry2);
 451     }
 452 };
 453
 454 } // namespace resolve_variant
 455
 456
 457 /*!
 458 \brief \brief_check{are spatially equal}
 459 \details \details_check12{equals, is spatially equal}. Spatially equal means
 460     that the same point set is included. A box can therefore be spatially equal
 461     to a ring or a polygon, or a linestring can be spatially equal to a
 462     multi-linestring or a segment. This only works theoretically, not all
 463     combinations are implemented yet.
 464 \ingroup equals
 465 \tparam Geometry1 \tparam_geometry
 466 \tparam Geometry2 \tparam_geometry
 467 \param geometry1 \param_geometry
 468 \param geometry2 \param_geometry
 469 \return \return_check2{are spatially equal}
 470
 471 \qbk{[include reference/algorithms/equals.qbk]}
 472
 473  */
 474 template <typename Geometry1, typename Geometry2>
 475 inline bool equals(Geometry1 const& geometry1, Geometry2 const& geometry2)
 476 {
 477     return resolve_variant::equals<Geometry1, Geometry2>
 478                           ::apply(geometry1, geometry2);
 479 }
 480
 481
 482 }} // namespace boost::geometry
 483
 484
 485 #endif // BOOST_GEOMETRY_ALGORITHMS_EQUALS_HPP
 486