1 // Boost.Geometry (aka GGL, Generic Geometry Library)
2 
3 // Copyright (c) 2007-2012 Barend Gehrels, Amsterdam, the Netherlands.
4 // Copyright (c) 2008-2012 Bruno Lalande, Paris, France.
5 // Copyright (c) 2009-2012 Mateusz Loskot, London, UK.
6 
7 // This file was modified by Oracle on 2018, 2019.
8 // Modifications copyright (c) 2018, 2019, Oracle and/or its affiliates.
9 
10 // Contributed and/or modified by Adam Wulkiewicz, on behalf of Oracle
11 
12 // Parts of Boost.Geometry are redesigned from Geodan's Geographic Library
13 // (geolib/GGL), copyright (c) 1995-2010 Geodan, Amsterdam, the Netherlands.
14 
15 // Use, modification and distribution is subject to the Boost Software License,
16 // Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
17 // http://www.boost.org/LICENSE_1_0.txt)
18 
19 #ifndef BOOST_GEOMETRY_STRATEGIES_CARTESIAN_POINT_IN_POLY_CROSSINGS_MULTIPLY_HPP
20 #define BOOST_GEOMETRY_STRATEGIES_CARTESIAN_POINT_IN_POLY_CROSSINGS_MULTIPLY_HPP
21 
22 
23 #include <boost/geometry/core/access.hpp>
24 #include <boost/geometry/core/coordinate_type.hpp>
25 #include <boost/geometry/util/select_calculation_type.hpp>
26 
27 
28 namespace boost { namespace geometry
29 {
30 
31 namespace strategy { namespace within
32 {
33 
34 /*!
35 \brief Within detection using cross counting,
36 \ingroup strategies
37 \tparam Point \tparam_point
38 \tparam PointOfSegment \tparam_segment_point
39 \tparam CalculationType \tparam_calculation
40 \see http://tog.acm.org/resources/GraphicsGems/gemsiv/ptpoly_haines/ptinpoly.c
41 \note Does NOT work correctly for point ON border
42 \qbk{
43 [heading See also]
44 [link geometry.reference.algorithms.within.within_3_with_strategy within (with strategy)]
45 }
46  */
47 
48 template
49 <
50     typename Point_,                   // for backward compatibility
51     typename PointOfSegment_ = Point_, // for backward compatibility
52     typename CalculationType = void
53 >
54 class crossings_multiply
55 {
56     template <typename Point, typename PointOfSegment>
57     struct calculation_type
58         : select_calculation_type
59             <
60                 Point,
61                 PointOfSegment,
62                 CalculationType
63             >
64     {};
65 
66     class flags
67     {
68         bool inside_flag;
69         bool first;
70         bool yflag0;
71 
72     public :
73 
74         friend class crossings_multiply;
75 
flags()76         inline flags()
77             : inside_flag(false)
78             , first(true)
79             , yflag0(false)
80         {}
81     };
82 
83 public :
84 
85     typedef flags state_type;
86 
87     template <typename Point, typename PointOfSegment>
apply(Point const & point,PointOfSegment const & seg1,PointOfSegment const & seg2,flags & state)88     static inline bool apply(Point const& point,
89             PointOfSegment const& seg1, PointOfSegment const& seg2,
90             flags& state)
91     {
92         typedef typename calculation_type<Point, PointOfSegment>::type calc_t;
93 
94         calc_t const tx = get<0>(point);
95         calc_t const ty = get<1>(point);
96         calc_t const x0 = get<0>(seg1);
97         calc_t const y0 = get<1>(seg1);
98         calc_t const x1 = get<0>(seg2);
99         calc_t const y1 = get<1>(seg2);
100 
101         if (state.first)
102         {
103             state.first = false;
104             state.yflag0 = y0 >= ty;
105         }
106 
107 
108         bool yflag1 = y1 >= ty;
109         if (state.yflag0 != yflag1)
110         {
111             if ( ((y1-ty) * (x0-x1) >= (x1-tx) * (y0-y1)) == yflag1 )
112             {
113                 state.inside_flag = ! state.inside_flag;
114             }
115         }
116         state.yflag0 = yflag1;
117         return true;
118     }
119 
result(flags const & state)120     static inline int result(flags const& state)
121     {
122         return state.inside_flag ? 1 : -1;
123     }
124 };
125 
126 
127 
128 }} // namespace strategy::within
129 
130 
131 }} // namespace boost::geometry
132 
133 
134 #endif // BOOST_GEOMETRY_STRATEGIES_CARTESIAN_POINT_IN_POLY_CROSSINGS_MULTIPLY_HPP
135