ceph/src/boost/boost/geometry/algorithms/detail/point_is_spike_or_equal.hpp

   1 // Boost.Geometry (aka GGL, Generic Geometry Library)
   2
   3 // Copyright (c) 2007-2015 Barend Gehrels, Amsterdam, the Netherlands.
   4 // Copyright (c) 2008-2015 Bruno Lalande, Paris, France.
   5 // Copyright (c) 2009-2015 Mateusz Loskot, London, UK.
   6 // Copyright (c) 2013-2015 Adam Wulkiewicz, Lodz, Poland.
   7
   8 // This file was modified by Oracle on 2015, 2017.
   9 // Modifications copyright (c) 2015-2017 Oracle and/or its affiliates.
  10
  11 // Contributed and/or modified by Menelaos Karavelas, on behalf of Oracle
  12 // Contributed and/or modified by Adam Wulkiewicz, on behalf of Oracle
  13
  14 // Use, modification and distribution is subject to the Boost Software License,
  15 // Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
  16 // http://www.boost.org/LICENSE_1_0.txt)
  17
  18 #ifndef BOOST_GEOMETRY_ALGORITHMS_DETAIL_POINT_IS_EQUAL_OR_SPIKE_HPP
  19 #define BOOST_GEOMETRY_ALGORITHMS_DETAIL_POINT_IS_EQUAL_OR_SPIKE_HPP
  20
  21 #include <boost/geometry/algorithms/detail/direction_code.hpp>
  22 #include <boost/geometry/algorithms/detail/recalculate.hpp>
  23 #include <boost/geometry/core/cs.hpp>
  24 #include <boost/geometry/policies/robustness/robust_point_type.hpp>
  25 #include <boost/geometry/strategies/side.hpp>
  26 #include <boost/geometry/util/condition.hpp>
  27 #include <boost/geometry/util/math.hpp>
  28
  29
  30 namespace boost { namespace geometry
  31 {
  32
  33
  34 #ifndef DOXYGEN_NO_DETAIL
  35 namespace detail
  36 {
  37
  38 template <typename Point1, typename Point2, typename Point3>
  39 inline bool collinear_point_is_spike_or_equal(Point1 const& last_point,
  40                                                 Point2 const& segment_a,
  41                                                 Point3 const& segment_b)
  42 {
  43     // Check if segment is equal
  44     int const sgn_x1 = sign_of_difference<0>(last_point, segment_b);
  45     int const sgn_y1 = sign_of_difference<1>(last_point, segment_b);
  46     if (sgn_x1 == 0 && sgn_y1 == 0)
  47     {
  48         return true;
  49     }
  50
  51     // Check if segment moves forward
  52     int const sgn_x2 = sign_of_difference<0>(segment_b, segment_a);
  53     int const sgn_y2 = sign_of_difference<1>(segment_b, segment_a);
  54
  55     return sgn_x1 != sgn_x2 || sgn_y1 != sgn_y2;
  56 }
  57
  58 // Checks if a point ("last_point") causes a spike w.r.t.
  59 // the specified two other points (segment_a, segment_b)
  60 //
  61 //  x-------x------x
  62 //  a       lp     b
  63 //
  64 // Above, lp generates a spike w.r.t. segment(a,b)
  65 // So specify last point first, then (a,b)
  66 // The segment's orientation does matter: if lp is to the right of b
  67 // no spike is reported
  68 template
  69 <
  70     typename Point1, typename Point2, typename Point3,
  71     typename SideStrategy
  72 >
  73 static inline bool point_is_spike_or_equal(Point1 const& last_point, // prev | back
  74                                            Point2 const& segment_a,  // next | back - 2
  75                                            Point3 const& segment_b,  // curr | back - 1 | spike's vertex
  76                                            SideStrategy const& strategy)
  77 {
  78     int const side = strategy.apply(segment_a, segment_b, last_point);
  79     if (side == 0)
  80     {
  81         // Last point is collinear w.r.t previous segment.
  82 #ifdef BOOST_GEOMETRY_ENABLE_POINT_IS_SPIKE_OR_EQUAL_TEST
  83         bool r1 = collinear_point_is_spike_or_equal(last_point, segment_a, segment_b);
  84         bool r2 = direction_code(segment_a, segment_b, last_point) < 1;
  85         if (r1 != r2)
  86             std::cout << "spike detection failure with: " << r1 << " " << r2 << std::endl;
  87         return r2;
  88 #else
  89         return direction_code(segment_a, segment_b, last_point) < 1;
  90 #endif
  91     }
  92     return false;
  93 }
  94
  95 template
  96 <
  97     typename Point1,
  98     typename Point2,
  99     typename Point3,
 100     typename SideStrategy,
 101     typename RobustPolicy
 102 >
 103 static inline bool point_is_spike_or_equal(Point1 const& last_point,
 104             Point2 const& segment_a,
 105             Point3 const& segment_b,
 106             SideStrategy const& strategy,
 107             RobustPolicy const& robust_policy)
 108 {
 109     if (point_is_spike_or_equal(last_point, segment_a, segment_b, strategy))
 110     {
 111         return true;
 112     }
 113
 114     if (BOOST_GEOMETRY_CONDITION(! RobustPolicy::enabled))
 115     {
 116         return false;
 117     }
 118
 119     // Try using specified robust policy
 120     typedef typename geometry::robust_point_type
 121     <
 122         Point1,
 123         RobustPolicy
 124     >::type robust_point_type;
 125
 126     robust_point_type last_point_rob, segment_a_rob, segment_b_rob;
 127     geometry::recalculate(last_point_rob, last_point, robust_policy);
 128     geometry::recalculate(segment_a_rob, segment_a, robust_policy);
 129     geometry::recalculate(segment_b_rob, segment_b, robust_policy);
 130
 131     return point_is_spike_or_equal
 132         (
 133             last_point_rob,
 134             segment_a_rob,
 135             segment_b_rob,
 136             strategy
 137         );
 138 }
 139
 140
 141 } // namespace detail
 142 #endif
 143
 144 }} // namespace boost::geometry
 145
 146
 147 #endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_POINT_IS_EQUAL_OR_SPIKE_HPP