ceph/src/boost/boost/geometry/algorithms/convex_hull.hpp

   1 // Boost.Geometry (aka GGL, Generic Geometry Library)
   2
   3 // Copyright (c) 2007-2015 Barend Gehrels, Amsterdam, the Netherlands.
   4 // Copyright (c) 2008-2015 Bruno Lalande, Paris, France.
   5 // Copyright (c) 2009-2015 Mateusz Loskot, London, UK.
   6
   7 // This file was modified by Oracle on 2014, 2015.
   8 // Modifications copyright (c) 2014-2015 Oracle and/or its affiliates.
   9
  10 // Contributed and/or modified by Adam Wulkiewicz, on behalf of Oracle
  11 // Contributed and/or modified by Menelaos Karavelas, on behalf of Oracle
  12
  13 // Parts of Boost.Geometry are redesigned from Geodan's Geographic Library
  14 // (geolib/GGL), copyright (c) 1995-2010 Geodan, Amsterdam, the Netherlands.
  15
  16 // Use, modification and distribution is subject to the Boost Software License,
  17 // Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
  18 // http://www.boost.org/LICENSE_1_0.txt)
  19
  20 #ifndef BOOST_GEOMETRY_ALGORITHMS_CONVEX_HULL_HPP
  21 #define BOOST_GEOMETRY_ALGORITHMS_CONVEX_HULL_HPP
  22
  23 #include <boost/array.hpp>
  24
  25 #include <boost/variant/apply_visitor.hpp>
  26 #include <boost/variant/static_visitor.hpp>
  27 #include <boost/variant/variant_fwd.hpp>
  28
  29 #include <boost/geometry/core/cs.hpp>
  30 #include <boost/geometry/core/point_order.hpp>
  31 #include <boost/geometry/core/closure.hpp>
  32 #include <boost/geometry/core/exterior_ring.hpp>
  33
  34 #include <boost/geometry/geometries/concepts/check.hpp>
  35
  36 #include <boost/geometry/strategies/convex_hull.hpp>
  37 #include <boost/geometry/strategies/concepts/convex_hull_concept.hpp>
  38 #include <boost/geometry/strategies/default_strategy.hpp>
  39
  40 #include <boost/geometry/util/condition.hpp>
  41
  42 #include <boost/geometry/views/detail/range_type.hpp>
  43
  44 #include <boost/geometry/algorithms/is_empty.hpp>
  45 #include <boost/geometry/algorithms/detail/as_range.hpp>
  46 #include <boost/geometry/algorithms/detail/assign_box_corners.hpp>
  47
  48
  49 namespace boost { namespace geometry
  50 {
  51
  52
  53 #ifndef DOXYGEN_NO_DETAIL
  54 namespace detail { namespace convex_hull
  55 {
  56
  57 template <order_selector Order, closure_selector Closure>
  58 struct hull_insert
  59 {
  60
  61     // Member template function (to avoid inconvenient declaration
  62     // of output-iterator-type, from hull_to_geometry)
  63     template <typename Geometry, typename OutputIterator, typename Strategy>
  64     static inline OutputIterator apply(Geometry const& geometry,
  65             OutputIterator out, Strategy const& strategy)
  66     {
  67         typename Strategy::state_type state;
  68
  69         strategy.apply(geometry, state);
  70         strategy.result(state, out, Order == clockwise, Closure != open);
  71         return out;
  72     }
  73 };
  74
  75 struct hull_to_geometry
  76 {
  77     template <typename Geometry, typename OutputGeometry, typename Strategy>
  78     static inline void apply(Geometry const& geometry, OutputGeometry& out,
  79             Strategy const& strategy)
  80     {
  81         hull_insert
  82             <
  83                 geometry::point_order<OutputGeometry>::value,
  84                 geometry::closure<OutputGeometry>::value
  85             >::apply(geometry,
  86                 range::back_inserter(
  87                     // Handle linestring, ring and polygon the same:
  88                     detail::as_range
  89                         <
  90                             typename range_type<OutputGeometry>::type
  91                         >(out)), strategy);
  92     }
  93 };
  94
  95 }} // namespace detail::convex_hull
  96 #endif // DOXYGEN_NO_DETAIL
  97
  98
  99 #ifndef DOXYGEN_NO_DISPATCH
 100 namespace dispatch
 101 {
 102
 103
 104 template
 105 <
 106     typename Geometry,
 107     typename Tag = typename tag<Geometry>::type
 108 >
 109 struct convex_hull
 110     : detail::convex_hull::hull_to_geometry
 111 {};
 112
 113 template <typename Box>
 114 struct convex_hull<Box, box_tag>
 115 {
 116     template <typename OutputGeometry, typename Strategy>
 117     static inline void apply(Box const& box, OutputGeometry& out,
 118             Strategy const& )
 119     {
 120         static bool const Close
 121             = geometry::closure<OutputGeometry>::value == closed;
 122         static bool const Reverse
 123             = geometry::point_order<OutputGeometry>::value == counterclockwise;
 124
 125         // A hull for boxes is trivial. Any strategy is (currently) skipped.
 126         boost::array<typename point_type<Box>::type, 4> range;
 127         geometry::detail::assign_box_corners_oriented<Reverse>(box, range);
 128         geometry::append(out, range);
 129         if (BOOST_GEOMETRY_CONDITION(Close))
 130         {
 131             geometry::append(out, *boost::begin(range));
 132         }
 133     }
 134 };
 135
 136
 137
 138 template <order_selector Order, closure_selector Closure>
 139 struct convex_hull_insert
 140     : detail::convex_hull::hull_insert<Order, Closure>
 141 {};
 142
 143
 144 } // namespace dispatch
 145 #endif // DOXYGEN_NO_DISPATCH
 146
 147
 148 namespace resolve_strategy {
 149
 150 struct convex_hull
 151 {
 152     template <typename Geometry, typename OutputGeometry, typename Strategy>
 153     static inline void apply(Geometry const& geometry,
 154                              OutputGeometry& out,
 155                              Strategy const& strategy)
 156     {
 157         BOOST_CONCEPT_ASSERT( (geometry::concepts::ConvexHullStrategy<Strategy>) );
 158         dispatch::convex_hull<Geometry>::apply(geometry, out, strategy);
 159     }
 160
 161     template <typename Geometry, typename OutputGeometry>
 162     static inline void apply(Geometry const& geometry,
 163                              OutputGeometry& out,
 164                              default_strategy)
 165     {
 166         typedef typename strategy_convex_hull<
 167             Geometry,
 168             typename point_type<Geometry>::type
 169         >::type strategy_type;
 170
 171         apply(geometry, out, strategy_type());
 172     }
 173 };
 174
 175 struct convex_hull_insert
 176 {
 177     template <typename Geometry, typename OutputIterator, typename Strategy>
 178     static inline OutputIterator apply(Geometry const& geometry,
 179                                        OutputIterator& out,
 180                                        Strategy const& strategy)
 181     {
 182         BOOST_CONCEPT_ASSERT( (geometry::concepts::ConvexHullStrategy<Strategy>) );
 183
 184         return dispatch::convex_hull_insert<
 185                    geometry::point_order<Geometry>::value,
 186                    geometry::closure<Geometry>::value
 187                >::apply(geometry, out, strategy);
 188     }
 189
 190     template <typename Geometry, typename OutputIterator>
 191     static inline OutputIterator apply(Geometry const& geometry,
 192                                        OutputIterator& out,
 193                                        default_strategy)
 194     {
 195         typedef typename strategy_convex_hull<
 196             Geometry,
 197             typename point_type<Geometry>::type
 198         >::type strategy_type;
 199
 200         return apply(geometry, out, strategy_type());
 201     }
 202 };
 203
 204 } // namespace resolve_strategy
 205
 206
 207 namespace resolve_variant {
 208
 209 template <typename Geometry>
 210 struct convex_hull
 211 {
 212     template <typename OutputGeometry, typename Strategy>
 213     static inline void apply(Geometry const& geometry, OutputGeometry& out, Strategy const& strategy)
 214     {
 215         concepts::check_concepts_and_equal_dimensions<
 216             const Geometry,
 217             OutputGeometry
 218         >();
 219
 220         resolve_strategy::convex_hull::apply(geometry, out, strategy);
 221     }
 222 };
 223
 224 template <BOOST_VARIANT_ENUM_PARAMS(typename T)>
 225 struct convex_hull<boost::variant<BOOST_VARIANT_ENUM_PARAMS(T)> >
 226 {
 227     template <typename OutputGeometry, typename Strategy>
 228     struct visitor: boost::static_visitor<void>
 229     {
 230         OutputGeometry& m_out;
 231         Strategy const& m_strategy;
 232
 233         visitor(OutputGeometry& out, Strategy const& strategy)
 234         : m_out(out), m_strategy(strategy)
 235         {}
 236
 237         template <typename Geometry>
 238         void operator()(Geometry const& geometry) const
 239         {
 240             convex_hull<Geometry>::apply(geometry, m_out, m_strategy);
 241         }
 242     };
 243
 244     template <typename OutputGeometry, typename Strategy>
 245     static inline void
 246     apply(boost::variant<BOOST_VARIANT_ENUM_PARAMS(T)> const& geometry,
 247           OutputGeometry& out,
 248           Strategy const& strategy)
 249     {
 250         boost::apply_visitor(visitor<OutputGeometry, Strategy>(out, strategy), geometry);
 251     }
 252 };
 253
 254 template <typename Geometry>
 255 struct convex_hull_insert
 256 {
 257     template <typename OutputIterator, typename Strategy>
 258     static inline OutputIterator apply(Geometry const& geometry, OutputIterator& out, Strategy const& strategy)
 259     {
 260         // Concept: output point type = point type of input geometry
 261         concepts::check<Geometry const>();
 262         concepts::check<typename point_type<Geometry>::type>();
 263
 264         return resolve_strategy::convex_hull_insert::apply(geometry, out, strategy);
 265     }
 266 };
 267
 268 template <BOOST_VARIANT_ENUM_PARAMS(typename T)>
 269 struct convex_hull_insert<boost::variant<BOOST_VARIANT_ENUM_PARAMS(T)> >
 270 {
 271     template <typename OutputIterator, typename Strategy>
 272     struct visitor: boost::static_visitor<OutputIterator>
 273     {
 274         OutputIterator& m_out;
 275         Strategy const& m_strategy;
 276
 277         visitor(OutputIterator& out, Strategy const& strategy)
 278         : m_out(out), m_strategy(strategy)
 279         {}
 280
 281         template <typename Geometry>
 282         OutputIterator operator()(Geometry const& geometry) const
 283         {
 284             return convex_hull_insert<Geometry>::apply(geometry, m_out, m_strategy);
 285         }
 286     };
 287
 288     template <typename OutputIterator, typename Strategy>
 289     static inline OutputIterator
 290     apply(boost::variant<BOOST_VARIANT_ENUM_PARAMS(T)> const& geometry,
 291           OutputIterator& out,
 292           Strategy const& strategy)
 293     {
 294         return boost::apply_visitor(visitor<OutputIterator, Strategy>(out, strategy), geometry);
 295     }
 296 };
 297
 298 } // namespace resolve_variant
 299
 300
 301 template<typename Geometry, typename OutputGeometry, typename Strategy>
 302 inline void convex_hull(Geometry const& geometry,
 303             OutputGeometry& out, Strategy const& strategy)
 304 {
 305     if (geometry::is_empty(geometry))
 306     {
 307         // Leave output empty
 308         return;
 309     }
 310
 311     resolve_variant::convex_hull<Geometry>::apply(geometry, out, strategy);
 312 }
 313
 314
 315 /*!
 316 \brief \brief_calc{convex hull}
 317 \ingroup convex_hull
 318 \details \details_calc{convex_hull,convex hull}.
 319 \tparam Geometry the input geometry type
 320 \tparam OutputGeometry the output geometry type
 321 \param geometry \param_geometry,  input geometry
 322 \param hull \param_geometry \param_set{convex hull}
 323
 324 \qbk{[include reference/algorithms/convex_hull.qbk]}
 325  */
 326 template<typename Geometry, typename OutputGeometry>
 327 inline void convex_hull(Geometry const& geometry,
 328             OutputGeometry& hull)
 329 {
 330     geometry::convex_hull(geometry, hull, default_strategy());
 331 }
 332
 333 #ifndef DOXYGEN_NO_DETAIL
 334 namespace detail { namespace convex_hull
 335 {
 336
 337
 338 template<typename Geometry, typename OutputIterator, typename Strategy>
 339 inline OutputIterator convex_hull_insert(Geometry const& geometry,
 340             OutputIterator out, Strategy const& strategy)
 341 {
 342     return resolve_variant::convex_hull_insert<Geometry>
 343                           ::apply(geometry, out, strategy);
 344 }
 345
 346
 347 /*!
 348 \brief Calculate the convex hull of a geometry, output-iterator version
 349 \ingroup convex_hull
 350 \tparam Geometry the input geometry type
 351 \tparam OutputIterator: an output-iterator
 352 \param geometry the geometry to calculate convex hull from
 353 \param out an output iterator outputing points of the convex hull
 354 \note This overloaded version outputs to an output iterator.
 355 In this case, nothing is known about its point-type or
 356     about its clockwise order. Therefore, the input point-type
 357     and order are copied
 358
 359  */
 360 template<typename Geometry, typename OutputIterator>
 361 inline OutputIterator convex_hull_insert(Geometry const& geometry,
 362             OutputIterator out)
 363 {
 364     return convex_hull_insert(geometry, out, default_strategy());
 365 }
 366
 367
 368 }} // namespace detail::convex_hull
 369 #endif // DOXYGEN_NO_DETAIL
 370
 371
 372 }} // namespace boost::geometry
 373
 374
 375 #endif // BOOST_GEOMETRY_ALGORITHMS_CONVEX_HULL_HPP