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

   1 // Boost.Geometry (aka GGL, Generic Geometry Library)
   2
   3 // Copyright (c) 2014-2020, 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_LINEAR_HPP
  12 #define BOOST_GEOMETRY_ALGORITHMS_DETAIL_IS_VALID_LINEAR_HPP
  13
  14 #include <cstddef>
  15
  16 #include <boost/range/begin.hpp>
  17 #include <boost/range/empty.hpp>
  18 #include <boost/range/end.hpp>
  19 #include <boost/range/size.hpp>
  20
  21 #include <boost/geometry/algorithms/equals.hpp>
  22 #include <boost/geometry/algorithms/validity_failure_type.hpp>
  23 #include <boost/geometry/algorithms/detail/check_iterator_range.hpp>
  24 #include <boost/geometry/algorithms/detail/is_valid/has_invalid_coordinate.hpp>
  25 #include <boost/geometry/algorithms/detail/is_valid/has_spikes.hpp>
  26 #include <boost/geometry/algorithms/detail/num_distinct_consecutive_points.hpp>
  27
  28 #include <boost/geometry/algorithms/dispatch/is_valid.hpp>
  29
  30 #include <boost/geometry/core/closure.hpp>
  31 #include <boost/geometry/core/point_type.hpp>
  32 #include <boost/geometry/core/tags.hpp>
  33
  34 #include <boost/geometry/util/condition.hpp>
  35
  36
  37 namespace boost { namespace geometry
  38 {
  39
  40 #ifndef DOXYGEN_NO_DETAIL
  41 namespace detail { namespace is_valid
  42 {
  43
  44
  45 template <typename Linestring>
  46 struct is_valid_linestring
  47 {
  48     template <typename VisitPolicy, typename Strategy>
  49     static inline bool apply(Linestring const& linestring,
  50                              VisitPolicy& visitor,
  51                              Strategy const& strategy)
  52     {
  53         // TODO: Consider checking coordinates based on coordinate system
  54         //       Right now they are only checked for infinity in all systems.
  55         if (has_invalid_coordinate<Linestring>::apply(linestring, visitor))
  56         {
  57             return false;
  58         }
  59
  60         if (boost::size(linestring) < 2)
  61         {
  62             return visitor.template apply<failure_few_points>();
  63         }
  64
  65         std::size_t num_distinct = detail::num_distinct_consecutive_points
  66             <
  67                 Linestring,
  68                 3u,
  69                 true,
  70                 not_equal_to
  71                     <
  72                         typename point_type<Linestring>::type,
  73                         typename Strategy::equals_point_point_strategy_type
  74                     >
  75             >::apply(linestring);
  76
  77         if (num_distinct < 2u)
  78         {
  79             return
  80                 visitor.template apply<failure_wrong_topological_dimension>();
  81         }
  82
  83         if (num_distinct == 2u)
  84         {
  85             return visitor.template apply<no_failure>();
  86         }
  87
  88         // TODO: This algorithm iterates over the linestring until a spike is
  89         //   found and only then the decision about the validity is made. This
  90         //   is done regardless of VisitPolicy.
  91         //   An obvious improvement is to avoid calling the algorithm at all if
  92         //   spikes are allowed which is the default.
  93         return ! has_spikes
  94                     <
  95                         Linestring, closed
  96                     >::apply(linestring, visitor,
  97                              strategy.get_side_strategy());
  98     }
  99 };
 100
 101
 102 }} // namespace detail::is_valid
 103 #endif // DOXYGEN_NO_DETAIL
 104
 105
 106
 107
 108 #ifndef DOXYGEN_NO_DISPATCH
 109 namespace dispatch
 110 {
 111
 112
 113 // A linestring is a curve.
 114 // A curve is 1-dimensional so it has to have at least two distinct
 115 // points.
 116 // A curve is simple if it does not pass through the same point twice,
 117 // with the possible exception of its two endpoints
 118 //
 119 // There is an option here as to whether spikes are allowed for linestrings;
 120 // here we pass this as an additional template parameter: allow_spikes
 121 // If allow_spikes is set to true, spikes are allowed, false otherwise.
 122 // By default, spikes are disallowed
 123 //
 124 // Reference: OGC 06-103r4 (6.1.6.1)
 125 template <typename Linestring, bool AllowEmptyMultiGeometries>
 126 struct is_valid
 127     <
 128         Linestring, linestring_tag, AllowEmptyMultiGeometries
 129     > : detail::is_valid::is_valid_linestring<Linestring>
 130 {};
 131
 132
 133 // A MultiLinestring is a MultiCurve
 134 // A MultiCurve is simple if all of its elements are simple and the
 135 // only intersections between any two elements occur at Points that
 136 // are on the boundaries of both elements.
 137 //
 138 // Reference: OGC 06-103r4 (6.1.8.1; Fig. 9)
 139 template <typename MultiLinestring, bool AllowEmptyMultiGeometries>
 140 class is_valid
 141     <
 142         MultiLinestring, multi_linestring_tag, AllowEmptyMultiGeometries
 143     >
 144 {
 145 private:
 146     template <typename VisitPolicy, typename Strategy>
 147     struct per_linestring
 148     {
 149         per_linestring(VisitPolicy& policy, Strategy const& strategy)
 150             : m_policy(policy)
 151             , m_strategy(strategy)
 152         {}
 153
 154         template <typename Linestring>
 155         inline bool apply(Linestring const& linestring) const
 156         {
 157             return detail::is_valid::is_valid_linestring
 158                 <
 159                     Linestring
 160                 >::apply(linestring, m_policy, m_strategy);
 161         }
 162
 163         VisitPolicy& m_policy;
 164         Strategy const& m_strategy;
 165     };
 166
 167 public:
 168     template <typename VisitPolicy, typename Strategy>
 169     static inline bool apply(MultiLinestring const& multilinestring,
 170                              VisitPolicy& visitor,
 171                              Strategy const& strategy)
 172     {
 173         if (BOOST_GEOMETRY_CONDITION(
 174                 AllowEmptyMultiGeometries && boost::empty(multilinestring)))
 175         {
 176             return visitor.template apply<no_failure>();
 177         }
 178
 179         typedef per_linestring<VisitPolicy, Strategy> per_ls;
 180
 181         return detail::check_iterator_range
 182             <
 183                 per_ls,
 184                 false // do not check for empty multilinestring (done above)
 185             >::apply(boost::begin(multilinestring),
 186                      boost::end(multilinestring),
 187                      per_ls(visitor, strategy));
 188     }
 189 };
 190
 191
 192 } // namespace dispatch
 193 #endif // DOXYGEN_NO_DISPATCH
 194
 195
 196 }} // namespace boost::geometry
 197
 198
 199 #endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_IS_VALID_LINEAR_HPP