strategies/agnostic/point_in_poly_oriented_winding.hpp

0001 // Boost.Geometry (aka GGL, Generic Geometry Library)
0002
0003 // Copyright (c) 2011-2012 Barend Gehrels, Amsterdam, the Netherlands.
0004
0005 // Copyright (c) 2023, Oracle and/or its affiliates.
0006
0007 // Contributed and/or modified by Vissarion Fysikopoulos, on behalf of Oracle
0008
0009 // Parts of Boost.Geometry are redesigned from Geodan's Geographic Library
0010 // (geolib/GGL), copyright (c) 1995-2010 Geodan, Amsterdam, the Netherlands.
0011
0012 // Use, modification and distribution is subject to the Boost Software License,
0013 // Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
0014 // http://www.boost.org/LICENSE_1_0.txt)
0015
0016 #ifndef BOOST_GEOMETRY_STRATEGY_AGNOSTIC_POINT_IN_POLY_ORIENTED_WINDING_HPP
0017 #define BOOST_GEOMETRY_STRATEGY_AGNOSTIC_POINT_IN_POLY_ORIENTED_WINDING_HPP
0018
0019
0020 #include <boost/geometry/core/access.hpp>
0021 #include <boost/geometry/core/point_order.hpp>
0022 #include <boost/geometry/util/math.hpp>
0023 #include <boost/geometry/util/select_calculation_type.hpp>
0024
0025 #include <boost/geometry/strategies/side.hpp>
0026 #include <boost/geometry/strategies/within.hpp>
0027
0028
0029 namespace boost { namespace geometry
0030 {
0031
0032 namespace strategy { namespace within
0033 {
0034
0035 /*!
0036 \brief Within detection using winding rule, but checking if enclosing ring is
0037     counter clockwise and, if so, reverses the result
0038 \ingroup strategies
0039 \tparam Point \tparam_point
0040 \tparam Reverse True if parameter should be reversed
0041 \tparam PointOfSegment \tparam_segment_point
0042 \tparam CalculationType \tparam_calculation
0043 \author Barend Gehrels
0044 \note Only dependant on "side", -> agnostic, suitable for spherical/latlong
0045
0046 \qbk{
0047 [heading See also]
0048 [link geometry.reference.algorithms.within.within_3_with_strategy within (with strategy)]
0049 }
0050  */
0051 template
0052 <
0053     bool Reverse,
0054     typename Point,
0055     typename PointOfSegment = Point,
0056     typename CalculationType = void
0057 >
0058 class oriented_winding
0059 {
0060     typedef typename select_calculation_type
0061         <
0062             Point,
0063             PointOfSegment,
0064             CalculationType
0065         >::type calculation_type;
0066
0067
0068     typedef typename strategy::side::services::default_strategy
0069         <
0070             typename cs_tag<Point>::type
0071         >::type strategy_side_type;
0072
0073
0074     /*! subclass to keep state */
0075     class counter
0076     {
0077         int m_count;
0078         bool m_touches;
0079         calculation_type m_sum_area;
0080
0081         inline int code() const
0082         {
0083             return m_touches ? 0 : m_count == 0 ? -1 : 1;
0084         }
0085         inline int clockwise_oriented_code() const
0086         {
0087             return (m_sum_area > 0) ? code() : -code();
0088         }
0089         inline int oriented_code() const
0090         {
0091             return Reverse
0092                 ? -clockwise_oriented_code()
0093                 : clockwise_oriented_code();
0094         }
0095
0096     public :
0097         friend class oriented_winding;
0098
0099         inline counter()
0100             : m_count(0)
0101             , m_touches(false)
0102             , m_sum_area(0)
0103         {}
0104
0105         inline void add_to_area(calculation_type triangle)
0106         {
0107             m_sum_area += triangle;
0108         }
0109
0110     };
0111
0112
0113     template <size_t D>
0114     static inline int check_touch(Point const& point,
0115                 PointOfSegment const& seg1, PointOfSegment const& seg2,
0116                 counter& state)
0117     {
0118         calculation_type const p = get<D>(point);
0119         calculation_type const s1 = get<D>(seg1);
0120         calculation_type const s2 = get<D>(seg2);
0121         if ((s1 <= p && s2 >= p) || (s2 <= p && s1 >= p))
0122         {
0123             state.m_touches = true;
0124         }
0125         return 0;
0126     }
0127
0128
0129     template <size_t D>
0130     static inline int check_segment(Point const& point,
0131                 PointOfSegment const& seg1, PointOfSegment const& seg2,
0132                 counter& state)
0133     {
0134         calculation_type const p = get<D>(point);
0135         calculation_type const s1 = get<D>(seg1);
0136         calculation_type const s2 = get<D>(seg2);
0137
0138
0139         // Check if one of segment endpoints is at same level of point
0140         bool eq1 = math::equals(s1, p);
0141         bool eq2 = math::equals(s2, p);
0142
0143         if (eq1 && eq2)
0144         {
0145             // Both equal p -> segment is horizontal (or vertical for D=0)
0146             // The only thing which has to be done is check if point is ON segment
0147             return check_touch<1 - D>(point, seg1, seg2, state);
0148         }
0149
0150         return
0151               eq1 ? (s2 > p ?  1 : -1)  // Point on level s1, UP/DOWN depending on s2
0152             : eq2 ? (s1 > p ? -1 :  1)  // idem
0153             : s1 < p && s2 > p ?  2     // Point between s1 -> s2 --> UP
0154             : s2 < p && s1 > p ? -2     // Point between s2 -> s1 --> DOWN
0155             : 0;
0156     }
0157
0158
0159
0160
0161 public :
0162
0163     // Typedefs and static methods to fulfill the concept
0164     typedef Point point_type;
0165     typedef PointOfSegment segment_point_type;
0166     typedef counter state_type;
0167
0168     static inline bool apply(Point const& point,
0169                 PointOfSegment const& s1, PointOfSegment const& s2,
0170                 counter& state)
0171     {
0172         state.add_to_area(get<0>(s2) * get<1>(s1) - get<0>(s1) * get<1>(s2));
0173
0174         int count = check_segment<1>(point, s1, s2, state);
0175         if (count != 0)
0176         {
0177             int side = strategy_side_type::apply(s1, s2, point);
0178             if (side == 0)
0179             {
0180                 // Point is lying on segment
0181                 state.m_touches = true;
0182                 state.m_count = 0;
0183                 return false;
0184             }
0185
0186             // Side is NEG for right, POS for left.
0187             // The count is -2 for down, 2 for up (or -1/1)
0188             // Side positive thus means UP and LEFTSIDE or DOWN and RIGHTSIDE
0189             // See accompagnying figure (TODO)
0190             if (side * count > 0)
0191             {
0192                 state.m_count += count;
0193             }
0194         }
0195         return ! state.m_touches;
0196     }
0197
0198     static inline int result(counter const& state)
0199     {
0200         return state.oriented_code();
0201     }
0202 };
0203
0204
0205 }} // namespace strategy::within
0206
0207
0208 }} // namespace boost::geometry
0209
0210
0211 #endif // BOOST_GEOMETRY_STRATEGY_AGNOSTIC_POINT_IN_POLY_ORIENTED_WINDING_HPP