detail/is_valid/linear.hpp

0001 // Boost.Geometry (aka GGL, Generic Geometry Library)
0002
0003 // Copyright (c) 2023 Adam Wulkiewicz, Lodz, Poland.
0004
0005 // Copyright (c) 2014-2021, Oracle and/or its affiliates.
0006 // Contributed and/or modified by Vissarion Fysikopoulos, on behalf of Oracle
0007 // Contributed and/or modified by Menelaos Karavelas, on behalf of Oracle
0008 // Contributed and/or modified by Adam Wulkiewicz, on behalf of Oracle
0009
0010 // Licensed under the Boost Software License version 1.0.
0011 // http://www.boost.org/users/license.html
0012
0013 #ifndef BOOST_GEOMETRY_ALGORITHMS_DETAIL_IS_VALID_LINEAR_HPP
0014 #define BOOST_GEOMETRY_ALGORITHMS_DETAIL_IS_VALID_LINEAR_HPP
0015
0016 #include <cstddef>
0017
0018 #include <boost/range/begin.hpp>
0019 #include <boost/range/empty.hpp>
0020 #include <boost/range/end.hpp>
0021 #include <boost/range/size.hpp>
0022
0023 #include <boost/geometry/algorithms/equals.hpp>
0024 #include <boost/geometry/algorithms/validity_failure_type.hpp>
0025 #include <boost/geometry/algorithms/detail/is_valid/has_invalid_coordinate.hpp>
0026 #include <boost/geometry/algorithms/detail/is_valid/has_spikes.hpp>
0027 #include <boost/geometry/algorithms/detail/num_distinct_consecutive_points.hpp>
0028
0029 #include <boost/geometry/algorithms/dispatch/is_valid.hpp>
0030
0031 #include <boost/geometry/core/closure.hpp>
0032 #include <boost/geometry/core/point_type.hpp>
0033 #include <boost/geometry/core/tags.hpp>
0034
0035 #include <boost/geometry/util/constexpr.hpp>
0036
0037
0038 namespace boost { namespace geometry
0039 {
0040
0041 #ifndef DOXYGEN_NO_DETAIL
0042 namespace detail { namespace is_valid
0043 {
0044
0045
0046 template <typename Linestring>
0047 struct is_valid_linestring
0048 {
0049     template <typename VisitPolicy, typename Strategy>
0050     static inline bool apply(Linestring const& linestring,
0051                              VisitPolicy& visitor,
0052                              Strategy const& strategy)
0053     {
0054         // TODO: Consider checking coordinates based on coordinate system
0055         //       Right now they are only checked for infinity in all systems.
0056         if (has_invalid_coordinate<Linestring>::apply(linestring, visitor))
0057         {
0058             return false;
0059         }
0060
0061         if (boost::size(linestring) < 2)
0062         {
0063             return visitor.template apply<failure_few_points>();
0064         }
0065
0066         std::size_t num_distinct = detail::num_distinct_consecutive_points
0067             <
0068                 Linestring, 3u, true
0069             >::apply(linestring, strategy);
0070
0071         if (num_distinct < 2u)
0072         {
0073             return
0074                 visitor.template apply<failure_wrong_topological_dimension>();
0075         }
0076
0077         if (num_distinct == 2u)
0078         {
0079             return visitor.template apply<no_failure>();
0080         }
0081
0082         // TODO: This algorithm iterates over the linestring until a spike is
0083         //   found and only then the decision about the validity is made. This
0084         //   is done regardless of VisitPolicy.
0085         //   An obvious improvement is to avoid calling the algorithm at all if
0086         //   spikes are allowed which is the default.
0087         return ! has_spikes<Linestring>::apply(linestring, visitor, strategy);
0088     }
0089 };
0090
0091
0092 }} // namespace detail::is_valid
0093 #endif // DOXYGEN_NO_DETAIL
0094
0095
0096
0097
0098 #ifndef DOXYGEN_NO_DISPATCH
0099 namespace dispatch
0100 {
0101
0102
0103 // A linestring is a curve.
0104 // A curve is 1-dimensional so it has to have at least two distinct
0105 // points.
0106 // A curve is simple if it does not pass through the same point twice,
0107 // with the possible exception of its two endpoints
0108 //
0109 // There is an option here as to whether spikes are allowed for linestrings;
0110 // here we pass this as an additional template parameter: allow_spikes
0111 // If allow_spikes is set to true, spikes are allowed, false otherwise.
0112 // By default, spikes are disallowed
0113 //
0114 // Reference: OGC 06-103r4 (6.1.6.1)
0115 template <typename Linestring, bool AllowEmptyMultiGeometries>
0116 struct is_valid
0117     <
0118         Linestring, linestring_tag, AllowEmptyMultiGeometries
0119     > : detail::is_valid::is_valid_linestring<Linestring>
0120 {};
0121
0122
0123 // A MultiLinestring is a MultiCurve
0124 // A MultiCurve is simple if all of its elements are simple and the
0125 // only intersections between any two elements occur at Points that
0126 // are on the boundaries of both elements.
0127 //
0128 // Reference: OGC 06-103r4 (6.1.8.1; Fig. 9)
0129 template <typename MultiLinestring, bool AllowEmptyMultiGeometries>
0130 class is_valid
0131     <
0132         MultiLinestring, multi_linestring_tag, AllowEmptyMultiGeometries
0133     >
0134 {
0135     template <typename VisitPolicy, typename Strategy>
0136     struct per_linestring
0137     {
0138         per_linestring(VisitPolicy& policy, Strategy const& strategy)
0139             : m_policy(policy)
0140             , m_strategy(strategy)
0141         {}
0142
0143         template <typename Linestring>
0144         inline bool operator()(Linestring const& linestring) const
0145         {
0146             return detail::is_valid::is_valid_linestring
0147                 <
0148                     Linestring
0149                 >::apply(linestring, m_policy, m_strategy);
0150         }
0151
0152         VisitPolicy& m_policy;
0153         Strategy const& m_strategy;
0154     };
0155
0156 public:
0157     template <typename VisitPolicy, typename Strategy>
0158     static inline bool apply(MultiLinestring const& multilinestring,
0159                              VisitPolicy& visitor,
0160                              Strategy const& strategy)
0161     {
0162         if BOOST_GEOMETRY_CONSTEXPR (AllowEmptyMultiGeometries)
0163         {
0164             if (boost::empty(multilinestring))
0165             {
0166                 return visitor.template apply<no_failure>();
0167             }
0168         }
0169
0170         using per_ls = per_linestring<VisitPolicy, Strategy>;
0171
0172         return std::all_of(boost::begin(multilinestring),
0173                            boost::end(multilinestring),
0174                            per_ls(visitor, strategy));
0175     }
0176 };
0177
0178
0179 } // namespace dispatch
0180 #endif // DOXYGEN_NO_DISPATCH
0181
0182
0183 }} // namespace boost::geometry
0184
0185
0186 #endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_IS_VALID_LINEAR_HPP