← Back to branch summary

~ubuntu-branches/ubuntu/saucy/merkaartor/saucy

« back to all changes in this revision

Viewing changes to include/builtin-ggl/ggl/strategies/agnostic/agn_convex_hull.hpp

Tags: upstream-0.15.3+svn20934
Import upstream version 0.15.3+svn20934

Show diffs side-by-side

added added

removed removed

Lines of Context:
include/builtin-ggl/ggl/strategies/agnostic/agn_convex_hull.hpp
 
1
// Generic Geometry Library
 
2
//
 
3
// Copyright Barend Gehrels 1995-2009, Geodan Holding B.V. Amsterdam, the Netherlands.
 
4
// Copyright Bruno Lalande 2008, 2009
 
5
// Use, modification and distribution is subject to the Boost Software License,
 
6
// Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
 
7
// http://www.boost.org/LICENSE_1_0.txt)
 
8
 
 
9
#ifndef GGL_STRATEGIES_AGNOSTIC_CONVEX_HULL_HPP
 
10
#define GGL_STRATEGIES_AGNOSTIC_CONVEX_HULL_HPP
 
11
 
 
12
#ifdef _MSC_VER
 
13
#pragma warning( disable : 4101 )
 
14
#endif
 
15
 
 
16
#include <cstddef>
 
17
#include <algorithm>
 
18
#include <vector>
 
19
 
 
20
#include <boost/range/functions.hpp>
 
21
 
 
22
#include <ggl/core/cs.hpp>
 
23
#include <ggl/strategies/strategy_traits.hpp>
 
24
 
 
25
// TODO: Temporary, comparing tests, this can be removed in the end
 
26
#if defined(GGL_USE_SMOOTH_SORT)
 
27
#  include "SmoothSort.hpp"
 
28
#elif defined(GGL_USE_MERGE_SORT)
 
29
#  include "MergeSort.hpp"
 
30
#else
 
31
#endif
 
32
 
 
33
namespace ggl
 
