Chris@16: // Boost.Geometry (aka GGL, Generic Geometry Library)
Chris@16: 
Chris@16: // Copyright (c) 2007-2012 Barend Gehrels, Amsterdam, the Netherlands.
Chris@16: 
Chris@101: // This file was modified by Oracle on 2014.
Chris@101: // Modifications copyright (c) 2014 Oracle and/or its affiliates.
Chris@101: 
Chris@101: // Contributed and/or modified by Adam Wulkiewicz, on behalf of Oracle
Chris@101: 
Chris@16: // Parts of Boost.Geometry are redesigned from Geodan's Geographic Library
Chris@16: // (geolib/GGL), copyright (c) 1995-2010 Geodan, Amsterdam, the Netherlands.
Chris@16: 
Chris@16: // Use, modification and distribution is subject to the Boost Software License,
Chris@16: // Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
Chris@16: // http://www.boost.org/LICENSE_1_0.txt)
Chris@16: 
Chris@16: #ifndef BOOST_GEOMETRY_STRATEGIES_AGNOSTIC_CONVEX_GRAHAM_ANDREW_HPP
Chris@16: #define BOOST_GEOMETRY_STRATEGIES_AGNOSTIC_CONVEX_GRAHAM_ANDREW_HPP
Chris@16: 
Chris@16: 
Chris@16: #include <cstddef>
Chris@16: #include <algorithm>
Chris@16: #include <vector>
Chris@16: 
Chris@16: #include <boost/range.hpp>
Chris@16: 
Chris@16: #include <boost/geometry/core/cs.hpp>
Chris@16: #include <boost/geometry/core/point_type.hpp>
Chris@16: #include <boost/geometry/strategies/convex_hull.hpp>
Chris@16: 
Chris@16: #include <boost/geometry/views/detail/range_type.hpp>
Chris@16: 
Chris@16: #include <boost/geometry/policies/compare.hpp>
Chris@16: 
Chris@16: #include <boost/geometry/algorithms/detail/for_each_range.hpp>
Chris@16: #include <boost/geometry/views/reversible_view.hpp>
Chris@16: 
Chris@16: 
Chris@16: namespace boost { namespace geometry
Chris@16: {
Chris@16: 
Chris@16: namespace strategy { namespace convex_hull
Chris@16: {
Chris@16: 
Chris@16: #ifndef DOXYGEN_NO_DETAIL
Chris@16: namespace detail
Chris@16: {
Chris@16: 
Chris@16: 
Chris@16: template
Chris@16: <
Chris@16:     typename InputRange,
Chris@16:     typename RangeIterator,
Chris@16:     typename StrategyLess,
Chris@16:     typename StrategyGreater
Chris@16: >
Chris@16: struct get_extremes
Chris@16: {
Chris@16:     typedef typename point_type<InputRange>::type point_type;
Chris@16: 
Chris@16:     point_type left, right;
Chris@16: 
Chris@16:     bool first;
Chris@16: 
Chris@16:     StrategyLess less;
Chris@16:     StrategyGreater greater;
Chris@16: 
Chris@16:     inline get_extremes()
Chris@16:         : first(true)
Chris@16:     {}
Chris@16: 
Chris@16:     inline void apply(InputRange const& range)
Chris@16:     {
Chris@16:         if (boost::size(range) == 0)
Chris@16:         {
Chris@16:             return;
Chris@16:         }
Chris@16: 
Chris@16:         // First iterate through this range
Chris@16:         // (this two-stage approach avoids many point copies,
Chris@16:         //  because iterators are kept in memory. Because iterators are
Chris@16:         //  not persistent (in MSVC) this approach is not applicable
Chris@16:         //  for more ranges together)
Chris@16: 
Chris@16:         RangeIterator left_it = boost::begin(range);
Chris@16:         RangeIterator right_it = boost::begin(range);
Chris@16: 
Chris@16:         for (RangeIterator it = boost::begin(range) + 1;
Chris@16:             it != boost::end(range);
Chris@16:             ++it)
Chris@16:         {
Chris@16:             if (less(*it, *left_it))
Chris@16:             {
Chris@16:                 left_it = it;
Chris@16:             }
Chris@16: 
Chris@16:             if (greater(*it, *right_it))
Chris@16:             {
Chris@16:                 right_it = it;
Chris@16:             }
Chris@16:         }
Chris@16: 
Chris@16:         // Then compare with earlier
Chris@16:         if (first)
Chris@16:         {
Chris@16:             // First time, assign left/right
Chris@16:             left = *left_it;
Chris@16:             right = *right_it;
Chris@16:             first = false;
Chris@16:         }
Chris@16:         else
Chris@16:         {
Chris@16:             // Next time, check if this range was left/right from
Chris@16:             // the extremes already collected
Chris@16:             if (less(*left_it, left))
Chris@16:             {
Chris@16:                 left = *left_it;
Chris@16:             }
Chris@16: 
Chris@16:             if (greater(*right_it, right))
Chris@16:             {
Chris@16:                 right = *right_it;
Chris@16:             }
Chris@16:         }
Chris@16:     }
Chris@16: };
Chris@16: 
Chris@16: 
Chris@16: template
Chris@16: <
Chris@16:     typename InputRange,
Chris@16:     typename RangeIterator,
Chris@16:     typename Container,
Chris@16:     typename SideStrategy
Chris@16: >
Chris@16: struct assign_range
Chris@16: {
Chris@16:     Container lower_points, upper_points;
Chris@16: 
Chris@16:     typedef typename point_type<InputRange>::type point_type;
Chris@16: 
Chris@16:     point_type const& most_left;
Chris@16:     point_type const& most_right;
Chris@16: 
Chris@16:     inline assign_range(point_type const& left, point_type const& right)
Chris@16:         : most_left(left)
Chris@16:         , most_right(right)
Chris@16:     {}
Chris@16: 
Chris@16:     inline void apply(InputRange const& range)
Chris@16:     {
Chris@16:         typedef SideStrategy side;
Chris@16: 
Chris@16:         // Put points in one of the two output sequences
Chris@16:         for (RangeIterator it = boost::begin(range);
Chris@16:             it != boost::end(range);
Chris@16:             ++it)
Chris@16:         {
Chris@16:             // check if it is lying most_left or most_right from the line
Chris@16: 
Chris@16:             int dir = side::apply(most_left, most_right, *it);
Chris@16:             switch(dir)
Chris@16:             {
Chris@16:                 case 1 : // left side
Chris@16:                     upper_points.push_back(*it);
Chris@16:                     break;
Chris@16:                 case -1 : // right side
Chris@16:                     lower_points.push_back(*it);
Chris@16:                     break;
Chris@16: 
Chris@16:                 // 0: on line most_left-most_right,
Chris@16:                 //    or most_left, or most_right,
Chris@16:                 //    -> all never part of hull
Chris@16:             }
Chris@16:         }
Chris@16:     }
Chris@16: };
Chris@16: 
Chris@16: template <typename Range>
Chris@16: static inline void sort(Range& range)
Chris@16: {
Chris@16:     typedef typename boost::range_value<Range>::type point_type;
Chris@16:     typedef geometry::less<point_type> comparator;
Chris@16: 
Chris@16:     std::sort(boost::begin(range), boost::end(range), comparator());
Chris@16: }
Chris@16: 
Chris@16: } // namespace detail
Chris@16: #endif // DOXYGEN_NO_DETAIL
Chris@16: 
Chris@16: 
Chris@16: /*!
Chris@16: \brief Graham scan strategy to calculate convex hull
Chris@16: \ingroup strategies
Chris@16: \note Completely reworked version inspired on the sources listed below
Chris@16: \see http://www.ddj.com/architect/201806315
Chris@16: \see http://marknelson.us/2007/08/22/convex
Chris@16:  */
Chris@16: template <typename InputGeometry, typename OutputPoint>
Chris@16: class graham_andrew
Chris@16: {
Chris@16: public :
Chris@16:     typedef OutputPoint point_type;
Chris@16:     typedef InputGeometry geometry_type;
Chris@16: 
Chris@16: private:
Chris@16: 
Chris@16:     typedef typename cs_tag<point_type>::type cs_tag;
Chris@16: 
Chris@16:     typedef typename std::vector<point_type> container_type;
Chris@16:     typedef typename std::vector<point_type>::const_iterator iterator;
Chris@16:     typedef typename std::vector<point_type>::const_reverse_iterator rev_iterator;
Chris@16: 
Chris@16: 
Chris@16:     class partitions
Chris@16:     {
Chris@16:         friend class graham_andrew;
Chris@16: 
Chris@16:         container_type m_lower_hull;
Chris@16:         container_type m_upper_hull;
Chris@16:         container_type m_copied_input;
Chris@16:     };
Chris@16: 
Chris@16: 
Chris@16: public:
Chris@16:     typedef partitions state_type;
Chris@16: 
Chris@16: 
Chris@16:     inline void apply(InputGeometry const& geometry, partitions& state) const
Chris@16:     {
Chris@16:         // First pass.
Chris@16:         // Get min/max (in most cases left / right) points
Chris@16:         // This makes use of the geometry::less/greater predicates
Chris@16: 
Chris@16:         // For the left boundary it is important that multiple points
Chris@16:         // are sorted from bottom to top. Therefore the less predicate
Chris@16:         // does not take the x-only template parameter (this fixes ticket #6019.
Chris@101:         // For the right boundary it is not necessary (though also not harmful),
Chris@16:         // because points are sorted from bottom to top in a later stage.
Chris@16:         // For symmetry and to get often more balanced lower/upper halves
Chris@16:         // we keep it.
Chris@16: 
Chris@16:         typedef typename geometry::detail::range_type<InputGeometry>::type range_type;
Chris@16: 
Chris@16:         typedef typename boost::range_iterator
Chris@16:             <
Chris@16:                 range_type const
Chris@16:             >::type range_iterator;
Chris@16: 
Chris@16:         detail::get_extremes
Chris@16:             <
Chris@16:                 range_type,
Chris@16:                 range_iterator,
Chris@16:                 geometry::less<point_type>,
Chris@16:                 geometry::greater<point_type>
Chris@16:             > extremes;
Chris@16:         geometry::detail::for_each_range(geometry, extremes);
Chris@16: 
Chris@16:         // Bounding left/right points
Chris@16:         // Second pass, now that extremes are found, assign all points
Chris@16:         // in either lower, either upper
Chris@16:         detail::assign_range
Chris@16:             <
Chris@16:                 range_type,
Chris@16:                 range_iterator,
Chris@16:                 container_type,
Chris@16:                 typename strategy::side::services::default_strategy<cs_tag>::type
Chris@16:             > assigner(extremes.left, extremes.right);
Chris@16: 
Chris@16:         geometry::detail::for_each_range(geometry, assigner);
Chris@16: 
Chris@16: 
Chris@16:         // Sort both collections, first on x(, then on y)
Chris@16:         detail::sort(assigner.lower_points);
Chris@16:         detail::sort(assigner.upper_points);
Chris@16: 
Chris@16:         //std::cout << boost::size(assigner.lower_points) << std::endl;
Chris@16:         //std::cout << boost::size(assigner.upper_points) << std::endl;
Chris@16: 
Chris@16:         // And decide which point should be in the final hull
Chris@16:         build_half_hull<-1>(assigner.lower_points, state.m_lower_hull,
Chris@16:                 extremes.left, extremes.right);
Chris@16:         build_half_hull<1>(assigner.upper_points, state.m_upper_hull,
Chris@16:                 extremes.left, extremes.right);
Chris@16:     }
Chris@16: 
Chris@16: 
Chris@16:     template <typename OutputIterator>
Chris@16:     inline void result(partitions const& state,
Chris@101:                        OutputIterator out,
Chris@101:                        bool clockwise,
Chris@101:                        bool closed) const
Chris@16:     {
Chris@16:         if (clockwise)
Chris@16:         {
Chris@101:             output_ranges(state.m_upper_hull, state.m_lower_hull, out, closed);
Chris@16:         }
Chris@16:         else
Chris@16:         {
Chris@101:             output_ranges(state.m_lower_hull, state.m_upper_hull, out, closed);
Chris@16:         }
Chris@16:     }
Chris@16: 
Chris@16: 
Chris@16: private:
Chris@16: 
Chris@16:     template <int Factor>
Chris@16:     static inline void build_half_hull(container_type const& input,
Chris@16:             container_type& output,
Chris@16:             point_type const& left, point_type const& right)
Chris@16:     {
Chris@16:         output.push_back(left);
Chris@16:         for(iterator it = input.begin(); it != input.end(); ++it)
Chris@16:         {
Chris@16:             add_to_hull<Factor>(*it, output);
Chris@16:         }
Chris@16:         add_to_hull<Factor>(right, output);
Chris@16:     }
Chris@16: 
Chris@16: 
Chris@16:     template <int Factor>
Chris@16:     static inline void add_to_hull(point_type const& p, container_type& output)
Chris@16:     {
Chris@16:         typedef typename strategy::side::services::default_strategy<cs_tag>::type side;
Chris@16: 
Chris@16:         output.push_back(p);
Chris@101:         std::size_t output_size = output.size();
Chris@16:         while (output_size >= 3)
Chris@16:         {
Chris@16:             rev_iterator rit = output.rbegin();
Chris@101:             point_type const last = *rit++;
Chris@16:             point_type const& last2 = *rit++;
Chris@16: 
Chris@16:             if (Factor * side::apply(*rit, last, last2) <= 0)
Chris@16:             {
Chris@16:                 // Remove last two points from stack, and add last again
Chris@16:                 // This is much faster then erasing the one but last.
Chris@16:                 output.pop_back();
Chris@16:                 output.pop_back();
Chris@16:                 output.push_back(last);
Chris@16:                 output_size--;
Chris@16:             }
Chris@16:             else
Chris@16:             {
Chris@16:                 return;
Chris@16:             }
Chris@16:         }
Chris@16:     }
Chris@16: 
Chris@16: 
Chris@101:     template <typename OutputIterator>
Chris@101:     static inline void output_ranges(container_type const& first, container_type const& second,
Chris@101:                                      OutputIterator out, bool closed)
Chris@16:     {
Chris@101:         std::copy(boost::begin(first), boost::end(first), out);
Chris@101: 
Chris@101:         BOOST_ASSERT(closed ? !boost::empty(second) : boost::size(second) > 1);
Chris@101:         std::copy(++boost::rbegin(second), // skip the first Point
Chris@101:                   closed ? boost::rend(second) : --boost::rend(second), // skip the last Point if open
Chris@101:                   out);
Chris@101: 
Chris@101:         typedef typename boost::range_size<container_type>::type size_type;
Chris@101:         size_type const count = boost::size(first) + boost::size(second) - 1;
Chris@101:         // count describes a closed case but comparison with min size of closed
Chris@101:         // gives the result compatible also with open
Chris@101:         // here core_detail::closure::minimum_ring_size<closed> could be used
Chris@101:         if (count < 4)
Chris@16:         {
Chris@101:             // there should be only one missing
Chris@101:             *out++ = *boost::begin(first);
Chris@16:         }
Chris@16:     }
Chris@16: };
Chris@16: 
Chris@16: }} // namespace strategy::convex_hull
Chris@16: 
Chris@16: 
Chris@16: #ifndef DOXYGEN_NO_STRATEGY_SPECIALIZATIONS
Chris@16: template <typename InputGeometry, typename OutputPoint>
Chris@16: struct strategy_convex_hull<InputGeometry, OutputPoint, cartesian_tag>
Chris@16: {
Chris@16:     typedef strategy::convex_hull::graham_andrew<InputGeometry, OutputPoint> type;
Chris@16: };
Chris@16: #endif
Chris@16: 
Chris@16: }} // namespace boost::geometry
Chris@16: 
Chris@16: 
Chris@16: #endif // BOOST_GEOMETRY_STRATEGIES_AGNOSTIC_CONVEX_GRAHAM_ANDREW_HPP