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