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, 2018, 2019.
   9 // Modifications copyright (c) 2014-2019 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& )
  68     {
  69         return Strategy::apply(point1, point2);
  70     }
  71 };
  72
  73
  74 template
  75 <
  76     std::size_t Dimension,
  77     std::size_t DimensionCount
  78 >
  79 struct box_box
  80 {
  81     template <typename Box1, typename Box2, typename Strategy>
  82     static inline bool apply(Box1 const& box1, Box2 const& box2, Strategy const& strategy)
  83     {
  84         if (!geometry::math::equals(get<min_corner, Dimension>(box1), get<min_corner, Dimension>(box2))
  85             || !geometry::math::equals(get<max_corner, Dimension>(box1), get<max_corner, Dimension>(box2)))
  86         {
  87             return false;
  88         }
  89         return box_box<Dimension + 1, DimensionCount>::apply(box1, box2, strategy);
  90     }
  91 };
  92
  93 template <std::size_t DimensionCount>
  94 struct box_box<DimensionCount, DimensionCount>
  95 {
  96     template <typename Box1, typename Box2, typename Strategy>
  97     static inline bool apply(Box1 const& , Box2 const& , Strategy const& )
  98     {
  99         return true;
 100     }
 101 };
 102
 103
 104 struct segment_segment
 105 {
 106     template <typename Segment1, typename Segment2, typename Strategy>
 107     static inline bool apply(Segment1 const& segment1, Segment2 const& segment2,
 108                              Strategy const& strategy)
 109     {
 110         typename Strategy::point_in_point_strategy_type const&
 111             pt_pt_strategy = strategy.get_point_in_point_strategy();
 112
 113         return equals::equals_point_point(
 114                     indexed_point_view<Segment1 const, 0>(segment1),
 115                     indexed_point_view<Segment2 const, 0>(segment2),
 116                     pt_pt_strategy)
 117                 ? equals::equals_point_point(
 118                     indexed_point_view<Segment1 const, 1>(segment1),
 119                     indexed_point_view<Segment2 const, 1>(segment2),
 120                     pt_pt_strategy)
 121                 : ( equals::equals_point_point(
 122                         indexed_point_view<Segment1 const, 0>(segment1),
 123                         indexed_point_view<Segment2 const, 1>(segment2),
 124                         pt_pt_strategy)
 125                  && equals::equals_point_point(
 126                         indexed_point_view<Segment1 const, 1>(segment1),
 127                         indexed_point_view<Segment2 const, 0>(segment2),
 128                         pt_pt_strategy)
 129                   );
 130     }
 131 };
 132
 133
 134 struct area_check
 135 {
 136     template <typename Geometry1, typename Geometry2, typename Strategy>
 137     static inline bool apply(Geometry1 const& geometry1,
 138                              Geometry2 const& geometry2,
 139                              Strategy const& strategy)
 140     {
 141         return geometry::math::equals(
 142             geometry::area(geometry1,
 143                            strategy.template get_area_strategy<Geometry1>()),
 144             geometry::area(geometry2,
 145                            strategy.template get_area_strategy<Geometry2>()));
 146     }
 147 };
 148
 149
 150 struct length_check
 151 {
 152     template <typename Geometry1, typename Geometry2, typename Strategy>
 153     static inline bool apply(Geometry1 const& geometry1,
 154                              Geometry2 const& geometry2,
 155                              Strategy const& strategy)
 156     {
 157         return geometry::math::equals(
 158             geometry::length(geometry1,
 159                              strategy.template get_distance_strategy<Geometry1>()),
 160             geometry::length(geometry2,
 161                              strategy.template get_distance_strategy<Geometry2>()));
 162     }
 163 };
 164
 165
 166 template <typename Geometry1, typename Geometry2, typename IntersectionStrategy>
 167 struct collected_vector
 168 {
 169     typedef typename geometry::select_most_precise
 170         <
 171             typename select_coordinate_type
 172                 <
 173                     Geometry1, Geometry2
 174                 >::type,
 175             double
 176         >::type calculation_type;
 177
 178     typedef geometry::collected_vector
 179         <
 180             calculation_type,
 181             Geometry1,
 182             typename IntersectionStrategy::side_strategy_type
 183         > type;
 184 };
 185
 186 template <typename TrivialCheck>
 187 struct equals_by_collection
 188 {
 189     template <typename Geometry1, typename Geometry2, typename Strategy>
 190     static inline bool apply(Geometry1 const& geometry1,
 191                              Geometry2 const& geometry2,
 192                              Strategy const& strategy)
 193     {
 194         if (! TrivialCheck::apply(geometry1, geometry2, strategy))
 195         {
 196             return false;
 197         }
 198
 199         typedef typename collected_vector
 200             <
 201                 Geometry1, Geometry2, Strategy
 202             >::type collected_vector_type;
 203
 204         std::vector<collected_vector_type> c1, c2;
 205
 206         geometry::collect_vectors(c1, geometry1);
 207         geometry::collect_vectors(c2, geometry2);
 208
 209         if (boost::size(c1) != boost::size(c2))
 210         {
 211             return false;
 212         }
 213
 214         std::sort(c1.begin(), c1.end());
 215         std::sort(c2.begin(), c2.end());
 216
 217         // Just check if these vectors are equal.
 218         return std::equal(c1.begin(), c1.end(), c2.begin());
 219     }
 220 };
 221
 222 template<typename Geometry1, typename Geometry2>
 223 struct equals_by_relate
 224     : detail::relate::relate_impl
 225         <
 226             detail::de9im::static_mask_equals_type,
 227             Geometry1,
 228             Geometry2
 229         >
 230 {};
 231
 232 // If collect_vectors which is a SideStrategy-dispatched optimization
 233 // is implemented in a way consistent with the Intersection/Side Strategy
 234 // then collect_vectors is used, otherwise relate is used.
 235 // NOTE: the result could be conceptually different for invalid
 236 // geometries in different coordinate systems because collect_vectors
 237 // and relate treat invalid geometries differently.
 238 template<typename TrivialCheck>
 239 struct equals_by_collection_or_relate
 240 {
 241     template <typename Geometry1, typename Geometry2, typename Strategy>
 242     static inline bool apply(Geometry1 const& geometry1,
 243                              Geometry2 const& geometry2,
 244                              Strategy const& strategy)
 245     {
 246         typedef typename boost::is_base_of
 247             <
 248                 nyi::not_implemented_tag,
 249                 typename collected_vector
 250                     <
 251                         Geometry1, Geometry2, Strategy
 252                     >::type
 253             >::type enable_relate_type;
 254
 255         return apply(geometry1, geometry2, strategy, enable_relate_type());
 256     }
 257
 258 private:
 259     template <typename Geometry1, typename Geometry2, typename Strategy>
 260     static inline bool apply(Geometry1 const& geometry1,
 261                              Geometry2 const& geometry2,
 262                              Strategy const& strategy,
 263                              boost::false_type /*enable_relate*/)
 264     {
 265         return equals_by_collection<TrivialCheck>::apply(geometry1, geometry2, strategy);
 266     }
 267
 268     template <typename Geometry1, typename Geometry2, typename Strategy>
 269     static inline bool apply(Geometry1 const& geometry1,
 270                              Geometry2 const& geometry2,
 271                              Strategy const& strategy,
 272                              boost::true_type /*enable_relate*/)
 273     {
 274         return equals_by_relate<Geometry1, Geometry2>::apply(geometry1, geometry2, strategy);
 275     }
 276 };
 277
 278 struct equals_always_false
 279 {
 280     template <typename Geometry1, typename Geometry2, typename Strategy>
 281     static inline bool apply(Geometry1 const& , Geometry2 const& , Strategy const& )
 282     {
 283         return false;
 284     }
 285 };
 286
 287
 288 }} // namespace detail::equals
 289 #endif // DOXYGEN_NO_DETAIL
 290
 291
 292 #ifndef DOXYGEN_NO_DISPATCH
 293 namespace dispatch
 294 {
 295
 296 template <typename P1, typename P2, std::size_t DimensionCount, bool Reverse>
 297 struct equals<P1, P2, point_tag, point_tag, pointlike_tag, pointlike_tag, DimensionCount, Reverse>
 298     : detail::equals::point_point<0, DimensionCount>
 299 {};
 300
 301 template <typename MultiPoint1, typename MultiPoint2, std::size_t DimensionCount, bool Reverse>
 302 struct equals<MultiPoint1, MultiPoint2, multi_point_tag, multi_point_tag, pointlike_tag, pointlike_tag, DimensionCount, Reverse>
 303     : detail::equals::equals_by_relate<MultiPoint1, MultiPoint2>
 304 {};
 305
 306 template <typename MultiPoint, typename Point, std::size_t DimensionCount, bool Reverse>
 307 struct equals<Point, MultiPoint, point_tag, multi_point_tag, pointlike_tag, pointlike_tag, DimensionCount, Reverse>
 308     : detail::equals::equals_by_relate<Point, MultiPoint>
 309 {};
 310
 311 template <typename Box1, typename Box2, std::size_t DimensionCount, bool Reverse>
 312 struct equals<Box1, Box2, box_tag, box_tag, areal_tag, areal_tag, DimensionCount, Reverse>
 313     : detail::equals::box_box<0, DimensionCount>
 314 {};
 315
 316
 317 template <typename Ring1, typename Ring2, bool Reverse>
 318 struct equals<Ring1, Ring2, ring_tag, ring_tag, areal_tag, areal_tag, 2, Reverse>
 319     : detail::equals::equals_by_collection_or_relate<detail::equals::area_check>
 320 {};
 321
 322
 323 template <typename Polygon1, typename Polygon2, bool Reverse>
 324 struct equals<Polygon1, Polygon2, polygon_tag, polygon_tag, areal_tag, areal_tag, 2, Reverse>
 325     : detail::equals::equals_by_collection_or_relate<detail::equals::area_check>
 326 {};
 327
 328
 329 template <typename Polygon, typename Ring, bool Reverse>
 330 struct equals<Polygon, Ring, polygon_tag, ring_tag, areal_tag, areal_tag, 2, Reverse>
 331     : detail::equals::equals_by_collection_or_relate<detail::equals::area_check>
 332 {};
 333
 334
 335 template <typename Ring, typename Box, bool Reverse>
 336 struct equals<Ring, Box, ring_tag, box_tag, areal_tag, areal_tag, 2, Reverse>
 337     : detail::equals::equals_by_collection<detail::equals::area_check>
 338 {};
 339
 340
 341 template <typename Polygon, typename Box, bool Reverse>
 342 struct equals<Polygon, Box, polygon_tag, box_tag, areal_tag, areal_tag, 2, Reverse>
 343     : detail::equals::equals_by_collection<detail::equals::area_check>
 344 {};
 345
 346 template <typename Segment1, typename Segment2, std::size_t DimensionCount, bool Reverse>
 347 struct equals<Segment1, Segment2, segment_tag, segment_tag, linear_tag, linear_tag, DimensionCount, Reverse>
 348     : detail::equals::segment_segment
 349 {};
 350
 351 template <typename LineString1, typename LineString2, bool Reverse>
 352 struct equals<LineString1, LineString2, linestring_tag, linestring_tag, linear_tag, linear_tag, 2, Reverse>
 353     : detail::equals::equals_by_relate<LineString1, LineString2>
 354 {};
 355
 356 template <typename LineString, typename MultiLineString, bool Reverse>
 357 struct equals<LineString, MultiLineString, linestring_tag, multi_linestring_tag, linear_tag, linear_tag, 2, Reverse>
 358     : detail::equals::equals_by_relate<LineString, MultiLineString>
 359 {};
 360
 361 template <typename MultiLineString1, typename MultiLineString2, bool Reverse>
 362 struct equals<MultiLineString1, MultiLineString2, multi_linestring_tag, multi_linestring_tag, linear_tag, linear_tag, 2, Reverse>
 363     : detail::equals::equals_by_relate<MultiLineString1, MultiLineString2>
 364 {};
 365
 366 template <typename LineString, typename Segment, bool Reverse>
 367 struct equals<LineString, Segment, linestring_tag, segment_tag, linear_tag, linear_tag, 2, Reverse>
 368     : detail::equals::equals_by_relate<LineString, Segment>
 369 {};
 370
 371 template <typename MultiLineString, typename Segment, bool Reverse>
 372 struct equals<MultiLineString, Segment, multi_linestring_tag, segment_tag, linear_tag, linear_tag, 2, Reverse>
 373     : detail::equals::equals_by_relate<MultiLineString, Segment>
 374 {};
 375
 376
 377 template <typename MultiPolygon1, typename MultiPolygon2, bool Reverse>
 378 struct equals
 379     <
 380         MultiPolygon1, MultiPolygon2,
 381         multi_polygon_tag, multi_polygon_tag,
 382         areal_tag, areal_tag,
 383         2,
 384         Reverse
 385     >
 386     : detail::equals::equals_by_collection_or_relate<detail::equals::area_check>
 387 {};
 388
 389
 390 template <typename Polygon, typename MultiPolygon, bool Reverse>
 391 struct equals
 392     <
 393         Polygon, MultiPolygon,
 394         polygon_tag, multi_polygon_tag,
 395         areal_tag, areal_tag,
 396         2,
 397         Reverse
 398     >
 399     : detail::equals::equals_by_collection_or_relate<detail::equals::area_check>
 400 {};
 401
 402 template <typename MultiPolygon, typename Ring, bool Reverse>
 403 struct equals
 404     <
 405         MultiPolygon, Ring,
 406         multi_polygon_tag, ring_tag,
 407         areal_tag, areal_tag,
 408         2,
 409         Reverse
 410     >
 411     : detail::equals::equals_by_collection_or_relate<detail::equals::area_check>
 412 {};
 413
 414
 415 // NOTE: degenerated linear geometries, e.g. segment or linestring containing
 416 //   2 equal points, are considered to be invalid. Though theoretically
 417 //   degenerated segments and linestrings could be treated as points and
 418 //   multi-linestrings as multi-points.
 419 //   This reasoning could also be applied to boxes.
 420
 421 template <typename Geometry1, typename Geometry2, typename Tag1, typename Tag2, std::size_t DimensionCount>
 422 struct equals<Geometry1, Geometry2, Tag1, Tag2, pointlike_tag, linear_tag, DimensionCount, false>
 423     : detail::equals::equals_always_false
 424 {};
 425
 426 template <typename Geometry1, typename Geometry2, typename Tag1, typename Tag2, std::size_t DimensionCount>
 427 struct equals<Geometry1, Geometry2, Tag1, Tag2, linear_tag, pointlike_tag, DimensionCount, false>
 428     : detail::equals::equals_always_false
 429 {};
 430
 431 template <typename Geometry1, typename Geometry2, typename Tag1, typename Tag2, std::size_t DimensionCount>
 432 struct equals<Geometry1, Geometry2, Tag1, Tag2, pointlike_tag, areal_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, areal_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, linear_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, linear_tag, DimensionCount, false>
 448     : detail::equals::equals_always_false
 449 {};
 450
 451 } // namespace dispatch
 452 #endif // DOXYGEN_NO_DISPATCH
 453
 454
 455 }} // namespace boost::geometry
 456
 457
 458 #endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_EQUALS_IMPLEMENTATION_HPP
 459