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

   1 // Boost.Geometry (aka GGL, Generic Geometry Library)
   2
   3 // Copyright (c) 2014-2021, Oracle and/or its affiliates.
   4
   5 // Contributed and/or modified by Vissarion Fysikopoulos, on behalf of Oracle
   6 // Contributed and/or modified by Menelaos Karavelas, on behalf of Oracle
   7 // Contributed and/or modified by Adam Wulkiewicz, on behalf of Oracle
   8
   9 // Licensed under the Boost Software License version 1.0.
  10 // http://www.boost.org/users/license.html
  11
  12 #ifndef BOOST_GEOMETRY_ALGORITHMS_DETAIL_IS_VALID_LINEAR_HPP
  13 #define BOOST_GEOMETRY_ALGORITHMS_DETAIL_IS_VALID_LINEAR_HPP
  14
  15 #include <cstddef>
  16
  17 #include <boost/range/begin.hpp>
  18 #include <boost/range/empty.hpp>
  19 #include <boost/range/end.hpp>
  20 #include <boost/range/size.hpp>
  21
  22 #include <boost/geometry/algorithms/equals.hpp>
  23 #include <boost/geometry/algorithms/validity_failure_type.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, 3u, true
  68             >::apply(linestring, strategy);
  69
  70         if (num_distinct < 2u)
  71         {
  72             return
  73                 visitor.template apply<failure_wrong_topological_dimension>();
  74         }
  75
  76         if (num_distinct == 2u)
  77         {
  78             return visitor.template apply<no_failure>();
  79         }
  80
  81         // TODO: This algorithm iterates over the linestring until a spike is
  82         //   found and only then the decision about the validity is made. This
  83         //   is done regardless of VisitPolicy.
  84         //   An obvious improvement is to avoid calling the algorithm at all if
  85         //   spikes are allowed which is the default.
  86         return ! has_spikes<Linestring>::apply(linestring, visitor, strategy);
  87     }
  88 };
  89
  90
  91 }} // namespace detail::is_valid
  92 #endif // DOXYGEN_NO_DETAIL
  93
  94
  95
  96
  97 #ifndef DOXYGEN_NO_DISPATCH
  98 namespace dispatch
  99 {
 100
 101
 102 // A linestring is a curve.
 103 // A curve is 1-dimensional so it has to have at least two distinct
 104 // points.
 105 // A curve is simple if it does not pass through the same point twice,
 106 // with the possible exception of its two endpoints
 107 //
 108 // There is an option here as to whether spikes are allowed for linestrings;
 109 // here we pass this as an additional template parameter: allow_spikes
 110 // If allow_spikes is set to true, spikes are allowed, false otherwise.
 111 // By default, spikes are disallowed
 112 //
 113 // Reference: OGC 06-103r4 (6.1.6.1)
 114 template <typename Linestring, bool AllowEmptyMultiGeometries>
 115 struct is_valid
 116     <
 117         Linestring, linestring_tag, AllowEmptyMultiGeometries
 118     > : detail::is_valid::is_valid_linestring<Linestring>
 119 {};
 120
 121
 122 // A MultiLinestring is a MultiCurve
 123 // A MultiCurve is simple if all of its elements are simple and the
 124 // only intersections between any two elements occur at Points that
 125 // are on the boundaries of both elements.
 126 //
 127 // Reference: OGC 06-103r4 (6.1.8.1; Fig. 9)
 128 template <typename MultiLinestring, bool AllowEmptyMultiGeometries>
 129 class is_valid
 130     <
 131         MultiLinestring, multi_linestring_tag, AllowEmptyMultiGeometries
 132     >
 133 {
 134     template <typename VisitPolicy, typename Strategy>
 135     struct per_linestring
 136     {
 137         per_linestring(VisitPolicy& policy, Strategy const& strategy)
 138             : m_policy(policy)
 139             , m_strategy(strategy)
 140         {}
 141
 142         template <typename Linestring>
 143         inline bool operator()(Linestring const& linestring) const
 144         {
 145             return detail::is_valid::is_valid_linestring
 146                 <
 147                     Linestring
 148                 >::apply(linestring, m_policy, m_strategy);
 149         }
 150
 151         VisitPolicy& m_policy;
 152         Strategy const& m_strategy;
 153     };
 154
 155 public:
 156     template <typename VisitPolicy, typename Strategy>
 157     static inline bool apply(MultiLinestring const& multilinestring,
 158                              VisitPolicy& visitor,
 159                              Strategy const& strategy)
 160     {
 161         if (BOOST_GEOMETRY_CONDITION(
 162                 AllowEmptyMultiGeometries && boost::empty(multilinestring)))
 163         {
 164             return visitor.template apply<no_failure>();
 165         }
 166
 167         using per_ls = per_linestring<VisitPolicy, Strategy>;
 168
 169         return std::all_of(boost::begin(multilinestring),
 170                            boost::end(multilinestring),
 171                            per_ls(visitor, strategy));
 172     }
 173 };
 174
 175
 176 } // namespace dispatch
 177 #endif // DOXYGEN_NO_DISPATCH
 178
 179
 180 }} // namespace boost::geometry
 181
 182
 183 #endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_IS_VALID_LINEAR_HPP