strategies/cartesian/point_in_poly_winding.hpp

0001 // Boost.Geometry (aka GGL, Generic Geometry Library)
0002
0003 // Copyright (c) 2007-2012 Barend Gehrels, Amsterdam, the Netherlands.
0004 // Copyright (c) 2013 Adam Wulkiewicz, Lodz, Poland.
0005
0006 // This file was modified by Oracle on 2013-2021.
0007 // Modifications copyright (c) 2013-2021 Oracle and/or its affiliates.
0008 // Contributed and/or modified by Adam Wulkiewicz, on behalf of Oracle
0009
0010 // Parts of Boost.Geometry are redesigned from Geodan's Geographic Library
0011 // (geolib/GGL), copyright (c) 1995-2010 Geodan, Amsterdam, the Netherlands.
0012
0013 // Use, modification and distribution is subject to the Boost Software License,
0014 // Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
0015 // http://www.boost.org/LICENSE_1_0.txt)
0016
0017 #ifndef BOOST_GEOMETRY_STRATEGY_CARTESIAN_POINT_IN_POLY_WINDING_HPP
0018 #define BOOST_GEOMETRY_STRATEGY_CARTESIAN_POINT_IN_POLY_WINDING_HPP
0019
0020
0021 #include <boost/geometry/core/tags.hpp>
0022
0023 #include <boost/geometry/util/math.hpp>
0024 #include <boost/geometry/util/select_calculation_type.hpp>
0025
0026 #include <boost/geometry/strategy/cartesian/expand_point.hpp>
0027 #include <boost/geometry/strategies/side.hpp>
0028
0029 #include <boost/geometry/strategies/cartesian/point_in_box.hpp>
0030 #include <boost/geometry/strategies/cartesian/disjoint_box_box.hpp>
0031 #include <boost/geometry/strategies/covered_by.hpp>
0032 #include <boost/geometry/strategies/within.hpp>
0033
0034
0035 namespace boost { namespace geometry
0036 {
0037
0038 namespace strategy { namespace within
0039 {
0040
0041 #ifndef DOXYGEN_NO_DETAIL
0042 namespace detail
0043 {
0044
0045 /*!
0046 \brief Within detection using winding rule in cartesian coordinate system.
0047 \ingroup strategies
0048 \tparam SideStrategy A strategy defining creation along sides
0049 \tparam CalculationType \tparam_calculation
0050  */
0051 template <typename SideStrategy, typename CalculationType>
0052 class cartesian_winding_base
0053 {
0054     template <typename Point, typename PointOfSegment>
0055     struct calculation_type
0056         : select_calculation_type
0057             <
0058                 Point,
0059                 PointOfSegment,
0060                 CalculationType
0061             >
0062     {};
0063
0064     /*! subclass to keep state */
0065     class counter
0066     {
0067         int m_count;
0068         bool m_touches;
0069
0070         inline int code() const
0071         {
0072             return m_touches ? 0 : m_count == 0 ? -1 : 1;
0073         }
0074
0075     public :
0076         friend class cartesian_winding_base;
0077
0078         inline counter()
0079             : m_count(0)
0080             , m_touches(false)
0081         {}
0082
0083     };
0084
0085 public:
0086     typedef cartesian_tag cs_tag;
0087
0088     // Typedefs and static methods to fulfill the concept
0089     typedef counter state_type;
0090
0091     template <typename Point, typename PointOfSegment>
0092     static inline bool apply(Point const& point,
0093                              PointOfSegment const& s1, PointOfSegment const& s2,
0094                              counter& state)
0095     {
0096         bool eq1 = false;
0097         bool eq2 = false;
0098
0099         int count = check_segment(point, s1, s2, state, eq1, eq2);
0100         if (count != 0)
0101         {
0102             int side = 0;
0103             if (count == 1 || count == -1)
0104             {
0105                 side = side_equal(point, eq1 ? s1 : s2, count);
0106             }
0107             else // count == 2 || count == -2
0108             {
0109                 // 1 left, -1 right
0110                 side = SideStrategy::apply(s1, s2, point);
0111             }
0112
0113             if (side == 0)
0114             {
0115                 // Point is lying on segment
0116                 state.m_touches = true;
0117                 state.m_count = 0;
0118                 return false;
0119             }
0120
0121             // Side is NEG for right, POS for left.
0122             // The count is -2 for left, 2 for right (or -1/1)
0123             // Side positive thus means RIGHT and LEFTSIDE or LEFT and RIGHTSIDE
0124             // See accompagnying figure (TODO)
0125             if (side * count > 0)
0126             {
0127                 state.m_count += count;
0128             }
0129         }
0130         return ! state.m_touches;
0131     }
0132
0133     static inline int result(counter const& state)
0134     {
0135         return state.code();
0136     }
0137
0138 private:
0139     template <typename Point, typename PointOfSegment>
0140     static inline int check_segment(Point const& point,
0141                                     PointOfSegment const& seg1,
0142                                     PointOfSegment const& seg2,
0143                                     counter& state,
0144                                     bool& eq1, bool& eq2)
0145     {
0146         if (check_touch(point, seg1, seg2, state, eq1, eq2))
0147         {
0148             return 0;
0149         }
0150
0151         return calculate_count(point, seg1, seg2, eq1, eq2);
0152     }
0153
0154     template <typename Point, typename PointOfSegment>
0155     static inline bool check_touch(Point const& point,
0156                                    PointOfSegment const& seg1,
0157                                    PointOfSegment const& seg2,
0158                                    counter& state,
0159                                    bool& eq1, bool& eq2)
0160     {
0161         typedef typename calculation_type<Point, PointOfSegment>::type calc_t;
0162
0163         calc_t const px = get<0>(point);
0164         calc_t const s1x = get<0>(seg1);
0165         calc_t const s2x = get<0>(seg2);
0166
0167         eq1 = math::equals(s1x, px);
0168         eq2 = math::equals(s2x, px);
0169
0170         // Both equal p -> segment vertical
0171         // The only thing which has to be done is check if point is ON segment
0172         if (eq1 && eq2)
0173         {
0174             calc_t const py = get<1>(point);
0175             calc_t const s1y = get<1>(seg1);
0176             calc_t const s2y = get<1>(seg2);
0177             if ((s1y <= py && s2y >= py) || (s2y <= py && s1y >= py))
0178             {
0179                 state.m_touches = true;
0180             }
0181             return true;
0182         }
0183         return false;
0184     }
0185
0186     template <typename Point, typename PointOfSegment>
0187     static inline int calculate_count(Point const& point,
0188                                       PointOfSegment const& seg1,
0189                                       PointOfSegment const& seg2,
0190                                       bool eq1, bool eq2)
0191     {
0192         typedef typename calculation_type<Point, PointOfSegment>::type calc_t;
0193
0194         calc_t const p = get<0>(point);
0195         calc_t const s1 = get<0>(seg1);
0196         calc_t const s2 = get<0>(seg2);
0197
0198         return eq1 ? (s2 > p ?  1 : -1)  // Point on level s1, E/W depending on s2
0199              : eq2 ? (s1 > p ? -1 :  1)  // idem
0200              : s1 < p && s2 > p ?  2     // Point between s1 -> s2 --> E
0201              : s2 < p && s1 > p ? -2     // Point between s2 -> s1 --> W
0202              : 0;
0203     }
0204
0205     template <typename Point, typename PointOfSegment>
0206     static inline int side_equal(Point const& point,
0207                                  PointOfSegment const& se,
0208                                  int count)
0209     {
0210         // NOTE: for D=0 the signs would be reversed
0211         return math::equals(get<1>(point), get<1>(se)) ?
0212                 0 :
0213                 get<1>(point) < get<1>(se) ?
0214                     // assuming count is equal to 1 or -1
0215                     -count : // ( count > 0 ? -1 : 1) :
0216                     count;   // ( count > 0 ? 1 : -1) ;
0217     }
0218 };
0219
0220 } // namespace detail
0221 #endif // DOXYGEN_NO_DETAIL
0222
0223 /*!
0224 \brief Within detection using winding rule in cartesian coordinate system.
0225 \ingroup strategies
0226 \tparam Point_ \tparam_point
0227 \tparam PointOfSegment_ \tparam_segment_point
0228 \tparam CalculationType \tparam_calculation
0229
0230 \qbk{
0231 [heading See also]
0232 [link geometry.reference.algorithms.within.within_3_with_strategy within (with strategy)]
0233 }
0234  */
0235 template
0236 <
0237     typename Point_ = void, // for backward compatibility
0238     typename PointOfSegment_ = Point_, // for backward compatibility
0239     typename CalculationType = void
0240 >
0241 class cartesian_winding
0242     : public detail::cartesian_winding_base
0243         <
0244             typename side::services::default_strategy<cartesian_tag, CalculationType>::type,
0245             CalculationType
0246         >
0247 {};
0248
0249 #ifndef DOXYGEN_NO_STRATEGY_SPECIALIZATIONS
0250
0251 namespace services
0252 {
0253
0254 template <typename PointLike, typename Geometry, typename AnyTag1, typename AnyTag2>
0255 struct default_strategy<PointLike, Geometry, AnyTag1, AnyTag2, pointlike_tag, polygonal_tag, cartesian_tag, cartesian_tag>
0256 {
0257     using type = cartesian_winding<>;
0258 };
0259
0260 template <typename PointLike, typename Geometry, typename AnyTag1, typename AnyTag2>
0261 struct default_strategy<PointLike, Geometry, AnyTag1, AnyTag2, pointlike_tag, linear_tag, cartesian_tag, cartesian_tag>
0262 {
0263     using type = cartesian_winding<>;
0264 };
0265
0266 } // namespace services
0267
0268 #endif
0269
0270
0271 }} // namespace strategy::within
0272
0273
0274 #ifndef DOXYGEN_NO_STRATEGY_SPECIALIZATIONS
0275 namespace strategy { namespace covered_by { namespace services
0276 {
0277
0278 template <typename PointLike, typename Geometry, typename AnyTag1, typename AnyTag2>
0279 struct default_strategy<PointLike, Geometry, AnyTag1, AnyTag2, pointlike_tag, polygonal_tag, cartesian_tag, cartesian_tag>
0280 {
0281     using type = within::cartesian_winding<>;
0282 };
0283
0284 template <typename PointLike, typename Geometry, typename AnyTag1, typename AnyTag2>
0285 struct default_strategy<PointLike, Geometry, AnyTag1, AnyTag2, pointlike_tag, linear_tag, cartesian_tag, cartesian_tag>
0286 {
0287     using type = within::cartesian_winding<>;
0288 };
0289
0290 }}} // namespace strategy::covered_by::services
0291 #endif
0292
0293
0294 }} // namespace boost::geometry
0295
0296
0297 #endif // BOOST_GEOMETRY_STRATEGY_CARTESIAN_POINT_IN_POLY_WINDING_HPP