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, 2019.
   9 // Modifications copyright (c) 2015-2019 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 // Checks if a point ("last_point") causes a spike w.r.t.
  39 // the specified two other points (segment_a, segment_b)
  40 //
  41 //  x-------x------x
  42 //  a       lp     b
  43 //
  44 // Above, lp generates a spike w.r.t. segment(a,b)
  45 // So specify last point first, then (a,b)
  46 // The segment's orientation does matter: if lp is to the right of b
  47 // no spike is reported
  48 template
  49 <
  50     typename Point1, typename Point2, typename Point3,
  51     typename SideStrategy
  52 >
  53 inline bool point_is_spike_or_equal(Point1 const& last_point, // prev | back
  54                                     Point2 const& segment_a,  // next | back - 2
  55                                     Point3 const& segment_b,  // curr | back - 1 | spike's vertex
  56                                     SideStrategy const& strategy)
  57 {
  58     typedef typename SideStrategy::cs_tag cs_tag;
  59
  60     int const side = strategy.apply(segment_a, segment_b, last_point);
  61     if (side == 0)
  62     {
  63         // Last point is collinear w.r.t previous segment.
  64         return direction_code<cs_tag>(segment_a, segment_b, last_point) < 1;
  65     }
  66     return false;
  67 }
  68
  69 template
  70 <
  71     typename Point1,
  72     typename Point2,
  73     typename Point3,
  74     typename SideStrategy,
  75     typename RobustPolicy
  76 >
  77 inline bool point_is_spike_or_equal(Point1 const& last_point,
  78             Point2 const& segment_a,
  79             Point3 const& segment_b,
  80             SideStrategy const& strategy,
  81             RobustPolicy const& robust_policy)
  82 {
  83     if (point_is_spike_or_equal(last_point, segment_a, segment_b, strategy))
  84     {
  85         return true;
  86     }
  87
  88     if (BOOST_GEOMETRY_CONDITION(! RobustPolicy::enabled))
  89     {
  90         return false;
  91     }
  92
  93     // Try using specified robust policy
  94     typedef typename geometry::robust_point_type
  95     <
  96         Point1,
  97         RobustPolicy
  98     >::type robust_point_type;
  99
 100     robust_point_type last_point_rob, segment_a_rob, segment_b_rob;
 101     geometry::recalculate(last_point_rob, last_point, robust_policy);
 102     geometry::recalculate(segment_a_rob, segment_a, robust_policy);
 103     geometry::recalculate(segment_b_rob, segment_b, robust_policy);
 104
 105     return point_is_spike_or_equal
 106         (
 107             last_point_rob,
 108             segment_a_rob,
 109             segment_b_rob,
 110             strategy
 111         );
 112 }
 113
 114 template
 115 <
 116     typename Point1,
 117     typename Point2,
 118     typename Point3,
 119     typename SideStrategy,
 120     typename RobustPolicy
 121 >
 122 inline bool point_is_collinear(Point1 const& last_point,
 123             Point2 const& segment_a,
 124             Point3 const& segment_b,
 125             SideStrategy const& strategy,
 126             RobustPolicy const& robust_policy)
 127 {
 128     int const side = strategy.apply(segment_a, segment_b, last_point);
 129     if (side == 0)
 130     {
 131         return true;
 132     }
 133
 134     // This part (or whole method, because it is then trivial)
 135     // will be removed after rescaling
 136     if (BOOST_GEOMETRY_CONDITION(! RobustPolicy::enabled))
 137     {
 138         return false;
 139     }
 140
 141     // Redo, using specified robust policy
 142     typedef typename geometry::robust_point_type
 143     <
 144         Point1,
 145         RobustPolicy
 146     >::type robust_point_type;
 147
 148     robust_point_type last_point_rob, segment_a_rob, segment_b_rob;
 149     geometry::recalculate(last_point_rob, last_point, robust_policy);
 150     geometry::recalculate(segment_a_rob, segment_a, robust_policy);
 151     geometry::recalculate(segment_b_rob, segment_b, robust_policy);
 152
 153     int const side_rob = strategy.apply(segment_a_rob, segment_b_rob, last_point_rob);
 154     return side_rob == 0;
 155 }
 156
 157
 158 //! Version with intuitive order (A, B, C). The original order was
 159 //! unclear (C, A, B). It was used in a different way in has_spikes.
 160 //! On longer term the C,A,B version can be deprecated
 161 template
 162 <
 163     typename Point1,
 164     typename Point2,
 165     typename Point3,
 166     typename SideStrategy
 167 >
 168 inline bool is_spike_or_equal(Point1 const& a,
 169             Point2 const& b,
 170             Point3 const& c,
 171             SideStrategy const& strategy)
 172 {
 173     return point_is_spike_or_equal(c, a, b, strategy);
 174 }
 175
 176
 177 } // namespace detail
 178 #endif
 179
 180 }} // namespace boost::geometry
 181
 182
 183 #endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_POINT_IS_EQUAL_OR_SPIKE_HPP