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