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