detail/overlay/pointlike_areal.hpp

0001 // Boost.Geometry (aka GGL, Generic Geometry Library)
0002
0003 // Copyright (c) 2020, Oracle and/or its affiliates.
0004
0005 // Contributed and/or modified by Adam Wulkiewicz, on behalf of Oracle
0006
0007 // Licensed under the Boost Software License version 1.0.
0008 // http://www.boost.org/users/license.html
0009
0010
0011 #ifndef BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_POINTLIKE_AREAL_HPP
0012 #define BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_POINTLIKE_AREAL_HPP
0013
0014 #include <vector>
0015
0016 #include <boost/range/begin.hpp>
0017 #include <boost/range/end.hpp>
0018 #include <boost/range/size.hpp>
0019 #include <boost/range/value_type.hpp>
0020
0021 #include <boost/geometry/algorithms/disjoint.hpp>
0022 #include <boost/geometry/algorithms/envelope.hpp>
0023 #include <boost/geometry/algorithms/expand.hpp>
0024 #include <boost/geometry/algorithms/not_implemented.hpp>
0025
0026 #include <boost/geometry/algorithms/detail/not.hpp>
0027 #include <boost/geometry/algorithms/detail/partition.hpp>
0028 #include <boost/geometry/algorithms/detail/disjoint/point_geometry.hpp>
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/algorithms/detail/overlay/pointlike_linear.hpp>
0033
0034 #include <boost/geometry/core/tags.hpp>
0035
0036 #include <boost/geometry/geometries/box.hpp>
0037 #include <boost/geometry/geometries/point.hpp>
0038
0039 // TEMP
0040 #include <boost/geometry/strategies/envelope/cartesian.hpp>
0041 #include <boost/geometry/strategies/envelope/geographic.hpp>
0042 #include <boost/geometry/strategies/envelope/spherical.hpp>
0043
0044
0045 namespace boost { namespace geometry
0046 {
0047
0048
0049 #ifndef DOXYGEN_NO_DETAIL
0050 namespace detail { namespace overlay
0051 {
0052
0053
0054 // difference/intersection of multipoint-multipolygon
0055 template
0056 <
0057     typename MultiPoint,
0058     typename MultiPolygon,
0059     typename PointOut,
0060     overlay_type OverlayType,
0061     typename Policy
0062 >
0063 class multipoint_multipolygon_point
0064 {
0065 private:
0066     template <typename Strategy>
0067     struct expand_box_point
0068     {
0069         explicit expand_box_point(Strategy const& strategy)
0070             : m_strategy(strategy)
0071         {}
0072
0073         template <typename Box, typename Point>
0074         inline void apply(Box& total, Point const& point) const
0075         {
0076             geometry::expand(total, point, m_strategy);
0077         }
0078
0079         Strategy const& m_strategy;
0080     };
0081
0082     template <typename Strategy>
0083     struct expand_box_boxpair
0084     {
0085         explicit expand_box_boxpair(Strategy const& strategy)
0086             : m_strategy(strategy)
0087         {}
0088
0089         template <typename Box1, typename Box2, typename SizeT>
0090         inline void apply(Box1& total, std::pair<Box2, SizeT> const& box_pair) const
0091         {
0092             geometry::expand(total, box_pair.first, m_strategy);
0093         }
0094
0095         Strategy const& m_strategy;
0096     };
0097
0098     template <typename Strategy>
0099     struct overlaps_box_point
0100     {
0101         explicit overlaps_box_point(Strategy const& strategy)
0102             : m_strategy(strategy)
0103         {}
0104
0105         template <typename Box, typename Point>
0106         inline bool apply(Box const& box, Point const& point) const
0107         {
0108             return ! geometry::disjoint(point, box, m_strategy);
0109         }
0110
0111         Strategy const& m_strategy;
0112     };
0113
0114     template <typename Strategy>
0115     struct overlaps_box_boxpair
0116     {
0117         explicit overlaps_box_boxpair(Strategy const& strategy)
0118             : m_strategy(strategy)
0119         {}
0120
0121         template <typename Box1, typename Box2, typename SizeT>
0122         inline bool apply(Box1 const& box, std::pair<Box2, SizeT> const& box_pair) const
0123         {
0124             return ! geometry::disjoint(box, box_pair.first, m_strategy);
0125         }
0126
0127         Strategy const& m_strategy;
0128     };
0129
0130     template <typename OutputIterator, typename Strategy>
0131     class item_visitor_type
0132     {
0133     public:
0134         item_visitor_type(MultiPolygon const& multipolygon,
0135                           OutputIterator& oit,
0136                           Strategy const& strategy)
0137             : m_multipolygon(multipolygon)
0138             , m_oit(oit)
0139             , m_strategy(strategy)
0140         {}
0141
0142         template <typename Point, typename Box, typename SizeT>
0143         inline bool apply(Point const& item1, std::pair<Box, SizeT> const& item2)
0144         {
0145             action_selector_pl
0146                 <
0147                     PointOut, overlay_intersection
0148                 >::apply(item1,
0149                          Policy::apply(item1,
0150                                        range::at(m_multipolygon,
0151                                                  item2.second),
0152                          m_strategy),
0153                          m_oit);
0154
0155             return true;
0156         }
0157
0158     private:
0159         MultiPolygon const& m_multipolygon;
0160         OutputIterator& m_oit;
0161         Strategy const& m_strategy;
0162     };
0163
0164     template <typename Iterator, typename Box, typename SizeT, typename Strategy>
0165     static inline void fill_box_pairs(Iterator first, Iterator last,
0166                                       std::vector<std::pair<Box, SizeT> > & box_pairs,
0167                                       Strategy const& strategy)
0168     {
0169         SizeT index = 0;
0170         for (; first != last; ++first, ++index)
0171         {
0172             box_pairs.push_back(
0173                 std::make_pair(geometry::return_envelope<Box>(*first, strategy),
0174                                index));
0175         }
0176     }
0177
0178     template <typename OutputIterator, typename Strategy>
0179     static inline OutputIterator get_common_points(MultiPoint const& multipoint,
0180                                                    MultiPolygon const& multipolygon,
0181                                                    OutputIterator oit,
0182                                                    Strategy const& strategy)
0183     {
0184         item_visitor_type<OutputIterator, Strategy> item_visitor(multipolygon, oit, strategy);
0185
0186         typedef geometry::model::point
0187             <
0188                 typename geometry::coordinate_type<MultiPoint>::type,
0189                 geometry::dimension<MultiPoint>::value,
0190                 typename geometry::coordinate_system<MultiPoint>::type
0191             > point_type;
0192         typedef geometry::model::box<point_type> box_type;
0193         typedef std::pair<box_type, std::size_t> box_pair;
0194         std::vector<box_pair> box_pairs;
0195         box_pairs.reserve(boost::size(multipolygon));
0196
0197         fill_box_pairs(boost::begin(multipolygon),
0198                        boost::end(multipolygon),
0199                        box_pairs, strategy);
0200
0201         geometry::partition
0202             <
0203                 box_type
0204             >::apply(multipoint, box_pairs, item_visitor,
0205                      expand_box_point<Strategy>(strategy),
0206                      overlaps_box_point<Strategy>(strategy),
0207                      expand_box_boxpair<Strategy>(strategy),
0208                      overlaps_box_boxpair<Strategy>(strategy));
0209
0210         return oit;
0211     }
0212
0213 public:
0214     template <typename RobustPolicy, typename OutputIterator, typename Strategy>
0215     static inline OutputIterator apply(MultiPoint const& multipoint,
0216                                        MultiPolygon const& multipolygon,
0217                                        RobustPolicy const& robust_policy,
0218                                        OutputIterator oit,
0219                                        Strategy const& strategy)
0220     {
0221         typedef std::vector
0222             <
0223                 typename boost::range_value<MultiPoint>::type
0224             > point_vector_type;
0225
0226         point_vector_type common_points;
0227
0228         // compute the common points
0229         get_common_points(multipoint, multipolygon,
0230                           std::back_inserter(common_points),
0231                           strategy);
0232
0233         return multipoint_multipoint_point
0234             <
0235                 MultiPoint, point_vector_type, PointOut, OverlayType
0236             >::apply(multipoint, common_points, robust_policy, oit, strategy);
0237     }
0238 };
0239
0240
0241 }} // namespace detail::overlay
0242 #endif // DOXYGEN_NO_DISPATCH
0243
0244
0245 #ifndef DOXYGEN_NO_DISPATCH
0246 namespace detail_dispatch { namespace overlay
0247 {
0248
0249 // dispatch struct for pointlike-areal difference/intersection computation
0250 template
0251 <
0252     typename PointLike,
0253     typename Areal,
0254     typename PointOut,
0255     overlay_type OverlayType,
0256     typename Tag1,
0257     typename Tag2
0258 >
0259 struct pointlike_areal_point
0260     : not_implemented<PointLike, Areal, PointOut>
0261 {};
0262
0263
0264 template
0265 <
0266     typename Point,
0267     typename Areal,
0268     typename PointOut,
0269     overlay_type OverlayType,
0270     typename Tag2
0271 >
0272 struct pointlike_areal_point
0273     <
0274         Point, Areal, PointOut, OverlayType, point_tag, Tag2
0275     > : detail::overlay::point_single_point
0276         <
0277             Point, Areal, PointOut, OverlayType,
0278             detail::not_<detail::disjoint::reverse_covered_by>
0279         >
0280 {};
0281
0282
0283 // TODO: Consider implementing Areal-specific version
0284 //   calculating envelope first in order to reject Points without
0285 //   calling disjoint for Rings and Polygons
0286 template
0287 <
0288     typename MultiPoint,
0289     typename Areal,
0290     typename PointOut,
0291     overlay_type OverlayType,
0292     typename Tag2
0293 >
0294 struct pointlike_areal_point
0295     <
0296         MultiPoint, Areal, PointOut, OverlayType, multi_point_tag, Tag2
0297     > : detail::overlay::multipoint_single_point
0298         <
0299             MultiPoint, Areal, PointOut, OverlayType,
0300             detail::not_<detail::disjoint::reverse_covered_by>
0301         >
0302 {};
0303
0304
0305 template
0306 <
0307     typename MultiPoint,
0308     typename MultiPolygon,
0309     typename PointOut,
0310     overlay_type OverlayType
0311 >
0312 struct pointlike_areal_point
0313     <
0314         MultiPoint, MultiPolygon, PointOut, OverlayType, multi_point_tag, multi_polygon_tag
0315     > : detail::overlay::multipoint_multipolygon_point
0316         <
0317             MultiPoint, MultiPolygon, PointOut, OverlayType,
0318             detail::not_<detail::disjoint::reverse_covered_by>
0319         >
0320 {};
0321
0322
0323 }} // namespace detail_dispatch::overlay
0324 #endif // DOXYGEN_NO_DISPATCH
0325
0326
0327 }} // namespace boost::geometry
0328
0329
0330 #endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_POINTLIKE_AREAL_HPP