summaryrefslogtreecommitdiff
path: root/boost/geometry/algorithms/detail/envelope/range.hpp
blob: b5591f61ab3f5f0fcbd7c675a0eb6b9872182ae9 (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
// Boost.Geometry (aka GGL, Generic Geometry Library)

// Copyright (c) 2007-2015 Barend Gehrels, Amsterdam, the Netherlands.
// Copyright (c) 2008-2015 Bruno Lalande, Paris, France.
// Copyright (c) 2009-2015 Mateusz Loskot, London, UK.

// This file was modified by Oracle on 2015, 2016.
// Modifications copyright (c) 2015-2016, Oracle and/or its affiliates.

// Contributed and/or modified by Vissarion Fysikopoulos, on behalf of Oracle
// Contributed and/or modified by Menelaos Karavelas, on behalf of Oracle

// Parts of Boost.Geometry are redesigned from Geodan's Geographic Library
// (geolib/GGL), copyright (c) 1995-2010 Geodan, Amsterdam, the Netherlands.

// Distributed under the Boost Software License, Version 1.0.
// (See accompanying file LICENSE_1_0.txt or copy at
// http://www.boost.org/LICENSE_1_0.txt)

#ifndef BOOST_GEOMETRY_ALGORITHMS_DETAIL_ENVELOPE_RANGE_HPP
#define BOOST_GEOMETRY_ALGORITHMS_DETAIL_ENVELOPE_RANGE_HPP

#include <iterator>
#include <vector>

#include <boost/range.hpp>

#include <boost/geometry/core/coordinate_dimension.hpp>

#include <boost/geometry/util/range.hpp>

#include <boost/geometry/algorithms/is_empty.hpp>

#include <boost/geometry/algorithms/detail/envelope/initialize.hpp>
#include <boost/geometry/algorithms/detail/envelope/range_of_boxes.hpp>

#include <boost/geometry/algorithms/detail/expand/box.hpp>
#include <boost/geometry/algorithms/detail/expand/point.hpp>
#include <boost/geometry/algorithms/detail/expand/segment.hpp>

#include <boost/geometry/algorithms/dispatch/envelope.hpp>


namespace boost { namespace geometry
{

#ifndef DOXYGEN_NO_DETAIL
namespace detail { namespace envelope
{


// implementation for simple ranges
struct envelope_range
{
    template <typename Iterator, typename Box, typename Strategy>
    static inline void apply(Iterator first,
                             Iterator last,
                             Box& mbr,
                             Strategy const& strategy)
    {
        typedef typename std::iterator_traits<Iterator>::value_type value_type;

        // initialize MBR
        initialize<Box, 0, dimension<Box>::value>::apply(mbr);

        Iterator it = first;
        if (it != last)
        {
            // initialize box with first element in range
            dispatch::envelope<value_type>::apply(*it, mbr, strategy);

            // consider now the remaining elements in the range (if any)
            for (++it; it != last; ++it)
            {
                dispatch::expand<Box, value_type>::apply(mbr, *it, strategy);
            }
        }
    }

    template <typename Range, typename Box, typename Strategy>
    static inline void apply(Range const& range, Box& mbr, Strategy const& strategy)
    {
        return apply(boost::begin(range), boost::end(range), mbr, strategy);
    }
};


// implementation for multi-ranges
template <typename EnvelopePolicy>
struct envelope_multi_range
{
    template <typename MultiRange, typename Box, typename Strategy>
    static inline void apply(MultiRange const& multirange,
                             Box& mbr,
                             Strategy const& strategy)
    {
        typedef typename boost::range_iterator
            <
                MultiRange const
            >::type iterator_type;

        bool initialized = false;
        for (iterator_type it = boost::begin(multirange);
             it != boost::end(multirange);
             ++it)
        {
            if (! geometry::is_empty(*it))
            {
                if (initialized)
                {
                    Box helper_mbr;
                    EnvelopePolicy::apply(*it, helper_mbr, strategy);

                    dispatch::expand<Box, Box>::apply(mbr, helper_mbr, strategy);
                }
                else
                {
                    // compute the initial envelope
                    EnvelopePolicy::apply(*it, mbr, strategy);
                    initialized = true;
                }
            }
        }

        if (! initialized)
        {
            // if not already initialized, initialize MBR
            initialize<Box, 0, dimension<Box>::value>::apply(mbr);
        }
    }
};


// implementation for multi-range on a spheroid (longitude is periodic)
template <typename EnvelopePolicy>
struct envelope_multi_range_on_spheroid
{
    template <typename MultiRange, typename Box, typename Strategy>
    static inline void apply(MultiRange const& multirange,
                             Box& mbr,
                             Strategy const& strategy)
    {
        typedef typename boost::range_iterator
            <
                MultiRange const
            >::type iterator_type;

        // due to the periodicity of longitudes we need to compute the boxes
        // of all the single geometries and keep them in a container
        std::vector<Box> boxes;
        for (iterator_type it = boost::begin(multirange);
             it != boost::end(multirange);
             ++it)
        {
            if (! geometry::is_empty(*it))
            {
                Box helper_box;
                EnvelopePolicy::apply(*it, helper_box, strategy);
                boxes.push_back(helper_box);
            }
        }

        // now we need to compute the envelope of the range of boxes
        // (cannot be done in an incremental fashion as in the
        // Cartesian coordinate system)
        // if all single geometries are empty no boxes have been found
        // and the MBR is simply initialized
        if (! boxes.empty())
        {
            envelope_range_of_boxes::apply(boxes, mbr, strategy);
        }
        else
        {
            initialize<Box, 0, dimension<Box>::value>::apply(mbr);
        }

    }
};


}} // namespace detail::envelope
#endif // DOXYGEN_NO_DETAIL


}} // namespace boost::geometry

#endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_ENVELOPE_RANGE_HPP