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.
8 // Modifications copyright (c) 2018, 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,
51     typename PointOfSegment = Point,
52     typename CalculationType = void
53 >
54 class crossings_multiply
55 {
56     typedef typename select_calculation_type
57         <
58             Point,
59             PointOfSegment,
60             CalculationType
61         >::type calculation_type;
62 
63     class flags
64     {
65         bool inside_flag;
66         bool first;
67         bool yflag0;
68 
69     public :
70 
71         friend class crossings_multiply;
72 
flags()73         inline flags()
74             : inside_flag(false)
75             , first(true)
76             , yflag0(false)
77         {}
78     };
79 
80 public :
81 
82     typedef Point point_type;
83     typedef PointOfSegment segment_point_type;
84     typedef flags state_type;
85 
apply(Point const & point,PointOfSegment const & seg1,PointOfSegment const & seg2,flags & state)86     static inline bool apply(Point const& point,
87             PointOfSegment const& seg1, PointOfSegment const& seg2,
88             flags& state)
89     {
90         calculation_type const tx = get<0>(point);
91         calculation_type const ty = get<1>(point);
92         calculation_type const x0 = get<0>(seg1);
93         calculation_type const y0 = get<1>(seg1);
94         calculation_type const x1 = get<0>(seg2);
95         calculation_type const y1 = get<1>(seg2);
96 
97         if (state.first)
98         {
99             state.first = false;
100             state.yflag0 = y0 >= ty;
101         }
102 
103 
104         bool yflag1 = y1 >= ty;
105         if (state.yflag0 != yflag1)
106         {
107             if ( ((y1-ty) * (x0-x1) >= (x1-tx) * (y0-y1)) == yflag1 )
108             {
109                 state.inside_flag = ! state.inside_flag;
110             }
111         }
112         state.yflag0 = yflag1;
113         return true;
114     }
115 
result(flags const & state)116     static inline int result(flags const& state)
117     {
118         return state.inside_flag ? 1 : -1;
119     }
120 };
121 
122 
123 
124 }} // namespace strategy::within
125 
126 
127 }} // namespace boost::geometry
128 
129 
130 #endif // BOOST_GEOMETRY_STRATEGIES_CARTESIAN_POINT_IN_POLY_CROSSINGS_MULTIPLY_HPP
131