boost/geometry/algorithms/detail/distance/geometry_to_segment_or_box.hpp

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