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