• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
1 // Boost.Geometry (aka GGL, Generic Geometry Library)
2 
3 // Copyright (c) 2020, Oracle and/or its affiliates.
4 
5 // Contributed and/or modified by Adam Wulkiewicz, on behalf of Oracle
6 
7 // Licensed under the Boost Software License version 1.0.
8 // http://www.boost.org/users/license.html
9 
10 
11 #ifndef BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_POINTLIKE_AREAL_HPP
12 #define BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_POINTLIKE_AREAL_HPP
13 
14 #include <vector>
15 
16 #include <boost/range.hpp>
17 
18 #include <boost/geometry/core/tags.hpp>
19 
20 #include <boost/geometry/geometries/box.hpp>
21 #include <boost/geometry/geometries/point.hpp>
22 
23 #include <boost/geometry/algorithms/disjoint.hpp>
24 #include <boost/geometry/algorithms/envelope.hpp>
25 #include <boost/geometry/algorithms/expand.hpp>
26 #include <boost/geometry/algorithms/not_implemented.hpp>
27 
28 #include <boost/geometry/algorithms/detail/not.hpp>
29 #include <boost/geometry/algorithms/detail/partition.hpp>
30 #include <boost/geometry/algorithms/detail/disjoint/point_geometry.hpp>
31 #include <boost/geometry/algorithms/detail/equals/point_point.hpp>
32 #include <boost/geometry/algorithms/detail/overlay/overlay_type.hpp>
33 
34 #include <boost/geometry/algorithms/detail/overlay/pointlike_linear.hpp>
35 
36 
37 namespace boost { namespace geometry
38 {
39 
40 
41 #ifndef DOXYGEN_NO_DETAIL
42 namespace detail { namespace overlay
43 {
44 
45 
46 // difference/intersection of multipoint-multipolygon
47 template
48 <
49     typename MultiPoint,
50     typename MultiPolygon,
51     typename PointOut,
52     overlay_type OverlayType,
53     typename Policy
54 >
55 class multipoint_multipolygon_point
56 {
57 private:
58     template <typename ExpandPointStrategy>
59     struct expand_box_point
60     {
61         template <typename Box, typename Point>
applyboost::geometry::detail::overlay::multipoint_multipolygon_point::expand_box_point62         static inline void apply(Box& total, Point const& point)
63         {
64             geometry::expand(total, point, ExpandPointStrategy());
65         }
66     };
67 
68     template <typename ExpandBoxStrategy>
69     struct expand_box_boxpair
70     {
71         template <typename Box1, typename Box2, typename SizeT>
applyboost::geometry::detail::overlay::multipoint_multipolygon_point::expand_box_boxpair72         static inline void apply(Box1& total, std::pair<Box2, SizeT> const& box_pair)
73         {
74             geometry::expand(total, box_pair.first, ExpandBoxStrategy());
75         }
76     };
77 
78     template <typename DisjointPointBoxStrategy>
79     struct overlaps_box_point
80     {
81         template <typename Box, typename Point>
applyboost::geometry::detail::overlay::multipoint_multipolygon_point::overlaps_box_point82         static inline bool apply(Box const& box, Point const& point)
83         {
84             return ! geometry::disjoint(point, box, DisjointPointBoxStrategy());
85         }
86     };
87 
88     template <typename DisjointBoxBoxStrategy>
89     struct overlaps_box_boxpair
90     {
91         template <typename Box1, typename Box2, typename SizeT>
applyboost::geometry::detail::overlay::multipoint_multipolygon_point::overlaps_box_boxpair92         static inline bool apply(Box1 const& box, std::pair<Box2, SizeT> const& box_pair)
93         {
94             return ! geometry::disjoint(box, box_pair.first, DisjointBoxBoxStrategy());
95         }
96     };
97 
98     template <typename OutputIterator, typename Strategy>
99     class item_visitor_type
100     {
101     public:
item_visitor_type(MultiPolygon const & multipolygon,OutputIterator & oit,Strategy const & strategy)102         item_visitor_type(MultiPolygon const& multipolygon,
103                           OutputIterator& oit,
104                           Strategy const& strategy)
105             : m_multipolygon(multipolygon)
106             , m_oit(oit)
107             , m_strategy(strategy)
108         {}
109 
110         template <typename Point, typename Box, typename SizeT>
apply(Point const & item1,std::pair<Box,SizeT> const & item2)111         inline bool apply(Point const& item1, std::pair<Box, SizeT> const& item2)
112         {
113             action_selector_pl
114                 <
115                     PointOut, overlay_intersection
116                 >::apply(item1,
117                          Policy::apply(item1,
118                                        range::at(m_multipolygon,
119                                                  item2.second),
120                          m_strategy),
121                          m_oit);
122 
123             return true;
124         }
125 
126     private:
127         MultiPolygon const& m_multipolygon;
128         OutputIterator& m_oit;
129         Strategy const& m_strategy;
130     };
131 
132     template <typename Iterator, typename Box, typename SizeT, typename EnvelopeStrategy>
fill_box_pairs(Iterator first,Iterator last,std::vector<std::pair<Box,SizeT>> & box_pairs,EnvelopeStrategy const & strategy)133     static inline void fill_box_pairs(Iterator first, Iterator last,
134                                       std::vector<std::pair<Box, SizeT> > & box_pairs,
135                                       EnvelopeStrategy const& strategy)
136     {
137         SizeT index = 0;
138         for (; first != last; ++first, ++index)
139         {
140             box_pairs.push_back(
141                 std::make_pair(geometry::return_envelope<Box>(*first, strategy),
142                                index));
143         }
144     }
145 
146     template <typename OutputIterator, typename Strategy>
get_common_points(MultiPoint const & multipoint,MultiPolygon const & multipolygon,OutputIterator oit,Strategy const & strategy)147     static inline OutputIterator get_common_points(MultiPoint const& multipoint,
148                                                    MultiPolygon const& multipolygon,
149                                                    OutputIterator oit,
150                                                    Strategy const& strategy)
151     {
152         item_visitor_type<OutputIterator, Strategy> item_visitor(multipolygon, oit, strategy);
153 
154         typedef geometry::model::point
155             <
156                 typename geometry::coordinate_type<MultiPoint>::type,
157                 geometry::dimension<MultiPoint>::value,
158                 typename geometry::coordinate_system<MultiPoint>::type
159             > point_type;
160         typedef geometry::model::box<point_type> box_type;
161         typedef std::pair<box_type, std::size_t> box_pair;
162         std::vector<box_pair> box_pairs;
163         box_pairs.reserve(boost::size(multipolygon));
164 
165         fill_box_pairs(boost::begin(multipolygon),
166                        boost::end(multipolygon),
167                        box_pairs,
168                        strategy.get_envelope_strategy());
169 
170         typedef typename Strategy::envelope_strategy_type::box_expand_strategy_type expand_box_strategy_type;
171         typedef typename Strategy::disjoint_box_box_strategy_type disjoint_box_box_strategy_type;
172         typedef typename Strategy::disjoint_point_box_strategy_type disjoint_point_box_strategy_type;
173         typedef typename Strategy::expand_point_strategy_type expand_point_strategy_type;
174 
175         geometry::partition
176             <
177                 box_type
178             >::apply(multipoint, box_pairs, item_visitor,
179                      expand_box_point<expand_point_strategy_type>(),
180                      overlaps_box_point<disjoint_point_box_strategy_type>(),
181                      expand_box_boxpair<expand_box_strategy_type>(),
182                      overlaps_box_boxpair<disjoint_box_box_strategy_type>());
183 
184         return oit;
185     }
186 
187 public:
188     template <typename RobustPolicy, typename OutputIterator, typename Strategy>
apply(MultiPoint const & multipoint,MultiPolygon const & multipolygon,RobustPolicy const & robust_policy,OutputIterator oit,Strategy const & strategy)189     static inline OutputIterator apply(MultiPoint const& multipoint,
190                                        MultiPolygon const& multipolygon,
191                                        RobustPolicy const& robust_policy,
192                                        OutputIterator oit,
193                                        Strategy const& strategy)
194     {
195         typedef std::vector
196             <
197                 typename boost::range_value<MultiPoint>::type
198             > point_vector_type;
199 
200         point_vector_type common_points;
201 
202         // compute the common points
203         get_common_points(multipoint, multipolygon,
204                           std::back_inserter(common_points),
205                           strategy);
206 
207         return multipoint_multipoint_point
208             <
209                 MultiPoint, point_vector_type, PointOut, OverlayType
210             >::apply(multipoint, common_points, robust_policy, oit, strategy);
211     }
212 };
213 
214 
215 }} // namespace detail::overlay
216 #endif // DOXYGEN_NO_DISPATCH
217 
218 
219 #ifndef DOXYGEN_NO_DISPATCH
220 namespace detail_dispatch { namespace overlay
221 {
222 
223 // dispatch struct for pointlike-areal difference/intersection computation
224 template
225 <
226     typename PointLike,
227     typename Areal,
228     typename PointOut,
229     overlay_type OverlayType,
230     typename Tag1,
231     typename Tag2
232 >
233 struct pointlike_areal_point
234     : not_implemented<PointLike, Areal, PointOut>
235 {};
236 
237 
238 template
239 <
240     typename Point,
241     typename Areal,
242     typename PointOut,
243     overlay_type OverlayType,
244     typename Tag2
245 >
246 struct pointlike_areal_point
247     <
248         Point, Areal, PointOut, OverlayType, point_tag, Tag2
249     > : detail::overlay::point_single_point
250         <
251             Point, Areal, PointOut, OverlayType,
252             detail::not_<detail::disjoint::reverse_covered_by>
253         >
254 {};
255 
256 
257 // TODO: Consider implementing Areal-specific version
258 //   calculating envelope first in order to reject Points without
259 //   calling disjoint for Rings and Polygons
260 template
261 <
262     typename MultiPoint,
263     typename Areal,
264     typename PointOut,
265     overlay_type OverlayType,
266     typename Tag2
267 >
268 struct pointlike_areal_point
269     <
270         MultiPoint, Areal, PointOut, OverlayType, multi_point_tag, Tag2
271     > : detail::overlay::multipoint_single_point
272         <
273             MultiPoint, Areal, PointOut, OverlayType,
274             detail::not_<detail::disjoint::reverse_covered_by>
275         >
276 {};
277 
278 
279 template
280 <
281     typename MultiPoint,
282     typename MultiPolygon,
283     typename PointOut,
284     overlay_type OverlayType
285 >
286 struct pointlike_areal_point
287     <
288         MultiPoint, MultiPolygon, PointOut, OverlayType, multi_point_tag, multi_polygon_tag
289     > : detail::overlay::multipoint_multipolygon_point
290         <
291             MultiPoint, MultiPolygon, PointOut, OverlayType,
292             detail::not_<detail::disjoint::reverse_covered_by>
293         >
294 {};
295 
296 
297 }} // namespace detail_dispatch::overlay
298 #endif // DOXYGEN_NO_DISPATCH
299 
300 
301 }} // namespace boost::geometry
302 
303 
304 #endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_POINTLIKE_AREAL_HPP
305