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>
applyboost::geometry::detail::envelope::envelope_range56     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>
applyboost::geometry::detail::envelope::envelope_range81     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>
applyboost::geometry::detail::envelope::envelope_multi_range93     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>
applyboost::geometry::detail::envelope::envelope_multi_range_on_spheroid139     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
188