1 // Boost.Geometry (aka GGL, Generic Geometry Library)
3 // Copyright (c) 2014, Oracle and/or its affiliates.
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)
9 // Contributed and/or modified by Adam Wulkiewicz, on behalf of Oracle
11 #ifndef BOOST_GEOMETRY_ALGORITHMS_DETAIL_RELATE_TOPOLOGY_CHECK_HPP
12 #define BOOST_GEOMETRY_ALGORITHMS_DETAIL_RELATE_TOPOLOGY_CHECK_HPP
14 #include <boost/geometry/util/range.hpp>
16 #include <boost/geometry/algorithms/detail/equals/point_point.hpp>
17 #include <boost/geometry/policies/compare.hpp>
19 #include <boost/geometry/util/has_nan_coordinate.hpp>
21 namespace boost { namespace geometry {
23 #ifndef DOXYGEN_NO_DETAIL
24 namespace detail { namespace relate {
26 // TODO: change the name for e.g. something with the word "exterior"
28 template <typename Geometry,
29 typename Tag = typename geometry::tag<Geometry>::type>
31 : not_implemented<Tag>
34 //template <typename Point>
35 //struct topology_check<Point, point_tag>
37 // static const char interior = '0';
38 // static const char boundary = 'F';
40 // static const bool has_interior = true;
41 // static const bool has_boundary = false;
43 // topology_check(Point const&) {}
44 // template <typename IgnoreBoundaryPoint>
45 // topology_check(Point const&, IgnoreBoundaryPoint const&) {}
48 template <typename Linestring>
49 struct topology_check<Linestring, linestring_tag>
51 static const char interior = '1';
52 static const char boundary = '0';
57 topology_check(Linestring const& ls)
59 init(ls, 0); /*dummy param*/
62 template <typename IgnoreBoundaryPoint>
63 topology_check(Linestring const& ls, IgnoreBoundaryPoint const& ibp)
65 init(ls, ibp); /*dummy param, won't be used*/
68 // Even if some point is on the boundary, if the Linestring has the boundary,
69 // there will be second boundary point different than IgnoreBoundaryPoint
70 template <typename IgnoreBoundaryPoint>
71 void init(Linestring const& ls, IgnoreBoundaryPoint const&)
73 std::size_t count = boost::size(ls);
74 has_interior = count > 0;
75 // NOTE: Linestring with all points equal is treated as 1d linear ring
76 has_boundary = count > 1
77 && ! detail::equals::equals_point_point(range::front(ls), range::back(ls));
81 template <typename MultiLinestring>
82 struct topology_check<MultiLinestring, multi_linestring_tag>
84 static const char interior = '1';
85 static const char boundary = '0';
90 topology_check(MultiLinestring const& mls)
92 init(mls, not_ignoring_counter());
95 template <typename IgnoreBoundaryPoint>
96 topology_check(MultiLinestring const& mls, IgnoreBoundaryPoint const& ibp)
98 init(mls, ignoring_counter<IgnoreBoundaryPoint>(ibp));
101 template <typename OddCounter>
102 void init(MultiLinestring const& mls, OddCounter const& odd_counter)
104 typedef typename geometry::point_type<MultiLinestring>::type point_type;
105 std::vector<point_type> endpoints;
106 endpoints.reserve(boost::size(mls) * 2);
108 typedef typename boost::range_iterator<MultiLinestring const>::type ls_iterator;
109 for ( ls_iterator it = boost::begin(mls) ; it != boost::end(mls) ; ++it )
111 typename boost::range_reference<MultiLinestring const>::type
114 std::size_t count = boost::size(ls);
123 typedef typename boost::range_reference
125 typename boost::range_value<MultiLinestring const>::type const
126 >::type point_reference;
128 point_reference front_pt = range::front(ls);
129 point_reference back_pt = range::back(ls);
131 // don't store boundaries of linear rings, this doesn't change anything
132 if (! equals::equals_point_point(front_pt, back_pt))
134 // do not add points containing NaN coordinates
135 // because they cannot be reasonably compared, e.g. with MSVC
136 // an assertion failure is reported in std::equal_range()
137 // NOTE: currently ignoring_counter calling std::equal_range()
138 // is not used anywhere in the code, still it's safer this way
139 if (! geometry::has_nan_coordinate(front_pt))
141 endpoints.push_back(front_pt);
143 if (! geometry::has_nan_coordinate(back_pt))
145 endpoints.push_back(back_pt);
151 has_boundary = false;
153 if ( !endpoints.empty() )
155 std::sort(endpoints.begin(), endpoints.end(), geometry::less<point_type>());
156 has_boundary = odd_counter(endpoints.begin(), endpoints.end());
160 struct not_ignoring_counter
162 template <typename It>
163 bool operator()(It first, It last) const
165 return find_odd_count(first, last);
169 template <typename Point>
170 struct ignoring_counter
172 ignoring_counter(Point const& pt) : m_pt(pt) {}
174 template <typename It>
175 bool operator()(It first, It last) const
177 typedef typename std::iterator_traits<It>::value_type point_type;
179 std::pair<It, It> ignore_range
180 = std::equal_range(first, last, m_pt,
181 geometry::less<point_type>());
183 if ( find_odd_count(first, ignore_range.first) )
186 return find_odd_count(ignore_range.second, last);
192 template <typename It>
193 static inline bool find_odd_count(It first, It last)
198 std::size_t count = 1;
201 for ( ; first != last ; ++first, ++prev )
203 // the end of the equal points subrange
204 if ( ! equals::equals_point_point(*first, *prev) )
206 if ( count % 2 != 0 )
217 return count % 2 != 0;
221 template <typename Ring>
222 struct topology_check<Ring, ring_tag>
224 static const char interior = '2';
225 static const char boundary = '1';
226 static const bool has_interior = true;
227 static const bool has_boundary = true;
229 topology_check(Ring const&) {}
230 template <typename P>
231 topology_check(Ring const&, P const&) {}
234 template <typename Polygon>
235 struct topology_check<Polygon, polygon_tag>
237 static const char interior = '2';
238 static const char boundary = '1';
239 static const bool has_interior = true;
240 static const bool has_boundary = true;
242 topology_check(Polygon const&) {}
243 template <typename P>
244 topology_check(Polygon const&, P const&) {}
247 template <typename MultiPolygon>
248 struct topology_check<MultiPolygon, multi_polygon_tag>
250 static const char interior = '2';
251 static const char boundary = '1';
252 static const bool has_interior = true;
253 static const bool has_boundary = true;
255 topology_check(MultiPolygon const&) {}
256 template <typename P>
257 topology_check(MultiPolygon const&, P const&) {}
260 }} // namespace detail::relate
261 #endif // DOXYGEN_NO_DETAIL
263 }} // namespace boost::geometry
265 #endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_RELATE_TOPOLOGY_CHECK_HPP