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-2023, 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/condition.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 = typename tag<GeometryIn>::type
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 RobustPolicy, typename OutputIterator, typename Strategy>
0153     static inline OutputIterator apply(Point1 const& point1,
0154                                        Point2 const& point2,
0155                                        RobustPolicy const& ,
0156                                        OutputIterator oit,
0157                                        Strategy const& strategy)
0158     {
0159         action_selector_pl
0160             <
0161                 PointOut, OverlayType
0162             >::apply(point1,
0163                      detail::equals::equals_point_point(point1, point2, strategy),
0164                      oit);
0165
0166         return oit;
0167     }
0168 };
0169
0170
0171
0172 // difference of multipoint-point
0173 //
0174 // the apply method in the following struct is called only for
0175 // difference; for intersection the reversal will
0176 // always call the point-multipoint version
0177 template
0178 <
0179     typename MultiPoint,
0180     typename Point,
0181     typename PointOut,
0182     overlay_type OverlayType
0183 >
0184 struct multipoint_point_point
0185 {
0186     template <typename RobustPolicy, typename OutputIterator, typename Strategy>
0187     static inline OutputIterator apply(MultiPoint const& multipoint,
0188                                        Point const& point,
0189                                        RobustPolicy const& ,
0190                                        OutputIterator oit,
0191                                        Strategy const& strategy)
0192     {
0193         BOOST_GEOMETRY_ASSERT( OverlayType == overlay_difference );
0194
0195         for (auto it = boost::begin(multipoint); it != boost::end(multipoint); ++it)
0196         {
0197             action_selector_pl
0198                 <
0199                     PointOut, OverlayType
0200                 >::apply(*it,
0201                          detail::equals::equals_point_point(*it, point, strategy),
0202                          oit);
0203         }
0204
0205         return oit;
0206     }
0207 };
0208
0209
0210 // difference/intersection of point-multipoint
0211 template
0212 <
0213     typename Point,
0214     typename MultiPoint,
0215     typename PointOut,
0216     overlay_type OverlayType
0217 >
0218 struct point_multipoint_point
0219 {
0220     template <typename RobustPolicy, typename OutputIterator, typename Strategy>
0221     static inline OutputIterator apply(Point const& point,
0222                                        MultiPoint const& multipoint,
0223                                        RobustPolicy const& ,
0224                                        OutputIterator oit,
0225                                        Strategy const& strategy)
0226     {
0227         typedef action_selector_pl<PointOut, OverlayType> action;
0228
0229         for (auto it = boost::begin(multipoint); it != boost::end(multipoint); ++it)
0230         {
0231             if ( detail::equals::equals_point_point(*it, point, strategy) )
0232             {
0233                 action::apply(point, true, oit);
0234                 return oit;
0235             }
0236         }
0237
0238         action::apply(point, false, oit);
0239         return oit;
0240     }
0241 };
0242
0243
0244
0245 // difference/intersection of multipoint-multipoint
0246 template
0247 <
0248     typename MultiPoint1,
0249     typename MultiPoint2,
0250     typename PointOut,
0251     overlay_type OverlayType
0252 >
0253 struct multipoint_multipoint_point
0254 {
0255     template <typename RobustPolicy, typename OutputIterator, typename Strategy>
0256     static inline OutputIterator apply(MultiPoint1 const& multipoint1,
0257                                        MultiPoint2 const& multipoint2,
0258                                        RobustPolicy const& robust_policy,
0259                                        OutputIterator oit,
0260                                        Strategy const& strategy)
0261     {
0262         typedef geometry::less<void, -1, Strategy> less_type;
0263
0264         if (BOOST_GEOMETRY_CONDITION(OverlayType != overlay_difference)
0265             && boost::size(multipoint1) > boost::size(multipoint2))
0266         {
0267             return multipoint_multipoint_point
0268                 <
0269                     MultiPoint2, MultiPoint1, PointOut, OverlayType
0270                 >::apply(multipoint2, multipoint1, robust_policy, oit, strategy);
0271         }
0272
0273         typedef typename boost::range_value<MultiPoint2>::type point2_type;
0274
0275         std::vector<point2_type> points2(boost::begin(multipoint2),
0276                                          boost::end(multipoint2));
0277
0278         less_type const less = less_type();
0279         std::sort(points2.begin(), points2.end(), less);
0280
0281         for (auto it1 = boost::begin(multipoint1); it1 != boost::end(multipoint1); ++it1)
0282         {
0283             bool found = std::binary_search(points2.begin(), points2.end(),
0284                                             *it1, less);
0285
0286             action_selector_pl
0287                 <
0288                     PointOut, OverlayType
0289                 >::apply(*it1, found, oit);
0290         }
0291         return oit;
0292     }
0293 };
0294
0295 }} // namespace detail::overlay
0296 #endif // DOXYGEN_NO_DETAIL
0297
0298
0299 //===========================================================================
0300
0301
0302 #ifndef DOXYGEN_NO_DISPATCH
0303 namespace detail_dispatch { namespace overlay
0304 {
0305
0306 // dispatch struct for pointlike-pointlike difference/intersection
0307 // computation
0308 template
0309 <
0310     typename PointLike1,
0311     typename PointLike2,
0312     typename PointOut,
0313     overlay_type OverlayType,
0314     typename Tag1,
0315     typename Tag2
0316 >
0317 struct pointlike_pointlike_point
0318     : not_implemented<PointLike1, PointLike2, PointOut>
0319 {};
0320
0321
0322 template
0323 <
0324     typename Point1,
0325     typename Point2,
0326     typename PointOut,
0327     overlay_type OverlayType
0328 >
0329 struct pointlike_pointlike_point
0330     <
0331         Point1, Point2, PointOut, OverlayType,
0332         point_tag, point_tag
0333     > : detail::overlay::point_point_point
0334         <
0335             Point1, Point2, PointOut, OverlayType
0336         >
0337 {};
0338
0339
0340 template
0341 <
0342     typename Point,
0343     typename MultiPoint,
0344     typename PointOut,
0345     overlay_type OverlayType
0346 >
0347 struct pointlike_pointlike_point
0348     <
0349         Point, MultiPoint, PointOut, OverlayType,
0350         point_tag, multi_point_tag
0351     > : detail::overlay::point_multipoint_point
0352         <
0353             Point, MultiPoint, PointOut, OverlayType
0354         >
0355 {};
0356
0357
0358 template
0359 <
0360     typename MultiPoint,
0361     typename Point,
0362     typename PointOut,
0363     overlay_type OverlayType
0364 >
0365 struct pointlike_pointlike_point
0366     <
0367         MultiPoint, Point, PointOut, OverlayType,
0368         multi_point_tag, point_tag
0369     > : detail::overlay::multipoint_point_point
0370         <
0371             MultiPoint, Point, PointOut, OverlayType
0372         >
0373 {};
0374
0375
0376 template
0377 <
0378     typename MultiPoint1,
0379     typename MultiPoint2,
0380     typename PointOut,
0381     overlay_type OverlayType
0382 >
0383 struct pointlike_pointlike_point
0384     <
0385         MultiPoint1, MultiPoint2, PointOut, OverlayType,
0386         multi_point_tag, multi_point_tag
0387     > : detail::overlay::multipoint_multipoint_point
0388         <
0389             MultiPoint1, MultiPoint2, PointOut, OverlayType
0390         >
0391 {};
0392
0393
0394 }} // namespace detail_dispatch::overlay
0395 #endif // DOXYGEN_NO_DISPATCH
0396
0397
0398 //===========================================================================
0399
0400
0401 #ifndef DOXYGEN_NO_DETAIL
0402 namespace detail { namespace overlay
0403 {
0404
0405
0406 // generic pointlike-pointlike union implementation
0407 template
0408 <
0409     typename PointLike1,
0410     typename PointLike2,
0411     typename PointOut
0412 >
0413 struct union_pointlike_pointlike_point
0414 {
0415     template <typename RobustPolicy, typename OutputIterator, typename Strategy>
0416     static inline OutputIterator apply(PointLike1 const& pointlike1,
0417                                        PointLike2 const& pointlike2,
0418                                        RobustPolicy const& robust_policy,
0419                                        OutputIterator oit,
0420                                        Strategy const& strategy)
0421     {
0422         copy_points<PointOut, PointLike1>::apply(pointlike1, oit);
0423
0424         return detail_dispatch::overlay::pointlike_pointlike_point
0425             <
0426                 PointLike2, PointLike1, PointOut, overlay_difference,
0427                 typename tag<PointLike2>::type,
0428                 typename tag<PointLike1>::type
0429             >::apply(pointlike2, pointlike1, robust_policy, oit, strategy);
0430     }
0431
0432 };
0433
0434
0435 }} // namespace detail::overlay
0436 #endif // DOXYGEN_NO_DETAIL
0437
0438
0439 }} // namespace boost::geometry
0440
0441
0442 #endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_POINTLIKE_POINTLIKE_HPP