]>
Commit | Line | Data |
---|---|---|
b32b8144 FG |
1 | // Boost.Geometry |
2 | ||
20effc67 | 3 | // Copyright (c) 2017-2020, Oracle and/or its affiliates. |
b32b8144 FG |
4 | // Contributed and/or modified by Adam Wulkiewicz, on behalf of Oracle |
5 | ||
6 | // Use, modification and distribution is subject to the Boost Software License, | |
7 | // Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at | |
8 | // http://www.boost.org/LICENSE_1_0.txt) | |
9 | ||
10 | #ifndef BOOST_GEOMETRY_ALGORITHMS_DETAIL_WITHIN_MULTI_POINT_HPP | |
11 | #define BOOST_GEOMETRY_ALGORITHMS_DETAIL_WITHIN_MULTI_POINT_HPP | |
12 | ||
13 | ||
14 | #include <algorithm> | |
15 | #include <vector> | |
16 | ||
20effc67 TL |
17 | #include <boost/range/begin.hpp> |
18 | #include <boost/range/end.hpp> | |
19 | #include <boost/range/size.hpp> | |
20 | #include <boost/range/value_type.hpp> | |
b32b8144 FG |
21 | |
22 | #include <boost/geometry/algorithms/detail/disjoint/box_box.hpp> | |
23 | #include <boost/geometry/algorithms/detail/disjoint/point_box.hpp> | |
24 | #include <boost/geometry/algorithms/detail/expand_by_epsilon.hpp> | |
25 | #include <boost/geometry/algorithms/detail/within/point_in_geometry.hpp> | |
26 | #include <boost/geometry/algorithms/envelope.hpp> | |
27 | #include <boost/geometry/algorithms/detail/partition.hpp> | |
28 | #include <boost/geometry/core/tag.hpp> | |
29 | #include <boost/geometry/core/tag_cast.hpp> | |
30 | #include <boost/geometry/core/tags.hpp> | |
31 | ||
32 | #include <boost/geometry/geometries/box.hpp> | |
33 | ||
34 | #include <boost/geometry/index/rtree.hpp> | |
35 | ||
36 | #include <boost/geometry/policies/compare.hpp> | |
37 | ||
38 | #include <boost/geometry/strategies/covered_by.hpp> | |
39 | #include <boost/geometry/strategies/disjoint.hpp> | |
40 | ||
20effc67 TL |
41 | #include <boost/geometry/util/type_traits.hpp> |
42 | ||
b32b8144 FG |
43 | |
44 | namespace boost { namespace geometry { | |
45 | ||
46 | #ifndef DOXYGEN_NO_DETAIL | |
47 | namespace detail { namespace within { | |
48 | ||
49 | struct multi_point_point | |
50 | { | |
51 | template <typename MultiPoint, typename Point, typename Strategy> | |
52 | static inline bool apply(MultiPoint const& multi_point, | |
53 | Point const& point, | |
54 | Strategy const& strategy) | |
55 | { | |
1e59de90 TL |
56 | auto const s = strategy.relate(multi_point, point); |
57 | ||
b32b8144 FG |
58 | typedef typename boost::range_const_iterator<MultiPoint>::type iterator; |
59 | for ( iterator it = boost::begin(multi_point) ; it != boost::end(multi_point) ; ++it ) | |
60 | { | |
1e59de90 | 61 | if (! s.apply(*it, point)) |
b32b8144 FG |
62 | { |
63 | return false; | |
64 | } | |
65 | } | |
66 | ||
67 | // all points of MultiPoint inside Point | |
68 | return true; | |
69 | } | |
70 | }; | |
71 | ||
72 | // NOTE: currently the strategy is ignored, math::equals() is used inside geometry::less<> | |
73 | struct multi_point_multi_point | |
74 | { | |
75 | template <typename MultiPoint1, typename MultiPoint2, typename Strategy> | |
76 | static inline bool apply(MultiPoint1 const& multi_point1, | |
77 | MultiPoint2 const& multi_point2, | |
78 | Strategy const& /*strategy*/) | |
79 | { | |
80 | typedef typename boost::range_value<MultiPoint2>::type point2_type; | |
92f5a8d4 TL |
81 | typedef typename Strategy::cs_tag cs_tag; |
82 | typedef geometry::less<void, -1, cs_tag> less_type; | |
b32b8144 | 83 | |
92f5a8d4 | 84 | less_type const less = less_type(); |
b32b8144 FG |
85 | |
86 | std::vector<point2_type> points2(boost::begin(multi_point2), boost::end(multi_point2)); | |
87 | std::sort(points2.begin(), points2.end(), less); | |
88 | ||
89 | bool result = false; | |
90 | ||
91 | typedef typename boost::range_const_iterator<MultiPoint1>::type iterator; | |
92 | for ( iterator it = boost::begin(multi_point1) ; it != boost::end(multi_point1) ; ++it ) | |
93 | { | |
94 | if (! std::binary_search(points2.begin(), points2.end(), *it, less)) | |
95 | { | |
96 | return false; | |
97 | } | |
98 | else | |
99 | { | |
100 | result = true; | |
101 | } | |
102 | } | |
103 | ||
104 | return result; | |
105 | } | |
106 | }; | |
107 | ||
108 | ||
109 | // TODO: the complexity could be lesser | |
110 | // the second geometry could be "prepared"/sorted | |
111 | // For Linear geometries partition could be used | |
112 | // For Areal geometries point_in_geometry() would have to call the winding | |
113 | // strategy differently, currently it linearly calls the strategy for each | |
114 | // segment. So the segments would have to be sorted in a way consistent with | |
115 | // the strategy and then the strategy called only for the segments in range. | |
116 | template <bool Within> | |
117 | struct multi_point_single_geometry | |
118 | { | |
119 | template <typename MultiPoint, typename LinearOrAreal, typename Strategy> | |
120 | static inline bool apply(MultiPoint const& multi_point, | |
121 | LinearOrAreal const& linear_or_areal, | |
122 | Strategy const& strategy) | |
123 | { | |
92f5a8d4 | 124 | //typedef typename boost::range_value<MultiPoint>::type point1_type; |
b32b8144 FG |
125 | typedef typename point_type<LinearOrAreal>::type point2_type; |
126 | typedef model::box<point2_type> box2_type; | |
127 | ||
128 | // Create envelope of geometry | |
129 | box2_type box; | |
1e59de90 | 130 | geometry::envelope(linear_or_areal, box, strategy); |
b32b8144 FG |
131 | geometry::detail::expand_by_epsilon(box); |
132 | ||
b32b8144 FG |
133 | // Test each Point with envelope and then geometry if needed |
134 | // If in the exterior, break | |
135 | bool result = false; | |
136 | ||
137 | typedef typename boost::range_const_iterator<MultiPoint>::type iterator; | |
138 | for ( iterator it = boost::begin(multi_point) ; it != boost::end(multi_point) ; ++it ) | |
139 | { | |
1e59de90 | 140 | typedef decltype(strategy.covered_by(*it, box)) point_in_box_type; |
b32b8144 | 141 | |
1e59de90 TL |
142 | int in_val = 0; |
143 | ||
b32b8144 FG |
144 | // exterior of box and of geometry |
145 | if (! point_in_box_type::apply(*it, box) | |
146 | || (in_val = point_in_geometry(*it, linear_or_areal, strategy)) < 0) | |
147 | { | |
148 | result = false; | |
149 | break; | |
150 | } | |
151 | ||
152 | // interior : interior/boundary | |
153 | if (Within ? in_val > 0 : in_val >= 0) | |
154 | { | |
155 | result = true; | |
156 | } | |
157 | } | |
158 | ||
159 | return result; | |
160 | } | |
161 | }; | |
162 | ||
163 | ||
164 | // TODO: same here, probably the complexity could be lesser | |
165 | template <bool Within> | |
166 | struct multi_point_multi_geometry | |
167 | { | |
168 | template <typename MultiPoint, typename LinearOrAreal, typename Strategy> | |
169 | static inline bool apply(MultiPoint const& multi_point, | |
170 | LinearOrAreal const& linear_or_areal, | |
171 | Strategy const& strategy) | |
172 | { | |
173 | typedef typename point_type<LinearOrAreal>::type point2_type; | |
174 | typedef model::box<point2_type> box2_type; | |
20effc67 | 175 | static const bool is_linear = util::is_linear<LinearOrAreal>::value; |
b32b8144 | 176 | |
b32b8144 FG |
177 | // TODO: box pairs could be constructed on the fly, inside the rtree |
178 | ||
179 | // Prepare range of envelopes and ids | |
180 | std::size_t count2 = boost::size(linear_or_areal); | |
181 | typedef std::pair<box2_type, std::size_t> box_pair_type; | |
182 | typedef std::vector<box_pair_type> box_pair_vector; | |
183 | box_pair_vector boxes(count2); | |
184 | for (std::size_t i = 0 ; i < count2 ; ++i) | |
185 | { | |
1e59de90 | 186 | geometry::envelope(linear_or_areal, boxes[i].first, strategy); |
b32b8144 FG |
187 | geometry::detail::expand_by_epsilon(boxes[i].first); |
188 | boxes[i].second = i; | |
189 | } | |
190 | ||
191 | // Create R-tree | |
1e59de90 | 192 | typedef index::parameters<index::rstar<4>, Strategy> index_parameters_type; |
92f5a8d4 TL |
193 | index::rtree<box_pair_type, index_parameters_type> |
194 | rtree(boxes.begin(), boxes.end(), | |
1e59de90 | 195 | index_parameters_type(index::rstar<4>(), strategy)); |
b32b8144 FG |
196 | |
197 | // For each point find overlapping envelopes and test corresponding single geometries | |
198 | // If a point is in the exterior break | |
199 | bool result = false; | |
200 | ||
201 | typedef typename boost::range_const_iterator<MultiPoint>::type iterator; | |
202 | for ( iterator it = boost::begin(multi_point) ; it != boost::end(multi_point) ; ++it ) | |
203 | { | |
204 | // TODO: investigate the possibility of using satisfies | |
205 | // TODO: investigate the possibility of using iterative queries (optimization below) | |
206 | box_pair_vector inters_boxes; | |
207 | rtree.query(index::intersects(*it), std::back_inserter(inters_boxes)); | |
208 | ||
209 | bool found_interior = false; | |
210 | bool found_boundary = false; | |
211 | int boundaries = 0; | |
212 | ||
92f5a8d4 TL |
213 | typedef typename box_pair_vector::const_iterator box_iterator; |
214 | for (box_iterator box_it = inters_boxes.begin() ; | |
215 | box_it != inters_boxes.end() ; ++box_it ) | |
b32b8144 | 216 | { |
92f5a8d4 TL |
217 | int const in_val = point_in_geometry(*it, |
218 | range::at(linear_or_areal, box_it->second), strategy); | |
b32b8144 FG |
219 | |
220 | if (in_val > 0) | |
92f5a8d4 | 221 | { |
b32b8144 | 222 | found_interior = true; |
92f5a8d4 | 223 | } |
b32b8144 | 224 | else if (in_val == 0) |
92f5a8d4 | 225 | { |
b32b8144 | 226 | ++boundaries; |
92f5a8d4 | 227 | } |
b32b8144 FG |
228 | |
229 | // If the result was set previously (interior or | |
230 | // interior/boundary found) the only thing that needs to be | |
231 | // done for other points is to make sure they're not | |
232 | // overlapping the exterior no need to analyse boundaries. | |
233 | if (result && in_val >= 0) | |
234 | { | |
235 | break; | |
236 | } | |
237 | } | |
238 | ||
92f5a8d4 | 239 | if (boundaries > 0) |
b32b8144 FG |
240 | { |
241 | if (is_linear && boundaries % 2 == 0) | |
92f5a8d4 | 242 | { |
b32b8144 | 243 | found_interior = true; |
92f5a8d4 | 244 | } |
b32b8144 | 245 | else |
92f5a8d4 | 246 | { |
b32b8144 | 247 | found_boundary = true; |
92f5a8d4 | 248 | } |
b32b8144 FG |
249 | } |
250 | ||
251 | // exterior | |
252 | if (! found_interior && ! found_boundary) | |
253 | { | |
254 | result = false; | |
255 | break; | |
256 | } | |
257 | ||
258 | // interior : interior/boundary | |
259 | if (Within ? found_interior : (found_interior || found_boundary)) | |
260 | { | |
261 | result = true; | |
262 | } | |
263 | } | |
264 | ||
265 | return result; | |
266 | } | |
267 | }; | |
268 | ||
269 | }} // namespace detail::within | |
270 | #endif // DOXYGEN_NO_DETAIL | |
271 | ||
272 | }} // namespace boost::geometry | |
273 | ||
274 | ||
275 | #endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_WITHIN_MULTI_POINT_HPP |