| // Boost.Geometry (aka GGL, Generic Geometry Library) |
| |
| // Copyright (c) 2014, Oracle and/or its affiliates. |
| |
| // Contributed and/or modified by Menelaos Karavelas, on behalf of Oracle |
| |
| // Licensed under the Boost Software License version 1.0. |
| // http://www.boost.org/users/license.html |
| |
| #ifndef BOOST_GEOMETRY_ALGORITHMS_DETAIL_DISTANCE_GEOMETRY_TO_SEGMENT_OR_BOX_HPP |
| #define BOOST_GEOMETRY_ALGORITHMS_DETAIL_DISTANCE_GEOMETRY_TO_SEGMENT_OR_BOX_HPP |
| |
| #include <iterator> |
| |
| #include <boost/range.hpp> |
| |
| #include <boost/geometry/core/point_type.hpp> |
| #include <boost/geometry/core/tag.hpp> |
| #include <boost/geometry/core/tags.hpp> |
| |
| #include <boost/geometry/strategies/distance.hpp> |
| #include <boost/geometry/strategies/tags.hpp> |
| |
| #include <boost/geometry/algorithms/assign.hpp> |
| #include <boost/geometry/algorithms/intersects.hpp> |
| #include <boost/geometry/algorithms/num_points.hpp> |
| |
| #include <boost/geometry/iterators/point_iterator.hpp> |
| #include <boost/geometry/iterators/segment_iterator.hpp> |
| |
| #include <boost/geometry/algorithms/dispatch/distance.hpp> |
| |
| #include <boost/geometry/algorithms/detail/closest_feature/geometry_to_range.hpp> |
| #include <boost/geometry/algorithms/detail/closest_feature/point_to_range.hpp> |
| |
| #include <boost/geometry/algorithms/detail/distance/is_comparable.hpp> |
| |
| #include <boost/geometry/util/condition.hpp> |
| |
| |
| namespace boost { namespace geometry |
| { |
| |
| #ifndef DOXYGEN_NO_DETAIL |
| namespace detail { namespace distance |
| { |
| |
| |
| // closure of segment or box point range |
| template |
| < |
| typename SegmentOrBox, |
| typename Tag = typename tag<SegmentOrBox>::type |
| > |
| struct segment_or_box_point_range_closure |
| : not_implemented<SegmentOrBox> |
| {}; |
| |
| template <typename Segment> |
| struct segment_or_box_point_range_closure<Segment, segment_tag> |
| { |
| static const closure_selector value = closed; |
| }; |
| |
| template <typename Box> |
| struct segment_or_box_point_range_closure<Box, box_tag> |
| { |
| static const closure_selector value = open; |
| }; |
| |
| |
| |
| template |
| < |
| typename Geometry, |
| typename SegmentOrBox, |
| typename Strategy, |
| typename Tag = typename tag<Geometry>::type |
| > |
| class geometry_to_segment_or_box |
| { |
| private: |
| typedef typename point_type<SegmentOrBox>::type segment_or_box_point; |
| |
| typedef typename strategy::distance::services::comparable_type |
| < |
| Strategy |
| >::type comparable_strategy; |
| |
| typedef detail::closest_feature::point_to_point_range |
| < |
| typename point_type<Geometry>::type, |
| std::vector<segment_or_box_point>, |
| segment_or_box_point_range_closure<SegmentOrBox>::value, |
| comparable_strategy |
| > point_to_point_range; |
| |
| typedef detail::closest_feature::geometry_to_range geometry_to_range; |
| |
| typedef typename strategy::distance::services::return_type |
| < |
| comparable_strategy, |
| typename point_type<Geometry>::type, |
| segment_or_box_point |
| >::type comparable_return_type; |
| |
| |
| // assign the new minimum value for an iterator of the point range |
| // of a segment or a box |
| template |
| < |
| typename SegOrBox, |
| typename SegOrBoxTag = typename tag<SegOrBox>::type |
| > |
| struct assign_new_min_iterator |
| : not_implemented<SegOrBox> |
| {}; |
| |
| template <typename Segment> |
| struct assign_new_min_iterator<Segment, segment_tag> |
| { |
| template <typename Iterator> |
| static inline void apply(Iterator&, Iterator) |
| { |
| } |
| }; |
| |
| template <typename Box> |
| struct assign_new_min_iterator<Box, box_tag> |
| { |
| template <typename Iterator> |
| static inline void apply(Iterator& it_min, Iterator it) |
| { |
| it_min = it; |
| } |
| }; |
| |
| |
| // assign the points of a segment or a box to a range |
| template |
| < |
| typename SegOrBox, |
| typename PointRange, |
| typename SegOrBoxTag = typename tag<SegOrBox>::type |
| > |
| struct assign_segment_or_box_points |
| {}; |
| |
| template <typename Segment, typename PointRange> |
| struct assign_segment_or_box_points<Segment, PointRange, segment_tag> |
| { |
| static inline void apply(Segment const& segment, PointRange& range) |
| { |
| detail::assign_point_from_index<0>(segment, range[0]); |
| detail::assign_point_from_index<1>(segment, range[1]); |
| } |
| }; |
| |
| template <typename Box, typename PointRange> |
| struct assign_segment_or_box_points<Box, PointRange, box_tag> |
| { |
| static inline void apply(Box const& box, PointRange& range) |
| { |
| detail::assign_box_corners_oriented<true>(box, range); |
| } |
| }; |
| |
| |
| public: |
| typedef typename strategy::distance::services::return_type |
| < |
| Strategy, |
| typename point_type<Geometry>::type, |
| segment_or_box_point |
| >::type return_type; |
| |
| static inline return_type apply(Geometry const& geometry, |
| SegmentOrBox const& segment_or_box, |
| Strategy const& strategy, |
| bool check_intersection = true) |
| { |
| typedef geometry::point_iterator<Geometry const> point_iterator_type; |
| typedef geometry::segment_iterator |
| < |
| Geometry const |
| > segment_iterator_type; |
| |
| typedef typename std::vector |
| < |
| segment_or_box_point |
| >::const_iterator seg_or_box_iterator_type; |
| |
| typedef assign_new_min_iterator<SegmentOrBox> assign_new_value; |
| |
| |
| if (check_intersection |
| && geometry::intersects(geometry, segment_or_box)) |
| { |
| return 0; |
| } |
| |
| comparable_strategy cstrategy = |
| strategy::distance::services::get_comparable |
| < |
| Strategy |
| >::apply(strategy); |
| |
| // get all points of the segment or the box |
| std::vector<segment_or_box_point> |
| seg_or_box_points(geometry::num_points(segment_or_box)); |
| |
| assign_segment_or_box_points |
| < |
| SegmentOrBox, |
| std::vector<segment_or_box_point> |
| >::apply(segment_or_box, seg_or_box_points); |
| |
| // consider all distances of the points in the geometry to the |
| // segment or box |
| comparable_return_type cd_min1(0); |
| point_iterator_type pit_min; |
| seg_or_box_iterator_type it_min1 = seg_or_box_points.begin(); |
| seg_or_box_iterator_type it_min2 = ++seg_or_box_points.begin(); |
| bool first = true; |
| |
| for (point_iterator_type pit = points_begin(geometry); |
| pit != points_end(geometry); ++pit, first = false) |
| { |
| comparable_return_type cd; |
| std::pair |
| < |
| seg_or_box_iterator_type, seg_or_box_iterator_type |
| > it_pair |
| = point_to_point_range::apply(*pit, |
| seg_or_box_points.begin(), |
| seg_or_box_points.end(), |
| cstrategy, |
| cd); |
| |
| if (first || cd < cd_min1) |
| { |
| cd_min1 = cd; |
| pit_min = pit; |
| assign_new_value::apply(it_min1, it_pair.first); |
| assign_new_value::apply(it_min2, it_pair.second); |
| } |
| } |
| |
| // consider all distances of the points in the segment or box to the |
| // segments of the geometry |
| comparable_return_type cd_min2(0); |
| segment_iterator_type sit_min; |
| typename std::vector<segment_or_box_point>::const_iterator it_min; |
| |
| first = true; |
| for (typename std::vector<segment_or_box_point>::const_iterator it |
| = seg_or_box_points.begin(); |
| it != seg_or_box_points.end(); ++it, first = false) |
| { |
| comparable_return_type cd; |
| segment_iterator_type sit |
| = geometry_to_range::apply(*it, |
| segments_begin(geometry), |
| segments_end(geometry), |
| cstrategy, |
| cd); |
| |
| if (first || cd < cd_min2) |
| { |
| cd_min2 = cd; |
| it_min = it; |
| sit_min = sit; |
| } |
| } |
| |
| if (BOOST_GEOMETRY_CONDITION(is_comparable<Strategy>::value)) |
| { |
| return (std::min)(cd_min1, cd_min2); |
| } |
| |
| if (cd_min1 < cd_min2) |
| { |
| return strategy.apply(*pit_min, *it_min1, *it_min2); |
| } |
| else |
| { |
| return dispatch::distance |
| < |
| segment_or_box_point, |
| typename std::iterator_traits |
| < |
| segment_iterator_type |
| >::value_type, |
| Strategy |
| >::apply(*it_min, *sit_min, strategy); |
| } |
| } |
| |
| |
| static inline return_type |
| apply(SegmentOrBox const& segment_or_box, Geometry const& geometry, |
| Strategy const& strategy, bool check_intersection = true) |
| { |
| return apply(geometry, segment_or_box, strategy, check_intersection); |
| } |
| }; |
| |
| |
| |
| template <typename MultiPoint, typename SegmentOrBox, typename Strategy> |
| class geometry_to_segment_or_box |
| < |
| MultiPoint, SegmentOrBox, Strategy, multi_point_tag |
| > |
| { |
| private: |
| typedef detail::closest_feature::geometry_to_range base_type; |
| |
| typedef typename boost::range_iterator |
| < |
| MultiPoint const |
| >::type iterator_type; |
| |
| typedef detail::closest_feature::geometry_to_range geometry_to_range; |
| |
| public: |
| typedef typename strategy::distance::services::return_type |
| < |
| Strategy, |
| typename point_type<SegmentOrBox>::type, |
| typename point_type<MultiPoint>::type |
| >::type return_type; |
| |
| static inline return_type apply(MultiPoint const& multipoint, |
| SegmentOrBox const& segment_or_box, |
| Strategy const& strategy) |
| { |
| namespace sds = strategy::distance::services; |
| |
| typename sds::return_type |
| < |
| typename sds::comparable_type<Strategy>::type, |
| typename point_type<SegmentOrBox>::type, |
| typename point_type<MultiPoint>::type |
| >::type cd_min; |
| |
| iterator_type it_min |
| = geometry_to_range::apply(segment_or_box, |
| boost::begin(multipoint), |
| boost::end(multipoint), |
| sds::get_comparable |
| < |
| Strategy |
| >::apply(strategy), |
| cd_min); |
| |
| return |
| is_comparable<Strategy>::value |
| ? |
| cd_min |
| : |
| dispatch::distance |
| < |
| typename point_type<MultiPoint>::type, |
| SegmentOrBox, |
| Strategy |
| >::apply(*it_min, segment_or_box, strategy); |
| } |
| }; |
| |
| |
| |
| }} // namespace detail::distance |
| #endif // DOXYGEN_NO_DETAIL |
| |
| |
| |
| #ifndef DOXYGEN_NO_DISPATCH |
| namespace dispatch |
| { |
| |
| |
| template <typename Linear, typename Segment, typename Strategy> |
| struct distance |
| < |
| Linear, Segment, Strategy, linear_tag, segment_tag, |
| strategy_tag_distance_point_segment, false |
| > : detail::distance::geometry_to_segment_or_box<Linear, Segment, Strategy> |
| {}; |
| |
| |
| template <typename Areal, typename Segment, typename Strategy> |
| struct distance |
| < |
| Areal, Segment, Strategy, areal_tag, segment_tag, |
| strategy_tag_distance_point_segment, false |
| > : detail::distance::geometry_to_segment_or_box<Areal, Segment, Strategy> |
| {}; |
| |
| |
| template <typename Segment, typename Areal, typename Strategy> |
| struct distance |
| < |
| Segment, Areal, Strategy, segment_tag, areal_tag, |
| strategy_tag_distance_point_segment, false |
| > : detail::distance::geometry_to_segment_or_box<Areal, Segment, Strategy> |
| {}; |
| |
| |
| template <typename Linear, typename Box, typename Strategy> |
| struct distance |
| < |
| Linear, Box, Strategy, linear_tag, box_tag, |
| strategy_tag_distance_point_segment, false |
| > : detail::distance::geometry_to_segment_or_box |
| < |
| Linear, Box, Strategy |
| > |
| {}; |
| |
| |
| template <typename Areal, typename Box, typename Strategy> |
| struct distance |
| < |
| Areal, Box, Strategy, areal_tag, box_tag, |
| strategy_tag_distance_point_segment, false |
| > : detail::distance::geometry_to_segment_or_box<Areal, Box, Strategy> |
| {}; |
| |
| |
| template <typename MultiPoint, typename Segment, typename Strategy> |
| struct distance |
| < |
| MultiPoint, Segment, Strategy, |
| multi_point_tag, segment_tag, |
| strategy_tag_distance_point_segment, false |
| > : detail::distance::geometry_to_segment_or_box |
| < |
| MultiPoint, Segment, Strategy |
| > |
| {}; |
| |
| |
| template <typename MultiPoint, typename Box, typename Strategy> |
| struct distance |
| < |
| MultiPoint, Box, Strategy, |
| multi_point_tag, box_tag, |
| strategy_tag_distance_point_box, false |
| > : detail::distance::geometry_to_segment_or_box |
| < |
| MultiPoint, Box, Strategy |
| > |
| {}; |
| |
| |
| } // namespace dispatch |
| #endif // DOXYGEN_NO_DISPATCH |
| |
| |
| }} // namespace boost::geometry |
| |
| |
| #endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_DISTANCE_GEOMETRY_TO_SEGMENT_OR_BOX_HPP |
