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, 2015, 2016, 2017.
   9 // Modifications copyright (c) 2014-2017 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 <vector>
  27
  28 #include <boost/range.hpp>
  29 #include <boost/type_traits/is_base_of.hpp>
  30
  31 #include <boost/geometry/core/access.hpp>
  32 #include <boost/geometry/core/tags.hpp>
  33
  34 #include <boost/geometry/algorithms/detail/equals/point_point.hpp>
  35
  36 // For trivial checks
  37 #include <boost/geometry/algorithms/area.hpp>
  38 #include <boost/geometry/algorithms/length.hpp>
  39 #include <boost/geometry/util/math.hpp>
  40 #include <boost/geometry/util/select_coordinate_type.hpp>
  41 #include <boost/geometry/util/select_most_precise.hpp>
  42
  43 #include <boost/geometry/algorithms/detail/equals/collect_vectors.hpp>
  44 #include <boost/geometry/algorithms/detail/equals/interface.hpp>
  45 #include <boost/geometry/algorithms/detail/relate/relate_impl.hpp>
  46 #include <boost/geometry/algorithms/relate.hpp>
  47
  48 #include <boost/geometry/views/detail/indexed_point_view.hpp>
  49
  50
  51 namespace boost { namespace geometry
  52 {
  53
  54 #ifndef DOXYGEN_NO_DETAIL
  55 namespace detail { namespace equals
  56 {
  57
  58
  59 template
  60 <
  61     std::size_t Dimension,
  62     std::size_t DimensionCount
  63 >
  64 struct point_point
  65 {
  66     template <typename Point1, typename Point2, typename Strategy>
  67     static inline bool apply(Point1 const& point1, Point2 const& point2, Strategy const& strategy)
  68     {
  69         return ! detail::disjoint::point_point
  70             <
  71                 Point1, Point2,
  72                 Dimension, DimensionCount
  73             >::apply(point1, point2, strategy);
  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, Strategy const& )
 112     {
 113         return equals::equals_point_point(
 114                     indexed_point_view<Segment1 const, 0>(segment1),
 115                     indexed_point_view<Segment2 const, 0>(segment2) )
 116                 ? equals::equals_point_point(
 117                     indexed_point_view<Segment1 const, 1>(segment1),
 118                     indexed_point_view<Segment2 const, 1>(segment2) )
 119                 : ( equals::equals_point_point(
 120                         indexed_point_view<Segment1 const, 0>(segment1),
 121                         indexed_point_view<Segment2 const, 1>(segment2) )
 122                  && equals::equals_point_point(
 123                         indexed_point_view<Segment1 const, 1>(segment1),
 124                         indexed_point_view<Segment2 const, 0>(segment2) )
 125                   );
 126     }
 127 };
 128
 129
 130 struct area_check
 131 {
 132     template <typename Geometry1, typename Geometry2, typename Strategy>
 133     static inline bool apply(Geometry1 const& geometry1,
 134                              Geometry2 const& geometry2,
 135                              Strategy const& strategy)
 136     {
 137         return geometry::math::equals(
 138             geometry::area(geometry1,
 139                            strategy.template get_area_strategy<Geometry1>()),
 140             geometry::area(geometry2,
 141                            strategy.template get_area_strategy<Geometry2>()));
 142     }
 143 };
 144
 145
 146 struct length_check
 147 {
 148     template <typename Geometry1, typename Geometry2, typename Strategy>
 149     static inline bool apply(Geometry1 const& geometry1,
 150                              Geometry2 const& geometry2,
 151                              Strategy const& strategy)
 152     {
 153         return geometry::math::equals(
 154             geometry::length(geometry1,
 155                              strategy.template get_distance_strategy<Geometry1>()),
 156             geometry::length(geometry2,
 157                              strategy.template get_distance_strategy<Geometry2>()));
 158     }
 159 };
 160
 161
 162 template <typename Geometry1, typename Geometry2, typename IntersectionStrategy>
 163 struct collected_vector
 164 {
 165     typedef typename geometry::select_most_precise
 166         <
 167             typename select_coordinate_type
 168                 <
 169                     Geometry1, Geometry2
 170                 >::type,
 171             double
 172         >::type calculation_type;
 173
 174     typedef geometry::collected_vector
 175         <
 176             calculation_type,
 177             Geometry1,
 178             typename IntersectionStrategy::side_strategy_type
 179         > type;
 180 };
 181
 182 template <typename TrivialCheck>
 183 struct equals_by_collection
 184 {
 185     template <typename Geometry1, typename Geometry2, typename Strategy>
 186     static inline bool apply(Geometry1 const& geometry1,
 187                              Geometry2 const& geometry2,
 188                              Strategy const& strategy)
 189     {
 190         if (! TrivialCheck::apply(geometry1, geometry2, strategy))
 191         {
 192             return false;
 193         }
 194
 195         typedef typename collected_vector
 196             <
 197                 Geometry1, Geometry2, Strategy
 198             >::type collected_vector_type;
 199
 200         std::vector<collected_vector_type> c1, c2;
 201
 202         geometry::collect_vectors(c1, geometry1);
 203         geometry::collect_vectors(c2, geometry2);
 204
 205         if (boost::size(c1) != boost::size(c2))
 206         {
 207             return false;
 208         }
 209
 210         std::sort(c1.begin(), c1.end());
 211         std::sort(c2.begin(), c2.end());
 212
 213         // Just check if these vectors are equal.
 214         return std::equal(c1.begin(), c1.end(), c2.begin());
 215     }
 216 };
 217
 218 template<typename Geometry1, typename Geometry2>
 219 struct equals_by_relate
 220     : detail::relate::relate_impl
 221         <
 222             detail::de9im::static_mask_equals_type,
 223             Geometry1,
 224             Geometry2
 225         >
 226 {};
 227
 228 // If collect_vectors which is a SideStrategy-dispatched optimization
 229 // is implemented in a way consistent with the Intersection/Side Strategy
 230 // then collect_vectors is used, otherwise relate is used.
 231 // NOTE: the result could be conceptually different for invalid
 232 // geometries in different coordinate systems because collect_vectors
 233 // and relate treat invalid geometries differently.
 234 template<typename TrivialCheck>
 235 struct equals_by_collection_or_relate
 236 {
 237     template <typename Geometry1, typename Geometry2, typename Strategy>
 238     static inline bool apply(Geometry1 const& geometry1,
 239                              Geometry2 const& geometry2,
 240                              Strategy const& strategy)
 241     {
 242         typedef typename boost::is_base_of
 243             <
 244                 nyi::not_implemented_tag,
 245                 typename collected_vector
 246                     <
 247                         Geometry1, Geometry2, Strategy
 248                     >::type
 249             >::type enable_relate_type;
 250
 251         return apply(geometry1, geometry2, strategy, enable_relate_type());
 252     }
 253
 254 private:
 255     template <typename Geometry1, typename Geometry2, typename Strategy>
 256     static inline bool apply(Geometry1 const& geometry1,
 257                              Geometry2 const& geometry2,
 258                              Strategy const& strategy,
 259                              boost::false_type /*enable_relate*/)
 260     {
 261         return equals_by_collection<TrivialCheck>::apply(geometry1, geometry2, strategy);
 262     }
 263
 264     template <typename Geometry1, typename Geometry2, typename Strategy>
 265     static inline bool apply(Geometry1 const& geometry1,
 266                              Geometry2 const& geometry2,
 267                              Strategy const& strategy,
 268                              boost::true_type /*enable_relate*/)
 269     {
 270         return equals_by_relate<Geometry1, Geometry2>::apply(geometry1, geometry2, strategy);
 271     }
 272 };
 273
 274
 275 }} // namespace detail::equals
 276 #endif // DOXYGEN_NO_DETAIL
 277
 278
 279 #ifndef DOXYGEN_NO_DISPATCH
 280 namespace dispatch
 281 {
 282
 283 template <typename P1, typename P2, std::size_t DimensionCount, bool Reverse>
 284 struct equals<P1, P2, point_tag, point_tag, DimensionCount, Reverse>
 285     : detail::equals::point_point<0, DimensionCount>
 286 {};
 287
 288 template <typename MultiPoint1, typename MultiPoint2, std::size_t DimensionCount, bool Reverse>
 289 struct equals<MultiPoint1, MultiPoint2, multi_point_tag, multi_point_tag, DimensionCount, Reverse>
 290     : detail::equals::equals_by_relate<MultiPoint1, MultiPoint2>
 291 {};
 292
 293 template <typename MultiPoint, typename Point, std::size_t DimensionCount, bool Reverse>
 294 struct equals<Point, MultiPoint, point_tag, multi_point_tag, DimensionCount, Reverse>
 295     : detail::equals::equals_by_relate<Point, MultiPoint>
 296 {};
 297
 298 template <typename Box1, typename Box2, std::size_t DimensionCount, bool Reverse>
 299 struct equals<Box1, Box2, box_tag, box_tag, DimensionCount, Reverse>
 300     : detail::equals::box_box<0, DimensionCount>
 301 {};
 302
 303
 304 template <typename Ring1, typename Ring2, bool Reverse>
 305 struct equals<Ring1, Ring2, ring_tag, ring_tag, 2, Reverse>
 306     : detail::equals::equals_by_collection_or_relate<detail::equals::area_check>
 307 {};
 308
 309
 310 template <typename Polygon1, typename Polygon2, bool Reverse>
 311 struct equals<Polygon1, Polygon2, polygon_tag, polygon_tag, 2, Reverse>
 312     : detail::equals::equals_by_collection_or_relate<detail::equals::area_check>
 313 {};
 314
 315
 316 template <typename Polygon, typename Ring, bool Reverse>
 317 struct equals<Polygon, Ring, polygon_tag, ring_tag, 2, Reverse>
 318     : detail::equals::equals_by_collection_or_relate<detail::equals::area_check>
 319 {};
 320
 321
 322 template <typename Ring, typename Box, bool Reverse>
 323 struct equals<Ring, Box, ring_tag, box_tag, 2, Reverse>
 324     : detail::equals::equals_by_collection<detail::equals::area_check>
 325 {};
 326
 327
 328 template <typename Polygon, typename Box, bool Reverse>
 329 struct equals<Polygon, Box, polygon_tag, box_tag, 2, Reverse>
 330     : detail::equals::equals_by_collection<detail::equals::area_check>
 331 {};
 332
 333 template <typename Segment1, typename Segment2, std::size_t DimensionCount, bool Reverse>
 334 struct equals<Segment1, Segment2, segment_tag, segment_tag, DimensionCount, Reverse>
 335     : detail::equals::segment_segment
 336 {};
 337
 338 template <typename LineString1, typename LineString2, bool Reverse>
 339 struct equals<LineString1, LineString2, linestring_tag, linestring_tag, 2, Reverse>
 340     : detail::equals::equals_by_relate<LineString1, LineString2>
 341 {};
 342
 343 template <typename LineString, typename MultiLineString, bool Reverse>
 344 struct equals<LineString, MultiLineString, linestring_tag, multi_linestring_tag, 2, Reverse>
 345     : detail::equals::equals_by_relate<LineString, MultiLineString>
 346 {};
 347
 348 template <typename MultiLineString1, typename MultiLineString2, bool Reverse>
 349 struct equals<MultiLineString1, MultiLineString2, multi_linestring_tag, multi_linestring_tag, 2, Reverse>
 350     : detail::equals::equals_by_relate<MultiLineString1, MultiLineString2>
 351 {};
 352
 353
 354 template <typename MultiPolygon1, typename MultiPolygon2, bool Reverse>
 355 struct equals
 356     <
 357         MultiPolygon1, MultiPolygon2,
 358         multi_polygon_tag, multi_polygon_tag,
 359         2,
 360         Reverse
 361     >
 362     : detail::equals::equals_by_collection_or_relate<detail::equals::area_check>
 363 {};
 364
 365
 366 template <typename Polygon, typename MultiPolygon, bool Reverse>
 367 struct equals
 368     <
 369         Polygon, MultiPolygon,
 370         polygon_tag, multi_polygon_tag,
 371         2,
 372         Reverse
 373     >
 374     : detail::equals::equals_by_collection_or_relate<detail::equals::area_check>
 375 {};
 376
 377 template <typename MultiPolygon, typename Ring, bool Reverse>
 378 struct equals
 379     <
 380         MultiPolygon, Ring,
 381         multi_polygon_tag, ring_tag,
 382         2,
 383         Reverse
 384     >
 385     : detail::equals::equals_by_collection_or_relate<detail::equals::area_check>
 386 {};
 387
 388
 389 } // namespace dispatch
 390 #endif // DOXYGEN_NO_DISPATCH
 391
 392
 393 }} // namespace boost::geometry
 394
 395
 396 #endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_EQUALS_IMPLEMENTATION_HPP
 397