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
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
|
// Boost.Geometry (aka GGL, Generic Geometry Library)
// Copyright (c) 2014, Oracle and/or its affiliates.
// Use, modification and distribution is subject to 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)
// Contributed and/or modified by Adam Wulkiewicz, on behalf of Oracle
#ifndef BOOST_GEOMETRY_ALGORITHMS_DETAIL_RELATE_TOPOLOGY_CHECK_HPP
#define BOOST_GEOMETRY_ALGORITHMS_DETAIL_RELATE_TOPOLOGY_CHECK_HPP
#include <boost/geometry/util/range.hpp>
#include <boost/geometry/algorithms/detail/equals/point_point.hpp>
#include <boost/geometry/policies/compare.hpp>
namespace boost { namespace geometry {
#ifndef DOXYGEN_NO_DETAIL
namespace detail { namespace relate {
// TODO: change the name for e.g. something with the word "exterior"
template <typename Geometry,
typename Tag = typename geometry::tag<Geometry>::type>
struct topology_check
: not_implemented<Tag>
{};
//template <typename Point>
//struct topology_check<Point, point_tag>
//{
// static const char interior = '0';
// static const char boundary = 'F';
//
// static const bool has_interior = true;
// static const bool has_boundary = false;
//
// topology_check(Point const&) {}
// template <typename IgnoreBoundaryPoint>
// topology_check(Point const&, IgnoreBoundaryPoint const&) {}
//};
template <typename Linestring>
struct topology_check<Linestring, linestring_tag>
{
static const char interior = '1';
static const char boundary = '0';
bool has_interior;
bool has_boundary;
topology_check(Linestring const& ls)
{
init(ls, 0); /*dummy param*/
}
template <typename IgnoreBoundaryPoint>
topology_check(Linestring const& ls, IgnoreBoundaryPoint const& ibp)
{
init(ls, ibp); /*dummy param, won't be used*/
}
// Even if some point is on the boundary, if the Linestring has the boundary,
// there will be second boundary point different than IgnoreBoundaryPoint
template <typename IgnoreBoundaryPoint>
void init(Linestring const& ls, IgnoreBoundaryPoint const&)
{
std::size_t count = boost::size(ls);
has_interior = count > 0;
// NOTE: Linestring with all points equal is treated as 1d linear ring
has_boundary = count > 1
&& ! detail::equals::equals_point_point(range::front(ls), range::back(ls));
}
};
template <typename MultiLinestring>
struct topology_check<MultiLinestring, multi_linestring_tag>
{
static const char interior = '1';
static const char boundary = '0';
bool has_interior;
bool has_boundary;
topology_check(MultiLinestring const& mls)
{
init(mls, not_ignoring_counter());
}
template <typename IgnoreBoundaryPoint>
topology_check(MultiLinestring const& mls, IgnoreBoundaryPoint const& ibp)
{
init(mls, ignoring_counter<IgnoreBoundaryPoint>(ibp));
}
template <typename OddCounter>
void init(MultiLinestring const& mls, OddCounter const& odd_counter)
{
typedef typename geometry::point_type<MultiLinestring>::type point_type;
std::vector<point_type> endpoints;
endpoints.reserve(boost::size(mls) * 2);
typedef typename boost::range_iterator<MultiLinestring const>::type ls_iterator;
for ( ls_iterator it = boost::begin(mls) ; it != boost::end(mls) ; ++it )
{
std::size_t count = boost::size(*it);
if ( count > 0 )
{
has_interior = true;
}
if ( count > 1 )
{
// don't store boundaries of linear rings, this doesn't change anything
if ( ! equals::equals_point_point(range::front(*it), range::back(*it)) )
{
endpoints.push_back(range::front(*it));
endpoints.push_back(range::back(*it));
}
}
}
has_boundary = false;
if ( !endpoints.empty() )
{
std::sort(endpoints.begin(), endpoints.end(), geometry::less<point_type>());
has_boundary = odd_counter(endpoints.begin(), endpoints.end());
}
}
struct not_ignoring_counter
{
template <typename It>
bool operator()(It first, It last) const
{
return find_odd_count(first, last);
}
};
template <typename Point>
struct ignoring_counter
{
ignoring_counter(Point const& pt) : m_pt(pt) {}
template <typename It>
bool operator()(It first, It last) const
{
typedef typename std::iterator_traits<It>::value_type point_type;
std::pair<It, It> ignore_range
= std::equal_range(first, last, m_pt,
geometry::less<point_type>());
if ( find_odd_count(first, ignore_range.first) )
return true;
return find_odd_count(ignore_range.second, last);
}
Point const& m_pt;
};
template <typename It>
static inline bool find_odd_count(It first, It last)
{
if ( first == last )
return false;
std::size_t count = 1;
It prev = first;
++first;
for ( ; first != last ; ++first, ++prev )
{
// the end of the equal points subrange
if ( ! equals::equals_point_point(*first, *prev) )
{
if ( count % 2 != 0 )
return true;
count = 1;
}
else
{
++count;
}
}
return count % 2 != 0;
}
};
template <typename Ring>
struct topology_check<Ring, ring_tag>
{
static const char interior = '2';
static const char boundary = '1';
static const bool has_interior = true;
static const bool has_boundary = true;
topology_check(Ring const&) {}
template <typename P>
topology_check(Ring const&, P const&) {}
};
template <typename Polygon>
struct topology_check<Polygon, polygon_tag>
{
static const char interior = '2';
static const char boundary = '1';
static const bool has_interior = true;
static const bool has_boundary = true;
topology_check(Polygon const&) {}
template <typename P>
topology_check(Polygon const&, P const&) {}
};
template <typename MultiPolygon>
struct topology_check<MultiPolygon, multi_polygon_tag>
{
static const char interior = '2';
static const char boundary = '1';
static const bool has_interior = true;
static const bool has_boundary = true;
topology_check(MultiPolygon const&) {}
template <typename P>
topology_check(MultiPolygon const&, P const&) {}
};
}} // namespace detail::relate
#endif // DOXYGEN_NO_DETAIL
}} // namespace boost::geometry
#endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_RELATE_TOPOLOGY_CHECK_HPP
|
