]>
Commit | Line | Data |
---|---|---|
7c673cae FG |
1 | // Boost.Geometry (aka GGL, Generic Geometry Library) |
2 | ||
1e59de90 | 3 | // Copyright (c) 2014-2021, Oracle and/or its affiliates. |
7c673cae FG |
4 | |
5 | // Contributed and/or modified by Menelaos Karavelas, on behalf of Oracle | |
92f5a8d4 | 6 | // Contributed and/or modified by Adam Wulkiewicz, on behalf of Oracle |
7c673cae FG |
7 | |
8 | // Licensed under the Boost Software License version 1.0. | |
9 | // http://www.boost.org/users/license.html | |
10 | ||
11 | #ifndef BOOST_GEOMETRY_ALGORITHMS_DETAIL_DISTANCE_GEOMETRY_TO_SEGMENT_OR_BOX_HPP | |
12 | #define BOOST_GEOMETRY_ALGORITHMS_DETAIL_DISTANCE_GEOMETRY_TO_SEGMENT_OR_BOX_HPP | |
13 | ||
14 | #include <iterator> | |
15 | ||
20effc67 TL |
16 | #include <boost/range/begin.hpp> |
17 | #include <boost/range/end.hpp> | |
7c673cae | 18 | |
7c673cae | 19 | #include <boost/geometry/algorithms/assign.hpp> |
1e59de90 TL |
20 | #include <boost/geometry/algorithms/detail/closest_feature/geometry_to_range.hpp> |
21 | #include <boost/geometry/algorithms/detail/closest_feature/point_to_range.hpp> | |
22 | #include <boost/geometry/algorithms/detail/distance/is_comparable.hpp> | |
23 | #include <boost/geometry/algorithms/detail/distance/strategy_utils.hpp> | |
24 | #include <boost/geometry/algorithms/dispatch/distance.hpp> | |
7c673cae FG |
25 | #include <boost/geometry/algorithms/intersects.hpp> |
26 | #include <boost/geometry/algorithms/num_points.hpp> | |
27 | ||
1e59de90 TL |
28 | #include <boost/geometry/core/point_type.hpp> |
29 | #include <boost/geometry/core/tag.hpp> | |
30 | #include <boost/geometry/core/tags.hpp> | |
31 | ||
7c673cae FG |
32 | #include <boost/geometry/iterators/point_iterator.hpp> |
33 | #include <boost/geometry/iterators/segment_iterator.hpp> | |
34 | ||
1e59de90 TL |
35 | #include <boost/geometry/strategies/distance.hpp> |
36 | #include <boost/geometry/strategies/tags.hpp> | |
7c673cae FG |
37 | |
38 | #include <boost/geometry/util/condition.hpp> | |
39 | ||
40 | ||
41 | namespace boost { namespace geometry | |
42 | { | |
43 | ||
44 | #ifndef DOXYGEN_NO_DETAIL | |
45 | namespace detail { namespace distance | |
46 | { | |
47 | ||
48 | ||
49 | // closure of segment or box point range | |
50 | template | |
51 | < | |
52 | typename SegmentOrBox, | |
53 | typename Tag = typename tag<SegmentOrBox>::type | |
54 | > | |
55 | struct segment_or_box_point_range_closure | |
56 | : not_implemented<SegmentOrBox> | |
57 | {}; | |
58 | ||
59 | template <typename Segment> | |
60 | struct segment_or_box_point_range_closure<Segment, segment_tag> | |
61 | { | |
62 | static const closure_selector value = closed; | |
63 | }; | |
64 | ||
65 | template <typename Box> | |
66 | struct segment_or_box_point_range_closure<Box, box_tag> | |
67 | { | |
68 | static const closure_selector value = open; | |
69 | }; | |
70 | ||
71 | ||
72 | ||
73 | template | |
74 | < | |
75 | typename Geometry, | |
76 | typename SegmentOrBox, | |
1e59de90 | 77 | typename Strategies, |
7c673cae FG |
78 | typename Tag = typename tag<Geometry>::type |
79 | > | |
80 | class geometry_to_segment_or_box | |
81 | { | |
82 | private: | |
83 | typedef typename point_type<SegmentOrBox>::type segment_or_box_point; | |
84 | ||
1e59de90 | 85 | typedef distance::strategy_t<Geometry, SegmentOrBox, Strategies> strategy_type; |
7c673cae FG |
86 | |
87 | typedef detail::closest_feature::point_to_point_range | |
88 | < | |
89 | typename point_type<Geometry>::type, | |
90 | std::vector<segment_or_box_point>, | |
1e59de90 | 91 | segment_or_box_point_range_closure<SegmentOrBox>::value |
7c673cae FG |
92 | > point_to_point_range; |
93 | ||
94 | typedef detail::closest_feature::geometry_to_range geometry_to_range; | |
95 | ||
1e59de90 | 96 | typedef distance::creturn_t<Geometry, SegmentOrBox, Strategies> comparable_return_type; |
7c673cae FG |
97 | |
98 | // assign the new minimum value for an iterator of the point range | |
99 | // of a segment or a box | |
100 | template | |
101 | < | |
102 | typename SegOrBox, | |
103 | typename SegOrBoxTag = typename tag<SegOrBox>::type | |
104 | > | |
105 | struct assign_new_min_iterator | |
106 | : not_implemented<SegOrBox> | |
107 | {}; | |
108 | ||
109 | template <typename Segment> | |
110 | struct assign_new_min_iterator<Segment, segment_tag> | |
111 | { | |
112 | template <typename Iterator> | |
113 | static inline void apply(Iterator&, Iterator) | |
114 | { | |
115 | } | |
116 | }; | |
117 | ||
118 | template <typename Box> | |
119 | struct assign_new_min_iterator<Box, box_tag> | |
120 | { | |
121 | template <typename Iterator> | |
122 | static inline void apply(Iterator& it_min, Iterator it) | |
123 | { | |
124 | it_min = it; | |
125 | } | |
126 | }; | |
127 | ||
128 | ||
129 | // assign the points of a segment or a box to a range | |
130 | template | |
131 | < | |
132 | typename SegOrBox, | |
133 | typename PointRange, | |
134 | typename SegOrBoxTag = typename tag<SegOrBox>::type | |
135 | > | |
136 | struct assign_segment_or_box_points | |
137 | {}; | |
138 | ||
139 | template <typename Segment, typename PointRange> | |
140 | struct assign_segment_or_box_points<Segment, PointRange, segment_tag> | |
141 | { | |
142 | static inline void apply(Segment const& segment, PointRange& range) | |
143 | { | |
144 | detail::assign_point_from_index<0>(segment, range[0]); | |
145 | detail::assign_point_from_index<1>(segment, range[1]); | |
146 | } | |
147 | }; | |
148 | ||
149 | template <typename Box, typename PointRange> | |
150 | struct assign_segment_or_box_points<Box, PointRange, box_tag> | |
151 | { | |
152 | static inline void apply(Box const& box, PointRange& range) | |
153 | { | |
154 | detail::assign_box_corners_oriented<true>(box, range); | |
155 | } | |
156 | }; | |
157 | ||
7c673cae | 158 | public: |
1e59de90 | 159 | typedef distance::return_t<Geometry, SegmentOrBox, Strategies> return_type; |
7c673cae FG |
160 | |
161 | static inline return_type apply(Geometry const& geometry, | |
162 | SegmentOrBox const& segment_or_box, | |
1e59de90 | 163 | Strategies const& strategies, |
7c673cae FG |
164 | bool check_intersection = true) |
165 | { | |
166 | typedef geometry::point_iterator<Geometry const> point_iterator_type; | |
167 | typedef geometry::segment_iterator | |
168 | < | |
169 | Geometry const | |
170 | > segment_iterator_type; | |
171 | ||
172 | typedef typename boost::range_const_iterator | |
173 | < | |
174 | std::vector<segment_or_box_point> | |
175 | >::type seg_or_box_const_iterator; | |
176 | ||
177 | typedef assign_new_min_iterator<SegmentOrBox> assign_new_value; | |
178 | ||
179 | ||
180 | if (check_intersection | |
1e59de90 | 181 | && geometry::intersects(geometry, segment_or_box, strategies)) |
7c673cae | 182 | { |
1e59de90 | 183 | return return_type(0); |
7c673cae FG |
184 | } |
185 | ||
1e59de90 TL |
186 | strategy_type const strategy = strategies.distance(geometry, segment_or_box); |
187 | ||
188 | auto const cstrategy = strategy::distance::services::get_comparable | |
189 | < | |
190 | strategy_type | |
191 | >::apply(strategy); | |
7c673cae FG |
192 | |
193 | // get all points of the segment or the box | |
194 | std::vector<segment_or_box_point> | |
195 | seg_or_box_points(geometry::num_points(segment_or_box)); | |
196 | ||
197 | assign_segment_or_box_points | |
198 | < | |
199 | SegmentOrBox, | |
200 | std::vector<segment_or_box_point> | |
201 | >::apply(segment_or_box, seg_or_box_points); | |
202 | ||
203 | // consider all distances of the points in the geometry to the | |
204 | // segment or box | |
205 | comparable_return_type cd_min1(0); | |
206 | point_iterator_type pit_min; | |
207 | seg_or_box_const_iterator it_min1 = boost::const_begin(seg_or_box_points); | |
208 | seg_or_box_const_iterator it_min2 = it_min1; | |
209 | ++it_min2; | |
210 | bool first = true; | |
211 | ||
212 | for (point_iterator_type pit = points_begin(geometry); | |
213 | pit != points_end(geometry); ++pit, first = false) | |
214 | { | |
215 | comparable_return_type cd; | |
216 | std::pair | |
217 | < | |
218 | seg_or_box_const_iterator, seg_or_box_const_iterator | |
219 | > it_pair | |
220 | = point_to_point_range::apply(*pit, | |
221 | boost::const_begin(seg_or_box_points), | |
222 | boost::const_end(seg_or_box_points), | |
223 | cstrategy, | |
224 | cd); | |
225 | ||
226 | if (first || cd < cd_min1) | |
227 | { | |
228 | cd_min1 = cd; | |
229 | pit_min = pit; | |
230 | assign_new_value::apply(it_min1, it_pair.first); | |
231 | assign_new_value::apply(it_min2, it_pair.second); | |
232 | } | |
233 | } | |
234 | ||
235 | // consider all distances of the points in the segment or box to the | |
236 | // segments of the geometry | |
237 | comparable_return_type cd_min2(0); | |
238 | segment_iterator_type sit_min; | |
239 | seg_or_box_const_iterator it_min; | |
240 | ||
241 | first = true; | |
242 | for (seg_or_box_const_iterator it = boost::const_begin(seg_or_box_points); | |
243 | it != boost::const_end(seg_or_box_points); ++it, first = false) | |
244 | { | |
245 | comparable_return_type cd; | |
246 | segment_iterator_type sit | |
247 | = geometry_to_range::apply(*it, | |
248 | segments_begin(geometry), | |
249 | segments_end(geometry), | |
250 | cstrategy, | |
251 | cd); | |
252 | ||
253 | if (first || cd < cd_min2) | |
254 | { | |
255 | cd_min2 = cd; | |
256 | it_min = it; | |
257 | sit_min = sit; | |
258 | } | |
259 | } | |
260 | ||
1e59de90 | 261 | if (BOOST_GEOMETRY_CONDITION(is_comparable<strategy_type>::value)) |
7c673cae FG |
262 | { |
263 | return (std::min)(cd_min1, cd_min2); | |
264 | } | |
265 | ||
266 | if (cd_min1 < cd_min2) | |
267 | { | |
268 | return strategy.apply(*pit_min, *it_min1, *it_min2); | |
269 | } | |
270 | else | |
271 | { | |
272 | return dispatch::distance | |
273 | < | |
274 | segment_or_box_point, | |
275 | typename std::iterator_traits | |
276 | < | |
277 | segment_iterator_type | |
278 | >::value_type, | |
1e59de90 TL |
279 | Strategies |
280 | >::apply(*it_min, *sit_min, strategies); | |
7c673cae FG |
281 | } |
282 | } | |
283 | ||
284 | ||
1e59de90 TL |
285 | static inline return_type apply(SegmentOrBox const& segment_or_box, Geometry const& geometry, |
286 | Strategies const& strategies, bool check_intersection = true) | |
7c673cae | 287 | { |
1e59de90 | 288 | return apply(geometry, segment_or_box, strategies, check_intersection); |
7c673cae FG |
289 | } |
290 | }; | |
291 | ||
292 | ||
293 | ||
1e59de90 | 294 | template <typename MultiPoint, typename SegmentOrBox, typename Strategies> |
7c673cae FG |
295 | class geometry_to_segment_or_box |
296 | < | |
1e59de90 | 297 | MultiPoint, SegmentOrBox, Strategies, multi_point_tag |
7c673cae FG |
298 | > |
299 | { | |
300 | private: | |
301 | typedef detail::closest_feature::geometry_to_range base_type; | |
302 | ||
303 | typedef typename boost::range_iterator | |
304 | < | |
305 | MultiPoint const | |
306 | >::type iterator_type; | |
307 | ||
308 | typedef detail::closest_feature::geometry_to_range geometry_to_range; | |
309 | ||
1e59de90 TL |
310 | typedef distance::strategy_t<MultiPoint, SegmentOrBox, Strategies> strategy_type; |
311 | ||
7c673cae | 312 | public: |
1e59de90 | 313 | typedef distance::return_t<MultiPoint, SegmentOrBox, Strategies> return_type; |
7c673cae FG |
314 | |
315 | static inline return_type apply(MultiPoint const& multipoint, | |
316 | SegmentOrBox const& segment_or_box, | |
1e59de90 | 317 | Strategies const& strategies) |
7c673cae | 318 | { |
1e59de90 | 319 | distance::creturn_t<MultiPoint, SegmentOrBox, Strategies> cd_min; |
7c673cae FG |
320 | |
321 | iterator_type it_min | |
322 | = geometry_to_range::apply(segment_or_box, | |
323 | boost::begin(multipoint), | |
324 | boost::end(multipoint), | |
1e59de90 | 325 | strategy::distance::services::get_comparable |
7c673cae | 326 | < |
1e59de90 TL |
327 | strategy_type |
328 | >::apply(strategies.distance(multipoint, segment_or_box)), | |
7c673cae FG |
329 | cd_min); |
330 | ||
331 | return | |
1e59de90 | 332 | is_comparable<strategy_type>::value |
7c673cae FG |
333 | ? |
334 | cd_min | |
335 | : | |
336 | dispatch::distance | |
337 | < | |
338 | typename point_type<MultiPoint>::type, | |
339 | SegmentOrBox, | |
1e59de90 TL |
340 | Strategies |
341 | >::apply(*it_min, segment_or_box, strategies); | |
7c673cae FG |
342 | } |
343 | }; | |
344 | ||
345 | ||
346 | ||
347 | }} // namespace detail::distance | |
348 | #endif // DOXYGEN_NO_DETAIL | |
349 | ||
350 | ||
351 | ||
352 | #ifndef DOXYGEN_NO_DISPATCH | |
353 | namespace dispatch | |
354 | { | |
355 | ||
356 | ||
357 | template <typename Linear, typename Segment, typename Strategy> | |
358 | struct distance | |
359 | < | |
360 | Linear, Segment, Strategy, linear_tag, segment_tag, | |
361 | strategy_tag_distance_point_segment, false | |
362 | > : detail::distance::geometry_to_segment_or_box<Linear, Segment, Strategy> | |
363 | {}; | |
364 | ||
365 | ||
366 | template <typename Areal, typename Segment, typename Strategy> | |
367 | struct distance | |
368 | < | |
369 | Areal, Segment, Strategy, areal_tag, segment_tag, | |
370 | strategy_tag_distance_point_segment, false | |
371 | > : detail::distance::geometry_to_segment_or_box<Areal, Segment, Strategy> | |
372 | {}; | |
373 | ||
374 | ||
375 | template <typename Segment, typename Areal, typename Strategy> | |
376 | struct distance | |
377 | < | |
378 | Segment, Areal, Strategy, segment_tag, areal_tag, | |
379 | strategy_tag_distance_point_segment, false | |
380 | > : detail::distance::geometry_to_segment_or_box<Areal, Segment, Strategy> | |
381 | {}; | |
382 | ||
383 | ||
384 | template <typename Linear, typename Box, typename Strategy> | |
385 | struct distance | |
386 | < | |
387 | Linear, Box, Strategy, linear_tag, box_tag, | |
388 | strategy_tag_distance_point_segment, false | |
389 | > : detail::distance::geometry_to_segment_or_box | |
390 | < | |
391 | Linear, Box, Strategy | |
392 | > | |
393 | {}; | |
394 | ||
395 | ||
396 | template <typename Areal, typename Box, typename Strategy> | |
397 | struct distance | |
398 | < | |
399 | Areal, Box, Strategy, areal_tag, box_tag, | |
400 | strategy_tag_distance_point_segment, false | |
401 | > : detail::distance::geometry_to_segment_or_box<Areal, Box, Strategy> | |
402 | {}; | |
403 | ||
404 | ||
405 | template <typename MultiPoint, typename Segment, typename Strategy> | |
406 | struct distance | |
407 | < | |
408 | MultiPoint, Segment, Strategy, | |
409 | multi_point_tag, segment_tag, | |
410 | strategy_tag_distance_point_segment, false | |
411 | > : detail::distance::geometry_to_segment_or_box | |
412 | < | |
413 | MultiPoint, Segment, Strategy | |
414 | > | |
415 | {}; | |
416 | ||
417 | ||
418 | template <typename MultiPoint, typename Box, typename Strategy> | |
419 | struct distance | |
420 | < | |
421 | MultiPoint, Box, Strategy, | |
422 | multi_point_tag, box_tag, | |
423 | strategy_tag_distance_point_box, false | |
424 | > : detail::distance::geometry_to_segment_or_box | |
425 | < | |
426 | MultiPoint, Box, Strategy | |
427 | > | |
428 | {}; | |
429 | ||
430 | ||
431 | } // namespace dispatch | |
432 | #endif // DOXYGEN_NO_DISPATCH | |
433 | ||
434 | ||
435 | }} // namespace boost::geometry | |
436 | ||
437 | ||
438 | #endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_DISTANCE_GEOMETRY_TO_SEGMENT_OR_BOX_HPP |