diff options
Diffstat (limited to 'boost/geometry/algorithms/detail/convex_hull/interface.hpp')
-rw-r--r-- | boost/geometry/algorithms/detail/convex_hull/interface.hpp | 619 |
1 files changed, 414 insertions, 205 deletions
diff --git a/boost/geometry/algorithms/detail/convex_hull/interface.hpp b/boost/geometry/algorithms/detail/convex_hull/interface.hpp index ce61c99802..b820cc4bf4 100644 --- a/boost/geometry/algorithms/detail/convex_hull/interface.hpp +++ b/boost/geometry/algorithms/detail/convex_hull/interface.hpp @@ -3,6 +3,7 @@ // Copyright (c) 2007-2015 Barend Gehrels, Amsterdam, the Netherlands. // Copyright (c) 2008-2015 Bruno Lalande, Paris, France. // Copyright (c) 2009-2015 Mateusz Loskot, London, UK. +// Copyright (c) 2023 Adam Wulkiewicz, Lodz, Poland. // This file was modified by Oracle on 2014-2021. // Modifications copyright (c) 2014-2021 Oracle and/or its affiliates. @@ -21,86 +22,171 @@ #ifndef BOOST_GEOMETRY_ALGORITHMS_CONVEX_HULL_INTERFACE_HPP #define BOOST_GEOMETRY_ALGORITHMS_CONVEX_HULL_INTERFACE_HPP -#include <boost/array.hpp> +#include <array> -#include <boost/variant/apply_visitor.hpp> -#include <boost/variant/static_visitor.hpp> -#include <boost/variant/variant_fwd.hpp> - -#include <boost/geometry/algorithms/detail/as_range.hpp> #include <boost/geometry/algorithms/detail/assign_box_corners.hpp> #include <boost/geometry/algorithms/detail/convex_hull/graham_andrew.hpp> +#include <boost/geometry/algorithms/detail/equals/point_point.hpp> +#include <boost/geometry/algorithms/detail/for_each_range.hpp> +#include <boost/geometry/algorithms/detail/select_geometry_type.hpp> +#include <boost/geometry/algorithms/detail/visit.hpp> #include <boost/geometry/algorithms/is_empty.hpp> #include <boost/geometry/core/closure.hpp> #include <boost/geometry/core/cs.hpp> #include <boost/geometry/core/exterior_ring.hpp> +#include <boost/geometry/core/geometry_types.hpp> #include <boost/geometry/core/point_order.hpp> #include <boost/geometry/core/ring_type.hpp> +#include <boost/geometry/core/tag.hpp> +#include <boost/geometry/core/tags.hpp> +#include <boost/geometry/core/visit.hpp> +#include <boost/geometry/geometries/adapted/boost_variant.hpp> // For backward compatibility #include <boost/geometry/geometries/concepts/check.hpp> +#include <boost/geometry/geometries/ring.hpp> -#include <boost/geometry/strategies/convex_hull/services.hpp> +#include <boost/geometry/strategies/convex_hull/cartesian.hpp> +#include <boost/geometry/strategies/convex_hull/geographic.hpp> +#include <boost/geometry/strategies/convex_hull/spherical.hpp> #include <boost/geometry/strategies/default_strategy.hpp> #include <boost/geometry/util/condition.hpp> +#include <boost/geometry/util/range.hpp> +#include <boost/geometry/util/sequence.hpp> +#include <boost/geometry/util/type_traits.hpp> namespace boost { namespace geometry { +// TODO: This file is named interface.hpp but the code below is not the interface. +// It's the implementation of the algorithm. #ifndef DOXYGEN_NO_DETAIL namespace detail { namespace convex_hull { -template <order_selector Order, closure_selector Closure> -struct hull_insert +// Abstraction representing ranges/rings of a geometry +template <typename Geometry> +struct input_geometry_proxy { - // Member template function (to avoid inconvenient declaration - // of output-iterator-type, from hull_to_geometry) - template <typename Geometry, typename OutputIterator, typename Strategy> - static inline OutputIterator apply(Geometry const& geometry, - OutputIterator out, - Strategy const& strategy) + input_geometry_proxy(Geometry const& geometry) + : m_geometry(geometry) + {} + + template <typename UnaryFunction> + inline void for_each_range(UnaryFunction fun) const { - typedef graham_andrew - < - Geometry, - typename point_type<Geometry>::type - > ConvexHullAlgorithm; + geometry::detail::for_each_range(m_geometry, fun); + } - ConvexHullAlgorithm algorithm; - typename ConvexHullAlgorithm::state_type state; + Geometry const& m_geometry; +}; - algorithm.apply(geometry, state, strategy); - algorithm.result(state, out, Order == clockwise, Closure != open); +// Abstraction representing ranges/rings of subgeometries of geometry collection +// with boxes converted to rings +template <typename Geometry, typename BoxRings> +struct input_geometry_collection_proxy +{ + input_geometry_collection_proxy(Geometry const& geometry, BoxRings const& box_rings) + : m_geometry(geometry) + , m_box_rings(box_rings) + {} + + template <typename UnaryFunction> + inline void for_each_range(UnaryFunction fun) const + { + detail::visit_breadth_first([&](auto const& g) + { + input_geometry_collection_proxy::call_for_non_boxes(g, fun); + return true; + }, m_geometry); - return out; + for (auto const& r : m_box_rings) + { + geometry::detail::for_each_range(r, fun); + } } -}; -struct hull_to_geometry -{ - template <typename Geometry, typename OutputGeometry, typename Strategy> - static inline void apply(Geometry const& geometry, OutputGeometry& out, - Strategy const& strategy) +private: + template <typename G, typename F, std::enable_if_t<! util::is_box<G>::value, int> = 0> + static inline void call_for_non_boxes(G const& g, F & f) { - // TODO: Why not handle multi-polygon here? - // TODO: detail::as_range() is only used in this place in the whole library - // it should probably be located here. - // NOTE: A variable is created here because this can be a proxy range - // and back_insert_iterator<> can store a pointer to it. - // Handle linestring, ring and polygon the same: - auto&& range = detail::as_range(out); - hull_insert - < - geometry::point_order<OutputGeometry>::value, - geometry::closure<OutputGeometry>::value - >::apply(geometry, range::back_inserter(range), strategy); + geometry::detail::for_each_range(g, f); } + template <typename G, typename F, std::enable_if_t<util::is_box<G>::value, int> = 0> + static inline void call_for_non_boxes(G const&, F &) + {} + + Geometry const& m_geometry; + BoxRings const& m_box_rings; +}; + + +// TODO: Or just implement point_type<> for GeometryCollection +// and enforce the same point_type used in the whole sequence in check(). +template <typename Geometry, typename Tag = typename tag<Geometry>::type> +struct default_strategy +{ + using type = typename strategies::convex_hull::services::default_strategy + < + Geometry + >::type; +}; + +template <typename Geometry> +struct default_strategy<Geometry, geometry_collection_tag> + : default_strategy<typename detail::first_geometry_type<Geometry>::type> +{}; + + +// Utilities for output GC and DG +template <typename G1, typename G2> +struct output_polygonal_less +{ + template <typename G> + using priority = std::integral_constant + < + int, + (util::is_ring<G>::value ? 0 : + util::is_polygon<G>::value ? 1 : + util::is_multi_polygon<G>::value ? 2 : 3) + >; + + static const bool value = priority<G1>::value < priority<G2>::value; }; +template <typename G1, typename G2> +struct output_linear_less +{ + template <typename G> + using priority = std::integral_constant + < + int, + (util::is_segment<G>::value ? 0 : + util::is_linestring<G>::value ? 1 : + util::is_multi_linestring<G>::value ? 2 : 3) + >; + + static const bool value = priority<G1>::value < priority<G2>::value; +}; + +template <typename G1, typename G2> +struct output_pointlike_less +{ + template <typename G> + using priority = std::integral_constant + < + int, + (util::is_point<G>::value ? 0 : + util::is_multi_point<G>::value ? 1 : 2) + >; + + static const bool value = priority<G1>::value < priority<G2>::value; +}; + + }} // namespace detail::convex_hull #endif // DOXYGEN_NO_DETAIL @@ -116,10 +202,23 @@ template typename Tag = typename tag<Geometry>::type > struct convex_hull - : detail::convex_hull::hull_to_geometry -{}; +{ + template <typename OutputGeometry, typename Strategy> + static inline void apply(Geometry const& geometry, + OutputGeometry& out, + Strategy const& strategy) + { + detail::convex_hull::input_geometry_proxy<Geometry> in_proxy(geometry); + detail::convex_hull::graham_andrew + < + typename point_type<Geometry>::type + >::apply(in_proxy, out, strategy); + } +}; -// TODO: This is not correct in spherical and geographic CS + +// A hull for boxes is trivial. Any strategy is (currently) skipped. +// TODO: This is not correct in spherical and geographic CS. template <typename Box> struct convex_hull<Box, box_tag> { @@ -133,185 +232,337 @@ struct convex_hull<Box, box_tag> static bool const Reverse = geometry::point_order<OutputGeometry>::value == counterclockwise; - // A hull for boxes is trivial. Any strategy is (currently) skipped. - boost::array<typename point_type<Box>::type, 4> range; - geometry::detail::assign_box_corners_oriented<Reverse>(box, range); - geometry::append(out, range); + std::array<typename point_type<OutputGeometry>::type, 4> arr; + // TODO: This assigns only 2d cooridnates! + // And it is also used in box_view<>! + geometry::detail::assign_box_corners_oriented<Reverse>(box, arr); + + std::move(arr.begin(), arr.end(), range::back_inserter(out)); if (BOOST_GEOMETRY_CONDITION(Close)) { - geometry::append(out, *boost::begin(range)); + range::push_back(out, range::front(out)); } } }; +template <typename GeometryCollection> +struct convex_hull<GeometryCollection, geometry_collection_tag> +{ + template <typename OutputGeometry, typename Strategy> + static inline void apply(GeometryCollection const& geometry, + OutputGeometry& out, + Strategy const& strategy) + { + // Assuming that single point_type is used by the GeometryCollection + using subgeometry_type = typename detail::first_geometry_type<GeometryCollection>::type; + using point_type = typename geometry::point_type<subgeometry_type>::type; + using ring_type = model::ring<point_type, true, false>; + + // Calculate box rings once + std::vector<ring_type> box_rings; + detail::visit_breadth_first([&](auto const& g) + { + convex_hull::add_ring_for_box(box_rings, g, strategy); + return true; + }, geometry); -template <order_selector Order, closure_selector Closure> -struct convex_hull_insert - : detail::convex_hull::hull_insert<Order, Closure> -{}; + detail::convex_hull::input_geometry_collection_proxy + < + GeometryCollection, std::vector<ring_type> + > in_proxy(geometry, box_rings); + detail::convex_hull::graham_andrew + < + point_type + >::apply(in_proxy, out, strategy); + } -} // namespace dispatch -#endif // DOXYGEN_NO_DISPATCH +private: + template + < + typename Ring, typename SubGeometry, typename Strategy, + std::enable_if_t<util::is_box<SubGeometry>::value, int> = 0 + > + static inline void add_ring_for_box(std::vector<Ring> & rings, SubGeometry const& box, + Strategy const& strategy) + { + Ring ring; + convex_hull<SubGeometry>::apply(box, ring, strategy); + rings.push_back(std::move(ring)); + } + template + < + typename Ring, typename SubGeometry, typename Strategy, + std::enable_if_t<! util::is_box<SubGeometry>::value, int> = 0 + > + static inline void add_ring_for_box(std::vector<Ring> & , SubGeometry const& , + Strategy const& ) + {} +}; -namespace resolve_strategy { +template <typename OutputGeometry, typename Tag = typename tag<OutputGeometry>::type> +struct convex_hull_out +{ + BOOST_GEOMETRY_STATIC_ASSERT_FALSE("This OutputGeometry is not supported.", OutputGeometry, Tag); +}; -struct convex_hull +template <typename OutputGeometry> +struct convex_hull_out<OutputGeometry, ring_tag> { - template <typename Geometry, typename OutputGeometry, typename Strategy> + template <typename Geometry, typename Strategies> static inline void apply(Geometry const& geometry, OutputGeometry& out, - Strategy const& strategy) + Strategies const& strategies) { - //BOOST_CONCEPT_ASSERT( (geometry::concepts::ConvexHullStrategy<Strategy>) ); - dispatch::convex_hull<Geometry>::apply(geometry, out, strategy); + dispatch::convex_hull<Geometry>::apply(geometry, out, strategies); } +}; - template <typename Geometry, typename OutputGeometry> +template <typename OutputGeometry> +struct convex_hull_out<OutputGeometry, polygon_tag> +{ + template <typename Geometry, typename Strategies> static inline void apply(Geometry const& geometry, OutputGeometry& out, - default_strategy) + Strategies const& strategies) { - typedef typename strategies::convex_hull::services::default_strategy - < - Geometry - >::type strategy_type; + auto&& ring = exterior_ring(out); + dispatch::convex_hull<Geometry>::apply(geometry, ring, strategies); + } +}; - apply(geometry, out, strategy_type()); +template <typename OutputGeometry> +struct convex_hull_out<OutputGeometry, multi_polygon_tag> +{ + template <typename Geometry, typename Strategies> + static inline void apply(Geometry const& geometry, + OutputGeometry& out, + Strategies const& strategies) + { + typename boost::range_value<OutputGeometry>::type polygon; + auto&& ring = exterior_ring(polygon); + dispatch::convex_hull<Geometry>::apply(geometry, ring, strategies); + // Empty input is checked so the output shouldn't be empty + range::push_back(out, std::move(polygon)); } }; -struct convex_hull_insert +template <typename OutputGeometry> +struct convex_hull_out<OutputGeometry, geometry_collection_tag> { - template <typename Geometry, typename OutputIterator, typename Strategy> - static inline OutputIterator apply(Geometry const& geometry, - OutputIterator& out, - Strategy const& strategy) + using polygonal_t = typename util::sequence_min_element + < + typename traits::geometry_types<OutputGeometry>::type, + detail::convex_hull::output_polygonal_less + >::type; + using linear_t = typename util::sequence_min_element + < + typename traits::geometry_types<OutputGeometry>::type, + detail::convex_hull::output_linear_less + >::type; + using pointlike_t = typename util::sequence_min_element + < + typename traits::geometry_types<OutputGeometry>::type, + detail::convex_hull::output_pointlike_less + >::type; + + // select_element may define different kind of geometry than the one that is desired + BOOST_GEOMETRY_STATIC_ASSERT(util::is_polygonal<polygonal_t>::value, + "It must be possible to store polygonal geometry in OutputGeometry.", polygonal_t); + BOOST_GEOMETRY_STATIC_ASSERT(util::is_linear<linear_t>::value, + "It must be possible to store linear geometry in OutputGeometry.", linear_t); + BOOST_GEOMETRY_STATIC_ASSERT(util::is_pointlike<pointlike_t>::value, + "It must be possible to store pointlike geometry in OutputGeometry.", pointlike_t); + + template <typename Geometry, typename Strategies> + static inline void apply(Geometry const& geometry, + OutputGeometry& out, + Strategies const& strategies) { - //BOOST_CONCEPT_ASSERT( (geometry::concepts::ConvexHullStrategy<Strategy>) ); + polygonal_t polygonal; + convex_hull_out<polygonal_t>::apply(geometry, polygonal, strategies); + // Empty input is checked so the output shouldn't be empty + auto&& out_ring = ring(polygonal); + + if (boost::size(out_ring) == detail::minimum_ring_size<polygonal_t>::value) + { + using detail::equals::equals_point_point; + if (equals_point_point(range::front(out_ring), range::at(out_ring, 1), strategies)) + { + pointlike_t pointlike; + move_to_pointlike(out_ring, pointlike); + move_to_out(pointlike, out); + return; + } + if (equals_point_point(range::front(out_ring), range::at(out_ring, 2), strategies)) + { + linear_t linear; + move_to_linear(out_ring, linear); + move_to_out(linear, out); + return; + } + } - return dispatch::convex_hull_insert< - geometry::point_order<Geometry>::value, - geometry::closure<Geometry>::value - >::apply(geometry, out, strategy); + move_to_out(polygonal, out); } - template <typename Geometry, typename OutputIterator> - static inline OutputIterator apply(Geometry const& geometry, - OutputIterator& out, - default_strategy) +private: + template <typename Polygonal, util::enable_if_ring_t<Polygonal, int> = 0> + static decltype(auto) ring(Polygonal const& polygonal) { - typedef typename strategies::convex_hull::services::default_strategy - < - Geometry - >::type strategy_type; + return polygonal; + } + template <typename Polygonal, util::enable_if_polygon_t<Polygonal, int> = 0> + static decltype(auto) ring(Polygonal const& polygonal) + { + return exterior_ring(polygonal); + } + template <typename Polygonal, util::enable_if_multi_polygon_t<Polygonal, int> = 0> + static decltype(auto) ring(Polygonal const& polygonal) + { + return exterior_ring(range::front(polygonal)); + } - return apply(geometry, out, strategy_type()); + template <typename Range, typename Linear, util::enable_if_segment_t<Linear, int> = 0> + static void move_to_linear(Range & out_range, Linear & seg) + { + detail::assign_point_to_index<0>(range::front(out_range), seg); + detail::assign_point_to_index<1>(range::at(out_range, 1), seg); + } + template <typename Range, typename Linear, util::enable_if_linestring_t<Linear, int> = 0> + static void move_to_linear(Range & out_range, Linear & ls) + { + std::move(boost::begin(out_range), boost::begin(out_range) + 2, range::back_inserter(ls)); + } + template <typename Range, typename Linear, util::enable_if_multi_linestring_t<Linear, int> = 0> + static void move_to_linear(Range & out_range, Linear & mls) + { + typename boost::range_value<Linear>::type ls; + std::move(boost::begin(out_range), boost::begin(out_range) + 2, range::back_inserter(ls)); + range::push_back(mls, std::move(ls)); + } + + template <typename Range, typename PointLike, util::enable_if_point_t<PointLike, int> = 0> + static void move_to_pointlike(Range & out_range, PointLike & pt) + { + pt = range::front(out_range); + } + template <typename Range, typename PointLike, util::enable_if_multi_point_t<PointLike, int> = 0> + static void move_to_pointlike(Range & out_range, PointLike & mpt) + { + range::push_back(mpt, std::move(range::front(out_range))); + } + + template + < + typename Geometry, typename OutputGeometry_, + util::enable_if_geometry_collection_t<OutputGeometry_, int> = 0 + > + static void move_to_out(Geometry & g, OutputGeometry_ & out) + { + range::emplace_back(out, std::move(g)); + } + template + < + typename Geometry, typename OutputGeometry_, + util::enable_if_dynamic_geometry_t<OutputGeometry_, int> = 0 + > + static void move_to_out(Geometry & g, OutputGeometry_ & out) + { + out = std::move(g); } }; -} // namespace resolve_strategy +template <typename OutputGeometry> +struct convex_hull_out<OutputGeometry, dynamic_geometry_tag> + : convex_hull_out<OutputGeometry, geometry_collection_tag> +{}; -namespace resolve_variant { +// For backward compatibility +template <typename OutputGeometry> +struct convex_hull_out<OutputGeometry, linestring_tag> + : convex_hull_out<OutputGeometry, ring_tag> +{}; -template <typename Geometry> + +} // namespace dispatch +#endif // DOXYGEN_NO_DISPATCH + + +namespace resolve_strategy { + +template <typename Strategies> struct convex_hull { - template <typename OutputGeometry, typename Strategy> + template <typename Geometry, typename OutputGeometry> static inline void apply(Geometry const& geometry, OutputGeometry& out, - Strategy const& strategy) + Strategies const& strategies) { - concepts::check_concepts_and_equal_dimensions< - const Geometry, - OutputGeometry - >(); - - resolve_strategy::convex_hull::apply(geometry, out, strategy); + dispatch::convex_hull_out<OutputGeometry>::apply(geometry, out, strategies); } }; -template <BOOST_VARIANT_ENUM_PARAMS(typename T)> -struct convex_hull<boost::variant<BOOST_VARIANT_ENUM_PARAMS(T)> > +template <> +struct convex_hull<default_strategy> { - template <typename OutputGeometry, typename Strategy> - struct visitor: boost::static_visitor<void> + template <typename Geometry, typename OutputGeometry> + static inline void apply(Geometry const& geometry, + OutputGeometry& out, + default_strategy const&) { - 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); - } - }; + using strategy_type = typename detail::convex_hull::default_strategy + < + Geometry + >::type; - 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); + dispatch::convex_hull_out<OutputGeometry>::apply(geometry, out, strategy_type()); } }; -template <typename Geometry> -struct convex_hull_insert + +} // namespace resolve_strategy + + +namespace resolve_dynamic { + +template <typename Geometry, typename Tag = typename tag<Geometry>::type> +struct convex_hull { - template <typename OutputIterator, typename Strategy> - static inline OutputIterator apply(Geometry const& geometry, - OutputIterator& out, - Strategy const& strategy) + template <typename OutputGeometry, typename Strategy> + static inline void apply(Geometry const& geometry, + OutputGeometry& out, + Strategy const& strategy) { - // Concept: output point type = point type of input geometry - concepts::check<Geometry const>(); - concepts::check<typename point_type<Geometry>::type>(); + concepts::check_concepts_and_equal_dimensions< + const Geometry, + OutputGeometry + >(); - return resolve_strategy::convex_hull_insert::apply(geometry, out, strategy); + resolve_strategy::convex_hull<Strategy>::apply(geometry, out, strategy); } }; -template <BOOST_VARIANT_ENUM_PARAMS(typename T)> -struct convex_hull_insert<boost::variant<BOOST_VARIANT_ENUM_PARAMS(T)> > +template <typename Geometry> +struct convex_hull<Geometry, dynamic_geometry_tag> { - template <typename OutputIterator, typename Strategy> - struct visitor: boost::static_visitor<OutputIterator> + template <typename OutputGeometry, typename Strategy> + static inline void apply(Geometry const& geometry, + OutputGeometry& out, + Strategy const& strategy) { - 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 + traits::visit<Geometry>::apply([&](auto const& g) { - 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); + convex_hull<util::remove_cref_t<decltype(g)>>::apply(g, out, strategy); + }, geometry); } }; -} // namespace resolve_variant + +} // namespace resolve_dynamic /*! @@ -330,8 +581,7 @@ struct convex_hull_insert<boost::variant<BOOST_VARIANT_ENUM_PARAMS(T)> > \qbk{[include reference/algorithms/convex_hull.qbk]} */ template<typename Geometry, typename OutputGeometry, typename Strategy> -inline void convex_hull(Geometry const& geometry, - OutputGeometry& out, Strategy const& strategy) +inline void convex_hull(Geometry const& geometry, OutputGeometry& out, Strategy const& strategy) { if (geometry::is_empty(geometry)) { @@ -339,7 +589,7 @@ inline void convex_hull(Geometry const& geometry, return; } - resolve_variant::convex_hull<Geometry>::apply(geometry, out, strategy); + resolve_dynamic::convex_hull<Geometry>::apply(geometry, out, strategy); } @@ -355,52 +605,11 @@ inline void convex_hull(Geometry const& geometry, \qbk{[include reference/algorithms/convex_hull.qbk]} */ template<typename Geometry, typename OutputGeometry> -inline void convex_hull(Geometry const& geometry, - OutputGeometry& hull) +inline void convex_hull(Geometry const& geometry, OutputGeometry& hull) { geometry::convex_hull(geometry, hull, default_strategy()); } -#ifndef DOXYGEN_NO_DETAIL -namespace detail { namespace convex_hull -{ - - -template<typename Geometry, typename OutputIterator, typename Strategy> -inline OutputIterator convex_hull_insert(Geometry const& geometry, - OutputIterator out, Strategy const& strategy) -{ - return resolve_variant::convex_hull_insert - < - Geometry - >::apply(geometry, out, strategy); -} - - -/*! -\brief Calculate the convex hull of a geometry, output-iterator version -\ingroup convex_hull -\tparam Geometry the input geometry type -\tparam OutputIterator: an output-iterator -\param geometry the geometry to calculate convex hull from -\param out an output iterator outputing points of the convex hull -\note This overloaded version outputs to an output iterator. -In this case, nothing is known about its point-type or - about its clockwise order. Therefore, the input point-type - and order are copied - - */ -template<typename Geometry, typename OutputIterator> -inline OutputIterator convex_hull_insert(Geometry const& geometry, - OutputIterator out) -{ - return convex_hull_insert(geometry, out, default_strategy()); -} - - -}} // namespace detail::convex_hull -#endif // DOXYGEN_NO_DETAIL - }} // namespace boost::geometry |