← Back to branch summary

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

« back to all changes in this revision

Viewing changes to include/ggl/algorithms/overlay/merge_intersection_points.hpp

  • Committer: Bazaar Package Importer
  • Author(s): Bernd Zeimetz
  • Date: 2009-09-13 00:52:12 UTC
  • mto: (1.2.7 upstream) (0.1.3 upstream) (3.1.7 sid)
  • mto: This revision was merged to the branch mainline in revision 10.
  • Revision ID: james.westby@ubuntu.com-20090913005212-pjecal8zxm07x0fj
Import upstream version 0.14+svnfixes~20090912

Show diffs side-by-side

added added

removed removed

Lines of Context:
include/ggl/algorithms/overlay/merge_intersection_points.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_ALGORITHMS_MERGE_INTERSECTION_POINTS_HPP
 
10
#define GGL_ALGORITHMS_MERGE_INTERSECTION_POINTS_HPP
 
11
 
 
12
#include <algorithm>
 
13
 
 
14
 
 
15
#include <boost/range/functions.hpp>
 
16
#include <boost/range/metafunctions.hpp>
 
17
 
 
18
 
 
19
#include <ggl/core/coordinate_type.hpp>
 
20
 
 
21
#include <ggl/algorithms/equals.hpp>
 
22
 
 
23
 
 
24
namespace ggl
 
25
{
 
26
 
 
27
 
 
28
#ifndef DOXYGEN_NO_DETAIL
 
29
namespace detail { namespace intersection {
 
30
 
 
31
template <typename PointType>
 
32
struct on_increasing_dimension
 
33
{
 
34
    typedef typename ggl::coordinate_type<PointType>::type coordinate_type;
 
35
 
 
36
    inline bool operator()(PointType const& lhs, PointType const& rhs) const
 
37
    {
 
38
        coordinate_type const& left0 = ggl::get<0>(lhs);
 
39
        coordinate_type const& right0 = ggl::get<0>(rhs);
 
40
 
 
41
        return math::equals(left0, right0)
 
42
            ? ggl::get<1>(lhs) < ggl::get<1>(rhs)
 
43
            : left0 < right0;
 
44
    }
 
45
};
 
46
 
 
47
 
 
48
template <typename T>
 
49
struct is_collinear
 
50
{
 
51
    inline bool operator()(T const& object) const
 
52
    {
 
53
        typedef typename T::traversal_vector tv;
 
54
        typedef typename boost::range_const_iterator<tv>::type tvit_type;
 
55
        for (tvit_type it = boost::begin(object.info);
 
56
                it != boost::end(object.info); ++it)
 
57
        {
 
58
            // If not collinear / not "TO", do NOT delete (false)
 
59
            if (it->how != 'c' && it->how != 't' && it->how != 'm')
 
60
            {
 
61
                return false;
 
62
            }
 
63
 
 
64
        }
 
65
        return true;
 
66
    }
 
67
};
 
68
 
 
69
 
 
70
template <typename T, int Index>
 
71
struct shared_code_is
 
72
{
 
73
    inline bool operator()(T const& object) const
 
74
    {
 
75
        return object.shared_code == Index;
 
76
    }
 
77
};
 
78
 
 
79
 
 
80
}} // namespace detail::intersection
 
81
#endif //DOXYGEN_NO_DETAIL
 
82
 
 
83
 
 
84
 
 
85
template <typename V>
 
86
inline void merge_intersection_points(V& intersection_points)
 
87
{
 
88
    typedef typename boost::range_value<V>::type trav_type;
 
89
 
 
90
    // Remove all IP's which are collinear
 
91
    intersection_points.erase(
 
92
        std::remove_if(
 
93
                boost::begin(intersection_points),
 
94
                boost::end(intersection_points),
 
95
                detail::intersection::is_collinear<trav_type>()),
 
96
        boost::end(intersection_points));
 
97
 
 
98
    if (intersection_points.size() <= 1)
 
99
    {
 
100
        return;
 
101
    }
 
102
 
 
103
 
 
104
    // Sort all IP's from left->right, ymin->ymax such that
 
105
    // all same IP's are consecutive
 
106
    // (and we need this order lateron again)
 
107
    // This order is NOT changed here and should not be after
 
108
    // (otherwise indexes are wrong)
 
109
    std::sort(boost::begin(intersection_points),
 
110
        boost::end(intersection_points),
 
111
        detail::intersection::on_increasing_dimension<trav_type>());
 
112
 
 
113
    typedef typename boost::range_iterator<V>::type iterator;
 
114
 
 
115
#ifdef GGL_DEBUG_INTERSECTION
 
116
    std::cout << "Sorted (x then y): " << std::endl;
 
117
    for (iterator it = boost::begin(intersection_points);
 
118
        it != boost::end(intersection_points); ++it)
 
119
    {
 
120
        std::cout << *it;
 
121
    }
 
122
#endif
 
123
    bool has_merge = false;
 
124
 
 
125
    // Merge all same IP's, combining there IP/segment-info entries
 
126
    iterator it = boost::begin(intersection_points);
 
127
    for (iterator prev = it++; it != boost::end(intersection_points); ++it)
 
128
    {
 
129
        // IP can be merged if the point is equal
 
130
        if (ggl::equals(prev->point, it->point))
 
131
        {
 
132
            has_merge = true;
 
133
            prev->shared_code = 1;
 
134
            it->shared_code = 2;
 
135
            std::copy(it->info.begin(), it->info.end(),
 
136
                        std::back_inserter(prev->info));
 
137
        }
 
138
        else
 
139
        {
 
140
            prev = it;
 
141
        }
 
142
    }
 
143
 
 
144
    if (has_merge)
 
145
    {
 
146
 
 
147
        // Remove all IP's which are merged (code=2)
 
148
        intersection_points.erase(
 
149
            std::remove_if(
 
150
                    boost::begin(intersection_points),
 
151
                    boost::end(intersection_points),
 
152
                    detail::intersection::shared_code_is<trav_type, 2>()),
 
153
            boost::end(intersection_points));
 
154
 
 
155
 
 
156
#ifdef GGL_DEBUG_INTERSECTION
 
157
        std::cout << "Merged: " << std::endl;
 
158
        for (iterator it = boost::begin(intersection_points);
 
159
            it != boost::end(intersection_points);
 
160
            ++it)
 
161
        {
 
162
            std::cout << *it;
 
163
        }
 
164
#endif
 
165
    }
 
166
}
 
167
 
 
168
} // namespace ggl
 
169
 
 
170
#endif // GGL_ALGORITHMS_MERGE_INTERSECTION_POINTS_HPP