ceph/src/boost/boost/geometry/algorithms/detail/envelope/range.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 2015, 2016.
   8 // Modifications copyright (c) 2015-2016, Oracle and/or its affiliates.
   9
  10 // Contributed and/or modified by Vissarion Fysikopoulos, 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 // Distributed under the Boost Software License, Version 1.0.
  17 // (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_DETAIL_ENVELOPE_RANGE_HPP
  21 #define BOOST_GEOMETRY_ALGORITHMS_DETAIL_ENVELOPE_RANGE_HPP
  22
  23 #include <iterator>
  24 #include <vector>
  25
  26 #include <boost/range.hpp>
  27
  28 #include <boost/geometry/core/coordinate_dimension.hpp>
  29
  30 #include <boost/geometry/util/range.hpp>
  31
  32 #include <boost/geometry/algorithms/is_empty.hpp>
  33
  34 #include <boost/geometry/algorithms/detail/envelope/initialize.hpp>
  35 #include <boost/geometry/algorithms/detail/envelope/range_of_boxes.hpp>
  36
  37 #include <boost/geometry/algorithms/detail/expand/box.hpp>
  38 #include <boost/geometry/algorithms/detail/expand/point.hpp>
  39 #include <boost/geometry/algorithms/detail/expand/segment.hpp>
  40
  41 #include <boost/geometry/algorithms/dispatch/envelope.hpp>
  42
  43
  44 namespace boost { namespace geometry
  45 {
  46
  47 #ifndef DOXYGEN_NO_DETAIL
  48 namespace detail { namespace envelope
  49 {
  50
  51
  52 // implementation for simple ranges
  53 struct envelope_range
  54 {
  55     template <typename Iterator, typename Box, typename Strategy>
  56     static inline void apply(Iterator first,
  57                              Iterator last,
  58                              Box& mbr,
  59                              Strategy const& strategy)
  60     {
  61         typedef typename std::iterator_traits<Iterator>::value_type value_type;
  62
  63         // initialize MBR
  64         initialize<Box, 0, dimension<Box>::value>::apply(mbr);
  65
  66         Iterator it = first;
  67         if (it != last)
  68         {
  69             // initialize box with first element in range
  70             dispatch::envelope<value_type>::apply(*it, mbr, strategy);
  71
  72             // consider now the remaining elements in the range (if any)
  73             for (++it; it != last; ++it)
  74             {
  75                 dispatch::expand<Box, value_type>::apply(mbr, *it, strategy);
  76             }
  77         }
  78     }
  79
  80     template <typename Range, typename Box, typename Strategy>
  81     static inline void apply(Range const& range, Box& mbr, Strategy const& strategy)
  82     {
  83         return apply(boost::begin(range), boost::end(range), mbr, strategy);
  84     }
  85 };
  86
  87
  88 // implementation for multi-ranges
  89 template <typename EnvelopePolicy>
  90 struct envelope_multi_range
  91 {
  92     template <typename MultiRange, typename Box, typename Strategy>
  93     static inline void apply(MultiRange const& multirange,
  94                              Box& mbr,
  95                              Strategy const& strategy)
  96     {
  97         typedef typename boost::range_iterator
  98             <
  99                 MultiRange const
 100             >::type iterator_type;
 101
 102         bool initialized = false;
 103         for (iterator_type it = boost::begin(multirange);
 104              it != boost::end(multirange);
 105              ++it)
 106         {
 107             if (! geometry::is_empty(*it))
 108             {
 109                 if (initialized)
 110                 {
 111                     Box helper_mbr;
 112                     EnvelopePolicy::apply(*it, helper_mbr, strategy);
 113
 114                     dispatch::expand<Box, Box>::apply(mbr, helper_mbr, strategy);
 115                 }
 116                 else
 117                 {
 118                     // compute the initial envelope
 119                     EnvelopePolicy::apply(*it, mbr, strategy);
 120                     initialized = true;
 121                 }
 122             }
 123         }
 124
 125         if (! initialized)
 126         {
 127             // if not already initialized, initialize MBR
 128             initialize<Box, 0, dimension<Box>::value>::apply(mbr);
 129         }
 130     }
 131 };
 132
 133
 134 // implementation for multi-range on a spheroid (longitude is periodic)
 135 template <typename EnvelopePolicy>
 136 struct envelope_multi_range_on_spheroid
 137 {
 138     template <typename MultiRange, typename Box, typename Strategy>
 139     static inline void apply(MultiRange const& multirange,
 140                              Box& mbr,
 141                              Strategy const& strategy)
 142     {
 143         typedef typename boost::range_iterator
 144             <
 145                 MultiRange const
 146             >::type iterator_type;
 147
 148         // due to the periodicity of longitudes we need to compute the boxes
 149         // of all the single geometries and keep them in a container
 150         std::vector<Box> boxes;
 151         for (iterator_type it = boost::begin(multirange);
 152              it != boost::end(multirange);
 153              ++it)
 154         {
 155             if (! geometry::is_empty(*it))
 156             {
 157                 Box helper_box;
 158                 EnvelopePolicy::apply(*it, helper_box, strategy);
 159                 boxes.push_back(helper_box);
 160             }
 161         }
 162
 163         // now we need to compute the envelope of the range of boxes
 164         // (cannot be done in an incremental fashion as in the
 165         // Cartesian coordinate system)
 166         // if all single geometries are empty no boxes have been found
 167         // and the MBR is simply initialized
 168         if (! boxes.empty())
 169         {
 170             envelope_range_of_boxes::apply(boxes, mbr, strategy);
 171         }
 172         else
 173         {
 174             initialize<Box, 0, dimension<Box>::value>::apply(mbr);
 175         }
 176
 177     }
 178 };
 179
 180
 181 }} // namespace detail::envelope
 182 #endif // DOXYGEN_NO_DETAIL
 183
 184
 185 }} // namespace boost::geometry
 186
 187 #endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_ENVELOPE_RANGE_HPP