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 Point \tparam_point
0038 \tparam PointOfSegment \tparam_segment_point
0039 \tparam CalculationType \tparam_calculation
0040 \see http://tog.acm.org/resources/GraphicsGems/gemsiv/ptpoly_haines/ptinpoly.c
0041 \note Does NOT work correctly for point ON border
0042 \qbk{
0043 [heading See also]
0044 [link geometry.reference.algorithms.within.within_3_with_strategy within (with strategy)]
0045 }
0046  */
0047
0048 template
0049 <
0050     typename Point_,                   // for backward compatibility
0051     typename PointOfSegment_ = Point_, // for backward compatibility
0052     typename CalculationType = void
0053 >
0054 class crossings_multiply
0055 {
0056     template <typename Point, typename PointOfSegment>
0057     struct calculation_type
0058         : select_calculation_type
0059             <
0060                 Point,
0061                 PointOfSegment,
0062                 CalculationType
0063             >
0064     {};
0065
0066     class flags
0067     {
0068         bool inside_flag;
0069         bool first;
0070         bool yflag0;
0071
0072     public :
0073
0074         friend class crossings_multiply;
0075
0076         inline flags()
0077             : inside_flag(false)
0078             , first(true)
0079             , yflag0(false)
0080         {}
0081     };
0082
0083 public :
0084
0085     typedef flags state_type;
0086
0087     template <typename Point, typename PointOfSegment>
0088     static inline bool apply(Point const& point,
0089             PointOfSegment const& seg1, PointOfSegment const& seg2,
0090             flags& state)
0091     {
0092         typedef typename calculation_type<Point, PointOfSegment>::type calc_t;
0093
0094         calc_t const tx = get<0>(point);
0095         calc_t const ty = get<1>(point);
0096         calc_t const x0 = get<0>(seg1);
0097         calc_t const y0 = get<1>(seg1);
0098         calc_t const x1 = get<0>(seg2);
0099         calc_t const y1 = get<1>(seg2);
0100
0101         if (state.first)
0102         {
0103             state.first = false;
0104             state.yflag0 = y0 >= ty;
0105         }
0106
0107
0108         bool yflag1 = y1 >= ty;
0109         if (state.yflag0 != yflag1)
0110         {
0111             if ( ((y1-ty) * (x0-x1) >= (x1-tx) * (y0-y1)) == yflag1 )
0112             {
0113                 state.inside_flag = ! state.inside_flag;
0114             }
0115         }
0116         state.yflag0 = yflag1;
0117         return true;
0118     }
0119
0120     static inline int result(flags const& state)
0121     {
0122         return state.inside_flag ? 1 : -1;
0123     }
0124 };
0125
0126
0127
0128 }} // namespace strategy::within
0129
0130
0131 }} // namespace boost::geometry
0132
0133
0134 #endif // BOOST_GEOMETRY_STRATEGIES_CARTESIAN_POINT_IN_POLY_CROSSINGS_MULTIPLY_HPP