34
{
 
35
 
 
36
namespace strategy { namespace convex_hull {
 
37
 
 
38
#ifndef DOXYGEN_NO_DETAIL
 
39
namespace detail
 
40
{
 
41
 
 
42
template <typename Range, typename RangeIterator, typename Strategy>
 
43
static inline void get_extremes(const Range& range,
 
44
            RangeIterator& min_it, RangeIterator& max_it,
 
45
            const Strategy& strategy)
 
46
{
 
47
    min_it = boost::begin(range);
 
48
    max_it = boost::begin(range);
 
49
 
 
50
    for (RangeIterator it = boost::begin(range) + 1; it != boost::end(range); ++it)
 
51
    {
 
52
        if (strategy.smaller(*it, *min_it))
 
53
        {
 
54
            min_it = it;
 
55
        }
 
56
 
 
57
        if (strategy.larger(*it, *max_it))
 
58
        {
 
59
            max_it = it;
 
60
        }
 
61
    }
 
62
}
 
63
 
 
64
template <typename R>
 
65
static inline void sort(R& range)
 
66
{
 
67
    #if defined(USE_SMOOTH_SORT)
 
68
    smoothsort::sort(boost::begin(range), boost::end(range));
 
69
    #elif defined(USE_MERGE_SORT)
 
70
    comparing::merge_sort<thread_count>(boost::begin(range), boost::end(range), std::less<P>());
 
71
    #else
 
72
    std::sort(boost::begin(range), boost::end(range));
 
73
    #endif
 
74
}
 
75
 
 
76
} // namespace detail
 
77
#endif // DOXYGEN_NO_DETAIL
 
78
 
 
79
 
 
80
// Completely reworked version from source at:
 
81
// http://www.ddj.com/architect/201806315
 
82
// also available at http://marknelson.us/2007/08/22/convex
 
83
template <typename P>
 
84
class graham
 
85
{
 
86
private:
 
87
 
 
88
    typedef typename cs_tag<P>::type cs_tag;
 
89
    typedef typename std::vector<P> container;
 
90
    typedef typename std::vector<P>::const_iterator iterator;
 
91
    typedef typename std::vector<P>::const_reverse_iterator rev_iterator;
 
92
 
 
93
    container m_lower_hull;
 
94
    container m_upper_hull;
 
95
    container m_copied_input;
 
96
 
 
97
 
 
98
public:
 
99
 
 
100
    // Default constructor, ranges can be added using "add_range" but note they'll be copied
 
101
    inline graham()
 
102
    {
 
103
    }
 
104
 
 
105
    // Constructor with a range
 
106
    template <typename Range>
 
107
    inline graham(const Range& range)
 
108
    {
 
109
        handle_range(range);
 
110
    }
 
111
 
 
112
 
 
113
    template <typename OutputIterator>
 
114
    inline void get(OutputIterator out)
 
115
    {
 
116
        for (iterator it = m_upper_hull.begin(); it != m_upper_hull.end(); ++it, ++out)
 
117
        {
 
118
            *out = *it;
 
119
        }
 
120
 
 
121
        // STL Port does not accept iterating from rbegin+1 to rend
 
122
        std::size_t size = m_lower_hull.size();
 
123
        if (size > 0)
 
124
        {
 
125
            rev_iterator it = m_lower_hull.rbegin() + 1;
 
126
            for (std::size_t i = 1; i < size; ++i, ++it, ++out)
 
127
            {
 
128
                *out = *it;
 
129
            }
 
130
        }
 
131
    }
 
132
 
 
133
 
 
134
    // Note /
 
135
    // TODO:
 
136
    // Consider if it is better to create an iterator over a multi, which is then used here,
 
137
    // instead of copying the range
 
138
    // It makes it slightly more complicated but avoids the copy, which is attractive because
 
139
    // multi-polygons (where it is used for) can be large.
 
140
    template <typename Range>
 
141
    inline void add_range(const Range& range)
 
142
    {
 
143
        std::copy(boost::begin(range), boost::end(range), std::back_inserter(m_copied_input));
 
144
    }
 
145
 
 
146
    inline void handle_input()
 
147
    {
 
148
        handle_range(m_copied_input);
 
149
    }
 
150
 
 
151
 
 
152
private:
 
153
 
 
154
    template <typename Range>
 
155
    inline void handle_range(const Range& range)
 
156
    {
 
157
        typedef typename boost::range_const_iterator<Range>::type range_iterator;
 
158
 
 
159
        // Polygons with three corners, or closed with 4 points, are always convex
 
160
        if (boost::size(range) <= 3)
 
161
        {
 
162
            for (range_iterator it = boost::begin(range);
 
163
                        it != boost::end(range);
 
164
                        ++it)
 
165
            {
 
166
                m_upper_hull.push_back(*it);
 
167
            }
 
168
            return;
 
169
        }
 
170
 
 
171
        // Get min/max (in most cases left / right) points
 
172
        range_iterator left_it, right_it;
 
173
        typename strategy_compare<cs_tag, P, 0>::type comparing;
 
174
        detail::get_extremes(range, left_it, right_it, comparing);
 
175
 
 
176
        // Bounding left/right points
 
177
        container lower_points, upper_points;
 
178
 
 
179
        assign_range(range, left_it, right_it, lower_points, upper_points);
 
180
 
 
181
        detail::sort(lower_points);
 
182
        detail::sort(upper_points);
 
183
 
 
184
        build_half_hull<1>(lower_points, m_lower_hull, *left_it, *right_it);
 
185
        build_half_hull<-1>(upper_points, m_upper_hull, *left_it, *right_it);
 
186
    }
 
187
 
 
188
 
 
189
 
 
190
    template <typename RangeIterator, typename Range>
 
191
    inline void assign_range(const Range& range,
 
192
            const RangeIterator& left_it,
 
193
            const RangeIterator& right_it,
 
194
            container& lower_points,
 
195
            container& upper_points)
 
196
    {
 
197
        typename strategy_side<cs_tag, P>::type side;
 
198
 
 
199
        // Put points in one of the two output sequences
 
200
        for (RangeIterator it = boost::begin(range);
 
201
            it != boost::end(range);
 
202
            ++it)
 
203
        {
 
204
            if (it != left_it && it != right_it)
 
205
            {
 
206
                int dir = side.side(*left_it, *right_it, *it);
 
207
                if ( dir < 0 )
 
208
                {
 
209
                    upper_points.push_back(*it);
 
210
                }
 
211
                else
 
212
                {
 
213
                    lower_points.push_back(*it);
 
214
                }
 
215
            }
 
216
        }
 
217
    }
 
218
 
 
219
 
 
220
    template <int Factor>
 
221
    inline void build_half_hull(const container& input, container& output,
 
222
            const P& left, const P& right)
 
223
    {
 
224
        output.push_back(left);
 
225
        for(iterator it = input.begin(); it != input.end(); ++it)
 
226
        {
 
227
            add_to_hull<Factor>(*it, output);
 
228
        }
 
229
        add_to_hull<Factor>(right, output);
 
230
    }
 
231
 
 
232
    template <int Factor>
 
233
    inline void add_to_hull(const P& p, container& output)
 
234
    {
 
235
        typename strategy_side<cs_tag, P>::type side;
 
236
 
 
237
        output.push_back(p);
 
238
        register std::size_t output_size = output.size();
 
239
        while (output_size >= 3)
 
240
        {
 
241
            rev_iterator rit = output.rbegin();
 
242
            const P& last = *rit++;
 
243
            const P& last2 = *rit++;
 
244
 
 
245
            if (Factor * side.side(*rit, last, last2) <= 0)
 
246
            {
 
247
                // Remove last two points from stack, and add last again
 
248
                // This is much faster then erasing the one but last.
 
249
                output.pop_back();
 
250
                output.pop_back();
 
251
                output.push_back(last);
 
252
                output_size--;
 
253
            }
 
254
            else
 
255
            {
 
256
                return;
 
257
            }
 
258
        }
 
259
    }
 
260
 
 
261
 
 
262
};
 
263
 
 
264
}} // namespace strategy::convex_hull
 
265
 
 
266
 
 
267
#ifndef DOXYGEN_NO_STRATEGY_SPECIALIZATIONS
 
268
template <typename P>
 
269
struct strategy_convex_hull<cartesian_tag, P>
 
270
{
 
271
    typedef strategy::convex_hull::graham<P> type;
 
272
};
 
273
#endif
 
274
 
 
275
} // namespace ggl
 
276
 
 
277
 
 
278
#endif // GGL_STRATEGY_AGNOSTIC_CONVEX_HULL_HPP