diff options
Diffstat (limited to 'boost/geometry/algorithms/convex_hull.hpp')
| -rw-r--r-- | boost/geometry/algorithms/convex_hull.hpp | 262 |
1 files changed, 179 insertions, 83 deletions
diff --git a/boost/geometry/algorithms/convex_hull.hpp b/boost/geometry/algorithms/convex_hull.hpp index 56b87c8c15..09f4c5142d 100644 --- a/boost/geometry/algorithms/convex_hull.hpp +++ b/boost/geometry/algorithms/convex_hull.hpp @@ -4,6 +4,11 @@ // Copyright (c) 2008-2012 Bruno Lalande, Paris, France. // Copyright (c) 2009-2012 Mateusz Loskot, London, UK. +// This file was modified by Oracle on 2014. +// Modifications copyright (c) 2014 Oracle and/or its affiliates. + +// Contributed and/or modified by Adam Wulkiewicz, 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. @@ -15,15 +20,20 @@ #define BOOST_GEOMETRY_ALGORITHMS_CONVEX_HULL_HPP #include <boost/array.hpp> +#include <boost/variant/static_visitor.hpp> +#include <boost/variant/apply_visitor.hpp> +#include <boost/variant/variant_fwd.hpp> #include <boost/geometry/core/cs.hpp> #include <boost/geometry/core/point_order.hpp> +#include <boost/geometry/core/closure.hpp> #include <boost/geometry/core/exterior_ring.hpp> #include <boost/geometry/geometries/concepts/check.hpp> #include <boost/geometry/strategies/convex_hull.hpp> #include <boost/geometry/strategies/concepts/convex_hull_concept.hpp> +#include <boost/geometry/strategies/default_strategy.hpp> #include <boost/geometry/views/detail/range_type.hpp> @@ -40,45 +50,34 @@ namespace boost { namespace geometry namespace detail { namespace convex_hull { -template -< - typename Geometry, - order_selector Order, - typename Strategy -> +template <order_selector Order, closure_selector Closure> struct hull_insert { // Member template function (to avoid inconvenient declaration // of output-iterator-type, from hull_to_geometry) - template <typename OutputIterator> + template <typename Geometry, typename OutputIterator, typename Strategy> static inline OutputIterator apply(Geometry const& geometry, OutputIterator out, Strategy const& strategy) { typename Strategy::state_type state; strategy.apply(geometry, state); - strategy.result(state, out, Order == clockwise); + strategy.result(state, out, Order == clockwise, Closure != open); return out; } }; -template -< - typename Geometry, - typename Strategy -> struct hull_to_geometry { - template <typename OutputGeometry> + template <typename Geometry, typename OutputGeometry, typename Strategy> static inline void apply(Geometry const& geometry, OutputGeometry& out, Strategy const& strategy) { hull_insert < - Geometry, geometry::point_order<OutputGeometry>::value, - Strategy + geometry::closure<OutputGeometry>::value >::apply(geometry, std::back_inserter( // Handle linestring, ring and polygon the same: @@ -89,18 +88,6 @@ struct hull_to_geometry } }; - -// Helper metafunction for default strategy retrieval -template <typename Geometry> -struct default_strategy - : strategy_convex_hull - < - Geometry, - typename point_type<Geometry>::type - > -{}; - - }} // namespace detail::convex_hull #endif // DOXYGEN_NO_DETAIL @@ -113,21 +100,16 @@ namespace dispatch template < typename Geometry, - typename Strategy = typename detail::convex_hull::default_strategy<Geometry>::type, typename Tag = typename tag<Geometry>::type > struct convex_hull - : detail::convex_hull::hull_to_geometry<Geometry, Strategy> + : detail::convex_hull::hull_to_geometry {}; -template -< - typename Box, - typename Strategy -> -struct convex_hull<Box, Strategy, box_tag> +template <typename Box> +struct convex_hull<Box, box_tag> { - template <typename OutputGeometry> + template <typename OutputGeometry, typename Strategy> static inline void apply(Box const& box, OutputGeometry& out, Strategy const& ) { @@ -149,13 +131,9 @@ struct convex_hull<Box, Strategy, box_tag> -template -< - order_selector Order, - typename Geometry, typename Strategy -> +template <order_selector Order, closure_selector Closure> struct convex_hull_insert - : detail::convex_hull::hull_insert<Geometry, Order, Strategy> + : detail::convex_hull::hull_insert<Order, Closure> {}; @@ -163,29 +141,170 @@ struct convex_hull_insert #endif // DOXYGEN_NO_DISPATCH -template<typename Geometry, typename OutputGeometry, typename Strategy> -inline void convex_hull(Geometry const& geometry, - OutputGeometry& out, Strategy const& strategy) +namespace resolve_strategy { + +struct convex_hull { - concept::check_concepts_and_equal_dimensions - < + template <typename Geometry, typename OutputGeometry, typename Strategy> + static inline void apply(Geometry const& geometry, + OutputGeometry& out, + Strategy const& strategy) + { + BOOST_CONCEPT_ASSERT( (geometry::concept::ConvexHullStrategy<Strategy>) ); + dispatch::convex_hull<Geometry>::apply(geometry, out, strategy); + } + + template <typename Geometry, typename OutputGeometry> + static inline void apply(Geometry const& geometry, + OutputGeometry& out, + default_strategy) + { + typedef typename strategy_convex_hull< + Geometry, + typename point_type<Geometry>::type + >::type strategy_type; + + apply(geometry, out, strategy_type()); + } +}; + +struct convex_hull_insert +{ + template <typename Geometry, typename OutputIterator, typename Strategy> + static inline OutputIterator apply(Geometry const& geometry, + OutputIterator& out, + Strategy const& strategy) + { + BOOST_CONCEPT_ASSERT( (geometry::concept::ConvexHullStrategy<Strategy>) ); + + return dispatch::convex_hull_insert< + geometry::point_order<Geometry>::value, + geometry::closure<Geometry>::value + >::apply(geometry, out, strategy); + } + + template <typename Geometry, typename OutputIterator> + static inline OutputIterator apply(Geometry const& geometry, + OutputIterator& out, + default_strategy) + { + typedef typename strategy_convex_hull< + Geometry, + typename point_type<Geometry>::type + >::type strategy_type; + + return apply(geometry, out, strategy_type()); + } +}; + +} // namespace resolve_strategy + + +namespace resolve_variant { + +template <typename Geometry> +struct convex_hull +{ + template <typename OutputGeometry, typename Strategy> + static inline void apply(Geometry const& geometry, OutputGeometry& out, Strategy const& strategy) + { + concept::check_concepts_and_equal_dimensions< const Geometry, OutputGeometry >(); - BOOST_CONCEPT_ASSERT( (geometry::concept::ConvexHullStrategy<Strategy>) ); + resolve_strategy::convex_hull::apply(geometry, out, strategy); + } +}; + +template <BOOST_VARIANT_ENUM_PARAMS(typename T)> +struct convex_hull<boost::variant<BOOST_VARIANT_ENUM_PARAMS(T)> > +{ + template <typename OutputGeometry, typename Strategy> + struct visitor: boost::static_visitor<void> + { + OutputGeometry& m_out; + Strategy const& m_strategy; + + visitor(OutputGeometry& out, Strategy const& strategy) + : m_out(out), m_strategy(strategy) + {} + + template <typename Geometry> + void operator()(Geometry const& geometry) const + { + convex_hull<Geometry>::apply(geometry, m_out, m_strategy); + } + }; + + template <typename OutputGeometry, typename Strategy> + static inline void + apply(boost::variant<BOOST_VARIANT_ENUM_PARAMS(T)> const& geometry, + OutputGeometry& out, + Strategy const& strategy) + { + boost::apply_visitor(visitor<OutputGeometry, Strategy>(out, strategy), geometry); + } +}; + +template <typename Geometry> +struct convex_hull_insert +{ + template <typename OutputIterator, typename Strategy> + static inline OutputIterator apply(Geometry const& geometry, OutputIterator& out, Strategy const& strategy) + { + // Concept: output point type = point type of input geometry + concept::check<Geometry const>(); + concept::check<typename point_type<Geometry>::type>(); + + return resolve_strategy::convex_hull_insert::apply(geometry, out, strategy); + } +}; + +template <BOOST_VARIANT_ENUM_PARAMS(typename T)> +struct convex_hull_insert<boost::variant<BOOST_VARIANT_ENUM_PARAMS(T)> > +{ + template <typename OutputIterator, typename Strategy> + struct visitor: boost::static_visitor<OutputIterator> + { + OutputIterator& m_out; + Strategy const& m_strategy; + + visitor(OutputIterator& out, Strategy const& strategy) + : m_out(out), m_strategy(strategy) + {} + template <typename Geometry> + OutputIterator operator()(Geometry const& geometry) const + { + return convex_hull_insert<Geometry>::apply(geometry, m_out, m_strategy); + } + }; + + template <typename OutputIterator, typename Strategy> + static inline OutputIterator + apply(boost::variant<BOOST_VARIANT_ENUM_PARAMS(T)> const& geometry, + OutputIterator& out, + Strategy const& strategy) + { + return boost::apply_visitor(visitor<OutputIterator, Strategy>(out, strategy), geometry); + } +}; + +} // namespace resolve_variant + + +template<typename Geometry, typename OutputGeometry, typename Strategy> +inline void convex_hull(Geometry const& geometry, + OutputGeometry& out, Strategy const& strategy) +{ if (geometry::num_points(geometry) == 0) { // Leave output empty return; } - dispatch::convex_hull - < - Geometry, - Strategy - >::apply(geometry, out, strategy); + resolve_variant::convex_hull<Geometry>::apply(geometry, out, strategy); } @@ -193,8 +312,8 @@ inline void convex_hull(Geometry const& geometry, \brief \brief_calc{convex hull} \ingroup convex_hull \details \details_calc{convex_hull,convex hull}. -\tparam Geometry1 \tparam_geometry -\tparam Geometry2 \tparam_geometry +\tparam Geometry the input geometry type +\tparam OutputGeometry the output geometry type \param geometry \param_geometry, input geometry \param hull \param_geometry \param_set{convex hull} @@ -204,15 +323,7 @@ template<typename Geometry, typename OutputGeometry> inline void convex_hull(Geometry const& geometry, OutputGeometry& hull) { - concept::check_concepts_and_equal_dimensions - < - const Geometry, - OutputGeometry - >(); - - typedef typename detail::convex_hull::default_strategy<Geometry>::type strategy_type; - - convex_hull(geometry, hull, strategy_type()); + convex_hull(geometry, hull, default_strategy()); } #ifndef DOXYGEN_NO_DETAIL @@ -224,17 +335,8 @@ template<typename Geometry, typename OutputIterator, typename Strategy> inline OutputIterator convex_hull_insert(Geometry const& geometry, OutputIterator out, Strategy const& strategy) { - // Concept: output point type = point type of input geometry - concept::check<Geometry const>(); - concept::check<typename point_type<Geometry>::type>(); - - BOOST_CONCEPT_ASSERT( (geometry::concept::ConvexHullStrategy<Strategy>) ); - - return dispatch::convex_hull_insert - < - geometry::point_order<Geometry>::value, - Geometry, Strategy - >::apply(geometry, out, strategy); + return resolve_variant::convex_hull_insert<Geometry> + ::apply(geometry, out, strategy); } @@ -255,13 +357,7 @@ template<typename Geometry, typename OutputIterator> inline OutputIterator convex_hull_insert(Geometry const& geometry, OutputIterator out) { - // Concept: output point type = point type of input geometry - concept::check<Geometry const>(); - concept::check<typename point_type<Geometry>::type>(); - - typedef typename detail::convex_hull::default_strategy<Geometry>::type strategy_type; - - return convex_hull_insert(geometry, out, strategy_type()); + return convex_hull_insert(geometry, out, default_strategy()); } |