strategies/cartesian/point_in_poly_crossings_multiply.hpp

0001 // Boost.Geometry (aka GGL, Generic Geometry Library)
0002
0003 // Copyright (c) 2007-2012 Barend Gehrels, Amsterdam, the Netherlands.
0004 // Copyright (c) 2008-2012 Bruno Lalande, Paris, France.
0005 // Copyright (c) 2009-2012 Mateusz Loskot, London, UK.
0006
0007 // This file was modified by Oracle on 2018, 2019.
0008 // Modifications copyright (c) 2018, 2019, Oracle and/or its affiliates.
0009
0010 // Contributed and/or modified by Adam Wulkiewicz, on behalf of Oracle
0011
0012 // Parts of Boost.Geometry are redesigned from Geodan's Geographic Library
0013 // (geolib/GGL), copyright (c) 1995-2010 Geodan, Amsterdam, the Netherlands.
0014
0015 // Use, modification and distribution is subject to the Boost Software License,
0016 // Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
0017 // http://www.boost.org/LICENSE_1_0.txt)
0018
0019 #ifndef BOOST_GEOMETRY_STRATEGIES_CARTESIAN_POINT_IN_POLY_CROSSINGS_MULTIPLY_HPP
0020 #define BOOST_GEOMETRY_STRATEGIES_CARTESIAN_POINT_IN_POLY_CROSSINGS_MULTIPLY_HPP
0021
0022
0023 #include <boost/geometry/core/access.hpp>
0024 #include <boost/geometry/core/coordinate_type.hpp>
0025 #include <boost/geometry/util/select_calculation_type.hpp>
0026
0027
0028 namespace boost { namespace geometry
0029 {
0030
0031 namespace strategy { namespace within
0032 {
0033
0034 /*!
0035 \brief Within detection using cross counting,
0036 \ingroup strategies
0037 \tparam CalculationType \tparam_calculation
0038 \see http://tog.acm.org/resources/GraphicsGems/gemsiv/ptpoly_haines/ptinpoly.c
0039 \note Does NOT work correctly for point ON border
0040 \qbk{
0041 [heading See also]
0042 [link geometry.reference.algorithms.within.within_3_with_strategy within (with strategy)]
0043 }
0044  */
0045
0046 template
0047 <
0048     typename Point_,                   // for backward compatibility
0049     typename PointOfSegment_ = Point_, // for backward compatibility
0050     typename CalculationType = void
0051 >
0052 class crossings_multiply
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     class flags
0065     {
0066         bool inside_flag;
0067         bool first;
0068         bool yflag0;
0069
0070     public :
0071
0072         friend class crossings_multiply;
0073
0074         inline flags()
0075             : inside_flag(false)
0076             , first(true)
0077             , yflag0(false)
0078         {}
0079     };
0080
0081 public :
0082
0083     typedef flags state_type;
0084
0085     template <typename Point, typename PointOfSegment>
0086     static inline bool apply(Point const& point,
0087             PointOfSegment const& seg1, PointOfSegment const& seg2,
0088             flags& state)
0089     {
0090         typedef typename calculation_type<Point, PointOfSegment>::type calc_t;
0091
0092         calc_t const tx = get<0>(point);
0093         calc_t const ty = get<1>(point);
0094         calc_t const x0 = get<0>(seg1);
0095         calc_t const y0 = get<1>(seg1);
0096         calc_t const x1 = get<0>(seg2);
0097         calc_t const y1 = get<1>(seg2);
0098
0099         if (state.first)
0100         {
0101             state.first = false;
0102             state.yflag0 = y0 >= ty;
0103         }
0104
0105
0106         bool yflag1 = y1 >= ty;
0107         if (state.yflag0 != yflag1)
0108         {
0109             if ( ((y1-ty) * (x0-x1) >= (x1-tx) * (y0-y1)) == yflag1 )
0110             {
0111                 state.inside_flag = ! state.inside_flag;
0112             }
0113         }
0114         state.yflag0 = yflag1;
0115         return true;
0116     }
0117
0118     static inline int result(flags const& state)
0119     {
0120         return state.inside_flag ? 1 : -1;
0121     }
0122 };
0123
0124
0125
0126 }} // namespace strategy::within
0127
0128
0129 }} // namespace boost::geometry
0130
0131
0132 #endif // BOOST_GEOMETRY_STRATEGIES_CARTESIAN_POINT_IN_POLY_CROSSINGS_MULTIPLY_HPP