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-2020.
   7 // Modifications copyright (c) 2013-2020 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/strategy/cartesian/expand_point.hpp>
  27
  28 #include <boost/geometry/strategies/cartesian/point_in_box.hpp>
  29 #include <boost/geometry/strategies/cartesian/disjoint_box_box.hpp>
  30 #include <boost/geometry/strategies/cartesian/side_by_triangle.hpp>
  31 #include <boost/geometry/strategies/covered_by.hpp>
  32 #include <boost/geometry/strategies/within.hpp>
  33
  34
  35 namespace boost { namespace geometry
  36 {
  37
  38 namespace strategy { namespace within
  39 {
  40
  41
  42 /*!
  43 \brief Within detection using winding rule in cartesian coordinate system.
  44 \ingroup strategies
  45 \tparam Point_ \tparam_point
  46 \tparam PointOfSegment_ \tparam_segment_point
  47 \tparam CalculationType \tparam_calculation
  48 \author Barend Gehrels
  49
  50 \qbk{
  51 [heading See also]
  52 [link geometry.reference.algorithms.within.within_3_with_strategy within (with strategy)]
  53 }
  54  */
  55 template
  56 <
  57     typename Point_ = void, // for backward compatibility
  58     typename PointOfSegment_ = Point_, // for backward compatibility
  59     typename CalculationType = void
  60 >
  61 class cartesian_winding
  62 {
  63     template <typename Point, typename PointOfSegment>
  64     struct calculation_type
  65         : select_calculation_type
  66             <
  67                 Point,
  68                 PointOfSegment,
  69                 CalculationType
  70             >
  71     {};
  72
  73     /*! subclass to keep state */
  74     class counter
  75     {
  76         int m_count;
  77         bool m_touches;
  78
  79         inline int code() const
  80         {
  81             return m_touches ? 0 : m_count == 0 ? -1 : 1;
  82         }
  83
  84     public :
  85         friend class cartesian_winding;
  86
  87         inline counter()
  88             : m_count(0)
  89             , m_touches(false)
  90         {}
  91
  92     };
  93
  94 public:
  95     typedef cartesian_tag cs_tag;
  96
  97     typedef side::side_by_triangle<CalculationType> side_strategy_type;
  98
  99     static inline side_strategy_type get_side_strategy()
 100     {
 101         return side_strategy_type();
 102     }
 103
 104     typedef expand::cartesian_point expand_point_strategy_type;
 105
 106     typedef typename side_strategy_type::envelope_strategy_type envelope_strategy_type;
 107
 108     static inline envelope_strategy_type get_envelope_strategy()
 109     {
 110         return side_strategy_type::get_envelope_strategy();
 111     }
 112
 113     typedef typename side_strategy_type::disjoint_strategy_type disjoint_strategy_type;
 114
 115     static inline disjoint_strategy_type get_disjoint_strategy()
 116     {
 117         return side_strategy_type::get_disjoint_strategy();
 118     }
 119
 120     typedef typename side_strategy_type::equals_point_point_strategy_type equals_point_point_strategy_type;
 121     static inline equals_point_point_strategy_type get_equals_point_point_strategy()
 122     {
 123         return side_strategy_type::get_equals_point_point_strategy();
 124     }
 125
 126     typedef disjoint::cartesian_box_box disjoint_box_box_strategy_type;
 127     static inline disjoint_box_box_strategy_type get_disjoint_box_box_strategy()
 128     {
 129         return disjoint_box_box_strategy_type();
 130     }
 131
 132     typedef covered_by::cartesian_point_box disjoint_point_box_strategy_type;
 133
 134     // Typedefs and static methods to fulfill the concept
 135     typedef counter state_type;
 136
 137     template <typename Point, typename PointOfSegment>
 138     static inline bool apply(Point const& point,
 139                              PointOfSegment const& s1, PointOfSegment const& s2,
 140                              counter& state)
 141     {
 142         bool eq1 = false;
 143         bool eq2 = false;
 144
 145         int count = check_segment(point, s1, s2, state, eq1, eq2);
 146         if (count != 0)
 147         {
 148             int side = 0;
 149             if (count == 1 || count == -1)
 150             {
 151                 side = side_equal(point, eq1 ? s1 : s2, count);
 152             }
 153             else // count == 2 || count == -2
 154             {
 155                 // 1 left, -1 right
 156                 side = side_strategy_type::apply(s1, s2, point);
 157             }
 158
 159             if (side == 0)
 160             {
 161                 // Point is lying on segment
 162                 state.m_touches = true;
 163                 state.m_count = 0;
 164                 return false;
 165             }
 166
 167             // Side is NEG for right, POS for left.
 168             // The count is -2 for left, 2 for right (or -1/1)
 169             // Side positive thus means RIGHT and LEFTSIDE or LEFT and RIGHTSIDE
 170             // See accompagnying figure (TODO)
 171             if (side * count > 0)
 172             {
 173                 state.m_count += count;
 174             }
 175         }
 176         return ! state.m_touches;
 177     }
 178
 179     static inline int result(counter const& state)
 180     {
 181         return state.code();
 182     }
 183
 184 private:
 185     template <typename Point, typename PointOfSegment>
 186     static inline int check_segment(Point const& point,
 187                                     PointOfSegment const& seg1,
 188                                     PointOfSegment const& seg2,
 189                                     counter& state,
 190                                     bool& eq1, bool& eq2)
 191     {
 192         if (check_touch(point, seg1, seg2, state, eq1, eq2))
 193         {
 194             return 0;
 195         }
 196
 197         return calculate_count(point, seg1, seg2, eq1, eq2);
 198     }
 199
 200     template <typename Point, typename PointOfSegment>
 201     static inline bool check_touch(Point const& point,
 202                                    PointOfSegment const& seg1,
 203                                    PointOfSegment const& seg2,
 204                                    counter& state,
 205                                    bool& eq1, bool& eq2)
 206     {
 207         typedef typename calculation_type<Point, PointOfSegment>::type calc_t;
 208
 209         calc_t const px = get<0>(point);
 210         calc_t const s1x = get<0>(seg1);
 211         calc_t const s2x = get<0>(seg2);
 212
 213         eq1 = math::equals(s1x, px);
 214         eq2 = math::equals(s2x, px);
 215
 216         // Both equal p -> segment vertical
 217         // The only thing which has to be done is check if point is ON segment
 218         if (eq1 && eq2)
 219         {
 220             calc_t const py = get<1>(point);
 221             calc_t const s1y = get<1>(seg1);
 222             calc_t const s2y = get<1>(seg2);
 223             if ((s1y <= py && s2y >= py) || (s2y <= py && s1y >= py))
 224             {
 225                 state.m_touches = true;
 226             }
 227             return true;
 228         }
 229         return false;
 230     }
 231
 232     template <typename Point, typename PointOfSegment>
 233     static inline int calculate_count(Point const& point,
 234                                       PointOfSegment const& seg1,
 235                                       PointOfSegment const& seg2,
 236                                       bool eq1, bool eq2)
 237     {
 238         typedef typename calculation_type<Point, PointOfSegment>::type calc_t;
 239
 240         calc_t const p = get<0>(point);
 241         calc_t const s1 = get<0>(seg1);
 242         calc_t const s2 = get<0>(seg2);
 243
 244         return eq1 ? (s2 > p ?  1 : -1)  // Point on level s1, E/W depending on s2
 245              : eq2 ? (s1 > p ? -1 :  1)  // idem
 246              : s1 < p && s2 > p ?  2     // Point between s1 -> s2 --> E
 247              : s2 < p && s1 > p ? -2     // Point between s2 -> s1 --> W
 248              : 0;
 249     }
 250
 251     template <typename Point, typename PointOfSegment>
 252     static inline int side_equal(Point const& point,
 253                                  PointOfSegment const& se,
 254                                  int count)
 255     {
 256         // NOTE: for D=0 the signs would be reversed
 257         return math::equals(get<1>(point), get<1>(se)) ?
 258                 0 :
 259                 get<1>(point) < get<1>(se) ?
 260                     // assuming count is equal to 1 or -1
 261                     -count : // ( count > 0 ? -1 : 1) :
 262                     count;   // ( count > 0 ? 1 : -1) ;
 263     }
 264 };
 265
 266
 267 #ifndef DOXYGEN_NO_STRATEGY_SPECIALIZATIONS
 268
 269 namespace services
 270 {
 271
 272 template <typename PointLike, typename Geometry, typename AnyTag1, typename AnyTag2>
 273 struct default_strategy<PointLike, Geometry, AnyTag1, AnyTag2, pointlike_tag, polygonal_tag, cartesian_tag, cartesian_tag>
 274 {
 275     typedef cartesian_winding<> type;
 276 };
 277
 278 template <typename PointLike, typename Geometry, typename AnyTag1, typename AnyTag2>
 279 struct default_strategy<PointLike, Geometry, AnyTag1, AnyTag2, pointlike_tag, linear_tag, cartesian_tag, cartesian_tag>
 280 {
 281     typedef cartesian_winding<> type;
 282 };
 283
 284 } // namespace services
 285
 286 #endif
 287
 288
 289 }} // namespace strategy::within
 290
 291
 292 #ifndef DOXYGEN_NO_STRATEGY_SPECIALIZATIONS
 293 namespace strategy { namespace covered_by { namespace services
 294 {
 295
 296 template <typename PointLike, typename Geometry, typename AnyTag1, typename AnyTag2>
 297 struct default_strategy<PointLike, Geometry, AnyTag1, AnyTag2, pointlike_tag, polygonal_tag, cartesian_tag, cartesian_tag>
 298 {
 299     typedef within::cartesian_winding<> type;
 300 };
 301
 302 template <typename PointLike, typename Geometry, typename AnyTag1, typename AnyTag2>
 303 struct default_strategy<PointLike, Geometry, AnyTag1, AnyTag2, pointlike_tag, linear_tag, cartesian_tag, cartesian_tag>
 304 {
 305     typedef within::cartesian_winding<> type;
 306 };
 307
 308 }}} // namespace strategy::covered_by::services
 309 #endif
 310
 311
 312 }} // namespace boost::geometry
 313
 314
 315 #endif // BOOST_GEOMETRY_STRATEGY_CARTESIAN_POINT_IN_POLY_WINDING_HPP