]>
Commit | Line | Data |
---|---|---|
7c673cae FG |
1 | // Boost.Geometry (aka GGL, Generic Geometry Library) |
2 | ||
92f5a8d4 | 3 | // Copyright (c) 2014-2018, Oracle and/or its affiliates. |
b32b8144 FG |
4 | |
5 | // Contributed and/or modified by Adam Wulkiewicz, on behalf of Oracle | |
7c673cae FG |
6 | |
7 | // Use, modification and distribution is subject to the Boost Software License, | |
8 | // Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at | |
9 | // http://www.boost.org/LICENSE_1_0.txt) | |
10 | ||
7c673cae FG |
11 | #ifndef BOOST_GEOMETRY_ALGORITHMS_DETAIL_RELATE_TOPOLOGY_CHECK_HPP |
12 | #define BOOST_GEOMETRY_ALGORITHMS_DETAIL_RELATE_TOPOLOGY_CHECK_HPP | |
13 | ||
7c673cae FG |
14 | |
15 | #include <boost/geometry/algorithms/detail/equals/point_point.hpp> | |
92f5a8d4 | 16 | #include <boost/geometry/algorithms/not_implemented.hpp> |
b32b8144 | 17 | |
7c673cae FG |
18 | #include <boost/geometry/policies/compare.hpp> |
19 | ||
20 | #include <boost/geometry/util/has_nan_coordinate.hpp> | |
b32b8144 FG |
21 | #include <boost/geometry/util/range.hpp> |
22 | ||
7c673cae FG |
23 | |
24 | namespace boost { namespace geometry { | |
25 | ||
26 | #ifndef DOXYGEN_NO_DETAIL | |
27 | namespace detail { namespace relate { | |
28 | ||
29 | // TODO: change the name for e.g. something with the word "exterior" | |
30 | ||
31 | template <typename Geometry, | |
92f5a8d4 | 32 | typename EqPPStrategy, |
7c673cae FG |
33 | typename Tag = typename geometry::tag<Geometry>::type> |
34 | struct topology_check | |
35 | : not_implemented<Tag> | |
36 | {}; | |
37 | ||
38 | //template <typename Point> | |
39 | //struct topology_check<Point, point_tag> | |
40 | //{ | |
41 | // static const char interior = '0'; | |
42 | // static const char boundary = 'F'; | |
43 | // | |
44 | // static const bool has_interior = true; | |
45 | // static const bool has_boundary = false; | |
46 | // | |
47 | // topology_check(Point const&) {} | |
48 | // template <typename IgnoreBoundaryPoint> | |
49 | // topology_check(Point const&, IgnoreBoundaryPoint const&) {} | |
50 | //}; | |
51 | ||
92f5a8d4 TL |
52 | template <typename Linestring, typename EqPPStrategy> |
53 | struct topology_check<Linestring, EqPPStrategy, linestring_tag> | |
7c673cae FG |
54 | { |
55 | static const char interior = '1'; | |
56 | static const char boundary = '0'; | |
57 | ||
7c673cae | 58 | topology_check(Linestring const& ls) |
b32b8144 FG |
59 | : m_ls(ls) |
60 | , m_is_initialized(false) | |
61 | {} | |
62 | ||
63 | bool has_interior() const | |
7c673cae | 64 | { |
b32b8144 FG |
65 | init(); |
66 | return m_has_interior; | |
7c673cae FG |
67 | } |
68 | ||
b32b8144 | 69 | bool has_boundary() const |
7c673cae | 70 | { |
b32b8144 FG |
71 | init(); |
72 | return m_has_boundary; | |
7c673cae FG |
73 | } |
74 | ||
b32b8144 FG |
75 | /*template <typename Point> |
76 | bool check_boundary_point(Point const& point) const | |
77 | { | |
78 | init(); | |
79 | return m_has_boundary | |
80 | && ( equals::equals_point_point(point, range::front(m_ls)) | |
81 | || equals::equals_point_point(point, range::back(m_ls)) ); | |
82 | }*/ | |
83 | ||
84 | template <typename Visitor> | |
85 | void for_each_boundary_point(Visitor & visitor) const | |
7c673cae | 86 | { |
b32b8144 FG |
87 | init(); |
88 | if (m_has_boundary) | |
89 | { | |
90 | if (visitor.apply(range::front(m_ls))) | |
91 | visitor.apply(range::back(m_ls)); | |
92 | } | |
93 | } | |
94 | ||
95 | private: | |
96 | void init() const | |
97 | { | |
98 | if (m_is_initialized) | |
99 | return; | |
100 | ||
101 | std::size_t count = boost::size(m_ls); | |
102 | m_has_interior = count > 0; | |
7c673cae | 103 | // NOTE: Linestring with all points equal is treated as 1d linear ring |
b32b8144 | 104 | m_has_boundary = count > 1 |
92f5a8d4 TL |
105 | && ! detail::equals::equals_point_point(range::front(m_ls), |
106 | range::back(m_ls), | |
107 | EqPPStrategy()); | |
b32b8144 FG |
108 | |
109 | m_is_initialized = true; | |
7c673cae | 110 | } |
b32b8144 FG |
111 | |
112 | Linestring const& m_ls; | |
113 | mutable bool m_is_initialized; | |
114 | ||
115 | mutable bool m_has_interior; | |
116 | mutable bool m_has_boundary; | |
7c673cae FG |
117 | }; |
118 | ||
92f5a8d4 TL |
119 | template <typename MultiLinestring, typename EqPPStrategy> |
120 | struct topology_check<MultiLinestring, EqPPStrategy, multi_linestring_tag> | |
7c673cae FG |
121 | { |
122 | static const char interior = '1'; | |
123 | static const char boundary = '0'; | |
124 | ||
7c673cae | 125 | topology_check(MultiLinestring const& mls) |
b32b8144 FG |
126 | : m_mls(mls) |
127 | , m_is_initialized(false) | |
128 | {} | |
129 | ||
130 | bool has_interior() const | |
7c673cae | 131 | { |
b32b8144 FG |
132 | init(); |
133 | return m_has_interior; | |
7c673cae FG |
134 | } |
135 | ||
b32b8144 | 136 | bool has_boundary() const |
7c673cae | 137 | { |
b32b8144 FG |
138 | init(); |
139 | return m_has_boundary; | |
140 | } | |
141 | ||
142 | template <typename Point> | |
143 | bool check_boundary_point(Point const& point) const | |
144 | { | |
145 | init(); | |
146 | ||
147 | if (! m_has_boundary) | |
148 | return false; | |
149 | ||
150 | std::size_t count = count_equal(m_endpoints.begin(), m_endpoints.end(), point); | |
151 | ||
152 | return count % 2 != 0; // odd count -> boundary | |
153 | } | |
154 | ||
155 | template <typename Visitor> | |
156 | void for_each_boundary_point(Visitor & visitor) const | |
157 | { | |
158 | init(); | |
159 | if (m_has_boundary) | |
160 | { | |
161 | for_each_boundary_point(m_endpoints.begin(), m_endpoints.end(), visitor); | |
162 | } | |
7c673cae FG |
163 | } |
164 | ||
b32b8144 | 165 | private: |
92f5a8d4 TL |
166 | typedef geometry::less<void, -1, typename EqPPStrategy::cs_tag> less_type; |
167 | ||
b32b8144 | 168 | void init() const |
7c673cae | 169 | { |
b32b8144 FG |
170 | if (m_is_initialized) |
171 | return; | |
172 | ||
173 | m_endpoints.reserve(boost::size(m_mls) * 2); | |
174 | ||
175 | m_has_interior = false; | |
7c673cae FG |
176 | |
177 | typedef typename boost::range_iterator<MultiLinestring const>::type ls_iterator; | |
b32b8144 | 178 | for ( ls_iterator it = boost::begin(m_mls) ; it != boost::end(m_mls) ; ++it ) |
7c673cae FG |
179 | { |
180 | typename boost::range_reference<MultiLinestring const>::type | |
181 | ls = *it; | |
182 | ||
183 | std::size_t count = boost::size(ls); | |
184 | ||
185 | if (count > 0) | |
186 | { | |
b32b8144 | 187 | m_has_interior = true; |
7c673cae FG |
188 | } |
189 | ||
190 | if (count > 1) | |
191 | { | |
192 | typedef typename boost::range_reference | |
193 | < | |
194 | typename boost::range_value<MultiLinestring const>::type const | |
195 | >::type point_reference; | |
196 | ||
197 | point_reference front_pt = range::front(ls); | |
198 | point_reference back_pt = range::back(ls); | |
199 | ||
200 | // don't store boundaries of linear rings, this doesn't change anything | |
92f5a8d4 | 201 | if (! equals::equals_point_point(front_pt, back_pt, EqPPStrategy())) |
7c673cae FG |
202 | { |
203 | // do not add points containing NaN coordinates | |
204 | // because they cannot be reasonably compared, e.g. with MSVC | |
205 | // an assertion failure is reported in std::equal_range() | |
206 | // NOTE: currently ignoring_counter calling std::equal_range() | |
207 | // is not used anywhere in the code, still it's safer this way | |
208 | if (! geometry::has_nan_coordinate(front_pt)) | |
209 | { | |
b32b8144 | 210 | m_endpoints.push_back(front_pt); |
7c673cae FG |
211 | } |
212 | if (! geometry::has_nan_coordinate(back_pt)) | |
213 | { | |
b32b8144 | 214 | m_endpoints.push_back(back_pt); |
7c673cae FG |
215 | } |
216 | } | |
217 | } | |
218 | } | |
219 | ||
b32b8144 | 220 | m_has_boundary = false; |
7c673cae | 221 | |
b32b8144 | 222 | if (! m_endpoints.empty() ) |
7c673cae | 223 | { |
92f5a8d4 | 224 | std::sort(m_endpoints.begin(), m_endpoints.end(), less_type()); |
b32b8144 | 225 | m_has_boundary = find_odd_count(m_endpoints.begin(), m_endpoints.end()); |
7c673cae | 226 | } |
b32b8144 FG |
227 | |
228 | m_is_initialized = true; | |
7c673cae FG |
229 | } |
230 | ||
b32b8144 FG |
231 | template <typename It, typename Point> |
232 | static inline std::size_t count_equal(It first, It last, Point const& point) | |
7c673cae | 233 | { |
92f5a8d4 | 234 | std::pair<It, It> rng = std::equal_range(first, last, point, less_type()); |
b32b8144 FG |
235 | return (std::size_t)std::distance(rng.first, rng.second); |
236 | } | |
7c673cae | 237 | |
b32b8144 FG |
238 | template <typename It> |
239 | static inline bool find_odd_count(It first, It last) | |
7c673cae | 240 | { |
b32b8144 FG |
241 | interrupting_visitor visitor; |
242 | for_each_boundary_point(first, last, visitor); | |
243 | return visitor.found; | |
244 | } | |
7c673cae | 245 | |
b32b8144 FG |
246 | struct interrupting_visitor |
247 | { | |
248 | bool found; | |
249 | interrupting_visitor() : found(false) {} | |
250 | template <typename Point> | |
251 | bool apply(Point const&) | |
7c673cae | 252 | { |
b32b8144 FG |
253 | found = true; |
254 | return false; | |
7c673cae | 255 | } |
7c673cae FG |
256 | }; |
257 | ||
b32b8144 FG |
258 | template <typename It, typename Visitor> |
259 | static void for_each_boundary_point(It first, It last, Visitor& visitor) | |
7c673cae FG |
260 | { |
261 | if ( first == last ) | |
b32b8144 | 262 | return; |
7c673cae FG |
263 | |
264 | std::size_t count = 1; | |
265 | It prev = first; | |
266 | ++first; | |
267 | for ( ; first != last ; ++first, ++prev ) | |
268 | { | |
269 | // the end of the equal points subrange | |
92f5a8d4 | 270 | if ( ! equals::equals_point_point(*first, *prev, EqPPStrategy()) ) |
7c673cae | 271 | { |
b32b8144 | 272 | // odd count -> boundary |
7c673cae | 273 | if ( count % 2 != 0 ) |
b32b8144 FG |
274 | { |
275 | if (! visitor.apply(*prev)) | |
276 | { | |
277 | return; | |
278 | } | |
279 | } | |
7c673cae FG |
280 | |
281 | count = 1; | |
282 | } | |
283 | else | |
284 | { | |
285 | ++count; | |
286 | } | |
287 | } | |
288 | ||
b32b8144 FG |
289 | // odd count -> boundary |
290 | if ( count % 2 != 0 ) | |
291 | { | |
292 | visitor.apply(*prev); | |
293 | } | |
7c673cae | 294 | } |
b32b8144 FG |
295 | |
296 | private: | |
297 | MultiLinestring const& m_mls; | |
298 | mutable bool m_is_initialized; | |
299 | ||
300 | mutable bool m_has_interior; | |
301 | mutable bool m_has_boundary; | |
302 | ||
303 | typedef typename geometry::point_type<MultiLinestring>::type point_type; | |
304 | mutable std::vector<point_type> m_endpoints; | |
7c673cae FG |
305 | }; |
306 | ||
92f5a8d4 | 307 | struct topology_check_areal |
7c673cae FG |
308 | { |
309 | static const char interior = '2'; | |
310 | static const char boundary = '1'; | |
7c673cae | 311 | |
b32b8144 FG |
312 | static bool has_interior() { return true; } |
313 | static bool has_boundary() { return true; } | |
7c673cae FG |
314 | }; |
315 | ||
92f5a8d4 TL |
316 | template <typename Ring, typename EqPPStrategy> |
317 | struct topology_check<Ring, EqPPStrategy, ring_tag> | |
318 | : topology_check_areal | |
7c673cae | 319 | { |
92f5a8d4 TL |
320 | topology_check(Ring const&) {} |
321 | }; | |
b32b8144 | 322 | |
92f5a8d4 TL |
323 | template <typename Polygon, typename EqPPStrategy> |
324 | struct topology_check<Polygon, EqPPStrategy, polygon_tag> | |
325 | : topology_check_areal | |
326 | { | |
327 | topology_check(Polygon const&) {} | |
7c673cae FG |
328 | }; |
329 | ||
92f5a8d4 TL |
330 | template <typename MultiPolygon, typename EqPPStrategy> |
331 | struct topology_check<MultiPolygon, EqPPStrategy, multi_polygon_tag> | |
332 | : topology_check_areal | |
7c673cae | 333 | { |
7c673cae | 334 | topology_check(MultiPolygon const&) {} |
92f5a8d4 | 335 | |
b32b8144 FG |
336 | template <typename Point> |
337 | static bool check_boundary_point(Point const& ) { return true; } | |
7c673cae FG |
338 | }; |
339 | ||
340 | }} // namespace detail::relate | |
341 | #endif // DOXYGEN_NO_DETAIL | |
342 | ||
343 | }} // namespace boost::geometry | |
344 | ||
345 | #endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_RELATE_TOPOLOGY_CHECK_HPP |