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-2020, Oracle and/or its affiliates.
0006
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 RobustPolicy, typename OutputIterator, typename Strategy>
0069     static inline OutputIterator apply(Point const& point,
0070                                        Geometry const& geometry,
0071                                        RobustPolicy const&,
0072                                        OutputIterator oit,
0073                                        Strategy const& strategy)
0074     {
0075         action_selector_pl
0076             <
0077                 PointOut, OverlayType
0078             >::apply(point, Policy::apply(point, geometry, strategy), oit);
0079         return oit;
0080     }
0081 };
0082
0083 // difference/intersection of multipoint-segment
0084 template
0085 <
0086     typename MultiPoint,
0087     typename Geometry,
0088     typename PointOut,
0089     overlay_type OverlayType,
0090     typename Policy
0091 >
0092 struct multipoint_single_point
0093 {
0094     template <typename RobustPolicy, typename OutputIterator, typename Strategy>
0095     static inline OutputIterator apply(MultiPoint const& multipoint,
0096                                        Geometry const& geometry,
0097                                        RobustPolicy const&,
0098                                        OutputIterator oit,
0099                                        Strategy const& strategy)
0100     {
0101         for (auto it = boost::begin(multipoint); it != boost::end(multipoint); ++it)
0102         {
0103             action_selector_pl
0104                 <
0105                     PointOut, OverlayType
0106                 >::apply(*it, Policy::apply(*it, geometry, strategy), oit);
0107         }
0108
0109         return oit;
0110     }
0111 };
0112
0113
0114 // difference/intersection of multipoint-linear
0115 template
0116 <
0117     typename MultiPoint,
0118     typename Linear,
0119     typename PointOut,
0120     overlay_type OverlayType,
0121     typename Policy
0122 >
0123 class multipoint_linear_point
0124 {
0125 private:
0126     // structs for partition -- start
0127     template <typename Strategy>
0128     struct expand_box_point
0129     {
0130         expand_box_point(Strategy const& strategy)
0131             : m_strategy(strategy)
0132         {}
0133
0134         template <typename Box, typename Point>
0135         inline void apply(Box& total, Point const& point) const
0136         {
0137             geometry::expand(total, point, m_strategy);
0138         }
0139
0140         Strategy const& m_strategy;
0141     };
0142
0143     template <typename Strategy>
0144     struct expand_box_segment
0145     {
0146         explicit expand_box_segment(Strategy const& strategy)
0147             : m_strategy(strategy)
0148         {}
0149
0150         template <typename Box, typename Segment>
0151         inline void apply(Box& total, Segment const& segment) const
0152         {
0153             geometry::expand(total,
0154                              geometry::return_envelope<Box>(segment, m_strategy),
0155                              m_strategy);
0156         }
0157
0158         Strategy const& m_strategy;
0159     };
0160
0161     template <typename Strategy>
0162     struct overlaps_box_point
0163     {
0164         explicit overlaps_box_point(Strategy const& strategy)
0165             : m_strategy(strategy)
0166         {}
0167
0168         template <typename Box, typename Point>
0169         inline bool apply(Box const& box, Point const& point) const
0170         {
0171             return ! geometry::disjoint(point, box, m_strategy);
0172         }
0173
0174         Strategy const& m_strategy;
0175     };
0176
0177     template <typename Strategy>
0178     struct overlaps_box_segment
0179     {
0180         explicit overlaps_box_segment(Strategy const& strategy)
0181             : m_strategy(strategy)
0182         {}
0183
0184         template <typename Box, typename Segment>
0185         inline bool apply(Box const& box, Segment const& segment) const
0186         {
0187             return ! geometry::disjoint(segment, box, m_strategy);
0188         }
0189
0190         Strategy const& m_strategy;
0191     };
0192
0193     template <typename OutputIterator, typename Strategy>
0194     class item_visitor_type
0195     {
0196     public:
0197         item_visitor_type(OutputIterator& oit, Strategy const& strategy)
0198             : m_oit(oit)
0199             , m_strategy(strategy)
0200         {}
0201
0202         template <typename Item1, typename Item2>
0203         inline bool apply(Item1 const& item1, Item2 const& item2)
0204         {
0205             action_selector_pl
0206                 <
0207                     PointOut, overlay_intersection
0208                 >::apply(item1, Policy::apply(item1, item2, m_strategy), m_oit);
0209
0210             return true;
0211         }
0212
0213     private:
0214         OutputIterator& m_oit;
0215         Strategy const& m_strategy;
0216     };
0217     // structs for partition -- end
0218
0219     class segment_range
0220     {
0221     public:
0222         typedef geometry::segment_iterator<Linear const> const_iterator;
0223         typedef const_iterator iterator;
0224
0225         explicit segment_range(Linear const& linear)
0226             : m_linear(linear)
0227         {}
0228
0229         const_iterator begin() const
0230         {
0231             return geometry::segments_begin(m_linear);
0232         }
0233
0234         const_iterator end() const
0235         {
0236             return geometry::segments_end(m_linear);
0237         }
0238
0239     private:
0240         Linear const& m_linear;
0241     };
0242
0243     template <typename OutputIterator, typename Strategy>
0244     static inline OutputIterator get_common_points(MultiPoint const& multipoint,
0245                                                    Linear const& linear,
0246                                                    OutputIterator oit,
0247                                                    Strategy const& strategy)
0248     {
0249         item_visitor_type<OutputIterator, Strategy> item_visitor(oit, strategy);
0250
0251         // TODO: disjoint Segment/Box may be called in partition multiple times
0252         // possibly for non-cartesian segments which could be slow. We should consider
0253         // passing a range of bounding boxes of segments after calculating them once.
0254         // Alternatively instead of a range of segments a range of Segment/Envelope pairs
0255         // should be passed, where envelope would be lazily calculated when needed the first time
0256         geometry::partition
0257             <
0258                 geometry::model::box
0259                     <
0260                         typename boost::range_value<MultiPoint>::type
0261                     >
0262             >::apply(multipoint, segment_range(linear), item_visitor,
0263                      expand_box_point<Strategy>(strategy),
0264                      overlaps_box_point<Strategy>(strategy),
0265                      expand_box_segment<Strategy>(strategy),
0266                      overlaps_box_segment<Strategy>(strategy));
0267
0268         return oit;
0269     }
0270
0271 public:
0272     template <typename RobustPolicy, typename OutputIterator, typename Strategy>
0273     static inline OutputIterator apply(MultiPoint const& multipoint,
0274                                        Linear const& linear,
0275                                        RobustPolicy const& robust_policy,
0276                                        OutputIterator oit,
0277                                        Strategy const& strategy)
0278     {
0279         typedef std::vector
0280             <
0281                 typename boost::range_value<MultiPoint>::type
0282             > point_vector_type;
0283
0284         point_vector_type common_points;
0285
0286         // compute the common points
0287         get_common_points(multipoint, linear,
0288                           std::back_inserter(common_points),
0289                           strategy);
0290
0291         return multipoint_multipoint_point
0292             <
0293                 MultiPoint, point_vector_type, PointOut, OverlayType
0294             >::apply(multipoint, common_points, robust_policy, oit, strategy);
0295     }
0296 };
0297
0298
0299 }} // namespace detail::overlay
0300 #endif // DOXYGEN_NO_DETAIL
0301
0302
0303 #ifndef DOXYGEN_NO_DISPATCH
0304 namespace detail_dispatch { namespace overlay
0305 {
0306
0307 // dispatch struct for pointlike-linear difference/intersection computation
0308 template
0309 <
0310     typename PointLike,
0311     typename Linear,
0312     typename PointOut,
0313     overlay_type OverlayType,
0314     typename Tag1,
0315     typename Tag2
0316 >
0317 struct pointlike_linear_point
0318     : not_implemented<PointLike, Linear, PointOut>
0319 {};
0320
0321
0322 template
0323 <
0324     typename Point,
0325     typename Linear,
0326     typename PointOut,
0327     overlay_type OverlayType
0328 >
0329 struct pointlike_linear_point
0330     <
0331         Point, Linear, PointOut, OverlayType, point_tag, linear_tag
0332     > : detail::overlay::point_single_point
0333         <
0334             Point, Linear, PointOut, OverlayType,
0335             detail::not_<detail::disjoint::reverse_covered_by>
0336         >
0337 {};
0338
0339
0340 template
0341 <
0342     typename Point,
0343     typename Segment,
0344     typename PointOut,
0345     overlay_type OverlayType
0346 >
0347 struct pointlike_linear_point
0348     <
0349         Point, Segment, PointOut, OverlayType, point_tag, segment_tag
0350     > : detail::overlay::point_single_point
0351         <
0352             Point, Segment, PointOut, OverlayType,
0353             detail::not_<detail::disjoint::reverse_covered_by>
0354         >
0355 {};
0356
0357
0358 template
0359 <
0360     typename MultiPoint,
0361     typename Linear,
0362     typename PointOut,
0363     overlay_type OverlayType
0364 >
0365 struct pointlike_linear_point
0366     <
0367         MultiPoint, Linear, PointOut, OverlayType, multi_point_tag, linear_tag
0368     > : detail::overlay::multipoint_linear_point
0369         <
0370             MultiPoint, Linear, PointOut, OverlayType,
0371             detail::not_<detail::disjoint::reverse_covered_by>
0372         >
0373 {};
0374
0375
0376 template
0377 <
0378     typename MultiPoint,
0379     typename Segment,
0380     typename PointOut,
0381     overlay_type OverlayType
0382 >
0383 struct pointlike_linear_point
0384     <
0385         MultiPoint, Segment, PointOut, OverlayType, multi_point_tag, segment_tag
0386     > : detail::overlay::multipoint_single_point
0387         <
0388             MultiPoint, Segment, PointOut, OverlayType,
0389             detail::not_<detail::disjoint::reverse_covered_by>
0390         >
0391 {};
0392
0393
0394 }} // namespace detail_dispatch::overlay
0395 #endif // DOXYGEN_NO_DISPATCH
0396
0397
0398 }} // namespace boost::geometry
0399
0400
0401 #endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_POINTLIKE_LINEAR_HPP