1 // Boost.Geometry (aka GGL, Generic Geometry Library) 2 3 // Copyright (c) 2014-2018 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_BOUNDARY_CHECKER_HPP 12 #define BOOST_GEOMETRY_ALGORITHMS_DETAIL_RELATE_BOUNDARY_CHECKER_HPP 13 14 #include <boost/core/ignore_unused.hpp> 15 16 #include <boost/geometry/algorithms/detail/equals/point_point.hpp> 17 #include <boost/geometry/algorithms/detail/sub_range.hpp> 18 #include <boost/geometry/algorithms/num_points.hpp> 19 20 #include <boost/geometry/policies/compare.hpp> 21 22 #include <boost/geometry/util/has_nan_coordinate.hpp> 23 #include <boost/geometry/util/range.hpp> 24 25 namespace boost { namespace geometry 26 { 27 28 #ifndef DOXYGEN_NO_DETAIL 29 namespace detail { namespace relate { 30 31 enum boundary_query { boundary_front, boundary_back, boundary_any }; 32 33 template <typename Geometry, 34 typename WithinStrategy, // Point/Point equals (within) strategy 35 typename Tag = typename geometry::tag<Geometry>::type> 36 class boundary_checker {}; 37 38 template <typename Geometry, typename WithinStrategy> 39 class boundary_checker<Geometry, WithinStrategy, linestring_tag> 40 { 41 typedef typename point_type<Geometry>::type point_type; 42 43 public: 44 typedef WithinStrategy equals_strategy_type; 45 boundary_checker(Geometry const & g)46 boundary_checker(Geometry const& g) 47 : has_boundary( boost::size(g) >= 2 48 && !detail::equals::equals_point_point(range::front(g), 49 range::back(g), 50 equals_strategy_type()) ) 51 #ifdef BOOST_GEOMETRY_DEBUG_RELATE_BOUNDARY_CHECKER 52 , geometry(g) 53 #endif 54 {} 55 56 template <boundary_query BoundaryQuery> is_endpoint_boundary(point_type const & pt) const57 bool is_endpoint_boundary(point_type const& pt) const 58 { 59 boost::ignore_unused(pt); 60 #ifdef BOOST_GEOMETRY_DEBUG_RELATE_BOUNDARY_CHECKER 61 // may give false positives for INT 62 BOOST_GEOMETRY_ASSERT( (BoundaryQuery == boundary_front || BoundaryQuery == boundary_any) 63 && detail::equals::equals_point_point(pt, range::front(geometry), WithinStrategy()) 64 || (BoundaryQuery == boundary_back || BoundaryQuery == boundary_any) 65 && detail::equals::equals_point_point(pt, range::back(geometry), WithinStrategy()) ); 66 #endif 67 return has_boundary; 68 } 69 70 private: 71 bool has_boundary; 72 #ifdef BOOST_GEOMETRY_DEBUG_RELATE_BOUNDARY_CHECKER 73 Geometry const& geometry; 74 #endif 75 }; 76 77 template <typename Geometry, typename WithinStrategy> 78 class boundary_checker<Geometry, WithinStrategy, multi_linestring_tag> 79 { 80 typedef typename point_type<Geometry>::type point_type; 81 82 public: 83 typedef WithinStrategy equals_strategy_type; 84 boundary_checker(Geometry const & g)85 boundary_checker(Geometry const& g) 86 : is_filled(false), geometry(g) 87 {} 88 89 // First call O(NlogN) 90 // Each next call O(logN) 91 template <boundary_query BoundaryQuery> is_endpoint_boundary(point_type const & pt) const92 bool is_endpoint_boundary(point_type const& pt) const 93 { 94 typedef geometry::less<point_type, -1, typename WithinStrategy::cs_tag> less_type; 95 96 typedef typename boost::range_size<Geometry>::type size_type; 97 size_type multi_count = boost::size(geometry); 98 99 if ( multi_count < 1 ) 100 return false; 101 102 if ( ! is_filled ) 103 { 104 //boundary_points.clear(); 105 boundary_points.reserve(multi_count * 2); 106 107 typedef typename boost::range_iterator<Geometry const>::type multi_iterator; 108 for ( multi_iterator it = boost::begin(geometry) ; 109 it != boost::end(geometry) ; ++ it ) 110 { 111 typename boost::range_reference<Geometry const>::type 112 ls = *it; 113 114 // empty or point - no boundary 115 if (boost::size(ls) < 2) 116 { 117 continue; 118 } 119 120 typedef typename boost::range_reference 121 < 122 typename boost::range_value<Geometry const>::type const 123 >::type point_reference; 124 125 point_reference front_pt = range::front(ls); 126 point_reference back_pt = range::back(ls); 127 128 // linear ring or point - no boundary 129 if (! equals::equals_point_point(front_pt, back_pt, equals_strategy_type())) 130 { 131 // do not add points containing NaN coordinates 132 // because they cannot be reasonably compared, e.g. with MSVC 133 // an assertion failure is reported in std::equal_range() 134 if (! geometry::has_nan_coordinate(front_pt)) 135 { 136 boundary_points.push_back(front_pt); 137 } 138 if (! geometry::has_nan_coordinate(back_pt)) 139 { 140 boundary_points.push_back(back_pt); 141 } 142 } 143 } 144 145 std::sort(boundary_points.begin(), 146 boundary_points.end(), 147 less_type()); 148 149 is_filled = true; 150 } 151 152 std::size_t equal_points_count 153 = boost::size( 154 std::equal_range(boundary_points.begin(), 155 boundary_points.end(), 156 pt, 157 less_type()) 158 ); 159 160 return equal_points_count % 2 != 0;// && equal_points_count > 0; // the number is odd and > 0 161 } 162 163 private: 164 mutable bool is_filled; 165 // TODO: store references/pointers instead of points? 166 mutable std::vector<point_type> boundary_points; 167 168 Geometry const& geometry; 169 }; 170 171 }} // namespace detail::relate 172 #endif // DOXYGEN_NO_DETAIL 173 174 }} // namespace boost::geometry 175 176 #endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_RELATE_BOUNDARY_CHECKER_HPP 177