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