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

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