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