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