https://gitweb.dealii.org/ - dealii.git/blob

   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