ceph/src/boost/boost/geometry/algorithms/detail/equals/implementation.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-2021.
   9 // Modifications copyright (c) 2014-2021 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_DETAIL_EQUALS_IMPLEMENTATION_HPP
  22 #define BOOST_GEOMETRY_ALGORITHMS_DETAIL_EQUALS_IMPLEMENTATION_HPP
  23
  24
  25 #include <cstddef>
  26 #include <type_traits>
  27 #include <vector>
  28
  29 #include <boost/range/size.hpp>
  30
  31 #include <boost/geometry/core/access.hpp>
  32 #include <boost/geometry/core/tags.hpp>
  33
  34 #include <boost/geometry/algorithms/area.hpp>
  35 #include <boost/geometry/algorithms/length.hpp>
  36 #include <boost/geometry/algorithms/detail/equals/point_point.hpp>
  37 #include <boost/geometry/algorithms/detail/equals/collect_vectors.hpp>
  38 #include <boost/geometry/algorithms/detail/equals/interface.hpp>
  39 #include <boost/geometry/algorithms/detail/relate/relate_impl.hpp>
  40 #include <boost/geometry/algorithms/relate.hpp>
  41
  42 #include <boost/geometry/strategies/relate/cartesian.hpp>
  43 #include <boost/geometry/strategies/relate/geographic.hpp>
  44 #include <boost/geometry/strategies/relate/spherical.hpp>
  45
  46 #include <boost/geometry/util/math.hpp>
  47 #include <boost/geometry/util/select_coordinate_type.hpp>
  48 #include <boost/geometry/util/select_most_precise.hpp>
  49
  50 #include <boost/geometry/views/detail/indexed_point_view.hpp>
  51
  52
  53 namespace boost { namespace geometry
  54 {
  55
  56 #ifndef DOXYGEN_NO_DETAIL
  57 namespace detail { namespace equals
  58 {
  59
  60
  61 template
  62 <
  63     std::size_t Dimension,
  64     std::size_t DimensionCount
  65 >
  66 struct point_point
  67 {
  68     template <typename Point1, typename Point2, typename Strategy>
  69     static inline bool apply(Point1 const& point1, Point2 const& point2,
  70                              Strategy const& strategy)
  71     {
  72         typedef decltype(strategy.relate(point1, point2)) strategy_type;
  73         return strategy_type::apply(point1, point2);
  74     }
  75 };
  76
  77
  78 template
  79 <
  80     std::size_t Dimension,
  81     std::size_t DimensionCount
  82 >
  83 struct box_box
  84 {
  85     template <typename Box1, typename Box2, typename Strategy>
  86     static inline bool apply(Box1 const& box1, Box2 const& box2, Strategy const& strategy)
  87     {
  88         if (!geometry::math::equals(get<min_corner, Dimension>(box1), get<min_corner, Dimension>(box2))
  89             || !geometry::math::equals(get<max_corner, Dimension>(box1), get<max_corner, Dimension>(box2)))
  90         {
  91             return false;
  92         }
  93         return box_box<Dimension + 1, DimensionCount>::apply(box1, box2, strategy);
  94     }
  95 };
  96
  97 template <std::size_t DimensionCount>
  98 struct box_box<DimensionCount, DimensionCount>
  99 {
 100     template <typename Box1, typename Box2, typename Strategy>
 101     static inline bool apply(Box1 const& , Box2 const& , Strategy const& )
 102     {
 103         return true;
 104     }
 105 };
 106
 107
 108 struct segment_segment
 109 {
 110     template <typename Segment1, typename Segment2, typename Strategy>
 111     static inline bool apply(Segment1 const& segment1, Segment2 const& segment2,
 112                              Strategy const& strategy)
 113     {
 114         return equals::equals_point_point(
 115                     indexed_point_view<Segment1 const, 0>(segment1),
 116                     indexed_point_view<Segment2 const, 0>(segment2),
 117                     strategy)
 118                 ? equals::equals_point_point(
 119                     indexed_point_view<Segment1 const, 1>(segment1),
 120                     indexed_point_view<Segment2 const, 1>(segment2),
 121                     strategy)
 122                 : ( equals::equals_point_point(
 123                         indexed_point_view<Segment1 const, 0>(segment1),
 124                         indexed_point_view<Segment2 const, 1>(segment2),
 125                         strategy)
 126                  && equals::equals_point_point(
 127                         indexed_point_view<Segment1 const, 1>(segment1),
 128                         indexed_point_view<Segment2 const, 0>(segment2),
 129                         strategy)
 130                   );
 131     }
 132 };
 133
 134
 135 struct area_check
 136 {
 137     template <typename Geometry1, typename Geometry2, typename Strategy>
 138     static inline bool apply(Geometry1 const& geometry1,
 139                              Geometry2 const& geometry2,
 140                              Strategy const& strategy)
 141     {
 142         return geometry::math::equals(geometry::area(geometry1, strategy),
 143                                       geometry::area(geometry2, strategy));
 144     }
 145 };
 146
 147
 148 /*
 149 struct length_check
 150 {
 151     template <typename Geometry1, typename Geometry2, typename Strategy>
 152     static inline bool apply(Geometry1 const& geometry1,
 153                              Geometry2 const& geometry2,
 154                              Strategy const& strategy)
 155     {
 156         return geometry::math::equals(geometry::length(geometry1, strategy),
 157                                       geometry::length(geometry2, strategy));
 158     }
 159 };
 160 */
 161
 162
 163 // Small helper structure do decide to use collect_vectors, or not
 164 template <typename Strategy, typename CsTag>
 165 struct use_collect_vectors
 166 {
 167     static constexpr bool value = false;
 168 };
 169
 170 template <typename Strategy>
 171 struct use_collect_vectors<Strategy, cartesian_tag>
 172 {
 173     static constexpr bool value = true;
 174
 175     template <typename T, typename Point>
 176     using type = collected_vector_cartesian<T>;
 177 };
 178
 179 template <typename CV>
 180 struct use_collect_vectors<strategy::side::spherical_side_formula<CV>, spherical_tag>
 181 {
 182     static constexpr bool value = true;
 183
 184     template <typename T, typename Point>
 185     using type = collected_vector_spherical<T, Point>;
 186 };
 187
 188
 189 template <typename TrivialCheck>
 190 struct equals_by_collection
 191 {
 192     template <typename Geometry1, typename Geometry2, typename Strategy>
 193     static inline bool apply(Geometry1 const& geometry1,
 194                              Geometry2 const& geometry2,
 195                              Strategy const& strategy)
 196     {
 197         if (! TrivialCheck::apply(geometry1, geometry2, strategy))
 198         {
 199             return false;
 200         }
 201
 202         using calculation_type = typename geometry::select_most_precise
 203             <
 204                 typename select_coordinate_type
 205                     <
 206                         Geometry1, Geometry2
 207                     >::type,
 208                 double
 209             >::type;
 210
 211         using collected_vector_type = typename use_collect_vectors
 212             <
 213                 decltype(std::declval<Strategy>().side()),
 214                 typename Strategy::cs_tag
 215             >::template type
 216                 <
 217                     calculation_type,
 218                     typename geometry::point_type<Geometry1>::type
 219                 >;
 220
 221         std::vector<collected_vector_type> c1, c2;
 222
 223         geometry::collect_vectors(c1, geometry1);
 224         geometry::collect_vectors(c2, geometry2);
 225
 226         if (boost::size(c1) != boost::size(c2))
 227         {
 228             return false;
 229         }
 230
 231         std::sort(c1.begin(), c1.end());
 232         std::sort(c2.begin(), c2.end());
 233
 234         // Check if these vectors are equal.
 235         return std::equal(c1.begin(), c1.end(), c2.begin());
 236     }
 237 };
 238
 239 template<typename Geometry1, typename Geometry2>
 240 struct equals_by_relate
 241     : detail::relate::relate_impl
 242         <
 243             detail::de9im::static_mask_equals_type,
 244             Geometry1,
 245             Geometry2
 246         >
 247 {};
 248
 249 // Use either collect_vectors or relate
 250 // NOTE: the result could be conceptually different for invalid
 251 // geometries in different coordinate systems because collect_vectors
 252 // and relate treat invalid geometries differently.
 253 template<typename TrivialCheck>
 254 struct equals_by_collection_or_relate
 255 {
 256     template <typename Strategy>
 257     using use_vectors = use_collect_vectors
 258         <
 259             decltype(std::declval<Strategy>().side()),
 260             typename Strategy::cs_tag
 261         >;
 262
 263     template
 264     <
 265         typename Geometry1, typename Geometry2, typename Strategy,
 266         std::enable_if_t<use_vectors<Strategy>::value, int> = 0
 267     >
 268     static inline bool apply(Geometry1 const& geometry1,
 269                              Geometry2 const& geometry2,
 270                              Strategy const& strategy)
 271     {
 272         return equals_by_collection<TrivialCheck>::apply(geometry1, geometry2, strategy);
 273     }
 274
 275     template
 276     <
 277         typename Geometry1, typename Geometry2, typename Strategy,
 278         std::enable_if_t<! use_vectors<Strategy>::value, int> = 0
 279     >
 280     static inline bool apply(Geometry1 const& geometry1,
 281                              Geometry2 const& geometry2,
 282                              Strategy const& strategy)
 283     {
 284         return equals_by_relate<Geometry1, Geometry2>::apply(geometry1, geometry2, strategy);
 285     }
 286 };
 287
 288 struct equals_always_false
 289 {
 290     template <typename Geometry1, typename Geometry2, typename Strategy>
 291     static inline bool apply(Geometry1 const& , Geometry2 const& , Strategy const& )
 292     {
 293         return false;
 294     }
 295 };
 296
 297
 298 }} // namespace detail::equals
 299 #endif // DOXYGEN_NO_DETAIL
 300
 301
 302 #ifndef DOXYGEN_NO_DISPATCH
 303 namespace dispatch
 304 {
 305
 306 template <typename P1, typename P2, std::size_t DimensionCount, bool Reverse>
 307 struct equals<P1, P2, point_tag, point_tag, pointlike_tag, pointlike_tag, DimensionCount, Reverse>
 308     : detail::equals::point_point<0, DimensionCount>
 309 {};
 310
 311 template <typename MultiPoint1, typename MultiPoint2, std::size_t DimensionCount, bool Reverse>
 312 struct equals<MultiPoint1, MultiPoint2, multi_point_tag, multi_point_tag, pointlike_tag, pointlike_tag, DimensionCount, Reverse>
 313     : detail::equals::equals_by_relate<MultiPoint1, MultiPoint2>
 314 {};
 315
 316 template <typename MultiPoint, typename Point, std::size_t DimensionCount, bool Reverse>
 317 struct equals<Point, MultiPoint, point_tag, multi_point_tag, pointlike_tag, pointlike_tag, DimensionCount, Reverse>
 318     : detail::equals::equals_by_relate<Point, MultiPoint>
 319 {};
 320
 321 template <typename Box1, typename Box2, std::size_t DimensionCount, bool Reverse>
 322 struct equals<Box1, Box2, box_tag, box_tag, areal_tag, areal_tag, DimensionCount, Reverse>
 323     : detail::equals::box_box<0, DimensionCount>
 324 {};
 325
 326
 327 template <typename Ring1, typename Ring2, bool Reverse>
 328 struct equals<Ring1, Ring2, ring_tag, ring_tag, areal_tag, areal_tag, 2, Reverse>
 329     : detail::equals::equals_by_collection_or_relate<detail::equals::area_check>
 330 {};
 331
 332
 333 template <typename Polygon1, typename Polygon2, bool Reverse>
 334 struct equals<Polygon1, Polygon2, polygon_tag, polygon_tag, areal_tag, areal_tag, 2, Reverse>
 335     : detail::equals::equals_by_collection_or_relate<detail::equals::area_check>
 336 {};
 337
 338
 339 template <typename Polygon, typename Ring, bool Reverse>
 340 struct equals<Polygon, Ring, polygon_tag, ring_tag, areal_tag, areal_tag, 2, Reverse>
 341     : detail::equals::equals_by_collection_or_relate<detail::equals::area_check>
 342 {};
 343
 344
 345 template <typename Ring, typename Box, bool Reverse>
 346 struct equals<Ring, Box, ring_tag, box_tag, areal_tag, areal_tag, 2, Reverse>
 347     : detail::equals::equals_by_collection<detail::equals::area_check>
 348 {};
 349
 350
 351 template <typename Polygon, typename Box, bool Reverse>
 352 struct equals<Polygon, Box, polygon_tag, box_tag, areal_tag, areal_tag, 2, Reverse>
 353     : detail::equals::equals_by_collection<detail::equals::area_check>
 354 {};
 355
 356 template <typename Segment1, typename Segment2, std::size_t DimensionCount, bool Reverse>
 357 struct equals<Segment1, Segment2, segment_tag, segment_tag, linear_tag, linear_tag, DimensionCount, Reverse>
 358     : detail::equals::segment_segment
 359 {};
 360
 361 template <typename LineString1, typename LineString2, bool Reverse>
 362 struct equals<LineString1, LineString2, linestring_tag, linestring_tag, linear_tag, linear_tag, 2, Reverse>
 363     : detail::equals::equals_by_relate<LineString1, LineString2>
 364 {};
 365
 366 template <typename LineString, typename MultiLineString, bool Reverse>
 367 struct equals<LineString, MultiLineString, linestring_tag, multi_linestring_tag, linear_tag, linear_tag, 2, Reverse>
 368     : detail::equals::equals_by_relate<LineString, MultiLineString>
 369 {};
 370
 371 template <typename MultiLineString1, typename MultiLineString2, bool Reverse>
 372 struct equals<MultiLineString1, MultiLineString2, multi_linestring_tag, multi_linestring_tag, linear_tag, linear_tag, 2, Reverse>
 373     : detail::equals::equals_by_relate<MultiLineString1, MultiLineString2>
 374 {};
 375
 376 template <typename LineString, typename Segment, bool Reverse>
 377 struct equals<LineString, Segment, linestring_tag, segment_tag, linear_tag, linear_tag, 2, Reverse>
 378     : detail::equals::equals_by_relate<LineString, Segment>
 379 {};
 380
 381 template <typename MultiLineString, typename Segment, bool Reverse>
 382 struct equals<MultiLineString, Segment, multi_linestring_tag, segment_tag, linear_tag, linear_tag, 2, Reverse>
 383     : detail::equals::equals_by_relate<MultiLineString, Segment>
 384 {};
 385
 386
 387 template <typename MultiPolygon1, typename MultiPolygon2, bool Reverse>
 388 struct equals
 389     <
 390         MultiPolygon1, MultiPolygon2,
 391         multi_polygon_tag, multi_polygon_tag,
 392         areal_tag, areal_tag,
 393         2,
 394         Reverse
 395     >
 396     : detail::equals::equals_by_collection_or_relate<detail::equals::area_check>
 397 {};
 398
 399
 400 template <typename Polygon, typename MultiPolygon, bool Reverse>
 401 struct equals
 402     <
 403         Polygon, MultiPolygon,
 404         polygon_tag, multi_polygon_tag,
 405         areal_tag, areal_tag,
 406         2,
 407         Reverse
 408     >
 409     : detail::equals::equals_by_collection_or_relate<detail::equals::area_check>
 410 {};
 411
 412 template <typename MultiPolygon, typename Ring, bool Reverse>
 413 struct equals
 414     <
 415         MultiPolygon, Ring,
 416         multi_polygon_tag, ring_tag,
 417         areal_tag, areal_tag,
 418         2,
 419         Reverse
 420     >
 421     : detail::equals::equals_by_collection_or_relate<detail::equals::area_check>
 422 {};
 423
 424
 425 // NOTE: degenerated linear geometries, e.g. segment or linestring containing
 426 //   2 equal points, are considered to be invalid. Though theoretically
 427 //   degenerated segments and linestrings could be treated as points and
 428 //   multi-linestrings as multi-points.
 429 //   This reasoning could also be applied to boxes.
 430
 431 template <typename Geometry1, typename Geometry2, typename Tag1, typename Tag2, std::size_t DimensionCount>
 432 struct equals<Geometry1, Geometry2, Tag1, Tag2, pointlike_tag, linear_tag, DimensionCount, false>
 433     : detail::equals::equals_always_false
 434 {};
 435
 436 template <typename Geometry1, typename Geometry2, typename Tag1, typename Tag2, std::size_t DimensionCount>
 437 struct equals<Geometry1, Geometry2, Tag1, Tag2, linear_tag, pointlike_tag, DimensionCount, false>
 438     : detail::equals::equals_always_false
 439 {};
 440
 441 template <typename Geometry1, typename Geometry2, typename Tag1, typename Tag2, std::size_t DimensionCount>
 442 struct equals<Geometry1, Geometry2, Tag1, Tag2, pointlike_tag, areal_tag, DimensionCount, false>
 443     : detail::equals::equals_always_false
 444 {};
 445
 446 template <typename Geometry1, typename Geometry2, typename Tag1, typename Tag2, std::size_t DimensionCount>
 447 struct equals<Geometry1, Geometry2, Tag1, Tag2, areal_tag, pointlike_tag, DimensionCount, false>
 448     : detail::equals::equals_always_false
 449 {};
 450
 451 template <typename Geometry1, typename Geometry2, typename Tag1, typename Tag2, std::size_t DimensionCount>
 452 struct equals<Geometry1, Geometry2, Tag1, Tag2, linear_tag, areal_tag, DimensionCount, false>
 453     : detail::equals::equals_always_false
 454 {};
 455
 456 template <typename Geometry1, typename Geometry2, typename Tag1, typename Tag2, std::size_t DimensionCount>
 457 struct equals<Geometry1, Geometry2, Tag1, Tag2, areal_tag, linear_tag, DimensionCount, false>
 458     : detail::equals::equals_always_false
 459 {};
 460
 461 } // namespace dispatch
 462 #endif // DOXYGEN_NO_DISPATCH
 463
 464
 465 }} // namespace boost::geometry
 466
 467
 468 #endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_EQUALS_IMPLEMENTATION_HPP
 469