detail/overlay/pointlike_linear.hpp

0001 // Boost.Geometry (aka GGL, Generic Geometry Library)
0002
0003 // Copyright (c) 2017 Adam Wulkiewicz, Lodz, Poland.
0004
0005 // Copyright (c) 2015-2024, Oracle and/or its affiliates.
0006 // Contributed and/or modified by Vissarion Fysikopoulos, on behalf of Oracle
0007 // Contributed and/or modified by Menelaos Karavelas, on behalf of Oracle
0008 // Contributed and/or modified by Adam Wulkiewicz, on behalf of Oracle
0009
0010 // Licensed under the Boost Software License version 1.0.
0011 // http://www.boost.org/users/license.html
0012
0013
0014 #ifndef BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_POINTLIKE_LINEAR_HPP
0015 #define BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_POINTLIKE_LINEAR_HPP
0016
0017 #include <iterator>
0018 #include <vector>
0019
0020 #include <boost/range/begin.hpp>
0021 #include <boost/range/end.hpp>
0022 #include <boost/range/value_type.hpp>
0023
0024 #include <boost/geometry/algorithms/disjoint.hpp>
0025 #include <boost/geometry/algorithms/envelope.hpp>
0026 #include <boost/geometry/algorithms/expand.hpp>
0027 #include <boost/geometry/algorithms/not_implemented.hpp>
0028
0029 #include <boost/geometry/algorithms/detail/not.hpp>
0030 #include <boost/geometry/algorithms/detail/partition.hpp>
0031 #include <boost/geometry/algorithms/detail/disjoint/point_geometry.hpp>
0032 #include <boost/geometry/algorithms/detail/equals/point_point.hpp>
0033 #include <boost/geometry/algorithms/detail/overlay/overlay_type.hpp>
0034 #include <boost/geometry/algorithms/detail/overlay/pointlike_pointlike.hpp>
0035
0036 #include <boost/geometry/core/tags.hpp>
0037
0038 #include <boost/geometry/geometries/box.hpp>
0039
0040 #include <boost/geometry/iterators/segment_iterator.hpp>
0041
0042 // TEMP
0043 #include <boost/geometry/strategies/envelope/cartesian.hpp>
0044 #include <boost/geometry/strategies/envelope/geographic.hpp>
0045 #include <boost/geometry/strategies/envelope/spherical.hpp>
0046
0047
0048 namespace boost { namespace geometry
0049 {
0050
0051
0052 #ifndef DOXYGEN_NO_DETAIL
0053 namespace detail { namespace overlay
0054 {
0055
0056
0057 // difference/intersection of point-linear
0058 template
0059 <
0060     typename Point,
0061     typename Geometry,
0062     typename PointOut,
0063     overlay_type OverlayType,
0064     typename Policy
0065 >
0066 struct point_single_point
0067 {
0068     template <typename OutputIterator, typename Strategy>
0069     static inline OutputIterator apply(Point const& point,
0070                                        Geometry const& geometry,
0071                                        OutputIterator oit,
0072                                        Strategy const& strategy)
0073     {
0074         action_selector_pl
0075             <
0076                 PointOut, OverlayType
0077             >::apply(point, Policy::apply(point, geometry, strategy), oit);
0078         return oit;
0079     }
0080 };
0081
0082 // difference/intersection of multipoint-segment
0083 template
0084 <
0085     typename MultiPoint,
0086     typename Geometry,
0087     typename PointOut,
0088     overlay_type OverlayType,
0089     typename Policy
0090 >
0091 struct multipoint_single_point
0092 {
0093     template <typename OutputIterator, typename Strategy>
0094     static inline OutputIterator apply(MultiPoint const& multipoint,
0095                                        Geometry const& geometry,
0096                                        OutputIterator oit,
0097                                        Strategy const& strategy)
0098     {
0099         for (auto it = boost::begin(multipoint); it != boost::end(multipoint); ++it)
0100         {
0101             action_selector_pl
0102                 <
0103                     PointOut, OverlayType
0104                 >::apply(*it, Policy::apply(*it, geometry, strategy), oit);
0105         }
0106
0107         return oit;
0108     }
0109 };
0110
0111
0112 // difference/intersection of multipoint-linear
0113 template
0114 <
0115     typename MultiPoint,
0116     typename Linear,
0117     typename PointOut,
0118     overlay_type OverlayType,
0119     typename Policy
0120 >
0121 class multipoint_linear_point
0122 {
0123 private:
0124     // structs for partition -- start
0125     template <typename Strategy>
0126     struct expand_box_point
0127     {
0128         expand_box_point(Strategy const& strategy)
0129             : m_strategy(strategy)
0130         {}
0131
0132         template <typename Box, typename Point>
0133         inline void apply(Box& total, Point const& point) const
0134         {
0135             geometry::expand(total, point, m_strategy);
0136         }
0137
0138         Strategy const& m_strategy;
0139     };
0140
0141     template <typename Strategy>
0142     struct expand_box_segment
0143     {
0144         explicit expand_box_segment(Strategy const& strategy)
0145             : m_strategy(strategy)
0146         {}
0147
0148         template <typename Box, typename Segment>
0149         inline void apply(Box& total, Segment const& segment) const
0150         {
0151             geometry::expand(total,
0152                              geometry::return_envelope<Box>(segment, m_strategy),
0153                              m_strategy);
0154         }
0155
0156         Strategy const& m_strategy;
0157     };
0158
0159     template <typename Strategy>
0160     struct overlaps_box_point
0161     {
0162         explicit overlaps_box_point(Strategy const& strategy)
0163             : m_strategy(strategy)
0164         {}
0165
0166         template <typename Box, typename Point>
0167         inline bool apply(Box const& box, Point const& point) const
0168         {
0169             return ! geometry::disjoint(point, box, m_strategy);
0170         }
0171
0172         Strategy const& m_strategy;
0173     };
0174
0175     template <typename Strategy>
0176     struct overlaps_box_segment
0177     {
0178         explicit overlaps_box_segment(Strategy const& strategy)
0179             : m_strategy(strategy)
0180         {}
0181
0182         template <typename Box, typename Segment>
0183         inline bool apply(Box const& box, Segment const& segment) const
0184         {
0185             return ! geometry::disjoint(segment, box, m_strategy);
0186         }
0187
0188         Strategy const& m_strategy;
0189     };
0190
0191     template <typename OutputIterator, typename Strategy>
0192     class item_visitor_type
0193     {
0194     public:
0195         item_visitor_type(OutputIterator& oit, Strategy const& strategy)
0196             : m_oit(oit)
0197             , m_strategy(strategy)
0198         {}
0199
0200         template <typename Item1, typename Item2>
0201         inline bool apply(Item1 const& item1, Item2 const& item2)
0202         {
0203             action_selector_pl
0204                 <
0205                     PointOut, overlay_intersection
0206                 >::apply(item1, Policy::apply(item1, item2, m_strategy), m_oit);
0207
0208             return true;
0209         }
0210
0211     private:
0212         OutputIterator& m_oit;
0213         Strategy const& m_strategy;
0214     };
0215     // structs for partition -- end
0216
0217     class segment_range
0218     {
0219     public:
0220         using const_iterator = geometry::segment_iterator<Linear const>;
0221         using iterator = const_iterator;
0222
0223         explicit segment_range(Linear const& linear)
0224             : m_linear(linear)
0225         {}
0226
0227         const_iterator begin() const
0228         {
0229             return geometry::segments_begin(m_linear);
0230         }
0231
0232         const_iterator end() const
0233         {
0234             return geometry::segments_end(m_linear);
0235         }
0236
0237     private:
0238         Linear const& m_linear;
0239     };
0240
0241     template <typename OutputIterator, typename Strategy>
0242     static inline OutputIterator get_common_points(MultiPoint const& multipoint,
0243                                                    Linear const& linear,
0244                                                    OutputIterator oit,
0245                                                    Strategy const& strategy)
0246     {
0247         item_visitor_type<OutputIterator, Strategy> item_visitor(oit, strategy);
0248
0249         // TODO: disjoint Segment/Box may be called in partition multiple times
0250         // possibly for non-cartesian segments which could be slow. We should consider
0251         // passing a range of bounding boxes of segments after calculating them once.
0252         // Alternatively instead of a range of segments a range of Segment/Envelope pairs
0253         // should be passed, where envelope would be lazily calculated when needed the first time
0254         geometry::partition
0255             <
0256                 geometry::model::box
0257                     <
0258                         typename boost::range_value<MultiPoint>::type
0259                     >
0260             >::apply(multipoint, segment_range(linear), item_visitor,
0261                      expand_box_point<Strategy>(strategy),
0262                      overlaps_box_point<Strategy>(strategy),
0263                      expand_box_segment<Strategy>(strategy),
0264                      overlaps_box_segment<Strategy>(strategy));
0265
0266         return oit;
0267     }
0268
0269 public:
0270     template <typename OutputIterator, typename Strategy>
0271     static inline OutputIterator apply(MultiPoint const& multipoint,
0272                                        Linear const& linear,
0273                                        OutputIterator oit,
0274                                        Strategy const& strategy)
0275     {
0276         using point_vector_type = std::vector
0277             <
0278                 typename boost::range_value<MultiPoint>::type
0279             >;
0280
0281         point_vector_type common_points;
0282
0283         // compute the common points
0284         get_common_points(multipoint, linear,
0285                           std::back_inserter(common_points),
0286                           strategy);
0287
0288         return multipoint_multipoint_point
0289             <
0290                 MultiPoint, point_vector_type, PointOut, OverlayType
0291             >::apply(multipoint, common_points, oit, strategy);
0292     }
0293 };
0294
0295
0296 }} // namespace detail::overlay
0297 #endif // DOXYGEN_NO_DETAIL
0298
0299
0300 #ifndef DOXYGEN_NO_DISPATCH
0301 namespace detail_dispatch { namespace overlay
0302 {
0303
0304 // dispatch struct for pointlike-linear difference/intersection computation
0305 template
0306 <
0307     typename PointLike,
0308     typename Linear,
0309     typename PointOut,
0310     overlay_type OverlayType,
0311     typename Tag1,
0312     typename Tag2
0313 >
0314 struct pointlike_linear_point
0315     : not_implemented<PointLike, Linear, PointOut>
0316 {};
0317
0318
0319 template
0320 <
0321     typename Point,
0322     typename Linear,
0323     typename PointOut,
0324     overlay_type OverlayType
0325 >
0326 struct pointlike_linear_point
0327     <
0328         Point, Linear, PointOut, OverlayType, point_tag, linear_tag
0329     > : detail::overlay::point_single_point
0330         <
0331             Point, Linear, PointOut, OverlayType,
0332             detail::not_<detail::disjoint::reverse_covered_by>
0333         >
0334 {};
0335
0336
0337 template
0338 <
0339     typename Point,
0340     typename Segment,
0341     typename PointOut,
0342     overlay_type OverlayType
0343 >
0344 struct pointlike_linear_point
0345     <
0346         Point, Segment, PointOut, OverlayType, point_tag, segment_tag
0347     > : detail::overlay::point_single_point
0348         <
0349             Point, Segment, PointOut, OverlayType,
0350             detail::not_<detail::disjoint::reverse_covered_by>
0351         >
0352 {};
0353
0354
0355 template
0356 <
0357     typename MultiPoint,
0358     typename Linear,
0359     typename PointOut,
0360     overlay_type OverlayType
0361 >
0362 struct pointlike_linear_point
0363     <
0364         MultiPoint, Linear, PointOut, OverlayType, multi_point_tag, linear_tag
0365     > : detail::overlay::multipoint_linear_point
0366         <
0367             MultiPoint, Linear, PointOut, OverlayType,
0368             detail::not_<detail::disjoint::reverse_covered_by>
0369         >
0370 {};
0371
0372
0373 template
0374 <
0375     typename MultiPoint,
0376     typename Segment,
0377     typename PointOut,
0378     overlay_type OverlayType
0379 >
0380 struct pointlike_linear_point
0381     <
0382         MultiPoint, Segment, PointOut, OverlayType, multi_point_tag, segment_tag
0383     > : detail::overlay::multipoint_single_point
0384         <
0385             MultiPoint, Segment, PointOut, OverlayType,
0386             detail::not_<detail::disjoint::reverse_covered_by>
0387         >
0388 {};
0389
0390
0391 }} // namespace detail_dispatch::overlay
0392 #endif // DOXYGEN_NO_DISPATCH
0393
0394
0395 }} // namespace boost::geometry
0396
0397
0398 #endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_POINTLIKE_LINEAR_HPP