ceph/src/boost/boost/geometry/algorithms/detail/is_valid/has_spikes.hpp

   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
  50     equal_to(Point const& point)
  51         : m_point(point)
  52     {}
  53
  54     template <typename OtherPoint>
  55     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
  66     not_equal_to(Point const& point)
  67         : m_point(point)
  68     {}
  69
  70     template <typename OtherPoint>
  71     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>
  83     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>
  96     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