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 Menelaos Karavelas, on behalf of Oracle
6 // Contributed and/or modified by Adam Wulkiewicz, on behalf of Oracle
7 
8 // Licensed under the Boost Software License version 1.0.
9 // http://www.boost.org/users/license.html
10 
11 #ifndef BOOST_GEOMETRY_ALGORITHMS_DETAIL_IS_VALID_HAS_SPIKES_HPP
12 #define BOOST_GEOMETRY_ALGORITHMS_DETAIL_IS_VALID_HAS_SPIKES_HPP
13 
14 #include <algorithm>
15 
16 #include <boost/core/ignore_unused.hpp>
17 #include <boost/range.hpp>
18 #include <boost/type_traits/is_same.hpp>
19 
20 #include <boost/geometry/core/assert.hpp>
21 #include <boost/geometry/core/point_type.hpp>
22 #include <boost/geometry/core/tag.hpp>
23 #include <boost/geometry/core/tags.hpp>
24 
25 #include <boost/geometry/policies/is_valid/default_policy.hpp>
26 
27 #include <boost/geometry/util/range.hpp>
28 
29 #include <boost/geometry/views/closeable_view.hpp>
30 
31 #include <boost/geometry/algorithms/equals.hpp>
32 #include <boost/geometry/algorithms/validity_failure_type.hpp>
33 #include <boost/geometry/algorithms/detail/point_is_spike_or_equal.hpp>
34 #include <boost/geometry/io/dsv/write.hpp>
35 
36 
37 namespace boost { namespace geometry
38 {
39 
40 
41 #ifndef DOXYGEN_NO_DETAIL
42 namespace detail { namespace is_valid
43 {
44 
45 template <typename Point>
46 struct equal_to
47 {
48     Point const& m_point;
49 
equal_toboost::geometry::detail::is_valid::equal_to50     equal_to(Point const& point)
51         : m_point(point)
52     {}
53 
54     template <typename OtherPoint>
operator ()boost::geometry::detail::is_valid::equal_to55     inline bool operator()(OtherPoint const& other) const
56     {
57         return geometry::equals(m_point, other);
58     }
59 };
60 
61 template <typename Point>
62 struct not_equal_to
63 {
64     Point const& m_point;
65 
not_equal_toboost::geometry::detail::is_valid::not_equal_to66     not_equal_to(Point const& point)
67         : m_point(point)
68     {}
69 
70     template <typename OtherPoint>
operator ()boost::geometry::detail::is_valid::not_equal_to71     inline bool operator()(OtherPoint const& other) const
72     {
73         return ! geometry::equals(other, m_point);
74     }
75 };
76 
77 
78 
79 template <typename Range, closure_selector Closure>
80 struct has_spikes
81 {
82     template <typename Iterator>
find_different_from_firstboost::geometry::detail::is_valid::has_spikes83     static inline Iterator find_different_from_first(Iterator first,
84                                                      Iterator last)
85     {
86         typedef not_equal_to<typename point_type<Range>::type> not_equal;
87 
88         BOOST_GEOMETRY_ASSERT(first != last);
89 
90         Iterator second = first;
91         ++second;
92         return std::find_if(second, last, not_equal(*first));
93     }
94 
95     template <typename VisitPolicy, typename SideStrategy>
applyboost::geometry::detail::is_valid::has_spikes96     static inline bool apply(Range const& range, VisitPolicy& visitor,
97                              SideStrategy const& strategy)
98     {
99         boost::ignore_unused(visitor);
100 
101         typedef typename closeable_view<Range const, Closure>::type view_type;
102         typedef typename boost::range_iterator<view_type const>::type iterator;
103 
104         bool const is_linear
105             = boost::is_same<typename tag<Range>::type, linestring_tag>::value;
106 
107         view_type const view(range);
108 
109         iterator prev = boost::begin(view);
110 
111         iterator cur = find_different_from_first(prev, boost::end(view));
112         if (cur == boost::end(view))
113         {
114             // the range has only one distinct point, so it
115             // cannot have a spike
116             return ! visitor.template apply<no_failure>();
117         }
118 
119         iterator next = find_different_from_first(cur, boost::end(view));
120         if (next == boost::end(view))
121         {
122             // the range has only two distinct points, so it
123             // cannot have a spike
124             return ! visitor.template apply<no_failure>();
125         }
126 
127         while (next != boost::end(view))
128         {
129             if ( geometry::detail::point_is_spike_or_equal(*prev, *next, *cur,
130                                                            strategy) )
131             {
132                 return
133                     ! visitor.template apply<failure_spikes>(is_linear, *cur);
134             }
135             prev = cur;
136             cur = next;
137             next = find_different_from_first(cur, boost::end(view));
138         }
139 
140         if (geometry::equals(range::front(view), range::back(view)))
141         {
142             iterator cur = boost::begin(view);
143             typename boost::range_reverse_iterator
144                 <
145                     view_type const
146                 >::type prev = find_different_from_first(boost::rbegin(view),
147                                                          boost::rend(view));
148 
149             iterator next = find_different_from_first(cur, boost::end(view));
150             if (detail::point_is_spike_or_equal(*prev, *next, *cur, strategy))
151             {
152                 return
153                     ! visitor.template apply<failure_spikes>(is_linear, *cur);
154             }
155             else
156             {
157                 return ! visitor.template apply<no_failure>();
158             }
159         }
160 
161         return ! visitor.template apply<no_failure>();
162     }
163 };
164 
165 
166 
167 }} // namespace detail::is_valid
168 #endif // DOXYGEN_NO_DETAIL
169 
170 
171 }} // namespace boost::geometry
172 
173 
174 #endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_IS_VALID_HAS_SPIKES_HPP
175