ceph/src/boost/libs/geometry/include/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.
   9 // Modifications copyright (c) 2015 Oracle and/or its affiliates.
  10
  11 // Contributed and/or modified by Menelaos Karavelas, on behalf of Oracle
  12
  13 // Use, modification and distribution is subject to the Boost Software License,
  14 // Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
  15 // http://www.boost.org/LICENSE_1_0.txt)
  16
  17 #ifndef BOOST_GEOMETRY_ALGORITHMS_DETAIL_POINT_IS_EQUAL_OR_SPIKE_HPP
  18 #define BOOST_GEOMETRY_ALGORITHMS_DETAIL_POINT_IS_EQUAL_OR_SPIKE_HPP
  19
  20 #include <boost/geometry/algorithms/detail/direction_code.hpp>
  21 #include <boost/geometry/algorithms/detail/recalculate.hpp>
  22 #include <boost/geometry/policies/robustness/robust_point_type.hpp>
  23 #include <boost/geometry/strategies/side.hpp>
  24 #include <boost/geometry/util/condition.hpp>
  25 #include <boost/geometry/util/math.hpp>
  26
  27 namespace boost { namespace geometry
  28 {
  29
  30
  31 #ifndef DOXYGEN_NO_DETAIL
  32 namespace detail
  33 {
  34
  35 // Checks if a point ("last_point") causes a spike w.r.t.
  36 // the specified two other points (segment_a, segment_b)
  37 //
  38 //  x-------x------x
  39 //  a       lp     b
  40 //
  41 // Above, lp generates a spike w.r.t. segment(a,b)
  42 // So specify last point first, then (a,b)
  43 // The segment's orientation does matter: if lp is to the right of b
  44 // no spike is reported
  45 template <typename Point1, typename Point2, typename Point3>
  46 static inline bool point_is_spike_or_equal(Point1 const& last_point,
  47             Point2 const& segment_a,
  48             Point3 const& segment_b)
  49 {
  50     typedef typename strategy::side::services::default_strategy
  51     <
  52         typename cs_tag<Point1>::type
  53     >::type side_strategy;
  54
  55     int const side = side_strategy::apply(last_point, segment_a, segment_b);
  56     if (side == 0)
  57     {
  58         // Last point is collinear w.r.t previous segment.
  59         // Check if it is equal
  60         int const sgn_x1 = sign_of_difference<0>(last_point, segment_b);
  61         int const sgn_y1 = sign_of_difference<1>(last_point, segment_b);
  62         if (sgn_x1 == 0 && sgn_y1 == 0)
  63         {
  64             return true;
  65         }
  66
  67         // Check if it moves forward
  68         int const sgn_x2 = sign_of_difference<0>(segment_b, segment_a);
  69         int const sgn_y2 = sign_of_difference<1>(segment_b, segment_a);
  70
  71         return sgn_x1 != sgn_x2 || sgn_y1 != sgn_y2;
  72     }
  73     return false;
  74 }
  75
  76 template
  77 <
  78     typename Point1,
  79     typename Point2,
  80     typename Point3,
  81     typename RobustPolicy
  82 >
  83 static inline bool point_is_spike_or_equal(Point1 const& last_point,
  84             Point2 const& segment_a,
  85             Point3 const& segment_b,
  86             RobustPolicy const& robust_policy)
  87 {
  88     if (point_is_spike_or_equal(last_point, segment_a, segment_b))
  89     {
  90         return true;
  91     }
  92
  93     if (BOOST_GEOMETRY_CONDITION(! RobustPolicy::enabled))
  94     {
  95         return false;
  96     }
  97
  98     // Try using specified robust policy
  99     typedef typename geometry::robust_point_type
 100     <
 101         Point1,
 102         RobustPolicy
 103     >::type robust_point_type;
 104
 105     robust_point_type last_point_rob, segment_a_rob, segment_b_rob;
 106     geometry::recalculate(last_point_rob, last_point, robust_policy);
 107     geometry::recalculate(segment_a_rob, segment_a, robust_policy);
 108     geometry::recalculate(segment_b_rob, segment_b, robust_policy);
 109
 110     return point_is_spike_or_equal
 111         (
 112             last_point_rob,
 113             segment_a_rob,
 114             segment_b_rob
 115         );
 116 }
 117
 118
 119 } // namespace detail
 120 #endif
 121
 122 }} // namespace boost::geometry
 123
 124
 125 #endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_POINT_IS_EQUAL_OR_SPIKE_HPP