diff options
Diffstat (limited to 'boost/geometry/algorithms/detail/distance')
15 files changed, 3740 insertions, 0 deletions
diff --git a/boost/geometry/algorithms/detail/distance/backward_compatibility.hpp b/boost/geometry/algorithms/detail/distance/backward_compatibility.hpp new file mode 100644 index 0000000000..5b49e571dd --- /dev/null +++ b/boost/geometry/algorithms/detail/distance/backward_compatibility.hpp @@ -0,0 +1,333 @@ +// Boost.Geometry (aka GGL, Generic Geometry Library) + +// Copyright (c) 2007-2014 Barend Gehrels, Amsterdam, the Netherlands. +// Copyright (c) 2008-2014 Bruno Lalande, Paris, France. +// Copyright (c) 2009-2014 Mateusz Loskot, London, UK. +// Copyright (c) 2013-2014 Adam Wulkiewicz, Lodz, Poland. + +// This file was modified by Oracle on 2014. +// Modifications copyright (c) 2014, Oracle and/or its affiliates. + +// Contributed and/or modified by Menelaos Karavelas, on behalf of Oracle + +// Parts of Boost.Geometry are redesigned from Geodan's Geographic Library +// (geolib/GGL), copyright (c) 1995-2010 Geodan, Amsterdam, the Netherlands. + +// Use, modification and distribution is subject to the Boost Software License, +// Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at +// http://www.boost.org/LICENSE_1_0.txt) + +#ifndef BOOST_GEOMETRY_ALGORITHMS_DETAIL_DISTANCE_BACKWARD_COMPATIBILITY_HPP +#define BOOST_GEOMETRY_ALGORITHMS_DETAIL_DISTANCE_BACKWARD_COMPATIBILITY_HPP + +#include <boost/geometry/core/closure.hpp> +#include <boost/geometry/core/point_type.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/dispatch/distance.hpp> + +#include <boost/geometry/algorithms/detail/distance/default_strategies.hpp> +#include <boost/geometry/algorithms/detail/distance/point_to_geometry.hpp> +#include <boost/geometry/algorithms/detail/distance/multipoint_to_geometry.hpp> + + +namespace boost { namespace geometry +{ + + +#ifndef DOXYGEN_NO_DETAIL +namespace detail { namespace distance +{ + + +template<typename Point, typename Segment, typename Strategy> +struct point_to_segment +{ + static inline typename strategy::distance::services::return_type + < + Strategy, + Point, + typename point_type<Segment>::type + >::type + apply(Point const& point, Segment const& segment, Strategy const& ) + { + typename detail::distance::default_ps_strategy + < + Point, + typename point_type<Segment>::type, + Strategy + >::type segment_strategy; + + typename point_type<Segment>::type p[2]; + geometry::detail::assign_point_from_index<0>(segment, p[0]); + geometry::detail::assign_point_from_index<1>(segment, p[1]); + return segment_strategy.apply(point, p[0], p[1]); + } +}; + + +}} // namespace detail::distance +#endif // DOXYGEN_NO_DETAIL + + + + +#ifndef DOXYGEN_NO_DISPATCH +namespace dispatch +{ + + +// Point-segment version 1, with point-point strategy +template <typename Point, typename Segment, typename Strategy> +struct distance +< + Point, Segment, Strategy, + point_tag, segment_tag, strategy_tag_distance_point_point, + false +> : detail::distance::point_to_segment<Point, Segment, Strategy> +{}; + + +// Point-line version 1, where point-point strategy is specified +template <typename Point, typename Linestring, typename Strategy> +struct distance +< + Point, Linestring, Strategy, + point_tag, linestring_tag, strategy_tag_distance_point_point, + false +> +{ + + static inline typename strategy::distance::services::return_type + < + Strategy, Point, typename point_type<Linestring>::type + >::type + apply(Point const& point, + Linestring const& linestring, + Strategy const&) + { + typedef typename detail::distance::default_ps_strategy + < + Point, + typename point_type<Linestring>::type, + Strategy + >::type ps_strategy_type; + + return detail::distance::point_to_range + < + Point, Linestring, closed, ps_strategy_type + >::apply(point, linestring, ps_strategy_type()); + } +}; + + +// Point-ring , where point-point strategy is specified +template <typename Point, typename Ring, typename Strategy> +struct distance +< + Point, Ring, Strategy, + point_tag, ring_tag, strategy_tag_distance_point_point, + false +> +{ + typedef typename strategy::distance::services::return_type + < + Strategy, Point, typename point_type<Ring>::type + >::type return_type; + + static inline return_type apply(Point const& point, + Ring const& ring, + Strategy const&) + { + typedef typename detail::distance::default_ps_strategy + < + Point, + typename point_type<Ring>::type, + Strategy + >::type ps_strategy_type; + + return detail::distance::point_to_ring + < + Point, Ring, + geometry::closure<Ring>::value, + ps_strategy_type + >::apply(point, ring, ps_strategy_type()); + } +}; + + +// Point-polygon , where point-point strategy is specified +template <typename Point, typename Polygon, typename Strategy> +struct distance +< + Point, Polygon, Strategy, + point_tag, polygon_tag, strategy_tag_distance_point_point, + false +> +{ + typedef typename strategy::distance::services::return_type + < + Strategy, Point, typename point_type<Polygon>::type + >::type return_type; + + static inline return_type apply(Point const& point, + Polygon const& polygon, + Strategy const&) + { + typedef typename detail::distance::default_ps_strategy + < + Point, + typename point_type<Polygon>::type, + Strategy + >::type ps_strategy_type; + + return detail::distance::point_to_polygon + < + Point, + Polygon, + geometry::closure<Polygon>::value, + ps_strategy_type + >::apply(point, polygon, ps_strategy_type()); + } +}; + + + + +template +< + typename Point, + typename MultiGeometry, + typename MultiGeometryTag, + typename Strategy +> +struct distance + < + Point, MultiGeometry, Strategy, + point_tag, MultiGeometryTag, + strategy_tag_distance_point_point, false + > +{ + typedef typename strategy::distance::services::return_type + < + Strategy, Point, typename point_type<MultiGeometry>::type + >::type return_type; + + static inline return_type apply(Point const& point, + MultiGeometry const& multigeometry, + Strategy const&) + { + typedef typename detail::distance::default_ps_strategy + < + Point, + typename point_type<MultiGeometry>::type, + Strategy + >::type ps_strategy_type; + + return distance + < + Point, MultiGeometry, ps_strategy_type, + point_tag, MultiGeometryTag, + strategy_tag_distance_point_segment, false + >::apply(point, multigeometry, ps_strategy_type()); + } +}; + + +template +< + typename Geometry, + typename MultiPoint, + typename GeometryTag, + typename Strategy +> +struct distance + < + Geometry, MultiPoint, Strategy, + GeometryTag, multi_point_tag, + strategy_tag_distance_point_point, false + > +{ + typedef typename strategy::distance::services::return_type + < + Strategy, + typename point_type<MultiPoint>::type, + typename point_type<Geometry>::type + >::type return_type; + + static inline return_type apply(Geometry const& geometry, + MultiPoint const& multipoint, + Strategy const&) + { + typedef typename detail::distance::default_ps_strategy + < + typename point_type<MultiPoint>::type, + typename point_type<Geometry>::type, + Strategy + >::type ps_strategy_type; + + return distance + < + Geometry, MultiPoint, ps_strategy_type, + GeometryTag, multi_point_tag, + strategy_tag_distance_point_segment, false + >::apply(geometry, multipoint, ps_strategy_type()); + } +}; + + +template +< + typename MultiPoint, + typename MultiGeometry, + typename MultiGeometryTag, + typename Strategy +> +struct distance + < + MultiPoint, MultiGeometry, Strategy, + multi_point_tag, MultiGeometryTag, + strategy_tag_distance_point_point, false + > +{ + typedef typename strategy::distance::services::return_type + < + Strategy, + typename point_type<MultiPoint>::type, + typename point_type<MultiGeometry>::type + >::type return_type; + + static inline return_type apply(MultiPoint const& multipoint, + MultiGeometry const& multigeometry, + Strategy const&) + { + typedef typename detail::distance::default_ps_strategy + < + typename point_type<MultiPoint>::type, + typename point_type<MultiGeometry>::type, + Strategy + >::type ps_strategy_type; + + return distance + < + MultiPoint, MultiGeometry, ps_strategy_type, + multi_point_tag, MultiGeometryTag, + strategy_tag_distance_point_segment, false + >::apply(multipoint, multigeometry, ps_strategy_type()); + } +}; + + +} // namespace dispatch +#endif // DOXYGEN_NO_DISPATCH + + +}} // namespace boost::geometry + + +#endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_DISTANCE_BACKWARD_COMPATIBILITY_HPP diff --git a/boost/geometry/algorithms/detail/distance/box_to_box.hpp b/boost/geometry/algorithms/detail/distance/box_to_box.hpp new file mode 100644 index 0000000000..44778e9e06 --- /dev/null +++ b/boost/geometry/algorithms/detail/distance/box_to_box.hpp @@ -0,0 +1,60 @@ +// 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_BOX_TO_BOX_HPP +#define BOOST_GEOMETRY_ALGORITHMS_DETAIL_DISTANCE_BOX_TO_BOX_HPP + +#include <boost/core/ignore_unused.hpp> + +#include <boost/geometry/core/point_type.hpp> +#include <boost/geometry/core/tags.hpp> + +#include <boost/geometry/strategies/distance.hpp> +#include <boost/geometry/strategies/tags.hpp> + +#include <boost/geometry/algorithms/dispatch/distance.hpp> + + +namespace boost { namespace geometry +{ + +#ifndef DOXYGEN_NO_DISPATCH +namespace dispatch +{ + + +template <typename Box1, typename Box2, typename Strategy> +struct distance + < + Box1, Box2, Strategy, box_tag, box_tag, + strategy_tag_distance_box_box, false + > +{ + static inline typename strategy::distance::services::return_type + < + Strategy, + typename point_type<Box1>::type, + typename point_type<Box2>::type + >::type + apply(Box1 const& box1, Box2 const& box2, Strategy const& strategy) + { + boost::ignore_unused(strategy); + return strategy.apply(box1, box2); + } +}; + + +} // namespace dispatch +#endif // DOXYGEN_NO_DISPATCH + + +}} // namespace boost::geometry + + +#endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_DISTANCE_BOX_TO_BOX_HPP diff --git a/boost/geometry/algorithms/detail/distance/default_strategies.hpp b/boost/geometry/algorithms/detail/distance/default_strategies.hpp new file mode 100644 index 0000000000..a01ace2b58 --- /dev/null +++ b/boost/geometry/algorithms/detail/distance/default_strategies.hpp @@ -0,0 +1,137 @@ +// Boost.Geometry (aka GGL, Generic Geometry Library) + +// Copyright (c) 2007-2014 Barend Gehrels, Amsterdam, the Netherlands. +// Copyright (c) 2008-2014 Bruno Lalande, Paris, France. +// Copyright (c) 2009-2014 Mateusz Loskot, London, UK. +// Copyright (c) 2013-2014 Adam Wulkiewicz, Lodz, Poland. + +// This file was modified by Oracle on 2014. +// Modifications copyright (c) 2014, Oracle and/or its affiliates. + +// Contributed and/or modified by Menelaos Karavelas, on behalf of Oracle + +// Parts of Boost.Geometry are redesigned from Geodan's Geographic Library +// (geolib/GGL), copyright (c) 1995-2010 Geodan, Amsterdam, the Netherlands. + +// Use, modification and distribution is subject to the Boost Software License, +// Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at +// http://www.boost.org/LICENSE_1_0.txt) + +#ifndef BOOST_GEOMETRY_ALGORITHMS_DETAIL_DISTANCE_DEFAULT_STRATEGIES_HPP +#define BOOST_GEOMETRY_ALGORITHMS_DETAIL_DISTANCE_DEFAULT_STRATEGIES_HPP + +#include <boost/geometry/core/cs.hpp> +#include <boost/geometry/core/tag.hpp> +#include <boost/geometry/core/tag_cast.hpp> +#include <boost/geometry/core/tags.hpp> +#include <boost/geometry/core/point_type.hpp> +#include <boost/geometry/core/reverse_dispatch.hpp> + +#include <boost/geometry/strategies/distance.hpp> + + +namespace boost { namespace geometry +{ + +#ifndef DOXYGEN_NO_DETAIL +namespace detail { namespace distance +{ + + + +// Helper metafunction for default strategy retrieval +template +< + typename Geometry1, + typename Geometry2 = Geometry1, + typename Tag1 = typename tag_cast + < + typename tag<Geometry1>::type, pointlike_tag + >::type, + typename Tag2 = typename tag_cast + < + typename tag<Geometry2>::type, pointlike_tag + >::type, + bool Reverse = geometry::reverse_dispatch<Geometry1, Geometry2>::type::value +> +struct default_strategy + : strategy::distance::services::default_strategy + < + point_tag, segment_tag, + typename point_type<Geometry1>::type, + typename point_type<Geometry2>::type + > +{}; + +template +< + typename Geometry1, + typename Geometry2, + typename Tag1, + typename Tag2 +> +struct default_strategy<Geometry1, Geometry2, Tag1, Tag2, true> + : default_strategy<Geometry2, Geometry1, Tag2, Tag1, false> +{}; + + +template <typename Pointlike1, typename Pointlike2> +struct default_strategy + < + Pointlike1, Pointlike2, + pointlike_tag, pointlike_tag, false + > : strategy::distance::services::default_strategy + < + point_tag, point_tag, + typename point_type<Pointlike1>::type, + typename point_type<Pointlike2>::type + > +{}; + + +template <typename Pointlike, typename Box> +struct default_strategy<Pointlike, Box, pointlike_tag, box_tag, false> + : strategy::distance::services::default_strategy + < + point_tag, box_tag, + typename point_type<Pointlike>::type, + typename point_type<Box>::type + > +{}; + + +template <typename Box1, typename Box2> +struct default_strategy<Box1, Box2, box_tag, box_tag, false> + : strategy::distance::services::default_strategy + < + box_tag, box_tag, + typename point_type<Box1>::type, + typename point_type<Box2>::type + > +{}; + + + +// Helper metafunction for default point-segment strategy retrieval +template <typename Geometry1, typename Geometry2, typename Strategy> +struct default_ps_strategy + : strategy::distance::services::default_strategy + < + point_tag, segment_tag, + typename point_type<Geometry1>::type, + typename point_type<Geometry2>::type, + typename cs_tag<typename point_type<Geometry1>::type>::type, + typename cs_tag<typename point_type<Geometry2>::type>::type, + Strategy + > +{}; + + + +}} // namespace detail::distance +#endif // DOXYGEN_NO_DETAIL + +}} // namespace boost::geometry + + +#endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_DISTANCE_DEFAULT_STRATEGIES_HPP diff --git a/boost/geometry/algorithms/detail/distance/geometry_to_segment_or_box.hpp b/boost/geometry/algorithms/detail/distance/geometry_to_segment_or_box.hpp new file mode 100644 index 0000000000..04d1095cba --- /dev/null +++ b/boost/geometry/algorithms/detail/distance/geometry_to_segment_or_box.hpp @@ -0,0 +1,462 @@ +// 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> + + +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; + 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; + 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 (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 diff --git a/boost/geometry/algorithms/detail/distance/implementation.hpp b/boost/geometry/algorithms/detail/distance/implementation.hpp new file mode 100644 index 0000000000..7c009f4d79 --- /dev/null +++ b/boost/geometry/algorithms/detail/distance/implementation.hpp @@ -0,0 +1,35 @@ +// Boost.Geometry (aka GGL, Generic Geometry Library) + +// Copyright (c) 2007-2014 Barend Gehrels, Amsterdam, the Netherlands. +// Copyright (c) 2008-2014 Bruno Lalande, Paris, France. +// Copyright (c) 2009-2014 Mateusz Loskot, London, UK. +// Copyright (c) 2013-2014 Adam Wulkiewicz, Lodz, Poland. + +// This file was modified by Oracle on 2014. +// Modifications copyright (c) 2014, Oracle and/or its affiliates. + +// Contributed and/or modified by Menelaos Karavelas, on behalf of Oracle + +// Parts of Boost.Geometry are redesigned from Geodan's Geographic Library +// (geolib/GGL), copyright (c) 1995-2010 Geodan, Amsterdam, the Netherlands. + +// Use, modification and distribution is subject to the Boost Software License, +// Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at +// http://www.boost.org/LICENSE_1_0.txt) + +#ifndef BOOST_GEOMETRY_ALGORITHMS_DETAIL_DISTANCE_IMPLEMENTATION_HPP +#define BOOST_GEOMETRY_ALGORITHMS_DETAIL_DISTANCE_IMPLEMENTATION_HPP + +// the implementation details +#include <boost/geometry/algorithms/detail/distance/point_to_geometry.hpp> +#include <boost/geometry/algorithms/detail/distance/multipoint_to_geometry.hpp> +#include <boost/geometry/algorithms/detail/distance/linear_to_linear.hpp> +#include <boost/geometry/algorithms/detail/distance/linear_or_areal_to_areal.hpp> +#include <boost/geometry/algorithms/detail/distance/geometry_to_segment_or_box.hpp> +#include <boost/geometry/algorithms/detail/distance/segment_to_segment.hpp> +#include <boost/geometry/algorithms/detail/distance/segment_to_box.hpp> +#include <boost/geometry/algorithms/detail/distance/box_to_box.hpp> + +#include <boost/geometry/algorithms/detail/distance/backward_compatibility.hpp> + +#endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_DISTANCE_IMPLEMENTATION_HPP diff --git a/boost/geometry/algorithms/detail/distance/interface.hpp b/boost/geometry/algorithms/detail/distance/interface.hpp new file mode 100644 index 0000000000..9b377f524b --- /dev/null +++ b/boost/geometry/algorithms/detail/distance/interface.hpp @@ -0,0 +1,403 @@ +// Boost.Geometry (aka GGL, Generic Geometry Library) + +// Copyright (c) 2007-2014 Barend Gehrels, Amsterdam, the Netherlands. +// Copyright (c) 2008-2014 Bruno Lalande, Paris, France. +// Copyright (c) 2009-2014 Mateusz Loskot, London, UK. +// Copyright (c) 2013-2014 Adam Wulkiewicz, Lodz, Poland. +// Copyright (c) 2014 Samuel Debionne, Grenoble, France. + +// This file was modified by Oracle on 2014. +// Modifications copyright (c) 2014, Oracle and/or its affiliates. + +// Contributed and/or modified by Menelaos Karavelas, on behalf of Oracle + +// Parts of Boost.Geometry are redesigned from Geodan's Geographic Library +// (geolib/GGL), copyright (c) 1995-2010 Geodan, Amsterdam, the Netherlands. + +// Use, modification and distribution is subject to the Boost Software License, +// Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at +// http://www.boost.org/LICENSE_1_0.txt) + +#ifndef BOOST_GEOMETRY_ALGORITHMS_DETAIL_DISTANCE_INTERFACE_HPP +#define BOOST_GEOMETRY_ALGORITHMS_DETAIL_DISTANCE_INTERFACE_HPP + +#include <boost/concept_check.hpp> + +#include <boost/mpl/always.hpp> +#include <boost/mpl/bool.hpp> +#include <boost/mpl/vector.hpp> + +#include <boost/geometry/core/point_type.hpp> + +#include <boost/geometry/geometries/concepts/check.hpp> + +#include <boost/geometry/strategies/default_strategy.hpp> +#include <boost/geometry/strategies/distance.hpp> +#include <boost/geometry/strategies/default_distance_result.hpp> +#include <boost/geometry/strategies/distance_result.hpp> + +#include <boost/geometry/algorithms/detail/throw_on_empty_input.hpp> +#include <boost/geometry/algorithms/detail/distance/default_strategies.hpp> + +#include <boost/geometry/algorithms/dispatch/distance.hpp> + + +namespace boost { namespace geometry +{ + + +#ifndef DOXYGEN_NO_DISPATCH +namespace dispatch +{ + + +// If reversal is needed, perform it +template +< + typename Geometry1, typename Geometry2, typename Strategy, + typename Tag1, typename Tag2, typename StrategyTag +> +struct distance +< + Geometry1, Geometry2, Strategy, + Tag1, Tag2, StrategyTag, + true +> + : distance<Geometry2, Geometry1, Strategy, Tag2, Tag1, StrategyTag, false> +{ + typedef typename strategy::distance::services::return_type + < + Strategy, + typename point_type<Geometry2>::type, + typename point_type<Geometry1>::type + >::type return_type; + + static inline return_type apply( + Geometry1 const& g1, + Geometry2 const& g2, + Strategy const& strategy) + { + return distance + < + Geometry2, Geometry1, Strategy, + Tag2, Tag1, StrategyTag, + false + >::apply(g2, g1, strategy); + } +}; + + +} // namespace dispatch +#endif // DOXYGEN_NO_DISPATCH + + +namespace resolve_strategy +{ + +struct distance +{ + template <typename Geometry1, typename Geometry2, typename Strategy> + static inline typename distance_result<Geometry1, Geometry2, Strategy>::type + apply(Geometry1 const& geometry1, + Geometry2 const& geometry2, + Strategy const& strategy) + { + return dispatch::distance + < + Geometry1, Geometry2, Strategy + >::apply(geometry1, geometry2, strategy); + } + + template <typename Geometry1, typename Geometry2> + static inline + typename distance_result<Geometry1, Geometry2, default_strategy>::type + apply(Geometry1 const& geometry1, + Geometry2 const& geometry2, + default_strategy) + { + typedef typename detail::distance::default_strategy + < + Geometry1, Geometry2 + >::type strategy_type; + + return dispatch::distance + < + Geometry1, Geometry2, strategy_type + >::apply(geometry1, geometry2, strategy_type()); + } +}; + +} // namespace resolve_strategy + + +namespace resolve_variant +{ + + +template <typename Geometry1, typename Geometry2> +struct distance +{ + template <typename Strategy> + static inline typename distance_result<Geometry1, Geometry2, Strategy>::type + apply(Geometry1 const& geometry1, + Geometry2 const& geometry2, + Strategy const& strategy) + { + return + resolve_strategy::distance::apply(geometry1, geometry2, strategy); + } +}; + + +template <BOOST_VARIANT_ENUM_PARAMS(typename T), typename Geometry2> +struct distance<variant<BOOST_VARIANT_ENUM_PARAMS(T)>, Geometry2> +{ + template <typename Strategy> + struct visitor: static_visitor + < + typename distance_result + < + variant<BOOST_VARIANT_ENUM_PARAMS(T)>, + Geometry2, + Strategy + >::type + > + { + Geometry2 const& m_geometry2; + Strategy const& m_strategy; + + visitor(Geometry2 const& geometry2, + Strategy const& strategy) + : m_geometry2(geometry2), + m_strategy(strategy) + {} + + template <typename Geometry1> + typename distance_result<Geometry1, Geometry2, Strategy>::type + operator()(Geometry1 const& geometry1) const + { + return distance + < + Geometry1, + Geometry2 + >::template apply + < + Strategy + >(geometry1, m_geometry2, m_strategy); + } + }; + + template <typename Strategy> + static inline typename distance_result + < + variant<BOOST_VARIANT_ENUM_PARAMS(T)>, + Geometry2, + Strategy + >::type + apply(variant<BOOST_VARIANT_ENUM_PARAMS(T)> const& geometry1, + Geometry2 const& geometry2, + Strategy const& strategy) + { + return apply_visitor(visitor<Strategy>(geometry2, strategy), geometry1); + } +}; + + +template <typename Geometry1, BOOST_VARIANT_ENUM_PARAMS(typename T)> +struct distance<Geometry1, variant<BOOST_VARIANT_ENUM_PARAMS(T)> > +{ + template <typename Strategy> + struct visitor: static_visitor + < + typename distance_result + < + Geometry1, + variant<BOOST_VARIANT_ENUM_PARAMS(T)>, + Strategy + >::type + > + { + Geometry1 const& m_geometry1; + Strategy const& m_strategy; + + visitor(Geometry1 const& geometry1, + Strategy const& strategy) + : m_geometry1(geometry1), + m_strategy(strategy) + {} + + template <typename Geometry2> + typename distance_result<Geometry1, Geometry2, Strategy>::type + operator()(Geometry2 const& geometry2) const + { + return distance + < + Geometry1, + Geometry2 + >::template apply + < + Strategy + >(m_geometry1, geometry2, m_strategy); + } + }; + + template <typename Strategy> + static inline typename distance_result + < + Geometry1, + variant<BOOST_VARIANT_ENUM_PARAMS(T)>, + Strategy + >::type + apply( + Geometry1 const& geometry1, + const variant<BOOST_VARIANT_ENUM_PARAMS(T)>& geometry2, + Strategy const& strategy) + { + return apply_visitor(visitor<Strategy>(geometry1, strategy), geometry2); + } +}; + + +template +< + BOOST_VARIANT_ENUM_PARAMS(typename A), + BOOST_VARIANT_ENUM_PARAMS(typename B) +> +struct distance + < + boost::variant<BOOST_VARIANT_ENUM_PARAMS(A)>, + boost::variant<BOOST_VARIANT_ENUM_PARAMS(B)> + > +{ + template <typename Strategy> + struct visitor: static_visitor + < + typename distance_result + < + boost::variant<BOOST_VARIANT_ENUM_PARAMS(A)>, + boost::variant<BOOST_VARIANT_ENUM_PARAMS(B)>, + Strategy + >::type + > + { + Strategy const& m_strategy; + + visitor(Strategy const& strategy) + : m_strategy(strategy) + {} + + template <typename Geometry1, typename Geometry2> + typename distance_result<Geometry1, Geometry2, Strategy>::type + operator()(Geometry1 const& geometry1, Geometry2 const& geometry2) const + { + return distance + < + Geometry1, + Geometry2 + >::template apply + < + Strategy + >(geometry1, geometry2, m_strategy); + } + }; + + template <typename Strategy> + static inline typename distance_result + < + boost::variant<BOOST_VARIANT_ENUM_PARAMS(A)>, + boost::variant<BOOST_VARIANT_ENUM_PARAMS(B)>, + Strategy + >::type + apply(boost::variant<BOOST_VARIANT_ENUM_PARAMS(A)> const& geometry1, + boost::variant<BOOST_VARIANT_ENUM_PARAMS(B)> const& geometry2, + Strategy const& strategy) + { + return apply_visitor(visitor<Strategy>(strategy), geometry1, geometry2); + } +}; + +} // namespace resolve_variant + + +/*! +\brief \brief_calc2{distance} \brief_strategy +\ingroup distance +\details +\details \details_calc{area}. \brief_strategy. \details_strategy_reasons + +\tparam Geometry1 \tparam_geometry +\tparam Geometry2 \tparam_geometry +\tparam Strategy \tparam_strategy{Distance} +\param geometry1 \param_geometry +\param geometry2 \param_geometry +\param strategy \param_strategy{distance} +\return \return_calc{distance} +\note The strategy can be a point-point strategy. In case of distance point-line/point-polygon + it may also be a point-segment strategy. + +\qbk{distinguish,with strategy} + +\qbk{ +[heading Available Strategies] +\* [link geometry.reference.strategies.strategy_distance_pythagoras Pythagoras (cartesian)] +\* [link geometry.reference.strategies.strategy_distance_haversine Haversine (spherical)] +\* [link geometry.reference.strategies.strategy_distance_cross_track Cross track (spherical\, point-to-segment)] +\* [link geometry.reference.strategies.strategy_distance_projected_point Projected point (cartesian\, point-to-segment)] +\* more (currently extensions): Vincenty\, Andoyer (geographic) +} + */ + +/* +Note, in case of a Compilation Error: +if you get: + - "Failed to specialize function template ..." + - "error: no matching function for call to ..." +for distance, it is probably so that there is no specialization +for return_type<...> for your strategy. +*/ +template <typename Geometry1, typename Geometry2, typename Strategy> +inline typename distance_result<Geometry1, Geometry2, Strategy>::type +distance(Geometry1 const& geometry1, + Geometry2 const& geometry2, + Strategy const& strategy) +{ + concept::check<Geometry1 const>(); + concept::check<Geometry2 const>(); + + detail::throw_on_empty_input(geometry1); + detail::throw_on_empty_input(geometry2); + + return resolve_variant::distance + < + Geometry1, + Geometry2 + >::apply(geometry1, geometry2, strategy); +} + + +/*! +\brief \brief_calc2{distance} +\ingroup distance +\details The default strategy is used, corresponding to the coordinate system of the geometries +\tparam Geometry1 \tparam_geometry +\tparam Geometry2 \tparam_geometry +\param geometry1 \param_geometry +\param geometry2 \param_geometry +\return \return_calc{distance} + +\qbk{[include reference/algorithms/distance.qbk]} + */ +template <typename Geometry1, typename Geometry2> +inline typename default_distance_result<Geometry1, Geometry2>::type +distance(Geometry1 const& geometry1, + Geometry2 const& geometry2) +{ + concept::check<Geometry1 const>(); + concept::check<Geometry2 const>(); + + return distance(geometry1, geometry2, default_strategy()); +} + +}} // namespace boost::geometry + +#endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_DISTANCE_INTERFACE_HPP diff --git a/boost/geometry/algorithms/detail/distance/is_comparable.hpp b/boost/geometry/algorithms/detail/distance/is_comparable.hpp new file mode 100644 index 0000000000..d13cc6c740 --- /dev/null +++ b/boost/geometry/algorithms/detail/distance/is_comparable.hpp @@ -0,0 +1,45 @@ +// 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_ALGORITHS_DETAIL_DISTANCE_IS_COMPARABLE_HPP +#define BOOST_GEOMETRY_ALGORITHS_DETAIL_DISTANCE_IS_COMPARABLE_HPP + +#include <boost/type_traits/is_same.hpp> + +#include <boost/geometry/strategies/distance.hpp> + + +namespace boost { namespace geometry +{ + +#ifndef DOXYGEN_NO_DETAIL +namespace detail { namespace distance +{ + + +// metafunction to determine is a strategy is comparable or not +template <typename Strategy> +struct is_comparable + : boost::is_same + < + Strategy, + typename strategy::distance::services::comparable_type + < + Strategy + >::type + > +{}; + + +}} // namespace detail::distance +#endif // DOXYGEN_NO_DETAIL + +}} // namespace boost::geometry + +#endif // BOOST_GEOMETRY_ALGORITHS_DETAIL_DISTANCE_IS_COMPARABLE_HPP diff --git a/boost/geometry/algorithms/detail/distance/iterator_selector.hpp b/boost/geometry/algorithms/detail/distance/iterator_selector.hpp new file mode 100644 index 0000000000..363ec465a4 --- /dev/null +++ b/boost/geometry/algorithms/detail/distance/iterator_selector.hpp @@ -0,0 +1,70 @@ +// 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_ALGORITHS_DETAIL_DISTANCE_ITERATOR_SELECTOR_HPP +#define BOOST_GEOMETRY_ALGORITHS_DETAIL_DISTANCE_ITERATOR_SELECTOR_HPP + +#include <boost/geometry/core/tag.hpp> +#include <boost/geometry/core/tags.hpp> + +#include <boost/geometry/iterators/point_iterator.hpp> +#include <boost/geometry/iterators/segment_iterator.hpp> + + +namespace boost { namespace geometry +{ + + +#ifndef DOXYGEN_NO_DETAIL +namespace detail { namespace distance +{ + + +// class to choose between point_iterator and segment_iterator +template <typename Geometry, typename Tag = typename tag<Geometry>::type> +struct iterator_selector +{ + typedef geometry::segment_iterator<Geometry> iterator_type; + + static inline iterator_type begin(Geometry& geometry) + { + return segments_begin(geometry); + } + + static inline iterator_type end(Geometry& geometry) + { + return segments_end(geometry); + } +}; + +template <typename MultiPoint> +struct iterator_selector<MultiPoint, multi_point_tag> +{ + typedef geometry::point_iterator<MultiPoint> iterator_type; + + static inline iterator_type begin(MultiPoint& multipoint) + { + return points_begin(multipoint); + } + + static inline iterator_type end(MultiPoint& multipoint) + { + return points_end(multipoint); + } +}; + + +}} // namespace detail::distance +#endif // DOXYGEN_NO_DETAIL + + +}} // namespace boost::geometry + + +#endif // BOOST_GEOMETRY_ALGORITHS_DETAIL_DISTANCE_ITERATOR_SELECTOR_HPP diff --git a/boost/geometry/algorithms/detail/distance/linear_or_areal_to_areal.hpp b/boost/geometry/algorithms/detail/distance/linear_or_areal_to_areal.hpp new file mode 100644 index 0000000000..b63104da7d --- /dev/null +++ b/boost/geometry/algorithms/detail/distance/linear_or_areal_to_areal.hpp @@ -0,0 +1,147 @@ +// 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_LINEAR_OR_AREAL_TO_AREAL_HPP +#define BOOST_GEOMETRY_ALGORITHMS_DETAIL_DISTANCE_LINEAR_OR_AREAL_TO_AREAL_HPP + +#include <boost/geometry/core/point_type.hpp> + +#include <boost/geometry/strategies/distance.hpp> + +#include <boost/geometry/algorithms/intersects.hpp> + +#include <boost/geometry/algorithms/detail/distance/linear_to_linear.hpp> + + +namespace boost { namespace geometry +{ + +#ifndef DOXYGEN_NO_DETAIL +namespace detail { namespace distance +{ + + +template <typename Linear, typename Areal, typename Strategy> +struct linear_to_areal +{ + typedef typename strategy::distance::services::return_type + < + Strategy, + typename point_type<Linear>::type, + typename point_type<Areal>::type + >::type return_type; + + static inline return_type apply(Linear const& linear, + Areal const& areal, + Strategy const& strategy) + { + if ( geometry::intersects(linear, areal) ) + { + return 0; + } + + return linear_to_linear + < + Linear, Areal, Strategy + >::apply(linear, areal, strategy, false); + } + + + static inline return_type apply(Areal const& areal, + Linear const& linear, + Strategy const& strategy) + { + return apply(linear, areal, strategy); + } +}; + + +template <typename Areal1, typename Areal2, typename Strategy> +struct areal_to_areal +{ + typedef typename strategy::distance::services::return_type + < + Strategy, + typename point_type<Areal1>::type, + typename point_type<Areal2>::type + >::type return_type; + + static inline return_type apply(Areal1 const& areal1, + Areal2 const& areal2, + Strategy const& strategy) + { + if ( geometry::intersects(areal1, areal2) ) + { + return 0; + } + + return linear_to_linear + < + Areal1, Areal2, Strategy + >::apply(areal1, areal2, strategy, false); + } +}; + + +}} // namespace detail::distance +#endif // DOXYGEN_NO_DETAIL + + +#ifndef DOXYGEN_NO_DISPATCH +namespace dispatch +{ + +template <typename Linear, typename Areal, typename Strategy> +struct distance + < + Linear, Areal, Strategy, + linear_tag, areal_tag, + strategy_tag_distance_point_segment, false + > + : detail::distance::linear_to_areal + < + Linear, Areal, Strategy + > +{}; + + +template <typename Areal, typename Linear, typename Strategy> +struct distance + < + Areal, Linear, Strategy, + areal_tag, linear_tag, + strategy_tag_distance_point_segment, false + > + : detail::distance::linear_to_areal + < + Linear, Areal, Strategy + > +{}; + + +template <typename Areal1, typename Areal2, typename Strategy> +struct distance + < + Areal1, Areal2, Strategy, + areal_tag, areal_tag, + strategy_tag_distance_point_segment, false + > + : detail::distance::areal_to_areal + < + Areal1, Areal2, Strategy + > +{}; + + +} // namespace dispatch +#endif // DOXYGEN_NO_DISPATCH + +}} // namespace boost::geometry + +#endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_DISTANCE_LINEAR_OR_AREAL_TO_AREAL_HPP diff --git a/boost/geometry/algorithms/detail/distance/linear_to_linear.hpp b/boost/geometry/algorithms/detail/distance/linear_to_linear.hpp new file mode 100644 index 0000000000..e44b372842 --- /dev/null +++ b/boost/geometry/algorithms/detail/distance/linear_to_linear.hpp @@ -0,0 +1,123 @@ +// 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_LINEAR_TO_LINEAR_HPP +#define BOOST_GEOMETRY_ALGORITHMS_DETAIL_DISTANCE_LINEAR_TO_LINEAR_HPP + +#include <boost/geometry/core/point_type.hpp> + +#include <boost/geometry/strategies/distance.hpp> + +#include <boost/geometry/iterators/point_iterator.hpp> +#include <boost/geometry/iterators/segment_iterator.hpp> + +#include <boost/geometry/algorithms/num_points.hpp> +#include <boost/geometry/algorithms/num_segments.hpp> + +#include <boost/geometry/algorithms/dispatch/distance.hpp> + +#include <boost/geometry/algorithms/detail/distance/range_to_geometry_rtree.hpp> + + +namespace boost { namespace geometry +{ + +#ifndef DOXYGEN_NO_DETAIL +namespace detail { namespace distance +{ + + +template <typename Linear1, typename Linear2, typename Strategy> +struct linear_to_linear +{ + typedef typename strategy::distance::services::return_type + < + Strategy, + typename point_type<Linear1>::type, + typename point_type<Linear2>::type + >::type return_type; + + static inline return_type apply(Linear1 const& linear1, + Linear2 const& linear2, + Strategy const& strategy, + bool = false) + { + if (geometry::num_points(linear1) == 1) + { + return dispatch::distance + < + typename point_type<Linear1>::type, + Linear2, + Strategy + >::apply(*points_begin(linear1), linear2, strategy); + } + + if (geometry::num_points(linear2) == 1) + { + return dispatch::distance + < + typename point_type<Linear2>::type, + Linear1, + Strategy + >::apply(*points_begin(linear2), linear1, strategy); + } + + if (geometry::num_segments(linear2) < geometry::num_segments(linear1)) + { + return point_or_segment_range_to_geometry_rtree + < + geometry::segment_iterator<Linear2 const>, + Linear1, + Strategy + >::apply(geometry::segments_begin(linear2), + geometry::segments_end(linear2), + linear1, + strategy); + + } + + return point_or_segment_range_to_geometry_rtree + < + geometry::segment_iterator<Linear1 const>, + Linear2, + Strategy + >::apply(geometry::segments_begin(linear1), + geometry::segments_end(linear1), + linear2, + strategy); + } +}; + + +}} // namespace detail::distance +#endif // DOXYGEN_NO_DETAIL + + +#ifndef DOXYGEN_NO_DISPATCH +namespace dispatch +{ + +template <typename Linear1, typename Linear2, typename Strategy> +struct distance + < + Linear1, Linear2, Strategy, + linear_tag, linear_tag, + strategy_tag_distance_point_segment, false + > : detail::distance::linear_to_linear + < + Linear1, Linear2, Strategy + > +{}; + +} // namespace dispatch +#endif // DOXYGEN_NO_DISPATCH + +}} // namespace boost::geometry + +#endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_DISTANCE_LINEAR_TO_LINEAR_HPP diff --git a/boost/geometry/algorithms/detail/distance/multipoint_to_geometry.hpp b/boost/geometry/algorithms/detail/distance/multipoint_to_geometry.hpp new file mode 100644 index 0000000000..5f2c6e34fb --- /dev/null +++ b/boost/geometry/algorithms/detail/distance/multipoint_to_geometry.hpp @@ -0,0 +1,240 @@ +// 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_MULTIPOINT_TO_GEOMETRY_HPP +#define BOOST_GEOMETRY_ALGORITHMS_DETAIL_DISTANCE_MULTIPOINT_TO_GEOMETRY_HPP + +#include <boost/range.hpp> + +#include <boost/geometry/core/point_type.hpp> +#include <boost/geometry/core/tags.hpp> + +#include <boost/geometry/strategies/distance.hpp> +#include <boost/geometry/strategies/tags.hpp> + +#include <boost/geometry/algorithms/within.hpp> + +#include <boost/geometry/algorithms/dispatch/distance.hpp> + +#include <boost/geometry/algorithms/detail/check_iterator_range.hpp> +#include <boost/geometry/algorithms/detail/distance/range_to_geometry_rtree.hpp> + + +namespace boost { namespace geometry +{ + +#ifndef DOXYGEN_NO_DETAIL +namespace detail { namespace distance +{ + + +template <typename MultiPoint1, typename MultiPoint2, typename Strategy> +struct multipoint_to_multipoint +{ + typedef typename strategy::distance::services::return_type + < + Strategy, + typename point_type<MultiPoint1>::type, + typename point_type<MultiPoint2>::type + >::type return_type; + + static inline return_type apply(MultiPoint1 const& multipoint1, + MultiPoint2 const& multipoint2, + Strategy const& strategy) + { + if (boost::size(multipoint2) < boost::size(multipoint1)) + + { + return point_or_segment_range_to_geometry_rtree + < + typename boost::range_iterator<MultiPoint2 const>::type, + MultiPoint1, + Strategy + >::apply(boost::begin(multipoint2), + boost::end(multipoint2), + multipoint1, + strategy); + } + + return point_or_segment_range_to_geometry_rtree + < + typename boost::range_iterator<MultiPoint1 const>::type, + MultiPoint2, + Strategy + >::apply(boost::begin(multipoint1), + boost::end(multipoint1), + multipoint2, + strategy); + } +}; + + +template <typename MultiPoint, typename Linear, typename Strategy> +struct multipoint_to_linear +{ + typedef typename strategy::distance::services::return_type + < + Strategy, + typename point_type<MultiPoint>::type, + typename point_type<Linear>::type + >::type return_type; + + static inline return_type apply(MultiPoint const& multipoint, + Linear const& linear, + Strategy const& strategy) + { + return detail::distance::point_or_segment_range_to_geometry_rtree + < + typename boost::range_iterator<MultiPoint const>::type, + Linear, + Strategy + >::apply(boost::begin(multipoint), + boost::end(multipoint), + linear, + strategy); + } + + static inline return_type apply(Linear const& linear, + MultiPoint const& multipoint, + Strategy const& strategy) + { + return apply(multipoint, linear, strategy); + } +}; + + +template <typename MultiPoint, typename Areal, typename Strategy> +class multipoint_to_areal +{ +private: + struct within_areal + { + within_areal(Areal const& areal) + : m_areal(areal) + {} + + template <typename Point> + inline bool apply(Point const& point) const + { + return geometry::within(point, m_areal); + } + + Areal const& m_areal; + }; + +public: + typedef typename strategy::distance::services::return_type + < + Strategy, + typename point_type<MultiPoint>::type, + typename point_type<Areal>::type + >::type return_type; + + static inline return_type apply(MultiPoint const& multipoint, + Areal const& areal, + Strategy const& strategy) + { + within_areal predicate(areal); + + if (check_iterator_range + < + within_areal, false + >::apply(boost::begin(multipoint), + boost::end(multipoint), + predicate)) + { + return 0; + } + + return detail::distance::point_or_segment_range_to_geometry_rtree + < + typename boost::range_iterator<MultiPoint const>::type, + Areal, + Strategy + >::apply(boost::begin(multipoint), + boost::end(multipoint), + areal, + strategy); + } + + static inline return_type apply(Areal const& areal, + MultiPoint const& multipoint, + Strategy const& strategy) + { + return apply(multipoint, areal, strategy); + } +}; + + +}} // namespace detail::distance +#endif // DOXYGEN_NO_DETAIL + + + +#ifndef DOXYGEN_NO_DISPATCH +namespace dispatch +{ + + +template <typename MultiPoint1, typename MultiPoint2, typename Strategy> +struct distance + < + MultiPoint1, MultiPoint2, Strategy, + multi_point_tag, multi_point_tag, + strategy_tag_distance_point_point, false + > : detail::distance::multipoint_to_multipoint + < + MultiPoint1, MultiPoint2, Strategy + > +{}; + +template <typename MultiPoint, typename Linear, typename Strategy> +struct distance + < + MultiPoint, Linear, Strategy, multi_point_tag, linear_tag, + strategy_tag_distance_point_segment, false + > : detail::distance::multipoint_to_linear<MultiPoint, Linear, Strategy> +{}; + + +template <typename Linear, typename MultiPoint, typename Strategy> +struct distance + < + Linear, MultiPoint, Strategy, linear_tag, multi_point_tag, + strategy_tag_distance_point_segment, false + > : detail::distance::multipoint_to_linear<MultiPoint, Linear, Strategy> +{}; + + +template <typename MultiPoint, typename Areal, typename Strategy> +struct distance + < + MultiPoint, Areal, Strategy, multi_point_tag, areal_tag, + strategy_tag_distance_point_segment, false + > : detail::distance::multipoint_to_areal<MultiPoint, Areal, Strategy> +{}; + + +template <typename Areal, typename MultiPoint, typename Strategy> +struct distance + < + Areal, MultiPoint, Strategy, areal_tag, multi_point_tag, + strategy_tag_distance_point_segment, false + > : detail::distance::multipoint_to_areal<MultiPoint, Areal, Strategy> +{}; + + +} // namespace dispatch +#endif // DOXYGEN_NO_DISPATCH + + +}} // namespace boost::geometry + + +#endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_DISTANCE_MULTIPOINT_TO_GEOMETRY_HPP diff --git a/boost/geometry/algorithms/detail/distance/point_to_geometry.hpp b/boost/geometry/algorithms/detail/distance/point_to_geometry.hpp new file mode 100644 index 0000000000..ab5de3d9b2 --- /dev/null +++ b/boost/geometry/algorithms/detail/distance/point_to_geometry.hpp @@ -0,0 +1,518 @@ +// Boost.Geometry (aka GGL, Generic Geometry Library) + +// Copyright (c) 2007-2014 Barend Gehrels, Amsterdam, the Netherlands. +// Copyright (c) 2008-2014 Bruno Lalande, Paris, France. +// Copyright (c) 2009-2014 Mateusz Loskot, London, UK. +// Copyright (c) 2013-2014 Adam Wulkiewicz, Lodz, Poland. + +// This file was modified by Oracle on 2014. +// Modifications copyright (c) 2014, Oracle and/or its affiliates. + +// Contributed and/or modified by Menelaos Karavelas, on behalf of Oracle + +// Parts of Boost.Geometry are redesigned from Geodan's Geographic Library +// (geolib/GGL), copyright (c) 1995-2010 Geodan, Amsterdam, the Netherlands. + +// Use, modification and distribution is subject to the Boost Software License, +// Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at +// http://www.boost.org/LICENSE_1_0.txt) + +#ifndef BOOST_GEOMETRY_ALGORITHMS_DETAIL_DISTANCE_POINT_TO_GEOMETRY_HPP +#define BOOST_GEOMETRY_ALGORITHMS_DETAIL_DISTANCE_POINT_TO_GEOMETRY_HPP + +#include <iterator> + +#include <boost/core/ignore_unused.hpp> +#include <boost/range.hpp> +#include <boost/type_traits/is_same.hpp> + +#include <boost/geometry/core/closure.hpp> +#include <boost/geometry/core/point_type.hpp> +#include <boost/geometry/core/exterior_ring.hpp> +#include <boost/geometry/core/interior_rings.hpp> +#include <boost/geometry/core/tag.hpp> +#include <boost/geometry/core/tags.hpp> + +#include <boost/geometry/util/math.hpp> + +#include <boost/geometry/strategies/distance.hpp> +#include <boost/geometry/strategies/tags.hpp> + +#include <boost/geometry/algorithms/assign.hpp> +#include <boost/geometry/algorithms/covered_by.hpp> +#include <boost/geometry/algorithms/within.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/algorithms/detail/distance/iterator_selector.hpp> + +#include <boost/geometry/algorithms/dispatch/distance.hpp> + + +namespace boost { namespace geometry +{ + +#ifndef DOXYGEN_NO_DETAIL +namespace detail { namespace distance +{ + + +template <typename P1, typename P2, typename Strategy> +struct point_to_point +{ + static inline + typename strategy::distance::services::return_type<Strategy, P1, P2>::type + apply(P1 const& p1, P2 const& p2, Strategy const& strategy) + { + boost::ignore_unused(strategy); + return strategy.apply(p1, p2); + } +}; + + +template +< + typename Point, + typename Range, + closure_selector Closure, + typename Strategy +> +class point_to_range +{ +private: + typedef typename strategy::distance::services::comparable_type + < + Strategy + >::type comparable_strategy; + + typedef detail::closest_feature::point_to_point_range + < + Point, Range, Closure, comparable_strategy + > point_to_point_range; + +public: + typedef typename strategy::distance::services::return_type + < + Strategy, + Point, + typename boost::range_value<Range>::type + >::type return_type; + + static inline return_type apply(Point const& point, Range const& range, + Strategy const& strategy) + { + return_type const zero = return_type(0); + + if (boost::size(range) == 0) + { + return zero; + } + + namespace sds = strategy::distance::services; + + typename sds::return_type + < + comparable_strategy, + Point, + typename point_type<Range>::type + >::type cd_min; + + std::pair + < + typename boost::range_iterator<Range const>::type, + typename boost::range_iterator<Range const>::type + > it_pair + = point_to_point_range::apply(point, + boost::begin(range), + boost::end(range), + sds::get_comparable + < + Strategy + >::apply(strategy), + cd_min); + + return + is_comparable<Strategy>::value + ? + cd_min + : + strategy.apply(point, *it_pair.first, *it_pair.second); + } +}; + + +template +< + typename Point, + typename Ring, + closure_selector Closure, + typename Strategy +> +struct point_to_ring +{ + typedef typename strategy::distance::services::return_type + < + Strategy, Point, typename point_type<Ring>::type + >::type return_type; + + static inline return_type apply(Point const& point, + Ring const& ring, + Strategy const& strategy) + { + if (geometry::within(point, ring)) + { + return return_type(0); + } + + return point_to_range + < + Point, Ring, closure<Ring>::value, Strategy + >::apply(point, ring, strategy); + } +}; + + +template +< + typename Point, + typename Polygon, + closure_selector Closure, + typename Strategy +> +class point_to_polygon +{ +public: + typedef typename strategy::distance::services::return_type + < + Strategy, Point, typename point_type<Polygon>::type + >::type return_type; + +private: + typedef point_to_range + < + Point, typename ring_type<Polygon>::type, Closure, Strategy + > per_ring; + + struct distance_to_interior_rings + { + template <typename InteriorRingIterator> + static inline return_type apply(Point const& point, + InteriorRingIterator first, + InteriorRingIterator last, + Strategy const& strategy) + { + for (InteriorRingIterator it = first; it != last; ++it) + { + if (geometry::within(point, *it)) + { + // the point is inside a polygon hole, so its distance + // to the polygon its distance to the polygon's + // hole boundary + return per_ring::apply(point, *it, strategy); + } + } + return 0; + } + + template <typename InteriorRings> + static inline return_type apply(Point const& point, + InteriorRings const& interior_rings, + Strategy const& strategy) + { + return apply(point, + boost::begin(interior_rings), + boost::end(interior_rings), + strategy); + } + }; + + +public: + static inline return_type apply(Point const& point, + Polygon const& polygon, + Strategy const& strategy) + { + if (!geometry::covered_by(point, exterior_ring(polygon))) + { + // the point is outside the exterior ring, so its distance + // to the polygon is its distance to the polygon's exterior ring + return per_ring::apply(point, exterior_ring(polygon), strategy); + } + + // Check interior rings + return distance_to_interior_rings::apply(point, + interior_rings(polygon), + strategy); + } +}; + + +template +< + typename Point, + typename MultiGeometry, + typename Strategy, + bool CheckCoveredBy = boost::is_same + < + typename tag<MultiGeometry>::type, multi_polygon_tag + >::value +> +class point_to_multigeometry +{ +private: + typedef detail::closest_feature::geometry_to_range geometry_to_range; + +public: + typedef typename strategy::distance::services::return_type + < + Strategy, + Point, + typename point_type<MultiGeometry>::type + >::type return_type; + + static inline return_type apply(Point const& point, + MultiGeometry const& multigeometry, + Strategy const& strategy) + { + typedef iterator_selector<MultiGeometry const> selector_type; + + namespace sds = strategy::distance::services; + + typename sds::return_type + < + typename sds::comparable_type<Strategy>::type, + Point, + typename point_type<MultiGeometry>::type + >::type cd; + + typename selector_type::iterator_type it_min + = geometry_to_range::apply(point, + selector_type::begin(multigeometry), + selector_type::end(multigeometry), + sds::get_comparable + < + Strategy + >::apply(strategy), + cd); + + return + is_comparable<Strategy>::value + ? + cd + : + dispatch::distance + < + Point, + typename std::iterator_traits + < + typename selector_type::iterator_type + >::value_type, + Strategy + >::apply(point, *it_min, strategy); + } +}; + + +// this is called only for multipolygons, hence the change in the +// template parameter name MultiGeometry to MultiPolygon +template <typename Point, typename MultiPolygon, typename Strategy> +struct point_to_multigeometry<Point, MultiPolygon, Strategy, true> +{ + typedef typename strategy::distance::services::return_type + < + Strategy, + Point, + typename point_type<MultiPolygon>::type + >::type return_type; + + static inline return_type apply(Point const& point, + MultiPolygon const& multipolygon, + Strategy const& strategy) + { + if (geometry::covered_by(point, multipolygon)) + { + return 0; + } + + return point_to_multigeometry + < + Point, MultiPolygon, Strategy, false + >::apply(point, multipolygon, strategy); + } +}; + + +}} // namespace detail::distance +#endif // DOXYGEN_NO_DETAIL + + + + +#ifndef DOXYGEN_NO_DISPATCH +namespace dispatch +{ + + +// Point-point +template <typename P1, typename P2, typename Strategy> +struct distance + < + P1, P2, Strategy, point_tag, point_tag, + strategy_tag_distance_point_point, false + > : detail::distance::point_to_point<P1, P2, Strategy> +{}; + + +// Point-line version 2, where point-segment strategy is specified +template <typename Point, typename Linestring, typename Strategy> +struct distance + < + Point, Linestring, Strategy, point_tag, linestring_tag, + strategy_tag_distance_point_segment, false + > : detail::distance::point_to_range<Point, Linestring, closed, Strategy> +{}; + + +// Point-ring , where point-segment strategy is specified +template <typename Point, typename Ring, typename Strategy> +struct distance + < + Point, Ring, Strategy, point_tag, ring_tag, + strategy_tag_distance_point_segment, false + > : detail::distance::point_to_ring + < + Point, Ring, closure<Ring>::value, Strategy + > +{}; + + +// Point-polygon , where point-segment strategy is specified +template <typename Point, typename Polygon, typename Strategy> +struct distance + < + Point, Polygon, Strategy, point_tag, polygon_tag, + strategy_tag_distance_point_segment, false + > : detail::distance::point_to_polygon + < + Point, Polygon, closure<Polygon>::value, Strategy + > +{}; + + +// Point-segment version 2, with point-segment strategy +template <typename Point, typename Segment, typename Strategy> +struct distance + < + Point, Segment, Strategy, point_tag, segment_tag, + strategy_tag_distance_point_segment, false + > +{ + static inline typename strategy::distance::services::return_type + < + Strategy, Point, typename point_type<Segment>::type + >::type apply(Point const& point, + Segment const& segment, + Strategy const& strategy) + { + typename point_type<Segment>::type p[2]; + geometry::detail::assign_point_from_index<0>(segment, p[0]); + geometry::detail::assign_point_from_index<1>(segment, p[1]); + + boost::ignore_unused(strategy); + return strategy.apply(point, p[0], p[1]); + } +}; + + +template <typename Point, typename Box, typename Strategy> +struct distance + < + Point, Box, Strategy, point_tag, box_tag, + strategy_tag_distance_point_box, false + > +{ + static inline typename strategy::distance::services::return_type + < + Strategy, Point, typename point_type<Box>::type + >::type + apply(Point const& point, Box const& box, Strategy const& strategy) + { + boost::ignore_unused(strategy); + return strategy.apply(point, box); + } +}; + + +template<typename Point, typename MultiPoint, typename Strategy> +struct distance + < + Point, MultiPoint, Strategy, point_tag, multi_point_tag, + strategy_tag_distance_point_point, false + > : detail::distance::point_to_multigeometry + < + Point, MultiPoint, Strategy + > +{}; + + +template<typename Point, typename MultiLinestring, typename Strategy> +struct distance + < + Point, MultiLinestring, Strategy, point_tag, multi_linestring_tag, + strategy_tag_distance_point_segment, false + > : detail::distance::point_to_multigeometry + < + Point, MultiLinestring, Strategy + > +{}; + + +template<typename Point, typename MultiPolygon, typename Strategy> +struct distance + < + Point, MultiPolygon, Strategy, point_tag, multi_polygon_tag, + strategy_tag_distance_point_segment, false + > : detail::distance::point_to_multigeometry + < + Point, MultiPolygon, Strategy + > +{}; + + +template <typename Point, typename Linear, typename Strategy> +struct distance + < + Point, Linear, Strategy, point_tag, linear_tag, + strategy_tag_distance_point_segment, false + > : distance + < + Point, Linear, Strategy, + point_tag, typename tag<Linear>::type, + strategy_tag_distance_point_segment, false + > +{}; + + +template <typename Point, typename Areal, typename Strategy> +struct distance + < + Point, Areal, Strategy, point_tag, areal_tag, + strategy_tag_distance_point_segment, false + > : distance + < + Point, Areal, Strategy, + point_tag, typename tag<Areal>::type, + strategy_tag_distance_point_segment, false + > +{}; + + +} // namespace dispatch +#endif // DOXYGEN_NO_DISPATCH + + +}} // namespace boost::geometry + + +#endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_DISTANCE_POINT_TO_GEOMETRY_HPP diff --git a/boost/geometry/algorithms/detail/distance/range_to_geometry_rtree.hpp b/boost/geometry/algorithms/detail/distance/range_to_geometry_rtree.hpp new file mode 100644 index 0000000000..78189794a1 --- /dev/null +++ b/boost/geometry/algorithms/detail/distance/range_to_geometry_rtree.hpp @@ -0,0 +1,131 @@ +// 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_RANGE_TO_GEOMETRY_RTREE_HPP +#define BOOST_GEOMETRY_ALGORITHMS_DETAIL_DISTANCE_RANGE_TO_GEOMETRY_RTREE_HPP + +#include <iterator> +#include <utility> + +#include <boost/assert.hpp> + +#include <boost/geometry/core/point_type.hpp> + +#include <boost/geometry/iterators/has_one_element.hpp> + +#include <boost/geometry/strategies/distance.hpp> + +#include <boost/geometry/algorithms/dispatch/distance.hpp> + +#include <boost/geometry/algorithms/detail/closest_feature/range_to_range.hpp> +#include <boost/geometry/algorithms/detail/distance/is_comparable.hpp> +#include <boost/geometry/algorithms/detail/distance/iterator_selector.hpp> + + +namespace boost { namespace geometry +{ + + +#ifndef DOXYGEN_NO_DETAIL +namespace detail { namespace distance +{ + + +template +< + typename PointOrSegmentIterator, + typename Geometry, + typename Strategy +> +class point_or_segment_range_to_geometry_rtree +{ +private: + typedef typename std::iterator_traits + < + PointOrSegmentIterator + >::value_type point_or_segment_type; + + typedef iterator_selector<Geometry const> selector_type; + + typedef detail::closest_feature::range_to_range_rtree range_to_range; + +public: + typedef typename strategy::distance::services::return_type + < + Strategy, + typename point_type<point_or_segment_type>::type, + typename point_type<Geometry>::type + >::type return_type; + + static inline return_type apply(PointOrSegmentIterator first, + PointOrSegmentIterator last, + Geometry const& geometry, + Strategy const& strategy) + { + namespace sds = strategy::distance::services; + + BOOST_ASSERT( first != last ); + + if ( geometry::has_one_element(first, last) ) + { + return dispatch::distance + < + point_or_segment_type, Geometry, Strategy + >::apply(*first, geometry, strategy); + } + + typename sds::return_type + < + typename sds::comparable_type<Strategy>::type, + typename point_type<point_or_segment_type>::type, + typename point_type<Geometry>::type + >::type cd_min; + + std::pair + < + point_or_segment_type, + typename selector_type::iterator_type + > closest_features + = range_to_range::apply(first, + last, + selector_type::begin(geometry), + selector_type::end(geometry), + sds::get_comparable + < + Strategy + >::apply(strategy), + cd_min); + + return + is_comparable<Strategy>::value + ? + cd_min + : + dispatch::distance + < + point_or_segment_type, + typename std::iterator_traits + < + typename selector_type::iterator_type + >::value_type, + Strategy + >::apply(closest_features.first, + *closest_features.second, + strategy); + } +}; + + +}} // namespace detail::distance +#endif // DOXYGEN_NO_DETAIL + + +}} // namespace boost::geometry + +#endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_DISTANCE_RANGE_TO_GEOMETRY_RTREE_HPP diff --git a/boost/geometry/algorithms/detail/distance/segment_to_box.hpp b/boost/geometry/algorithms/detail/distance/segment_to_box.hpp new file mode 100644 index 0000000000..f64a3e9fca --- /dev/null +++ b/boost/geometry/algorithms/detail/distance/segment_to_box.hpp @@ -0,0 +1,886 @@ +// 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_SEGMENT_TO_BOX_HPP +#define BOOST_GEOMETRY_ALGORITHMS_DETAIL_DISTANCE_SEGMENT_TO_BOX_HPP + +#include <cstddef> + +#include <functional> +#include <vector> + +#include <boost/assert.hpp> +#include <boost/core/ignore_unused.hpp> +#include <boost/mpl/if.hpp> +#include <boost/numeric/conversion/cast.hpp> +#include <boost/type_traits/is_same.hpp> + +#include <boost/geometry/core/access.hpp> +#include <boost/geometry/core/closure.hpp> +#include <boost/geometry/core/coordinate_dimension.hpp> +#include <boost/geometry/core/point_type.hpp> +#include <boost/geometry/core/tags.hpp> + +#include <boost/geometry/util/calculation_type.hpp> +#include <boost/geometry/util/math.hpp> + +#include <boost/geometry/strategies/distance.hpp> +#include <boost/geometry/strategies/tags.hpp> + +#include <boost/geometry/policies/compare.hpp> + +#include <boost/geometry/algorithms/equals.hpp> +#include <boost/geometry/algorithms/intersects.hpp> +#include <boost/geometry/algorithms/not_implemented.hpp> + +#include <boost/geometry/algorithms/detail/assign_box_corners.hpp> +#include <boost/geometry/algorithms/detail/assign_indexed_point.hpp> +#include <boost/geometry/algorithms/detail/distance/default_strategies.hpp> +#include <boost/geometry/algorithms/detail/distance/is_comparable.hpp> + +#include <boost/geometry/algorithms/dispatch/distance.hpp> + + + +namespace boost { namespace geometry +{ + + +#ifndef DOXYGEN_NO_DETAIL +namespace detail { namespace distance +{ + + +template +< + typename Segment, + typename Box, + typename Strategy, + bool UsePointBoxStrategy = false +> +class segment_to_box_2D_generic +{ +private: + typedef typename point_type<Segment>::type segment_point; + typedef typename point_type<Box>::type box_point; + + typedef typename strategy::distance::services::comparable_type + < + Strategy + >::type comparable_strategy; + + typedef detail::closest_feature::point_to_point_range + < + segment_point, + std::vector<box_point>, + open, + comparable_strategy + > point_to_point_range; + + typedef typename strategy::distance::services::return_type + < + comparable_strategy, segment_point, box_point + >::type comparable_return_type; + +public: + typedef typename strategy::distance::services::return_type + < + Strategy, segment_point, box_point + >::type return_type; + + static inline return_type apply(Segment const& segment, + Box const& box, + Strategy const& strategy, + bool check_intersection = true) + { + if (check_intersection && geometry::intersects(segment, box)) + { + return 0; + } + + comparable_strategy cstrategy = + strategy::distance::services::get_comparable + < + Strategy + >::apply(strategy); + + // get segment points + segment_point p[2]; + detail::assign_point_from_index<0>(segment, p[0]); + detail::assign_point_from_index<1>(segment, p[1]); + + // get box points + std::vector<box_point> box_points(4); + detail::assign_box_corners_oriented<true>(box, box_points); + + comparable_return_type cd[6]; + for (unsigned int i = 0; i < 4; ++i) + { + cd[i] = cstrategy.apply(box_points[i], p[0], p[1]); + } + + std::pair + < + typename std::vector<box_point>::const_iterator, + typename std::vector<box_point>::const_iterator + > bit_min[2]; + + bit_min[0] = point_to_point_range::apply(p[0], + box_points.begin(), + box_points.end(), + cstrategy, + cd[4]); + bit_min[1] = point_to_point_range::apply(p[1], + box_points.begin(), + box_points.end(), + cstrategy, + cd[5]); + + unsigned int imin = 0; + for (unsigned int i = 1; i < 6; ++i) + { + if (cd[i] < cd[imin]) + { + imin = i; + } + } + + if (is_comparable<Strategy>::value) + { + return cd[imin]; + } + + if (imin < 4) + { + return strategy.apply(box_points[imin], p[0], p[1]); + } + else + { + unsigned int bimin = imin - 4; + return strategy.apply(p[bimin], + *bit_min[bimin].first, + *bit_min[bimin].second); + } + } +}; + + +template +< + typename Segment, + typename Box, + typename Strategy +> +class segment_to_box_2D_generic<Segment, Box, Strategy, true> +{ +private: + typedef typename point_type<Segment>::type segment_point; + typedef typename point_type<Box>::type box_point; + + typedef typename strategy::distance::services::comparable_type + < + Strategy + >::type comparable_strategy; + + typedef typename strategy::distance::services::return_type + < + comparable_strategy, segment_point, box_point + >::type comparable_return_type; + + typedef typename detail::distance::default_strategy + < + segment_point, Box + >::type point_box_strategy; + + typedef typename strategy::distance::services::comparable_type + < + point_box_strategy + >::type point_box_comparable_strategy; + +public: + typedef typename strategy::distance::services::return_type + < + Strategy, segment_point, box_point + >::type return_type; + + static inline return_type apply(Segment const& segment, + Box const& box, + Strategy const& strategy, + bool check_intersection = true) + { + if (check_intersection && geometry::intersects(segment, box)) + { + return 0; + } + + comparable_strategy cstrategy = + strategy::distance::services::get_comparable + < + Strategy + >::apply(strategy); + boost::ignore_unused(cstrategy); + + // get segment points + segment_point p[2]; + detail::assign_point_from_index<0>(segment, p[0]); + detail::assign_point_from_index<1>(segment, p[1]); + + // get box points + std::vector<box_point> box_points(4); + detail::assign_box_corners_oriented<true>(box, box_points); + + comparable_return_type cd[6]; + for (unsigned int i = 0; i < 4; ++i) + { + cd[i] = cstrategy.apply(box_points[i], p[0], p[1]); + } + + point_box_comparable_strategy pb_cstrategy; + boost::ignore_unused(pb_cstrategy); + cd[4] = pb_cstrategy.apply(p[0], box); + cd[5] = pb_cstrategy.apply(p[1], box); + + unsigned int imin = 0; + for (unsigned int i = 1; i < 6; ++i) + { + if (cd[i] < cd[imin]) + { + imin = i; + } + } + + if (is_comparable<Strategy>::value) + { + return cd[imin]; + } + + if (imin < 4) + { + strategy.apply(box_points[imin], p[0], p[1]); + } + else + { + return point_box_strategy().apply(p[imin - 4], box); + } + } +}; + + + + +template +< + typename ReturnType, + typename SegmentPoint, + typename BoxPoint, + typename PPStrategy, + typename PSStrategy +> +class segment_to_box_2D +{ +private: + template <typename Result> + struct cast_to_result + { + template <typename T> + static inline Result apply(T const& t) + { + return boost::numeric_cast<Result>(t); + } + }; + + + template <typename T, bool IsLess /* true */> + struct compare_less_equal + { + typedef compare_less_equal<T, !IsLess> other; + + template <typename T1, typename T2> + inline bool operator()(T1 const& t1, T2 const& t2) const + { + return std::less_equal<T>()(cast_to_result<T>::apply(t1), + cast_to_result<T>::apply(t2)); + } + }; + + template <typename T> + struct compare_less_equal<T, false> + { + typedef compare_less_equal<T, true> other; + + template <typename T1, typename T2> + inline bool operator()(T1 const& t1, T2 const& t2) const + { + return std::greater_equal<T>()(cast_to_result<T>::apply(t1), + cast_to_result<T>::apply(t2)); + } + }; + + + template <typename LessEqual> + struct other_compare + { + typedef typename LessEqual::other type; + }; + + + // it is assumed here that p0 lies to the right of the box (so the + // entire segment lies to the right of the box) + template <typename LessEqual> + struct right_of_box + { + static inline ReturnType apply(SegmentPoint const& p0, + SegmentPoint const& p1, + BoxPoint const& bottom_right, + BoxPoint const& top_right, + PPStrategy const& pp_strategy, + PSStrategy const& ps_strategy) + { + boost::ignore_unused(pp_strategy, ps_strategy); + + // the implementation below is written for non-negative slope + // segments + // + // for negative slope segments swap the roles of bottom_right + // and top_right and use greater_equal instead of less_equal. + + typedef cast_to_result<ReturnType> cast; + + LessEqual less_equal; + + if (less_equal(geometry::get<1>(top_right), geometry::get<1>(p0))) + { + // closest box point is the top-right corner + return cast::apply(pp_strategy.apply(p0, top_right)); + } + else if (less_equal(geometry::get<1>(bottom_right), + geometry::get<1>(p0))) + { + // distance is realized between p0 and right-most + // segment of box + ReturnType diff = cast::apply(geometry::get<0>(p0)) + - cast::apply(geometry::get<0>(bottom_right)); + return strategy::distance::services::result_from_distance + < + PSStrategy, BoxPoint, SegmentPoint + >::apply(ps_strategy, math::abs(diff)); + } + else + { + // distance is realized between the bottom-right + // corner of the box and the segment + return cast::apply(ps_strategy.apply(bottom_right, p0, p1)); + } + } + }; + + + // it is assumed here that p0 lies above the box (so the + // entire segment lies above the box) + template <typename LessEqual> + struct above_of_box + { + static inline ReturnType apply(SegmentPoint const& p0, + SegmentPoint const& p1, + BoxPoint const& top_left, + PSStrategy const& ps_strategy) + { + boost::ignore_unused(ps_strategy); + + // the segment lies above the box + + typedef cast_to_result<ReturnType> cast; + + LessEqual less_equal; + + // p0 is above the upper segment of the box + // (and inside its band) + if (less_equal(geometry::get<0>(top_left), geometry::get<0>(p0))) + { + ReturnType diff = cast::apply(geometry::get<1>(p0)) + - cast::apply(geometry::get<1>(top_left)); + return strategy::distance::services::result_from_distance + < + PSStrategy, SegmentPoint, BoxPoint + >::apply(ps_strategy, math::abs(diff)); + } + + // p0 is to the left of the box, but p1 is above the box + // in this case the distance is realized between the + // top-left corner of the box and the segment + return cast::apply(ps_strategy.apply(top_left, p0, p1)); + } + }; + + + template <typename LessEqual> + struct check_right_left_of_box + { + static inline bool apply(SegmentPoint const& p0, + SegmentPoint const& p1, + BoxPoint const& top_left, + BoxPoint const& top_right, + BoxPoint const& bottom_left, + BoxPoint const& bottom_right, + PPStrategy const& pp_strategy, + PSStrategy const& ps_strategy, + ReturnType& result) + { + // p0 lies to the right of the box + if (geometry::get<0>(p0) >= geometry::get<0>(top_right)) + { + result = right_of_box + < + LessEqual + >::apply(p0, p1, bottom_right, top_right, + pp_strategy, ps_strategy); + return true; + } + + // p1 lies to the left of the box + if (geometry::get<0>(p1) <= geometry::get<0>(bottom_left)) + { + result = right_of_box + < + typename other_compare<LessEqual>::type + >::apply(p1, p0, top_left, bottom_left, + pp_strategy, ps_strategy); + return true; + } + + return false; + } + }; + + + template <typename LessEqual> + struct check_above_below_of_box + { + static inline bool apply(SegmentPoint const& p0, + SegmentPoint const& p1, + BoxPoint const& top_left, + BoxPoint const& top_right, + BoxPoint const& bottom_left, + BoxPoint const& bottom_right, + PSStrategy const& ps_strategy, + ReturnType& result) + { + // the segment lies below the box + if (geometry::get<1>(p1) < geometry::get<1>(bottom_left)) + { + result = above_of_box + < + typename other_compare<LessEqual>::type + >::apply(p1, p0, bottom_right, ps_strategy); + return true; + } + + // the segment lies above the box + if (geometry::get<1>(p0) > geometry::get<1>(top_right)) + { + result = above_of_box + < + LessEqual + >::apply(p0, p1, top_left, ps_strategy); + return true; + } + return false; + } + }; + + struct check_generic_position + { + static inline bool apply(SegmentPoint const& p0, + SegmentPoint const& p1, + BoxPoint const& bottom_left0, + BoxPoint const& top_right0, + BoxPoint const& bottom_left1, + BoxPoint const& top_right1, + BoxPoint const& corner1, + BoxPoint const& corner2, + PSStrategy const& ps_strategy, + ReturnType& result) + { + typedef cast_to_result<ReturnType> cast; + + ReturnType diff0 = cast::apply(geometry::get<0>(p1)) + - cast::apply(geometry::get<0>(p0)); + ReturnType t_min0 = cast::apply(geometry::get<0>(bottom_left0)) + - cast::apply(geometry::get<0>(p0)); + ReturnType t_max0 = cast::apply(geometry::get<0>(top_right0)) + - cast::apply(geometry::get<0>(p0)); + + ReturnType diff1 = cast::apply(geometry::get<1>(p1)) + - cast::apply(geometry::get<1>(p0)); + ReturnType t_min1 = cast::apply(geometry::get<1>(bottom_left1)) + - cast::apply(geometry::get<1>(p0)); + ReturnType t_max1 = cast::apply(geometry::get<1>(top_right1)) + - cast::apply(geometry::get<1>(p0)); + + if (diff1 < 0) + { + diff1 = -diff1; + t_min1 = -t_min1; + t_max1 = -t_max1; + } + + // t_min0 > t_max1 + if (t_min0 * diff1 > t_max1 * diff0) + { + result = cast::apply(ps_strategy.apply(corner1, p0, p1)); + return true; + } + + // t_max0 < t_min1 + if (t_max0 * diff1 < t_min1 * diff0) + { + result = cast::apply(ps_strategy.apply(corner2, p0, p1)); + return true; + } + return false; + } + }; + + static inline ReturnType + non_negative_slope_segment(SegmentPoint const& p0, + SegmentPoint const& p1, + BoxPoint const& top_left, + BoxPoint const& top_right, + BoxPoint const& bottom_left, + BoxPoint const& bottom_right, + PPStrategy const& pp_strategy, + PSStrategy const& ps_strategy) + { + typedef compare_less_equal<ReturnType, true> less_equal; + + // assert that the segment has non-negative slope + BOOST_ASSERT( ( math::equals(geometry::get<0>(p0), geometry::get<0>(p1)) + && geometry::get<1>(p0) < geometry::get<1>(p1)) + || + ( geometry::get<0>(p0) < geometry::get<0>(p1) + && geometry::get<1>(p0) <= geometry::get<1>(p1) ) + ); + + ReturnType result(0); + + if (check_right_left_of_box + < + less_equal + >::apply(p0, p1, + top_left, top_right, bottom_left, bottom_right, + pp_strategy, ps_strategy, result)) + { + return result; + } + + if (check_above_below_of_box + < + less_equal + >::apply(p0, p1, + top_left, top_right, bottom_left, bottom_right, + ps_strategy, result)) + { + return result; + } + + if (check_generic_position::apply(p0, p1, + bottom_left, top_right, + bottom_left, top_right, + top_left, bottom_right, + ps_strategy, result)) + { + return result; + } + + // in all other cases the box and segment intersect, so return 0 + return result; + } + + + static inline ReturnType + negative_slope_segment(SegmentPoint const& p0, + SegmentPoint const& p1, + BoxPoint const& top_left, + BoxPoint const& top_right, + BoxPoint const& bottom_left, + BoxPoint const& bottom_right, + PPStrategy const& pp_strategy, + PSStrategy const& ps_strategy) + { + typedef compare_less_equal<ReturnType, false> greater_equal; + + // assert that the segment has negative slope + BOOST_ASSERT( geometry::get<0>(p0) < geometry::get<0>(p1) + && geometry::get<1>(p0) > geometry::get<1>(p1) ); + + ReturnType result(0); + + if (check_right_left_of_box + < + greater_equal + >::apply(p0, p1, + bottom_left, bottom_right, top_left, top_right, + pp_strategy, ps_strategy, result)) + { + return result; + } + + if (check_above_below_of_box + < + greater_equal + >::apply(p1, p0, + top_right, top_left, bottom_right, bottom_left, + ps_strategy, result)) + { + return result; + } + + if (check_generic_position::apply(p0, p1, + bottom_left, top_right, + top_right, bottom_left, + bottom_left, top_right, + ps_strategy, result)) + { + return result; + } + + // in all other cases the box and segment intersect, so return 0 + return result; + } + +public: + static inline ReturnType apply(SegmentPoint const& p0, + SegmentPoint const& p1, + BoxPoint const& top_left, + BoxPoint const& top_right, + BoxPoint const& bottom_left, + BoxPoint const& bottom_right, + PPStrategy const& pp_strategy, + PSStrategy const& ps_strategy) + { + BOOST_ASSERT( geometry::less<SegmentPoint>()(p0, p1) ); + + if (geometry::get<0>(p0) < geometry::get<0>(p1) + && geometry::get<1>(p0) > geometry::get<1>(p1)) + { + return negative_slope_segment(p0, p1, + top_left, top_right, + bottom_left, bottom_right, + pp_strategy, ps_strategy); + } + + return non_negative_slope_segment(p0, p1, + top_left, top_right, + bottom_left, bottom_right, + pp_strategy, ps_strategy); + } +}; + + +//========================================================================= + + +template +< + typename Segment, + typename Box, + typename std::size_t Dimension, + typename PPStrategy, + typename PSStrategy +> +class segment_to_box + : not_implemented<Segment, Box> +{}; + + +template +< + typename Segment, + typename Box, + typename PPStrategy, + typename PSStrategy +> +class segment_to_box<Segment, Box, 2, PPStrategy, PSStrategy> +{ +private: + typedef typename point_type<Segment>::type segment_point; + typedef typename point_type<Box>::type box_point; + + typedef typename strategy::distance::services::comparable_type + < + PPStrategy + >::type pp_comparable_strategy; + + typedef typename strategy::distance::services::comparable_type + < + PSStrategy + >::type ps_comparable_strategy; + + typedef typename strategy::distance::services::return_type + < + ps_comparable_strategy, segment_point, box_point + >::type comparable_return_type; +public: + typedef typename strategy::distance::services::return_type + < + PSStrategy, segment_point, box_point + >::type return_type; + + static inline return_type apply(Segment const& segment, + Box const& box, + PPStrategy const& pp_strategy, + PSStrategy const& ps_strategy) + { + segment_point p[2]; + detail::assign_point_from_index<0>(segment, p[0]); + detail::assign_point_from_index<1>(segment, p[1]); + + if (geometry::equals(p[0], p[1])) + { + typedef typename boost::mpl::if_ + < + boost::is_same + < + ps_comparable_strategy, + PSStrategy + >, + typename strategy::distance::services::comparable_type + < + typename detail::distance::default_strategy + < + segment_point, Box + >::type + >::type, + typename detail::distance::default_strategy + < + segment_point, Box + >::type + >::type point_box_strategy_type; + + return dispatch::distance + < + segment_point, + Box, + point_box_strategy_type + >::apply(p[0], box, point_box_strategy_type()); + } + + box_point top_left, top_right, bottom_left, bottom_right; + detail::assign_box_corners(box, bottom_left, bottom_right, + top_left, top_right); + + if (geometry::less<segment_point>()(p[0], p[1])) + { + return segment_to_box_2D + < + return_type, + segment_point, + box_point, + PPStrategy, + PSStrategy + >::apply(p[0], p[1], + top_left, top_right, bottom_left, bottom_right, + pp_strategy, + ps_strategy); + } + else + { + return segment_to_box_2D + < + return_type, + segment_point, + box_point, + PPStrategy, + PSStrategy + >::apply(p[1], p[0], + top_left, top_right, bottom_left, bottom_right, + pp_strategy, + ps_strategy); + } + } +}; + + +}} // namespace detail::distance +#endif // DOXYGEN_NO_DETAIL + + +#ifndef DOXYGEN_NO_DISPATCH +namespace dispatch +{ + + +template <typename Segment, typename Box, typename Strategy> +struct distance + < + Segment, Box, Strategy, segment_tag, box_tag, + strategy_tag_distance_point_segment, false + > +{ + typedef typename strategy::distance::services::return_type + < + Strategy, + typename point_type<Segment>::type, + typename point_type<Box>::type + >::type return_type; + + + static inline return_type apply(Segment const& segment, + Box const& box, + Strategy const& strategy) + { + assert_dimension_equal<Segment, Box>(); + + typedef typename boost::mpl::if_ + < + boost::is_same + < + typename strategy::distance::services::comparable_type + < + Strategy + >::type, + Strategy + >, + typename strategy::distance::services::comparable_type + < + typename detail::distance::default_strategy + < + typename point_type<Segment>::type, + typename point_type<Box>::type + >::type + >::type, + typename detail::distance::default_strategy + < + typename point_type<Segment>::type, + typename point_type<Box>::type + >::type + >::type pp_strategy_type; + + + return detail::distance::segment_to_box + < + Segment, + Box, + dimension<Segment>::value, + pp_strategy_type, + Strategy + >::apply(segment, box, pp_strategy_type(), strategy); + } +}; + + + +} // namespace dispatch +#endif // DOXYGEN_NO_DISPATCH + + +}} // namespace boost::geometry + + +#endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_DISTANCE_SEGMENT_TO_BOX_HPP diff --git a/boost/geometry/algorithms/detail/distance/segment_to_segment.hpp b/boost/geometry/algorithms/detail/distance/segment_to_segment.hpp new file mode 100644 index 0000000000..2dcde64946 --- /dev/null +++ b/boost/geometry/algorithms/detail/distance/segment_to_segment.hpp @@ -0,0 +1,150 @@ +// 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_SEGMENT_TO_SEGMENT_HPP +#define BOOST_GEOMETRY_ALGORITHMS_DETAIL_DISTANCE_SEGMENT_TO_SEGMENT_HPP + +#include <algorithm> +#include <iterator> + +#include <boost/core/addressof.hpp> + +#include <boost/geometry/core/point_type.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/detail/distance/is_comparable.hpp> + +#include <boost/geometry/algorithms/dispatch/distance.hpp> + + +namespace boost { namespace geometry +{ + + +#ifndef DOXYGEN_NO_DETAIL +namespace detail { namespace distance +{ + + + +// compute segment-segment distance +template<typename Segment1, typename Segment2, typename Strategy> +class segment_to_segment +{ +private: + typedef typename strategy::distance::services::comparable_type + < + Strategy + >::type comparable_strategy; + + typedef typename strategy::distance::services::return_type + < + comparable_strategy, + typename point_type<Segment1>::type, + typename point_type<Segment2>::type + >::type comparable_return_type; + +public: + typedef typename strategy::distance::services::return_type + < + Strategy, + typename point_type<Segment1>::type, + typename point_type<Segment2>::type + >::type return_type; + + static inline return_type + apply(Segment1 const& segment1, Segment2 const& segment2, + Strategy const& strategy) + { + if (geometry::intersects(segment1, segment2)) + { + return 0; + } + + typename point_type<Segment1>::type p[2]; + detail::assign_point_from_index<0>(segment1, p[0]); + detail::assign_point_from_index<1>(segment1, p[1]); + + typename point_type<Segment2>::type q[2]; + detail::assign_point_from_index<0>(segment2, q[0]); + detail::assign_point_from_index<1>(segment2, q[1]); + + comparable_strategy cstrategy = + strategy::distance::services::get_comparable + < + Strategy + >::apply(strategy); + + comparable_return_type d[4]; + d[0] = cstrategy.apply(q[0], p[0], p[1]); + d[1] = cstrategy.apply(q[1], p[0], p[1]); + d[2] = cstrategy.apply(p[0], q[0], q[1]); + d[3] = cstrategy.apply(p[1], q[0], q[1]); + + std::size_t imin = std::distance(boost::addressof(d[0]), + std::min_element(d, d + 4)); + + if (is_comparable<Strategy>::value) + { + return d[imin]; + } + + switch (imin) + { + case 0: + return strategy.apply(q[0], p[0], p[1]); + case 1: + return strategy.apply(q[1], p[0], p[1]); + case 2: + return strategy.apply(p[0], q[0], q[1]); + default: + return strategy.apply(p[1], q[0], q[1]); + } + } +}; + + + + +}} // namespace detail::distance +#endif // DOXYGEN_NO_DETAIL + + +#ifndef DOXYGEN_NO_DISPATCH +namespace dispatch +{ + + + +// segment-segment +template <typename Segment1, typename Segment2, typename Strategy> +struct distance + < + Segment1, Segment2, Strategy, segment_tag, segment_tag, + strategy_tag_distance_point_segment, false + > + : detail::distance::segment_to_segment<Segment1, Segment2, Strategy> +{}; + + + +} // namespace dispatch +#endif // DOXYGEN_NO_DISPATCH + + +}} // namespace boost::geometry + + +#endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_DISTANCE_SEGMENT_TO_SEGMENT_HPP |