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/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 = 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_CONSTEXPR (OverlayType != overlay_difference)
0265         {
0266             if (boost::size(multipoint1) > boost::size(multipoint2))
0267             {
0268                 return multipoint_multipoint_point
0269                     <
0270                         MultiPoint2, MultiPoint1, PointOut, OverlayType
0271                     >::apply(multipoint2, multipoint1, robust_policy, oit, strategy);
0272             }
0273         }
0274
0275         typedef typename boost::range_value<MultiPoint2>::type point2_type;
0276
0277         std::vector<point2_type> points2(boost::begin(multipoint2),
0278                                          boost::end(multipoint2));
0279
0280         less_type const less = less_type();
0281         std::sort(points2.begin(), points2.end(), less);
0282
0283         for (auto it1 = boost::begin(multipoint1); it1 != boost::end(multipoint1); ++it1)
0284         {
0285             bool found = std::binary_search(points2.begin(), points2.end(),
0286                                             *it1, less);
0287
0288             action_selector_pl
0289                 <
0290                     PointOut, OverlayType
0291                 >::apply(*it1, found, oit);
0292         }
0293         return oit;
0294     }
0295 };
0296
0297 }} // namespace detail::overlay
0298 #endif // DOXYGEN_NO_DETAIL
0299
0300
0301 //===========================================================================
0302
0303
0304 #ifndef DOXYGEN_NO_DISPATCH
0305 namespace detail_dispatch { namespace overlay
0306 {
0307
0308 // dispatch struct for pointlike-pointlike difference/intersection
0309 // computation
0310 template
0311 <
0312     typename PointLike1,
0313     typename PointLike2,
0314     typename PointOut,
0315     overlay_type OverlayType,
0316     typename Tag1,
0317     typename Tag2
0318 >
0319 struct pointlike_pointlike_point
0320     : not_implemented<PointLike1, PointLike2, PointOut>
0321 {};
0322
0323
0324 template
0325 <
0326     typename Point1,
0327     typename Point2,
0328     typename PointOut,
0329     overlay_type OverlayType
0330 >
0331 struct pointlike_pointlike_point
0332     <
0333         Point1, Point2, PointOut, OverlayType,
0334         point_tag, point_tag
0335     > : detail::overlay::point_point_point
0336         <
0337             Point1, Point2, PointOut, OverlayType
0338         >
0339 {};
0340
0341
0342 template
0343 <
0344     typename Point,
0345     typename MultiPoint,
0346     typename PointOut,
0347     overlay_type OverlayType
0348 >
0349 struct pointlike_pointlike_point
0350     <
0351         Point, MultiPoint, PointOut, OverlayType,
0352         point_tag, multi_point_tag
0353     > : detail::overlay::point_multipoint_point
0354         <
0355             Point, MultiPoint, PointOut, OverlayType
0356         >
0357 {};
0358
0359
0360 template
0361 <
0362     typename MultiPoint,
0363     typename Point,
0364     typename PointOut,
0365     overlay_type OverlayType
0366 >
0367 struct pointlike_pointlike_point
0368     <
0369         MultiPoint, Point, PointOut, OverlayType,
0370         multi_point_tag, point_tag
0371     > : detail::overlay::multipoint_point_point
0372         <
0373             MultiPoint, Point, PointOut, OverlayType
0374         >
0375 {};
0376
0377
0378 template
0379 <
0380     typename MultiPoint1,
0381     typename MultiPoint2,
0382     typename PointOut,
0383     overlay_type OverlayType
0384 >
0385 struct pointlike_pointlike_point
0386     <
0387         MultiPoint1, MultiPoint2, PointOut, OverlayType,
0388         multi_point_tag, multi_point_tag
0389     > : detail::overlay::multipoint_multipoint_point
0390         <
0391             MultiPoint1, MultiPoint2, PointOut, OverlayType
0392         >
0393 {};
0394
0395
0396 }} // namespace detail_dispatch::overlay
0397 #endif // DOXYGEN_NO_DISPATCH
0398
0399
0400 //===========================================================================
0401
0402
0403 #ifndef DOXYGEN_NO_DETAIL
0404 namespace detail { namespace overlay
0405 {
0406
0407
0408 // generic pointlike-pointlike union implementation
0409 template
0410 <
0411     typename PointLike1,
0412     typename PointLike2,
0413     typename PointOut
0414 >
0415 struct union_pointlike_pointlike_point
0416 {
0417     template <typename RobustPolicy, typename OutputIterator, typename Strategy>
0418     static inline OutputIterator apply(PointLike1 const& pointlike1,
0419                                        PointLike2 const& pointlike2,
0420                                        RobustPolicy const& robust_policy,
0421                                        OutputIterator oit,
0422                                        Strategy const& strategy)
0423     {
0424         copy_points<PointOut, PointLike1>::apply(pointlike1, oit);
0425
0426         return detail_dispatch::overlay::pointlike_pointlike_point
0427             <
0428                 PointLike2, PointLike1, PointOut, overlay_difference,
0429                 typename tag<PointLike2>::type,
0430                 typename tag<PointLike1>::type
0431             >::apply(pointlike2, pointlike1, robust_policy, oit, strategy);
0432     }
0433
0434 };
0435
0436
0437 }} // namespace detail::overlay
0438 #endif // DOXYGEN_NO_DETAIL
0439
0440
0441 }} // namespace boost::geometry
0442
0443
0444 #endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_POINTLIKE_POINTLIKE_HPP