detail/overlay/pointlike_areal.hpp

0001 // Boost.Geometry (aka GGL, Generic Geometry Library)
0002
0003 // Copyright (c) 2020-2024, Oracle and/or its affiliates.
0004 // Contributed and/or modified by Vissarion Fysikopoulos, on behalf of Oracle
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         using point_type = geometry::model::point
0187             <
0188                 geometry::coordinate_type_t<MultiPoint>,
0189                 geometry::dimension<MultiPoint>::value,
0190                 geometry::coordinate_system_t<MultiPoint>
0191             >;
0192         using box_type = geometry::model::box<point_type>;
0193         using box_pair = std::pair<box_type, std::size_t>;
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 OutputIterator, typename Strategy>
0215     static inline OutputIterator apply(MultiPoint const& multipoint,
0216                                        MultiPolygon const& multipolygon,
0217                                        OutputIterator oit,
0218                                        Strategy const& strategy)
0219     {
0220         using point_vector_type = std::vector
0221             <
0222                 typename boost::range_value<MultiPoint>::type
0223             >;
0224
0225         point_vector_type common_points;
0226
0227         // compute the common points
0228         get_common_points(multipoint, multipolygon,
0229                           std::back_inserter(common_points),
0230                           strategy);
0231
0232         return multipoint_multipoint_point
0233             <
0234                 MultiPoint, point_vector_type, PointOut, OverlayType
0235             >::apply(multipoint, common_points, oit, strategy);
0236     }
0237 };
0238
0239
0240 }} // namespace detail::overlay
0241 #endif // DOXYGEN_NO_DISPATCH
0242
0243
0244 #ifndef DOXYGEN_NO_DISPATCH
0245 namespace detail_dispatch { namespace overlay
0246 {
0247
0248 // dispatch struct for pointlike-areal difference/intersection computation
0249 template
0250 <
0251     typename PointLike,
0252     typename Areal,
0253     typename PointOut,
0254     overlay_type OverlayType,
0255     typename Tag1,
0256     typename Tag2
0257 >
0258 struct pointlike_areal_point
0259     : not_implemented<PointLike, Areal, PointOut>
0260 {};
0261
0262
0263 template
0264 <
0265     typename Point,
0266     typename Areal,
0267     typename PointOut,
0268     overlay_type OverlayType,
0269     typename Tag2
0270 >
0271 struct pointlike_areal_point
0272     <
0273         Point, Areal, PointOut, OverlayType, point_tag, Tag2
0274     > : detail::overlay::point_single_point
0275         <
0276             Point, Areal, PointOut, OverlayType,
0277             detail::not_<detail::disjoint::reverse_covered_by>
0278         >
0279 {};
0280
0281
0282 // TODO: Consider implementing Areal-specific version
0283 //   calculating envelope first in order to reject Points without
0284 //   calling disjoint for Rings and Polygons
0285 template
0286 <
0287     typename MultiPoint,
0288     typename Areal,
0289     typename PointOut,
0290     overlay_type OverlayType,
0291     typename Tag2
0292 >
0293 struct pointlike_areal_point
0294     <
0295         MultiPoint, Areal, PointOut, OverlayType, multi_point_tag, Tag2
0296     > : detail::overlay::multipoint_single_point
0297         <
0298             MultiPoint, Areal, PointOut, OverlayType,
0299             detail::not_<detail::disjoint::reverse_covered_by>
0300         >
0301 {};
0302
0303
0304 template
0305 <
0306     typename MultiPoint,
0307     typename MultiPolygon,
0308     typename PointOut,
0309     overlay_type OverlayType
0310 >
0311 struct pointlike_areal_point
0312     <
0313         MultiPoint, MultiPolygon, PointOut, OverlayType, multi_point_tag, multi_polygon_tag
0314     > : detail::overlay::multipoint_multipolygon_point
0315         <
0316             MultiPoint, MultiPolygon, PointOut, OverlayType,
0317             detail::not_<detail::disjoint::reverse_covered_by>
0318         >
0319 {};
0320
0321
0322 }} // namespace detail_dispatch::overlay
0323 #endif // DOXYGEN_NO_DISPATCH
0324
0325
0326 }} // namespace boost::geometry
0327
0328
0329 #endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_POINTLIKE_AREAL_HPP