1 // Boost.Geometry (aka GGL, Generic Geometry Library) 2 3 // Copyright (c) 2014, Oracle and/or its affiliates. 4 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 // Contributed and/or modified by Adam Wulkiewicz, on behalf of Oracle 10 11 #ifndef BOOST_GEOMETRY_ALGORITHMS_DETAIL_RELATE_TOPOLOGY_CHECK_HPP 12 #define BOOST_GEOMETRY_ALGORITHMS_DETAIL_RELATE_TOPOLOGY_CHECK_HPP 13 14 #include <boost/geometry/util/range.hpp> 15 16 #include <boost/geometry/algorithms/detail/equals/point_point.hpp> 17 #include <boost/geometry/policies/compare.hpp> 18 19 namespace boost { namespace geometry { 20 21 #ifndef DOXYGEN_NO_DETAIL 22 namespace detail { namespace relate { 23 24 // TODO: change the name for e.g. something with the word "exterior" 25 26 template <typename Geometry, 27 typename Tag = typename geometry::tag<Geometry>::type> 28 struct topology_check 29 : not_implemented<Tag> 30 {}; 31 32 //template <typename Point> 33 //struct topology_check<Point, point_tag> 34 //{ 35 // static const char interior = '0'; 36 // static const char boundary = 'F'; 37 // 38 // static const bool has_interior = true; 39 // static const bool has_boundary = false; 40 // 41 // topology_check(Point const&) {} 42 // template <typename IgnoreBoundaryPoint> 43 // topology_check(Point const&, IgnoreBoundaryPoint const&) {} 44 //}; 45 46 template <typename Linestring> 47 struct topology_check<Linestring, linestring_tag> 48 { 49 static const char interior = '1'; 50 static const char boundary = '0'; 51 52 bool has_interior; 53 bool has_boundary; 54 topology_checkboost::geometry::detail::relate::topology_check55 topology_check(Linestring const& ls) 56 { 57 init(ls, 0); /*dummy param*/ 58 } 59 60 template <typename IgnoreBoundaryPoint> topology_checkboost::geometry::detail::relate::topology_check61 topology_check(Linestring const& ls, IgnoreBoundaryPoint const& ibp) 62 { 63 init(ls, ibp); /*dummy param, won't be used*/ 64 } 65 66 // Even if some point is on the boundary, if the Linestring has the boundary, 67 // there will be second boundary point different than IgnoreBoundaryPoint 68 template <typename IgnoreBoundaryPoint> initboost::geometry::detail::relate::topology_check69 void init(Linestring const& ls, IgnoreBoundaryPoint const&) 70 { 71 std::size_t count = boost::size(ls); 72 has_interior = count > 0; 73 // NOTE: Linestring with all points equal is treated as 1d linear ring 74 has_boundary = count > 1 75 && ! detail::equals::equals_point_point(range::front(ls), range::back(ls)); 76 } 77 }; 78 79 template <typename MultiLinestring> 80 struct topology_check<MultiLinestring, multi_linestring_tag> 81 { 82 static const char interior = '1'; 83 static const char boundary = '0'; 84 85 bool has_interior; 86 bool has_boundary; 87 topology_checkboost::geometry::detail::relate::topology_check88 topology_check(MultiLinestring const& mls) 89 { 90 init(mls, not_ignoring_counter()); 91 } 92 93 template <typename IgnoreBoundaryPoint> topology_checkboost::geometry::detail::relate::topology_check94 topology_check(MultiLinestring const& mls, IgnoreBoundaryPoint const& ibp) 95 { 96 init(mls, ignoring_counter<IgnoreBoundaryPoint>(ibp)); 97 } 98 99 template <typename OddCounter> initboost::geometry::detail::relate::topology_check100 void init(MultiLinestring const& mls, OddCounter const& odd_counter) 101 { 102 typedef typename geometry::point_type<MultiLinestring>::type point_type; 103 std::vector<point_type> endpoints; 104 endpoints.reserve(boost::size(mls) * 2); 105 106 typedef typename boost::range_iterator<MultiLinestring const>::type ls_iterator; 107 for ( ls_iterator it = boost::begin(mls) ; it != boost::end(mls) ; ++it ) 108 { 109 std::size_t count = boost::size(*it); 110 111 if ( count > 0 ) 112 { 113 has_interior = true; 114 } 115 116 if ( count > 1 ) 117 { 118 // don't store boundaries of linear rings, this doesn't change anything 119 if ( ! equals::equals_point_point(range::front(*it), range::back(*it)) ) 120 { 121 endpoints.push_back(range::front(*it)); 122 endpoints.push_back(range::back(*it)); 123 } 124 } 125 } 126 127 has_boundary = false; 128 129 if ( !endpoints.empty() ) 130 { 131 std::sort(endpoints.begin(), endpoints.end(), geometry::less<point_type>()); 132 has_boundary = odd_counter(endpoints.begin(), endpoints.end()); 133 } 134 } 135 136 struct not_ignoring_counter 137 { 138 template <typename It> operator ()boost::geometry::detail::relate::topology_check::not_ignoring_counter139 bool operator()(It first, It last) const 140 { 141 return find_odd_count(first, last); 142 } 143 }; 144 145 template <typename Point> 146 struct ignoring_counter 147 { ignoring_counterboost::geometry::detail::relate::topology_check::ignoring_counter148 ignoring_counter(Point const& pt) : m_pt(pt) {} 149 150 template <typename It> operator ()boost::geometry::detail::relate::topology_check::ignoring_counter151 bool operator()(It first, It last) const 152 { 153 typedef typename std::iterator_traits<It>::value_type point_type; 154 155 std::pair<It, It> ignore_range 156 = std::equal_range(first, last, m_pt, 157 geometry::less<point_type>()); 158 159 if ( find_odd_count(first, ignore_range.first) ) 160 return true; 161 162 return find_odd_count(ignore_range.second, last); 163 } 164 165 Point const& m_pt; 166 }; 167 168 template <typename It> find_odd_countboost::geometry::detail::relate::topology_check169 static inline bool find_odd_count(It first, It last) 170 { 171 if ( first == last ) 172 return false; 173 174 std::size_t count = 1; 175 It prev = first; 176 ++first; 177 for ( ; first != last ; ++first, ++prev ) 178 { 179 // the end of the equal points subrange 180 if ( ! equals::equals_point_point(*first, *prev) ) 181 { 182 if ( count % 2 != 0 ) 183 return true; 184 185 count = 1; 186 } 187 else 188 { 189 ++count; 190 } 191 } 192 193 return count % 2 != 0; 194 } 195 }; 196 197 template <typename Ring> 198 struct topology_check<Ring, ring_tag> 199 { 200 static const char interior = '2'; 201 static const char boundary = '1'; 202 static const bool has_interior = true; 203 static const bool has_boundary = true; 204 topology_checkboost::geometry::detail::relate::topology_check205 topology_check(Ring const&) {} 206 template <typename P> topology_checkboost::geometry::detail::relate::topology_check207 topology_check(Ring const&, P const&) {} 208 }; 209 210 template <typename Polygon> 211 struct topology_check<Polygon, polygon_tag> 212 { 213 static const char interior = '2'; 214 static const char boundary = '1'; 215 static const bool has_interior = true; 216 static const bool has_boundary = true; 217 topology_checkboost::geometry::detail::relate::topology_check218 topology_check(Polygon const&) {} 219 template <typename P> topology_checkboost::geometry::detail::relate::topology_check220 topology_check(Polygon const&, P const&) {} 221 }; 222 223 template <typename MultiPolygon> 224 struct topology_check<MultiPolygon, multi_polygon_tag> 225 { 226 static const char interior = '2'; 227 static const char boundary = '1'; 228 static const bool has_interior = true; 229 static const bool has_boundary = true; 230 topology_checkboost::geometry::detail::relate::topology_check231 topology_check(MultiPolygon const&) {} 232 template <typename P> topology_checkboost::geometry::detail::relate::topology_check233 topology_check(MultiPolygon const&, P const&) {} 234 }; 235 236 }} // namespace detail::relate 237 #endif // DOXYGEN_NO_DETAIL 238 239 }} // namespace boost::geometry 240 241 #endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_RELATE_TOPOLOGY_CHECK_HPP 242