detail/equals/implementation.hpp

0001 // Boost.Geometry (aka GGL, Generic Geometry Library)
0002
0003 // Copyright (c) 2007-2015 Barend Gehrels, Amsterdam, the Netherlands.
0004 // Copyright (c) 2008-2015 Bruno Lalande, Paris, France.
0005 // Copyright (c) 2009-2015 Mateusz Loskot, London, UK.
0006 // Copyright (c) 2014-2015 Adam Wulkiewicz, Lodz, Poland.
0007
0008 // This file was modified by Oracle on 2014-2022.
0009 // Modifications copyright (c) 2014-2022 Oracle and/or its affiliates.
0010
0011 // Contributed and/or modified by Adam Wulkiewicz, on behalf of Oracle
0012 // Contributed and/or modified by Menelaos Karavelas, on behalf of Oracle
0013
0014 // Parts of Boost.Geometry are redesigned from Geodan's Geographic Library
0015 // (geolib/GGL), copyright (c) 1995-2010 Geodan, Amsterdam, the Netherlands.
0016
0017 // Use, modification and distribution is subject to the Boost Software License,
0018 // Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
0019 // http://www.boost.org/LICENSE_1_0.txt)
0020
0021 #ifndef BOOST_GEOMETRY_ALGORITHMS_DETAIL_EQUALS_IMPLEMENTATION_HPP
0022 #define BOOST_GEOMETRY_ALGORITHMS_DETAIL_EQUALS_IMPLEMENTATION_HPP
0023
0024
0025 #include <cstddef>
0026 #include <type_traits>
0027 #include <vector>
0028
0029 #include <boost/range/size.hpp>
0030
0031 #include <boost/geometry/core/access.hpp>
0032 #include <boost/geometry/core/tags.hpp>
0033
0034 #include <boost/geometry/algorithms/area.hpp>
0035 #include <boost/geometry/algorithms/length.hpp>
0036 #include <boost/geometry/algorithms/detail/equals/point_point.hpp>
0037 #include <boost/geometry/algorithms/detail/equals/collect_vectors.hpp>
0038 #include <boost/geometry/algorithms/detail/equals/interface.hpp>
0039 #include <boost/geometry/algorithms/detail/relate/implementation.hpp>
0040 #include <boost/geometry/algorithms/detail/relate/relate_impl.hpp>
0041
0042 #include <boost/geometry/strategies/relate/cartesian.hpp>
0043 #include <boost/geometry/strategies/relate/geographic.hpp>
0044 #include <boost/geometry/strategies/relate/spherical.hpp>
0045
0046 #include <boost/geometry/util/math.hpp>
0047 #include <boost/geometry/util/select_coordinate_type.hpp>
0048 #include <boost/geometry/util/select_most_precise.hpp>
0049
0050 #include <boost/geometry/views/detail/indexed_point_view.hpp>
0051
0052
0053 namespace boost { namespace geometry
0054 {
0055
0056 #ifndef DOXYGEN_NO_DETAIL
0057 namespace detail { namespace equals
0058 {
0059
0060
0061 template
0062 <
0063     std::size_t Dimension,
0064     std::size_t DimensionCount
0065 >
0066 struct point_point
0067 {
0068     template <typename Point1, typename Point2, typename Strategy>
0069     static inline bool apply(Point1 const& point1, Point2 const& point2,
0070                              Strategy const& strategy)
0071     {
0072         typedef decltype(strategy.relate(point1, point2)) strategy_type;
0073         return strategy_type::apply(point1, point2);
0074     }
0075 };
0076
0077
0078 template
0079 <
0080     std::size_t Dimension,
0081     std::size_t DimensionCount
0082 >
0083 struct box_box
0084 {
0085     template <typename Box1, typename Box2, typename Strategy>
0086     static inline bool apply(Box1 const& box1, Box2 const& box2, Strategy const& strategy)
0087     {
0088         if (!geometry::math::equals(get<min_corner, Dimension>(box1), get<min_corner, Dimension>(box2))
0089             || !geometry::math::equals(get<max_corner, Dimension>(box1), get<max_corner, Dimension>(box2)))
0090         {
0091             return false;
0092         }
0093         return box_box<Dimension + 1, DimensionCount>::apply(box1, box2, strategy);
0094     }
0095 };
0096
0097 template <std::size_t DimensionCount>
0098 struct box_box<DimensionCount, DimensionCount>
0099 {
0100     template <typename Box1, typename Box2, typename Strategy>
0101     static inline bool apply(Box1 const& , Box2 const& , Strategy const& )
0102     {
0103         return true;
0104     }
0105 };
0106
0107
0108 struct segment_segment
0109 {
0110     template <typename Segment1, typename Segment2, typename Strategy>
0111     static inline bool apply(Segment1 const& segment1, Segment2 const& segment2,
0112                              Strategy const& strategy)
0113     {
0114         return equals::equals_point_point(
0115                     indexed_point_view<Segment1 const, 0>(segment1),
0116                     indexed_point_view<Segment2 const, 0>(segment2),
0117                     strategy)
0118                 ? equals::equals_point_point(
0119                     indexed_point_view<Segment1 const, 1>(segment1),
0120                     indexed_point_view<Segment2 const, 1>(segment2),
0121                     strategy)
0122                 : ( equals::equals_point_point(
0123                         indexed_point_view<Segment1 const, 0>(segment1),
0124                         indexed_point_view<Segment2 const, 1>(segment2),
0125                         strategy)
0126                  && equals::equals_point_point(
0127                         indexed_point_view<Segment1 const, 1>(segment1),
0128                         indexed_point_view<Segment2 const, 0>(segment2),
0129                         strategy)
0130                   );
0131     }
0132 };
0133
0134
0135 struct area_check
0136 {
0137     template <typename Geometry1, typename Geometry2, typename Strategy>
0138     static inline bool apply(Geometry1 const& geometry1,
0139                              Geometry2 const& geometry2,
0140                              Strategy const& strategy)
0141     {
0142         return geometry::math::equals(geometry::area(geometry1, strategy),
0143                                       geometry::area(geometry2, strategy));
0144     }
0145 };
0146
0147
0148 /*
0149 struct length_check
0150 {
0151     template <typename Geometry1, typename Geometry2, typename Strategy>
0152     static inline bool apply(Geometry1 const& geometry1,
0153                              Geometry2 const& geometry2,
0154                              Strategy const& strategy)
0155     {
0156         return geometry::math::equals(geometry::length(geometry1, strategy),
0157                                       geometry::length(geometry2, strategy));
0158     }
0159 };
0160 */
0161
0162
0163 // Small helper structure do decide to use collect_vectors, or not
0164 template <typename Strategy, typename CsTag>
0165 struct use_collect_vectors
0166 {
0167     static constexpr bool value = false;
0168 };
0169
0170 template <typename Strategy>
0171 struct use_collect_vectors<Strategy, cartesian_tag>
0172 {
0173     static constexpr bool value = true;
0174
0175     template <typename T, typename Point>
0176     using type = collected_vector_cartesian<T>;
0177 };
0178
0179 template <typename CV>
0180 struct use_collect_vectors<strategy::side::spherical_side_formula<CV>, spherical_tag>
0181 {
0182     static constexpr bool value = true;
0183
0184     template <typename T, typename Point>
0185     using type = collected_vector_spherical<T, Point>;
0186 };
0187
0188
0189 template <typename TrivialCheck>
0190 struct equals_by_collection
0191 {
0192     template <typename Geometry1, typename Geometry2, typename Strategy>
0193     static inline bool apply(Geometry1 const& geometry1,
0194                              Geometry2 const& geometry2,
0195                              Strategy const& strategy)
0196     {
0197         if (! TrivialCheck::apply(geometry1, geometry2, strategy))
0198         {
0199             return false;
0200         }
0201
0202         using calculation_type = typename geometry::select_most_precise
0203             <
0204                 typename select_coordinate_type
0205                     <
0206                         Geometry1, Geometry2
0207                     >::type,
0208                 double
0209             >::type;
0210
0211         using collected_vector_type = typename use_collect_vectors
0212             <
0213                 decltype(std::declval<Strategy>().side()),
0214                 typename Strategy::cs_tag
0215             >::template type
0216                 <
0217                     calculation_type,
0218                     typename geometry::point_type<Geometry1>::type
0219                 >;
0220
0221         std::vector<collected_vector_type> c1, c2;
0222
0223         geometry::collect_vectors(c1, geometry1);
0224         geometry::collect_vectors(c2, geometry2);
0225
0226         if (boost::size(c1) != boost::size(c2))
0227         {
0228             return false;
0229         }
0230
0231         std::sort(c1.begin(), c1.end());
0232         std::sort(c2.begin(), c2.end());
0233
0234         // Check if these vectors are equal.
0235         return std::equal(c1.begin(), c1.end(), c2.begin());
0236     }
0237 };
0238
0239 template<typename Geometry1, typename Geometry2>
0240 struct equals_by_relate
0241     : detail::relate::relate_impl
0242         <
0243             detail::de9im::static_mask_equals_type,
0244             Geometry1,
0245             Geometry2
0246         >
0247 {};
0248
0249 // Use either collect_vectors or relate
0250 // NOTE: the result could be conceptually different for invalid
0251 // geometries in different coordinate systems because collect_vectors
0252 // and relate treat invalid geometries differently.
0253 template<typename TrivialCheck>
0254 struct equals_by_collection_or_relate
0255 {
0256     template <typename Strategy>
0257     using use_vectors = use_collect_vectors
0258         <
0259             decltype(std::declval<Strategy>().side()),
0260             typename Strategy::cs_tag
0261         >;
0262
0263     template
0264     <
0265         typename Geometry1, typename Geometry2, typename Strategy,
0266         std::enable_if_t<use_vectors<Strategy>::value, int> = 0
0267     >
0268     static inline bool apply(Geometry1 const& geometry1,
0269                              Geometry2 const& geometry2,
0270                              Strategy const& strategy)
0271     {
0272         return equals_by_collection<TrivialCheck>::apply(geometry1, geometry2, strategy);
0273     }
0274
0275     template
0276     <
0277         typename Geometry1, typename Geometry2, typename Strategy,
0278         std::enable_if_t<! use_vectors<Strategy>::value, int> = 0
0279     >
0280     static inline bool apply(Geometry1 const& geometry1,
0281                              Geometry2 const& geometry2,
0282                              Strategy const& strategy)
0283     {
0284         return equals_by_relate<Geometry1, Geometry2>::apply(geometry1, geometry2, strategy);
0285     }
0286 };
0287
0288 struct equals_always_false
0289 {
0290     template <typename Geometry1, typename Geometry2, typename Strategy>
0291     static inline bool apply(Geometry1 const& , Geometry2 const& , Strategy const& )
0292     {
0293         return false;
0294     }
0295 };
0296
0297
0298 }} // namespace detail::equals
0299 #endif // DOXYGEN_NO_DETAIL
0300
0301
0302 #ifndef DOXYGEN_NO_DISPATCH
0303 namespace dispatch
0304 {
0305
0306 template <typename P1, typename P2, std::size_t DimensionCount, bool Reverse>
0307 struct equals<P1, P2, point_tag, point_tag, pointlike_tag, pointlike_tag, DimensionCount, Reverse>
0308     : detail::equals::point_point<0, DimensionCount>
0309 {};
0310
0311 template <typename MultiPoint1, typename MultiPoint2, std::size_t DimensionCount, bool Reverse>
0312 struct equals<MultiPoint1, MultiPoint2, multi_point_tag, multi_point_tag, pointlike_tag, pointlike_tag, DimensionCount, Reverse>
0313     : detail::equals::equals_by_relate<MultiPoint1, MultiPoint2>
0314 {};
0315
0316 template <typename MultiPoint, typename Point, std::size_t DimensionCount, bool Reverse>
0317 struct equals<Point, MultiPoint, point_tag, multi_point_tag, pointlike_tag, pointlike_tag, DimensionCount, Reverse>
0318     : detail::equals::equals_by_relate<Point, MultiPoint>
0319 {};
0320
0321 template <typename Box1, typename Box2, std::size_t DimensionCount, bool Reverse>
0322 struct equals<Box1, Box2, box_tag, box_tag, areal_tag, areal_tag, DimensionCount, Reverse>
0323     : detail::equals::box_box<0, DimensionCount>
0324 {};
0325
0326
0327 template <typename Ring1, typename Ring2, bool Reverse>
0328 struct equals<Ring1, Ring2, ring_tag, ring_tag, areal_tag, areal_tag, 2, Reverse>
0329     : detail::equals::equals_by_collection_or_relate<detail::equals::area_check>
0330 {};
0331
0332
0333 template <typename Polygon1, typename Polygon2, bool Reverse>
0334 struct equals<Polygon1, Polygon2, polygon_tag, polygon_tag, areal_tag, areal_tag, 2, Reverse>
0335     : detail::equals::equals_by_collection_or_relate<detail::equals::area_check>
0336 {};
0337
0338
0339 template <typename Polygon, typename Ring, bool Reverse>
0340 struct equals<Polygon, Ring, polygon_tag, ring_tag, areal_tag, areal_tag, 2, Reverse>
0341     : detail::equals::equals_by_collection_or_relate<detail::equals::area_check>
0342 {};
0343
0344
0345 template <typename Ring, typename Box, bool Reverse>
0346 struct equals<Ring, Box, ring_tag, box_tag, areal_tag, areal_tag, 2, Reverse>
0347     : detail::equals::equals_by_collection<detail::equals::area_check>
0348 {};
0349
0350
0351 template <typename Polygon, typename Box, bool Reverse>
0352 struct equals<Polygon, Box, polygon_tag, box_tag, areal_tag, areal_tag, 2, Reverse>
0353     : detail::equals::equals_by_collection<detail::equals::area_check>
0354 {};
0355
0356 template <typename Segment1, typename Segment2, std::size_t DimensionCount, bool Reverse>
0357 struct equals<Segment1, Segment2, segment_tag, segment_tag, linear_tag, linear_tag, DimensionCount, Reverse>
0358     : detail::equals::segment_segment
0359 {};
0360
0361 template <typename LineString1, typename LineString2, bool Reverse>
0362 struct equals<LineString1, LineString2, linestring_tag, linestring_tag, linear_tag, linear_tag, 2, Reverse>
0363     : detail::equals::equals_by_relate<LineString1, LineString2>
0364 {};
0365
0366 template <typename LineString, typename MultiLineString, bool Reverse>
0367 struct equals<LineString, MultiLineString, linestring_tag, multi_linestring_tag, linear_tag, linear_tag, 2, Reverse>
0368     : detail::equals::equals_by_relate<LineString, MultiLineString>
0369 {};
0370
0371 template <typename MultiLineString1, typename MultiLineString2, bool Reverse>
0372 struct equals<MultiLineString1, MultiLineString2, multi_linestring_tag, multi_linestring_tag, linear_tag, linear_tag, 2, Reverse>
0373     : detail::equals::equals_by_relate<MultiLineString1, MultiLineString2>
0374 {};
0375
0376 template <typename LineString, typename Segment, bool Reverse>
0377 struct equals<LineString, Segment, linestring_tag, segment_tag, linear_tag, linear_tag, 2, Reverse>
0378     : detail::equals::equals_by_relate<LineString, Segment>
0379 {};
0380
0381 template <typename MultiLineString, typename Segment, bool Reverse>
0382 struct equals<MultiLineString, Segment, multi_linestring_tag, segment_tag, linear_tag, linear_tag, 2, Reverse>
0383     : detail::equals::equals_by_relate<MultiLineString, Segment>
0384 {};
0385
0386
0387 template <typename MultiPolygon1, typename MultiPolygon2, bool Reverse>
0388 struct equals
0389     <
0390         MultiPolygon1, MultiPolygon2,
0391         multi_polygon_tag, multi_polygon_tag,
0392         areal_tag, areal_tag,
0393         2,
0394         Reverse
0395     >
0396     : detail::equals::equals_by_collection_or_relate<detail::equals::area_check>
0397 {};
0398
0399
0400 template <typename Polygon, typename MultiPolygon, bool Reverse>
0401 struct equals
0402     <
0403         Polygon, MultiPolygon,
0404         polygon_tag, multi_polygon_tag,
0405         areal_tag, areal_tag,
0406         2,
0407         Reverse
0408     >
0409     : detail::equals::equals_by_collection_or_relate<detail::equals::area_check>
0410 {};
0411
0412 template <typename MultiPolygon, typename Ring, bool Reverse>
0413 struct equals
0414     <
0415         MultiPolygon, Ring,
0416         multi_polygon_tag, ring_tag,
0417         areal_tag, areal_tag,
0418         2,
0419         Reverse
0420     >
0421     : detail::equals::equals_by_collection_or_relate<detail::equals::area_check>
0422 {};
0423
0424
0425 // NOTE: degenerated linear geometries, e.g. segment or linestring containing
0426 //   2 equal points, are considered to be invalid. Though theoretically
0427 //   degenerated segments and linestrings could be treated as points and
0428 //   multi-linestrings as multi-points.
0429 //   This reasoning could also be applied to boxes.
0430
0431 template <typename Geometry1, typename Geometry2, typename Tag1, typename Tag2, std::size_t DimensionCount>
0432 struct equals<Geometry1, Geometry2, Tag1, Tag2, pointlike_tag, linear_tag, DimensionCount, false>
0433     : detail::equals::equals_always_false
0434 {};
0435
0436 template <typename Geometry1, typename Geometry2, typename Tag1, typename Tag2, std::size_t DimensionCount>
0437 struct equals<Geometry1, Geometry2, Tag1, Tag2, linear_tag, pointlike_tag, DimensionCount, false>
0438     : detail::equals::equals_always_false
0439 {};
0440
0441 template <typename Geometry1, typename Geometry2, typename Tag1, typename Tag2, std::size_t DimensionCount>
0442 struct equals<Geometry1, Geometry2, Tag1, Tag2, pointlike_tag, areal_tag, DimensionCount, false>
0443     : detail::equals::equals_always_false
0444 {};
0445
0446 template <typename Geometry1, typename Geometry2, typename Tag1, typename Tag2, std::size_t DimensionCount>
0447 struct equals<Geometry1, Geometry2, Tag1, Tag2, areal_tag, pointlike_tag, DimensionCount, false>
0448     : detail::equals::equals_always_false
0449 {};
0450
0451 template <typename Geometry1, typename Geometry2, typename Tag1, typename Tag2, std::size_t DimensionCount>
0452 struct equals<Geometry1, Geometry2, Tag1, Tag2, linear_tag, areal_tag, DimensionCount, false>
0453     : detail::equals::equals_always_false
0454 {};
0455
0456 template <typename Geometry1, typename Geometry2, typename Tag1, typename Tag2, std::size_t DimensionCount>
0457 struct equals<Geometry1, Geometry2, Tag1, Tag2, areal_tag, linear_tag, DimensionCount, false>
0458     : detail::equals::equals_always_false
0459 {};
0460
0461 } // namespace dispatch
0462 #endif // DOXYGEN_NO_DISPATCH
0463
0464
0465 }} // namespace boost::geometry
0466
0467
0468 #endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_EQUALS_IMPLEMENTATION_HPP
0469