detail/overlay/pointlike_pointlike.hpp

0001 // Boost.Geometry (aka GGL, Generic Geometry Library)
0002
0003 // Copyright (c) 2023 Adam Wulkiewicz, Lodz, Poland.
0004
0005 // Copyright (c) 2014-2024, Oracle and/or its affiliates.
0006
0007 // Contributed and/or modified by Vissarion Fysikopoulos, on behalf of Oracle
0008 // Contributed and/or modified by Menelaos Karavelas, on behalf of Oracle
0009 // Contributed and/or modified by Adam Wulkiewicz, on behalf of Oracle
0010
0011 // Licensed under the Boost Software License version 1.0.
0012 // http://www.boost.org/users/license.html
0013
0014
0015 #ifndef BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_POINTLIKE_POINTLIKE_HPP
0016 #define BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_POINTLIKE_POINTLIKE_HPP
0017
0018 #include <algorithm>
0019 #include <vector>
0020
0021 #include <boost/range/begin.hpp>
0022 #include <boost/range/end.hpp>
0023 #include <boost/range/size.hpp>
0024 #include <boost/range/value_type.hpp>
0025
0026 #include <boost/geometry/algorithms/convert.hpp>
0027 #include <boost/geometry/algorithms/not_implemented.hpp>
0028
0029 #include <boost/geometry/algorithms/detail/equals/point_point.hpp>
0030 #include <boost/geometry/algorithms/detail/overlay/overlay_type.hpp>
0031
0032 #include <boost/geometry/core/assert.hpp>
0033 #include <boost/geometry/core/point_type.hpp>
0034 #include <boost/geometry/core/tag.hpp>
0035 #include <boost/geometry/core/tags.hpp>
0036
0037 #include <boost/geometry/policies/compare.hpp>
0038
0039 #include <boost/geometry/util/constexpr.hpp>
0040
0041
0042 namespace boost { namespace geometry
0043 {
0044
0045
0046 #ifndef DOXYGEN_NO_DETAIL
0047 namespace detail { namespace overlay
0048 {
0049
0050
0051 // struct for copying points of the pointlike geometries to output
0052 template
0053 <
0054     typename PointOut,
0055     typename GeometryIn,
0056     typename TagIn = tag_t<GeometryIn>
0057 >
0058 struct copy_points
0059     : not_implemented<PointOut, GeometryIn>
0060 {};
0061
0062 template <typename PointOut, typename PointIn>
0063 struct copy_points<PointOut, PointIn, point_tag>
0064 {
0065     template <typename OutputIterator>
0066     static inline void apply(PointIn const& point_in,
0067                              OutputIterator& oit)
0068     {
0069         PointOut point_out;
0070         geometry::convert(point_in, point_out);
0071         *oit++ = point_out;
0072     }
0073 };
0074
0075
0076 template <typename PointOut, typename MultiPointIn>
0077 struct copy_points<PointOut, MultiPointIn, multi_point_tag>
0078 {
0079     template <typename OutputIterator>
0080     static inline void apply(MultiPointIn const& multi_point_in,
0081                              OutputIterator& oit)
0082     {
0083         for (auto it = boost::begin(multi_point_in); it != boost::end(multi_point_in); ++it)
0084         {
0085             PointOut point_out;
0086             geometry::convert(*it, point_out);
0087             *oit++ = point_out;
0088         }
0089     }
0090 };
0091
0092
0093
0094 // action struct for difference/intersection
0095 template <typename PointOut, overlay_type OverlayType>
0096 struct action_selector_pl
0097 {};
0098
0099 template <typename PointOut>
0100 struct action_selector_pl<PointOut, overlay_intersection>
0101 {
0102     template
0103     <
0104         typename Point,
0105         typename OutputIterator
0106     >
0107     static inline void apply(Point const& point,
0108                              bool is_common,
0109                              OutputIterator& oit)
0110     {
0111         if ( is_common )
0112         {
0113             copy_points<PointOut, Point>::apply(point, oit);
0114         }
0115     }
0116 };
0117
0118
0119
0120 template <typename PointOut>
0121 struct action_selector_pl<PointOut, overlay_difference>
0122 {
0123     template
0124     <
0125         typename Point,
0126         typename OutputIterator
0127     >
0128     static inline void apply(Point const& point,
0129                              bool is_common,
0130                              OutputIterator& oit)
0131     {
0132         if ( !is_common )
0133         {
0134             copy_points<PointOut, Point>::apply(point, oit);
0135         }
0136     }
0137 };
0138
0139
0140 //===========================================================================
0141
0142 // difference/intersection of point-point
0143 template
0144 <
0145     typename Point1,
0146     typename Point2,
0147     typename PointOut,
0148     overlay_type OverlayType
0149 >
0150 struct point_point_point
0151 {
0152     template <typename OutputIterator, typename Strategy>
0153     static inline OutputIterator apply(Point1 const& point1,
0154                                        Point2 const& point2,
0155                                        OutputIterator oit,
0156                                        Strategy const& strategy)
0157     {
0158         action_selector_pl
0159             <
0160                 PointOut, OverlayType
0161             >::apply(point1,
0162                      detail::equals::equals_point_point(point1, point2, strategy),
0163                      oit);
0164
0165         return oit;
0166     }
0167 };
0168
0169
0170
0171 // difference of multipoint-point
0172 //
0173 // the apply method in the following struct is called only for
0174 // difference; for intersection the reversal will
0175 // always call the point-multipoint version
0176 template
0177 <
0178     typename MultiPoint,
0179     typename Point,
0180     typename PointOut,
0181     overlay_type OverlayType
0182 >
0183 struct multipoint_point_point
0184 {
0185     template <typename OutputIterator, typename Strategy>
0186     static inline OutputIterator apply(MultiPoint const& multipoint,
0187                                        Point const& point,
0188                                        OutputIterator oit,
0189                                        Strategy const& strategy)
0190     {
0191         BOOST_GEOMETRY_ASSERT( OverlayType == overlay_difference );
0192
0193         for (auto it = boost::begin(multipoint); it != boost::end(multipoint); ++it)
0194         {
0195             action_selector_pl
0196                 <
0197                     PointOut, OverlayType
0198                 >::apply(*it,
0199                          detail::equals::equals_point_point(*it, point, strategy),
0200                          oit);
0201         }
0202
0203         return oit;
0204     }
0205 };
0206
0207
0208 // difference/intersection of point-multipoint
0209 template
0210 <
0211     typename Point,
0212     typename MultiPoint,
0213     typename PointOut,
0214     overlay_type OverlayType
0215 >
0216 struct point_multipoint_point
0217 {
0218     template <typename OutputIterator, typename Strategy>
0219     static inline OutputIterator apply(Point const& point,
0220                                        MultiPoint const& multipoint,
0221                                        OutputIterator oit,
0222                                        Strategy const& strategy)
0223     {
0224         using action = action_selector_pl<PointOut, OverlayType>;
0225
0226         for (auto it = boost::begin(multipoint); it != boost::end(multipoint); ++it)
0227         {
0228             if ( detail::equals::equals_point_point(*it, point, strategy) )
0229             {
0230                 action::apply(point, true, oit);
0231                 return oit;
0232             }
0233         }
0234
0235         action::apply(point, false, oit);
0236         return oit;
0237     }
0238 };
0239
0240
0241
0242 // difference/intersection of multipoint-multipoint
0243 template
0244 <
0245     typename MultiPoint1,
0246     typename MultiPoint2,
0247     typename PointOut,
0248     overlay_type OverlayType
0249 >
0250 struct multipoint_multipoint_point
0251 {
0252     template <typename OutputIterator, typename Strategy>
0253     static inline OutputIterator apply(MultiPoint1 const& multipoint1,
0254                                        MultiPoint2 const& multipoint2,
0255                                        OutputIterator oit,
0256                                        Strategy const& strategy)
0257     {
0258         using less_type = geometry::less<void, -1, Strategy>;
0259
0260         if BOOST_GEOMETRY_CONSTEXPR (OverlayType != overlay_difference)
0261         {
0262             if (boost::size(multipoint1) > boost::size(multipoint2))
0263             {
0264                 return multipoint_multipoint_point
0265                     <
0266                         MultiPoint2, MultiPoint1, PointOut, OverlayType
0267                     >::apply(multipoint2, multipoint1, oit, strategy);
0268             }
0269         }
0270
0271         using point2_type = typename boost::range_value<MultiPoint2>::type;
0272
0273         std::vector<point2_type> points2(boost::begin(multipoint2),
0274                                          boost::end(multipoint2));
0275
0276         less_type const less = less_type();
0277         std::sort(points2.begin(), points2.end(), less);
0278
0279         for (auto it1 = boost::begin(multipoint1); it1 != boost::end(multipoint1); ++it1)
0280         {
0281             bool found = std::binary_search(points2.begin(), points2.end(),
0282                                             *it1, less);
0283
0284             action_selector_pl
0285                 <
0286                     PointOut, OverlayType
0287                 >::apply(*it1, found, oit);
0288         }
0289         return oit;
0290     }
0291 };
0292
0293 }} // namespace detail::overlay
0294 #endif // DOXYGEN_NO_DETAIL
0295
0296
0297 //===========================================================================
0298
0299
0300 #ifndef DOXYGEN_NO_DISPATCH
0301 namespace detail_dispatch { namespace overlay
0302 {
0303
0304 // dispatch struct for pointlike-pointlike difference/intersection
0305 // computation
0306 template
0307 <
0308     typename PointLike1,
0309     typename PointLike2,
0310     typename PointOut,
0311     overlay_type OverlayType,
0312     typename Tag1,
0313     typename Tag2
0314 >
0315 struct pointlike_pointlike_point
0316     : not_implemented<PointLike1, PointLike2, PointOut>
0317 {};
0318
0319
0320 template
0321 <
0322     typename Point1,
0323     typename Point2,
0324     typename PointOut,
0325     overlay_type OverlayType
0326 >
0327 struct pointlike_pointlike_point
0328     <
0329         Point1, Point2, PointOut, OverlayType,
0330         point_tag, point_tag
0331     > : detail::overlay::point_point_point
0332         <
0333             Point1, Point2, PointOut, OverlayType
0334         >
0335 {};
0336
0337
0338 template
0339 <
0340     typename Point,
0341     typename MultiPoint,
0342     typename PointOut,
0343     overlay_type OverlayType
0344 >
0345 struct pointlike_pointlike_point
0346     <
0347         Point, MultiPoint, PointOut, OverlayType,
0348         point_tag, multi_point_tag
0349     > : detail::overlay::point_multipoint_point
0350         <
0351             Point, MultiPoint, PointOut, OverlayType
0352         >
0353 {};
0354
0355
0356 template
0357 <
0358     typename MultiPoint,
0359     typename Point,
0360     typename PointOut,
0361     overlay_type OverlayType
0362 >
0363 struct pointlike_pointlike_point
0364     <
0365         MultiPoint, Point, PointOut, OverlayType,
0366         multi_point_tag, point_tag
0367     > : detail::overlay::multipoint_point_point
0368         <
0369             MultiPoint, Point, PointOut, OverlayType
0370         >
0371 {};
0372
0373
0374 template
0375 <
0376     typename MultiPoint1,
0377     typename MultiPoint2,
0378     typename PointOut,
0379     overlay_type OverlayType
0380 >
0381 struct pointlike_pointlike_point
0382     <
0383         MultiPoint1, MultiPoint2, PointOut, OverlayType,
0384         multi_point_tag, multi_point_tag
0385     > : detail::overlay::multipoint_multipoint_point
0386         <
0387             MultiPoint1, MultiPoint2, PointOut, OverlayType
0388         >
0389 {};
0390
0391
0392 }} // namespace detail_dispatch::overlay
0393 #endif // DOXYGEN_NO_DISPATCH
0394
0395
0396 //===========================================================================
0397
0398
0399 #ifndef DOXYGEN_NO_DETAIL
0400 namespace detail { namespace overlay
0401 {
0402
0403
0404 // generic pointlike-pointlike union implementation
0405 template
0406 <
0407     typename PointLike1,
0408     typename PointLike2,
0409     typename PointOut
0410 >
0411 struct union_pointlike_pointlike_point
0412 {
0413     template <typename OutputIterator, typename Strategy>
0414     static inline OutputIterator apply(PointLike1 const& pointlike1,
0415                                        PointLike2 const& pointlike2,
0416                                        OutputIterator oit,
0417                                        Strategy const& strategy)
0418     {
0419         copy_points<PointOut, PointLike1>::apply(pointlike1, oit);
0420
0421         return detail_dispatch::overlay::pointlike_pointlike_point
0422             <
0423                 PointLike2, PointLike1, PointOut, overlay_difference,
0424                 tag_t<PointLike2>,
0425                 tag_t<PointLike1>
0426             >::apply(pointlike2, pointlike1, oit, strategy);
0427     }
0428
0429 };
0430
0431
0432 }} // namespace detail::overlay
0433 #endif // DOXYGEN_NO_DETAIL
0434
0435
0436 }} // namespace boost::geometry
0437
0438
0439 #endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_POINTLIKE_POINTLIKE_HPP