ceph/src/boost/boost/geometry/strategies/cartesian/point_in_poly_winding.hpp

   1 // Boost.Geometry (aka GGL, Generic Geometry Library)
   2
   3 // Copyright (c) 2007-2012 Barend Gehrels, Amsterdam, the Netherlands.
   4 // Copyright (c) 2013 Adam Wulkiewicz, Lodz, Poland.
   5
   6 // This file was modified by Oracle on 2013, 2014, 2016, 2017.
   7 // Modifications copyright (c) 2013-2017 Oracle and/or its affiliates.
   8 // Contributed and/or modified by Adam Wulkiewicz, on behalf of Oracle
   9
  10 // Parts of Boost.Geometry are redesigned from Geodan's Geographic Library
  11 // (geolib/GGL), copyright (c) 1995-2010 Geodan, Amsterdam, the Netherlands.
  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_STRATEGY_CARTESIAN_POINT_IN_POLY_WINDING_HPP
  18 #define BOOST_GEOMETRY_STRATEGY_CARTESIAN_POINT_IN_POLY_WINDING_HPP
  19
  20
  21 #include <boost/geometry/core/tags.hpp>
  22
  23 #include <boost/geometry/util/math.hpp>
  24 #include <boost/geometry/util/select_calculation_type.hpp>
  25
  26 #include <boost/geometry/strategies/cartesian/side_by_triangle.hpp>
  27 #include <boost/geometry/strategies/covered_by.hpp>
  28 #include <boost/geometry/strategies/within.hpp>
  29
  30
  31 namespace boost { namespace geometry
  32 {
  33
  34 namespace strategy { namespace within
  35 {
  36
  37
  38 /*!
  39 \brief Within detection using winding rule in cartesian coordinate system.
  40 \ingroup strategies
  41 \tparam Point \tparam_point
  42 \tparam PointOfSegment \tparam_segment_point
  43 \tparam CalculationType \tparam_calculation
  44 \author Barend Gehrels
  45 \note The implementation is inspired by terralib http://www.terralib.org (LGPL)
  46 \note but totally revised afterwards, especially for cases on segments
  47
  48 \qbk{
  49 [heading See also]
  50 [link geometry.reference.algorithms.within.within_3_with_strategy within (with strategy)]
  51 }
  52  */
  53 template
  54 <
  55     typename Point,
  56     typename PointOfSegment = Point,
  57     typename CalculationType = void
  58 >
  59 class cartesian_winding
  60 {
  61     typedef side::side_by_triangle<CalculationType> side_strategy_type;
  62
  63     typedef typename select_calculation_type
  64         <
  65             Point,
  66             PointOfSegment,
  67             CalculationType
  68         >::type calculation_type;
  69
  70     /*! subclass to keep state */
  71     class counter
  72     {
  73         int m_count;
  74         bool m_touches;
  75
  76         inline int code() const
  77         {
  78             return m_touches ? 0 : m_count == 0 ? -1 : 1;
  79         }
  80
  81     public :
  82         friend class cartesian_winding;
  83
  84         inline counter()
  85             : m_count(0)
  86             , m_touches(false)
  87         {}
  88
  89     };
  90
  91 public:
  92     typedef typename side_strategy_type::envelope_strategy_type envelope_strategy_type;
  93
  94     static inline envelope_strategy_type get_envelope_strategy()
  95     {
  96         return side_strategy_type::get_envelope_strategy();
  97     }
  98
  99     typedef typename side_strategy_type::disjoint_strategy_type disjoint_strategy_type;
 100
 101     static inline disjoint_strategy_type get_disjoint_strategy()
 102     {
 103         return side_strategy_type::get_disjoint_strategy();
 104     }
 105
 106     // Typedefs and static methods to fulfill the concept
 107     typedef Point point_type;
 108     typedef PointOfSegment segment_point_type;
 109     typedef counter state_type;
 110
 111     static inline bool apply(Point const& point,
 112                              PointOfSegment const& s1, PointOfSegment const& s2,
 113                              counter& state)
 114     {
 115         bool eq1 = false;
 116         bool eq2 = false;
 117
 118         int count = check_segment(point, s1, s2, state, eq1, eq2);
 119         if (count != 0)
 120         {
 121             int side = 0;
 122             if (count == 1 || count == -1)
 123             {
 124                 side = side_equal(point, eq1 ? s1 : s2, count);
 125             }
 126             else // count == 2 || count == -2
 127             {
 128                 // 1 left, -1 right
 129                 side = side_strategy_type::apply(s1, s2, point);
 130             }
 131
 132             if (side == 0)
 133             {
 134                 // Point is lying on segment
 135                 state.m_touches = true;
 136                 state.m_count = 0;
 137                 return false;
 138             }
 139
 140             // Side is NEG for right, POS for left.
 141             // The count is -2 for left, 2 for right (or -1/1)
 142             // Side positive thus means RIGHT and LEFTSIDE or LEFT and RIGHTSIDE
 143             // See accompagnying figure (TODO)
 144             if (side * count > 0)
 145             {
 146                 state.m_count += count;
 147             }
 148         }
 149         return ! state.m_touches;
 150     }
 151
 152     static inline int result(counter const& state)
 153     {
 154         return state.code();
 155     }
 156
 157 private:
 158     static inline int check_segment(Point const& point,
 159                                     PointOfSegment const& seg1,
 160                                     PointOfSegment const& seg2,
 161                                     counter& state,
 162                                     bool& eq1, bool& eq2)
 163     {
 164         if (check_touch(point, seg1, seg2, state, eq1, eq2))
 165         {
 166             return 0;
 167         }
 168
 169         return calculate_count(point, seg1, seg2, eq1, eq2);
 170     }
 171
 172     static inline bool check_touch(Point const& point,
 173                                    PointOfSegment const& seg1,
 174                                    PointOfSegment const& seg2,
 175                                    counter& state,
 176                                    bool& eq1, bool& eq2)
 177     {
 178         calculation_type const px = get<0>(point);
 179         calculation_type const s1x = get<0>(seg1);
 180         calculation_type const s2x = get<0>(seg2);
 181
 182         eq1 = math::equals(s1x, px);
 183         eq2 = math::equals(s2x, px);
 184
 185         // Both equal p -> segment vertical
 186         // The only thing which has to be done is check if point is ON segment
 187         if (eq1 && eq2)
 188         {
 189             calculation_type const py = get<1>(point);
 190             calculation_type const s1y = get<1>(seg1);
 191             calculation_type const s2y = get<1>(seg2);
 192             if ((s1y <= py && s2y >= py) || (s2y <= py && s1y >= py))
 193             {
 194                 state.m_touches = true;
 195             }
 196             return true;
 197         }
 198         return false;
 199     }
 200
 201     static inline int calculate_count(Point const& point,
 202                                       PointOfSegment const& seg1,
 203                                       PointOfSegment const& seg2,
 204                                       bool eq1, bool eq2)
 205     {
 206         calculation_type const p = get<0>(point);
 207         calculation_type const s1 = get<0>(seg1);
 208         calculation_type const s2 = get<0>(seg2);
 209
 210         return eq1 ? (s2 > p ?  1 : -1)  // Point on level s1, E/W depending on s2
 211              : eq2 ? (s1 > p ? -1 :  1)  // idem
 212              : s1 < p && s2 > p ?  2     // Point between s1 -> s2 --> E
 213              : s2 < p && s1 > p ? -2     // Point between s2 -> s1 --> W
 214              : 0;
 215     }
 216
 217     static inline int side_equal(Point const& point,
 218                                  PointOfSegment const& se,
 219                                  int count)
 220     {
 221         // NOTE: for D=0 the signs would be reversed
 222         return math::equals(get<1>(point), get<1>(se)) ?
 223                 0 :
 224                 get<1>(point) < get<1>(se) ?
 225                     // assuming count is equal to 1 or -1
 226                     -count : // ( count > 0 ? -1 : 1) :
 227                     count;   // ( count > 0 ? 1 : -1) ;
 228     }
 229 };
 230
 231
 232 #ifndef DOXYGEN_NO_STRATEGY_SPECIALIZATIONS
 233
 234 namespace services
 235 {
 236
 237 template <typename PointLike, typename Geometry, typename AnyTag1, typename AnyTag2>
 238 struct default_strategy<PointLike, Geometry, AnyTag1, AnyTag2, pointlike_tag, polygonal_tag, cartesian_tag, cartesian_tag>
 239 {
 240     typedef cartesian_winding
 241         <
 242             typename geometry::point_type<PointLike>::type,
 243             typename geometry::point_type<Geometry>::type
 244         > type;
 245 };
 246
 247 template <typename PointLike, typename Geometry, typename AnyTag1, typename AnyTag2>
 248 struct default_strategy<PointLike, Geometry, AnyTag1, AnyTag2, pointlike_tag, linear_tag, cartesian_tag, cartesian_tag>
 249 {
 250     typedef cartesian_winding
 251         <
 252             typename geometry::point_type<PointLike>::type,
 253             typename geometry::point_type<Geometry>::type
 254         > type;
 255 };
 256
 257 } // namespace services
 258
 259 #endif
 260
 261
 262 }} // namespace strategy::within
 263
 264
 265 #ifndef DOXYGEN_NO_STRATEGY_SPECIALIZATIONS
 266 namespace strategy { namespace covered_by { namespace services
 267 {
 268
 269 template <typename PointLike, typename Geometry, typename AnyTag1, typename AnyTag2>
 270 struct default_strategy<PointLike, Geometry, AnyTag1, AnyTag2, pointlike_tag, polygonal_tag, cartesian_tag, cartesian_tag>
 271 {
 272     typedef within::cartesian_winding
 273         <
 274             typename geometry::point_type<PointLike>::type,
 275             typename geometry::point_type<Geometry>::type
 276         > type;
 277 };
 278
 279 template <typename PointLike, typename Geometry, typename AnyTag1, typename AnyTag2>
 280 struct default_strategy<PointLike, Geometry, AnyTag1, AnyTag2, pointlike_tag, linear_tag, cartesian_tag, cartesian_tag>
 281 {
 282     typedef within::cartesian_winding
 283         <
 284             typename geometry::point_type<PointLike>::type,
 285             typename geometry::point_type<Geometry>::type
 286         > type;
 287 };
 288
 289 }}} // namespace strategy::covered_by::services
 290 #endif
 291
 292
 293 }} // namespace boost::geometry
 294
 295
 296 #endif // BOOST_GEOMETRY_STRATEGY_CARTESIAN_POINT_IN_POLY_WINDING_HPP