algorithms/detail/point_is_spike_or_equal.hpp

0001 // Boost.Geometry (aka GGL, Generic Geometry Library)
0002
0003 // Copyright (c) 2007-2015 Barend Gehrels, Amsterdam, the Netherlands.
0004 // Copyright (c) 2008-2015 Bruno Lalande, Paris, France.
0005 // Copyright (c) 2009-2015 Mateusz Loskot, London, UK.
0006 // Copyright (c) 2013-2023 Adam Wulkiewicz, Lodz, Poland.
0007
0008 // This file was modified by Oracle on 2015, 2017, 2019.
0009 // Modifications copyright (c) 2015-2019 Oracle and/or its affiliates.
0010 // Contributed and/or modified by Menelaos Karavelas, on behalf of Oracle
0011 // Contributed and/or modified by Adam Wulkiewicz, on behalf of Oracle
0012
0013 // Use, modification and distribution is subject to the Boost Software License,
0014 // Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
0015 // http://www.boost.org/LICENSE_1_0.txt)
0016
0017 #ifndef BOOST_GEOMETRY_ALGORITHMS_DETAIL_POINT_IS_EQUAL_OR_SPIKE_HPP
0018 #define BOOST_GEOMETRY_ALGORITHMS_DETAIL_POINT_IS_EQUAL_OR_SPIKE_HPP
0019
0020 #include <boost/geometry/algorithms/detail/direction_code.hpp>
0021 #include <boost/geometry/algorithms/detail/recalculate.hpp>
0022 #include <boost/geometry/core/cs.hpp>
0023 #include <boost/geometry/policies/robustness/robust_point_type.hpp>
0024 #include <boost/geometry/strategies/side.hpp>
0025 #include <boost/geometry/util/constexpr.hpp>
0026 #include <boost/geometry/util/math.hpp>
0027
0028
0029 namespace boost { namespace geometry
0030 {
0031
0032
0033 #ifndef DOXYGEN_NO_DETAIL
0034 namespace detail
0035 {
0036
0037 // Checks if a point ("last_point") causes a spike w.r.t.
0038 // the specified two other points (segment_a, segment_b)
0039 //
0040 //  x-------x------x
0041 //  a       lp     b
0042 //
0043 // Above, lp generates a spike w.r.t. segment(a,b)
0044 // So specify last point first, then (a,b)
0045 // The segment's orientation does matter: if lp is to the right of b
0046 // no spike is reported
0047 template
0048 <
0049     typename Point1, typename Point2, typename Point3,
0050     typename SideStrategy
0051 >
0052 inline bool point_is_spike_or_equal(Point1 const& last_point, // prev | back
0053                                     Point2 const& segment_a,  // next | back - 2
0054                                     Point3 const& segment_b,  // curr | back - 1 | spike's vertex
0055                                     SideStrategy const& strategy)
0056 {
0057     typedef typename SideStrategy::cs_tag cs_tag;
0058
0059     int const side = strategy.apply(segment_a, segment_b, last_point);
0060     if (side == 0)
0061     {
0062         // Last point is collinear w.r.t previous segment.
0063         return direction_code<cs_tag>(segment_a, segment_b, last_point) < 1;
0064     }
0065     return false;
0066 }
0067
0068 template
0069 <
0070     typename Point1,
0071     typename Point2,
0072     typename Point3,
0073     typename SideStrategy,
0074     typename RobustPolicy
0075 >
0076 inline bool point_is_spike_or_equal(Point1 const& last_point,
0077             Point2 const& segment_a,
0078             Point3 const& segment_b,
0079             SideStrategy const& strategy,
0080             RobustPolicy const& robust_policy)
0081 {
0082     if (point_is_spike_or_equal(last_point, segment_a, segment_b, strategy))
0083     {
0084         return true;
0085     }
0086
0087     if BOOST_GEOMETRY_CONSTEXPR (! RobustPolicy::enabled)
0088     {
0089         return false;
0090     }
0091     else // else prevents unreachable code warning
0092     {
0093         // Try using specified robust policy
0094         using robust_point_type = typename geometry::robust_point_type
0095             <
0096                 Point1,
0097                 RobustPolicy
0098             >::type;
0099
0100         robust_point_type last_point_rob, segment_a_rob, segment_b_rob;
0101         geometry::recalculate(last_point_rob, last_point, robust_policy);
0102         geometry::recalculate(segment_a_rob, segment_a, robust_policy);
0103         geometry::recalculate(segment_b_rob, segment_b, robust_policy);
0104
0105         return point_is_spike_or_equal(last_point_rob, segment_a_rob, segment_b_rob,
0106                                        strategy);
0107     }
0108 }
0109
0110 template
0111 <
0112     typename Point1,
0113     typename Point2,
0114     typename Point3,
0115     typename SideStrategy,
0116     typename RobustPolicy
0117 >
0118 inline bool point_is_collinear(Point1 const& last_point,
0119             Point2 const& segment_a,
0120             Point3 const& segment_b,
0121             SideStrategy const& strategy,
0122             RobustPolicy const& robust_policy)
0123 {
0124     int const side = strategy.apply(segment_a, segment_b, last_point);
0125     if (side == 0)
0126     {
0127         return true;
0128     }
0129
0130     // This part (or whole method, because it is then trivial)
0131     // will be removed after rescaling
0132     if BOOST_GEOMETRY_CONSTEXPR (! RobustPolicy::enabled)
0133     {
0134         return false;
0135     }
0136     else // else prevents unreachable code warning
0137     {
0138         // Redo, using specified robust policy
0139         using robust_point_type = typename geometry::robust_point_type
0140             <
0141                 Point1,
0142                 RobustPolicy
0143             >::type;
0144
0145         robust_point_type last_point_rob, segment_a_rob, segment_b_rob;
0146         geometry::recalculate(last_point_rob, last_point, robust_policy);
0147         geometry::recalculate(segment_a_rob, segment_a, robust_policy);
0148         geometry::recalculate(segment_b_rob, segment_b, robust_policy);
0149
0150         int const side_rob = strategy.apply(segment_a_rob, segment_b_rob, last_point_rob);
0151         return side_rob == 0;
0152     }
0153 }
0154
0155
0156 //! Version with intuitive order (A, B, C). The original order was
0157 //! unclear (C, A, B). It was used in a different way in has_spikes.
0158 //! On longer term the C,A,B version can be deprecated
0159 template
0160 <
0161     typename Point1,
0162     typename Point2,
0163     typename Point3,
0164     typename SideStrategy
0165 >
0166 inline bool is_spike_or_equal(Point1 const& a,
0167             Point2 const& b,
0168             Point3 const& c,
0169             SideStrategy const& strategy)
0170 {
0171     return point_is_spike_or_equal(c, a, b, strategy);
0172 }
0173
0174
0175 } // namespace detail
0176 #endif
0177
0178 }} // namespace boost::geometry
0179
0180
0181 #endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_POINT_IS_EQUAL_OR_SPIKE_HPP