detail/is_simple/linear.hpp

0001 // Boost.Geometry (aka GGL, Generic Geometry Library)
0002
0003 // Copyright (c) 2014-2021, Oracle and/or its affiliates.
0004
0005 // Contributed and/or modified by Vissarion Fysikopoulos, on behalf of Oracle
0006 // Contributed and/or modified by Menelaos Karavelas, on behalf of Oracle
0007 // Contributed and/or modified by Adam Wulkiewicz, on behalf of Oracle
0008
0009 // Licensed under the Boost Software License version 1.0.
0010 // http://www.boost.org/users/license.html
0011
0012 #ifndef BOOST_GEOMETRY_ALGORITHMS_DETAIL_IS_SIMPLE_LINEAR_HPP
0013 #define BOOST_GEOMETRY_ALGORITHMS_DETAIL_IS_SIMPLE_LINEAR_HPP
0014
0015 #include <algorithm>
0016 #include <deque>
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 #include <boost/range/value_type.hpp>
0023
0024 #include <boost/geometry/core/assert.hpp>
0025 #include <boost/geometry/core/closure.hpp>
0026 #include <boost/geometry/core/coordinate_type.hpp>
0027 #include <boost/geometry/core/point_type.hpp>
0028 #include <boost/geometry/core/tag.hpp>
0029 #include <boost/geometry/core/tags.hpp>
0030
0031 #include <boost/geometry/util/range.hpp>
0032
0033 #include <boost/geometry/policies/predicate_based_interrupt_policy.hpp>
0034 #include <boost/geometry/policies/robustness/no_rescale_policy.hpp>
0035 #include <boost/geometry/policies/robustness/segment_ratio.hpp>
0036
0037 #include <boost/geometry/algorithms/intersects.hpp>
0038 #include <boost/geometry/algorithms/not_implemented.hpp>
0039
0040 #include <boost/geometry/algorithms/detail/signed_size_type.hpp>
0041
0042 #include <boost/geometry/algorithms/detail/disjoint/linear_linear.hpp>
0043 #include <boost/geometry/algorithms/detail/equals/point_point.hpp>
0044 #include <boost/geometry/algorithms/detail/overlay/get_turn_info.hpp>
0045 #include <boost/geometry/algorithms/detail/overlay/turn_info.hpp>
0046 #include <boost/geometry/algorithms/detail/overlay/self_turn_points.hpp>
0047 #include <boost/geometry/algorithms/detail/is_valid/has_duplicates.hpp>
0048 #include <boost/geometry/algorithms/detail/is_valid/has_spikes.hpp>
0049
0050 #include <boost/geometry/algorithms/detail/is_simple/debug_print_boundary_points.hpp>
0051 #include <boost/geometry/algorithms/detail/is_simple/failure_policy.hpp>
0052 #include <boost/geometry/algorithms/detail/is_valid/debug_print_turns.hpp>
0053
0054 #include <boost/geometry/algorithms/dispatch/is_simple.hpp>
0055
0056 #include <boost/geometry/strategies/intersection.hpp>
0057
0058
0059 namespace boost { namespace geometry
0060 {
0061
0062
0063 #ifndef DOXYGEN_NO_DETAIL
0064 namespace detail { namespace is_simple
0065 {
0066
0067
0068 template <typename Turn>
0069 inline bool check_segment_indices(Turn const& turn,
0070                                   signed_size_type last_index)
0071 {
0072     return
0073         (turn.operations[0].seg_id.segment_index == 0
0074          && turn.operations[1].seg_id.segment_index == last_index)
0075         ||
0076         (turn.operations[0].seg_id.segment_index == 0
0077          && turn.operations[1].seg_id.segment_index == last_index);
0078 }
0079
0080
0081 template
0082 <
0083     typename Geometry,
0084     typename Strategy,
0085     typename Tag = typename tag<Geometry>::type
0086 >
0087 class is_acceptable_turn
0088     : not_implemented<Geometry>
0089 {};
0090
0091 template <typename Linestring, typename Strategy>
0092 class is_acceptable_turn<Linestring, Strategy, linestring_tag>
0093 {
0094 public:
0095     is_acceptable_turn(Linestring const& linestring, Strategy const& strategy)
0096         : m_linestring(linestring)
0097         , m_is_closed(geometry::detail::equals::equals_point_point(
0098                           range::front(linestring), range::back(linestring), strategy))
0099     {}
0100
0101     template <typename Turn>
0102     inline bool apply(Turn const& turn) const
0103     {
0104         BOOST_GEOMETRY_ASSERT(boost::size(m_linestring) > 1);
0105         return m_is_closed
0106             && turn.method == overlay::method_none
0107             && check_segment_indices(turn, boost::size(m_linestring) - 2)
0108             && turn.operations[0].fraction.is_zero();
0109     }
0110
0111 private:
0112     Linestring const& m_linestring;
0113     bool const m_is_closed;
0114 };
0115
0116 template <typename MultiLinestring, typename Strategy>
0117 class is_acceptable_turn<MultiLinestring, Strategy, multi_linestring_tag>
0118 {
0119 private:
0120     template <typename Point, typename Linestring>
0121     inline bool is_boundary_point_of(Point const& point, Linestring const& linestring) const
0122     {
0123         BOOST_GEOMETRY_ASSERT(boost::size(linestring) > 1);
0124         using geometry::detail::equals::equals_point_point;
0125         return ! equals_point_point(range::front(linestring), range::back(linestring), m_strategy)
0126             && (equals_point_point(point, range::front(linestring), m_strategy)
0127                 || equals_point_point(point, range::back(linestring), m_strategy));
0128     }
0129
0130     template <typename Turn, typename Linestring>
0131     inline bool is_closing_point_of(Turn const& turn, Linestring const& linestring) const
0132     {
0133         BOOST_GEOMETRY_ASSERT(boost::size(linestring) > 1);
0134         using geometry::detail::equals::equals_point_point;
0135         return turn.method == overlay::method_none
0136             && check_segment_indices(turn, boost::size(linestring) - 2)
0137             && equals_point_point(range::front(linestring), range::back(linestring), m_strategy)
0138             && turn.operations[0].fraction.is_zero();
0139     }
0140
0141     template <typename Linestring1, typename Linestring2>
0142     inline bool have_same_boundary_points(Linestring1 const& ls1, Linestring2 const& ls2) const
0143     {
0144         using geometry::detail::equals::equals_point_point;
0145         return equals_point_point(range::front(ls1), range::front(ls2), m_strategy)
0146              ? equals_point_point(range::back(ls1), range::back(ls2), m_strategy)
0147              : (equals_point_point(range::front(ls1), range::back(ls2), m_strategy)
0148                 && equals_point_point(range::back(ls1), range::front(ls2), m_strategy));
0149     }
0150
0151 public:
0152     is_acceptable_turn(MultiLinestring const& multilinestring, Strategy const& strategy)
0153         : m_multilinestring(multilinestring)
0154         , m_strategy(strategy)
0155     {}
0156
0157     template <typename Turn>
0158     inline bool apply(Turn const& turn) const
0159     {
0160         typedef typename boost::range_value<MultiLinestring>::type linestring_type;
0161
0162         linestring_type const& ls1 =
0163             range::at(m_multilinestring, turn.operations[0].seg_id.multi_index);
0164
0165         linestring_type const& ls2 =
0166             range::at(m_multilinestring, turn.operations[1].seg_id.multi_index);
0167
0168         if (turn.operations[0].seg_id.multi_index
0169             == turn.operations[1].seg_id.multi_index)
0170         {
0171             return is_closing_point_of(turn, ls1);
0172         }
0173
0174         return
0175             is_boundary_point_of(turn.point, ls1)
0176             && is_boundary_point_of(turn.point, ls2)
0177             &&
0178             ( boost::size(ls1) != 2
0179               || boost::size(ls2) != 2
0180               || ! have_same_boundary_points(ls1, ls2) );
0181     }
0182
0183 private:
0184     MultiLinestring const& m_multilinestring;
0185     Strategy const& m_strategy;
0186 };
0187
0188
0189 template <typename Linear, typename Strategy>
0190 inline bool has_self_intersections(Linear const& linear, Strategy const& strategy)
0191 {
0192     typedef typename point_type<Linear>::type point_type;
0193
0194     // compute self turns
0195     typedef detail::overlay::turn_info<point_type> turn_info;
0196
0197     std::deque<turn_info> turns;
0198
0199     typedef detail::overlay::get_turn_info
0200         <
0201             detail::disjoint::assign_disjoint_policy
0202         > turn_policy;
0203
0204     typedef is_acceptable_turn
0205         <
0206             Linear, Strategy
0207         > is_acceptable_turn_type;
0208
0209     is_acceptable_turn_type predicate(linear, strategy);
0210     detail::overlay::predicate_based_interrupt_policy
0211         <
0212             is_acceptable_turn_type
0213         > interrupt_policy(predicate);
0214
0215     // TODO: skip_adjacent should be set to false
0216     detail::self_get_turn_points::get_turns
0217         <
0218             false, turn_policy
0219         >::apply(linear,
0220                  strategy,
0221                  detail::no_rescale_policy(),
0222                  turns,
0223                  interrupt_policy, 0, true);
0224
0225     detail::is_valid::debug_print_turns(turns.begin(), turns.end());
0226     debug_print_boundary_points(linear);
0227
0228     return interrupt_policy.has_intersections;
0229 }
0230
0231
0232 template <typename Linestring, bool CheckSelfIntersections = true>
0233 struct is_simple_linestring
0234 {
0235     template <typename Strategy>
0236     static inline bool apply(Linestring const& linestring,
0237                              Strategy const& strategy)
0238     {
0239         simplicity_failure_policy policy;
0240         return ! boost::empty(linestring)
0241             && ! detail::is_valid::has_duplicates<Linestring>::apply(linestring, policy, strategy)
0242             && ! detail::is_valid::has_spikes<Linestring>::apply(linestring, policy, strategy);
0243     }
0244 };
0245
0246 template <typename Linestring>
0247 struct is_simple_linestring<Linestring, true>
0248 {
0249     template <typename Strategy>
0250     static inline bool apply(Linestring const& linestring,
0251                              Strategy const& strategy)
0252     {
0253         return is_simple_linestring<Linestring, false>::apply(linestring, strategy)
0254             && ! has_self_intersections(linestring, strategy);
0255     }
0256 };
0257
0258
0259 template <typename MultiLinestring>
0260 struct is_simple_multilinestring
0261 {
0262 private:
0263     template <typename Strategy>
0264     struct not_simple
0265     {
0266         not_simple(Strategy const& strategy)
0267             : m_strategy(strategy)
0268         {}
0269
0270         template <typename Linestring>
0271         inline bool operator()(Linestring const& linestring) const
0272         {
0273             return ! detail::is_simple::is_simple_linestring
0274                 <
0275                     Linestring,
0276                     false // do not compute self-intersections
0277                 >::apply(linestring, m_strategy);
0278         }
0279
0280         Strategy const& m_strategy;
0281     };
0282
0283 public:
0284     template <typename Strategy>
0285     static inline bool apply(MultiLinestring const& multilinestring,
0286                              Strategy const& strategy)
0287     {
0288         // check each of the linestrings for simplicity
0289         // but do not compute self-intersections yet; these will be
0290         // computed for the entire multilinestring
0291         // return true for empty multilinestring
0292
0293         using not_simple = not_simple<Strategy>; // do not compute self-intersections
0294
0295         if (std::any_of(boost::begin(multilinestring),
0296                         boost::end(multilinestring),
0297                         not_simple(strategy)))
0298         {
0299             return false;
0300         }
0301
0302         return ! has_self_intersections(multilinestring, strategy);
0303     }
0304 };
0305
0306
0307
0308 }} // namespace detail::is_simple
0309 #endif // DOXYGEN_NO_DETAIL
0310
0311
0312
0313 #ifndef DOXYGEN_NO_DISPATCH
0314 namespace dispatch
0315 {
0316
0317 // A linestring is a curve.
0318 // A curve is simple if it does not pass through the same point twice,
0319 // with the possible exception of its two endpoints
0320 //
0321 // Reference: OGC 06-103r4 (6.1.6.1)
0322 template <typename Linestring>
0323 struct is_simple<Linestring, linestring_tag>
0324     : detail::is_simple::is_simple_linestring<Linestring>
0325 {};
0326
0327
0328 // A MultiLinestring is a MultiCurve
0329 // A MultiCurve is simple if all of its elements are simple and the
0330 // only intersections between any two elements occur at Points that
0331 // are on the boundaries of both elements.
0332 //
0333 // Reference: OGC 06-103r4 (6.1.8.1; Fig. 9)
0334 template <typename MultiLinestring>
0335 struct is_simple<MultiLinestring, multi_linestring_tag>
0336     : detail::is_simple::is_simple_multilinestring<MultiLinestring>
0337 {};
0338
0339
0340 } // namespace dispatch
0341 #endif // DOXYGEN_NO_DISPATCH
0342
0343
0344 }} // namespace boost::geometry
0345
0346
0347 #endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_IS_SIMPLE_LINEAR_HPP