detail/is_valid/has_spikes.hpp

0001 // Boost.Geometry (aka GGL, Generic Geometry Library)
0002
0003 // Copyright (c) 2014-2021, Oracle and/or its affiliates.
0004
0005 // Contributed and/or modified by Menelaos Karavelas, on behalf of Oracle
0006 // Contributed and/or modified by Adam Wulkiewicz, on behalf of Oracle
0007
0008 // Licensed under the Boost Software License version 1.0.
0009 // http://www.boost.org/users/license.html
0010
0011 #ifndef BOOST_GEOMETRY_ALGORITHMS_DETAIL_IS_VALID_HAS_SPIKES_HPP
0012 #define BOOST_GEOMETRY_ALGORITHMS_DETAIL_IS_VALID_HAS_SPIKES_HPP
0013
0014 #include <algorithm>
0015
0016 #include <boost/core/ignore_unused.hpp>
0017 #include <boost/range/begin.hpp>
0018 #include <boost/range/end.hpp>
0019 #include <boost/range/rbegin.hpp>
0020 #include <boost/range/rend.hpp>
0021
0022 #include <boost/geometry/algorithms/detail/equals/point_point.hpp>
0023 #include <boost/geometry/algorithms/validity_failure_type.hpp>
0024 #include <boost/geometry/algorithms/detail/point_is_spike_or_equal.hpp>
0025
0026 #include <boost/geometry/core/assert.hpp>
0027 #include <boost/geometry/core/point_type.hpp>
0028 #include <boost/geometry/core/tag.hpp>
0029 #include <boost/geometry/core/tags.hpp>
0030
0031 #include <boost/geometry/io/dsv/write.hpp>
0032
0033 #include <boost/geometry/policies/is_valid/default_policy.hpp>
0034
0035 #include <boost/geometry/util/range.hpp>
0036 #include <boost/geometry/util/type_traits.hpp>
0037
0038 #include <boost/geometry/views/closeable_view.hpp>
0039
0040
0041 namespace boost { namespace geometry
0042 {
0043
0044
0045 #ifndef DOXYGEN_NO_DETAIL
0046 namespace detail { namespace is_valid
0047 {
0048
0049
0050 template <typename Range>
0051 struct has_spikes
0052 {
0053     template <typename Iterator, typename Strategy>
0054     static inline Iterator find_different_from_first(Iterator first,
0055                                                      Iterator last,
0056                                                      Strategy const& strategy)
0057     {
0058         if (first == last)
0059         {
0060             return last;
0061         }
0062         auto const& front = *first;
0063         ++first;
0064         return std::find_if(first, last, [&](auto const& pt) {
0065             return ! equals::equals_point_point(pt, front, strategy);
0066         });
0067     }
0068
0069     template <typename View, typename VisitPolicy, typename Strategy>
0070     static inline bool apply_at_closure(View const& view, VisitPolicy& visitor,
0071                                         Strategy const& strategy,
0072                                         bool is_linear)
0073     {
0074         boost::ignore_unused(visitor);
0075
0076         auto cur = boost::begin(view);
0077         auto prev = find_different_from_first(boost::rbegin(view),
0078                                               boost::rend(view),
0079                                               strategy);
0080
0081         auto next = find_different_from_first(cur, boost::end(view), strategy);
0082         if (detail::is_spike_or_equal(*next, *cur, *prev, strategy.side()))
0083         {
0084             return ! visitor.template apply<failure_spikes>(is_linear, *cur);
0085         }
0086         else
0087         {
0088             return ! visitor.template apply<no_failure>();
0089         }
0090     }
0091
0092
0093     template <typename VisitPolicy, typename Strategy>
0094     static inline bool apply(Range const& range, VisitPolicy& visitor,
0095                              Strategy const& strategy)
0096     {
0097         boost::ignore_unused(visitor);
0098
0099         bool const is_linestring = util::is_linestring<Range>::value;
0100
0101         detail::closed_view<Range const> const view(range);
0102
0103         auto prev = boost::begin(view);
0104         auto const end = boost::end(view);
0105
0106         auto cur = find_different_from_first(prev, boost::end(view), strategy);
0107         if (cur == end)
0108         {
0109             // the range has only one distinct point, so it
0110             // cannot have a spike
0111             return ! visitor.template apply<no_failure>();
0112         }
0113
0114         auto next = find_different_from_first(cur, boost::end(view), strategy);
0115         if (next == end)
0116         {
0117             // the range has only two distinct points, so it
0118             // cannot have a spike
0119             return ! visitor.template apply<no_failure>();
0120         }
0121
0122         while (next != end)
0123         {
0124             // Verify spike. TODO: this is a reverse order from expected
0125             // in is_spike_or_equal, but this order calls the side
0126             // strategy in the way to correctly detect the spikes,
0127             // also in geographic cases going over the pole
0128             if (detail::is_spike_or_equal(*next, *cur, *prev, strategy.side()))
0129             {
0130                 return ! visitor.template apply<failure_spikes>(is_linestring, *cur);
0131             }
0132             prev = cur;
0133             cur = next;
0134             next = find_different_from_first(cur, boost::end(view), strategy);
0135         }
0136
0137         if (equals::equals_point_point(range::front(view), range::back(view),
0138                                        strategy))
0139         {
0140             return apply_at_closure(view, visitor, strategy, is_linestring);
0141         }
0142
0143         return ! visitor.template apply<no_failure>();
0144     }
0145 };
0146
0147
0148
0149 }} // namespace detail::is_valid
0150 #endif // DOXYGEN_NO_DETAIL
0151
0152
0153 }} // namespace boost::geometry
0154
0155
0156 #endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_IS_VALID_HAS_SPIKES_HPP