1 // Boost.Geometry (aka GGL, Generic Geometry Library)
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.
7 // Parts of Boost.Geometry are redesigned from Geodan's Geographic Library
8 // (geolib/GGL), copyright (c) 1995-2010 Geodan, Amsterdam, the Netherlands.
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)
14 #ifndef BOOST_GEOMETRY_STRATEGIES_CARTESIAN_POINT_IN_POLY_CROSSINGS_MULTIPLY_HPP
15 #define BOOST_GEOMETRY_STRATEGIES_CARTESIAN_POINT_IN_POLY_CROSSINGS_MULTIPLY_HPP
18 #include <boost/geometry/core/coordinate_type.hpp>
19 #include <boost/geometry/util/select_calculation_type.hpp>
22 namespace boost { namespace geometry
25 namespace strategy { namespace within
29 \brief Within detection using cross counting,
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
38 [link geometry.reference.algorithms.within.within_3_with_strategy within (with strategy)]
45 typename PointOfSegment = Point,
46 typename CalculationType = void
48 class crossings_multiply
50 typedef typename select_calculation_type
55 >::type calculation_type;
65 friend class crossings_multiply;
76 typedef Point point_type;
77 typedef PointOfSegment segment_point_type;
78 typedef flags state_type;
80 static inline bool apply(Point const& point,
81 PointOfSegment const& seg1, PointOfSegment const& seg2,
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);
94 state.yflag0 = y0 >= ty;
98 bool yflag1 = y1 >= ty;
99 if (state.yflag0 != yflag1)
101 if ( ((y1-ty) * (x0-x1) >= (x1-tx) * (y0-y1)) == yflag1 )
103 state.inside_flag = ! state.inside_flag;
106 state.yflag0 = yflag1;
110 static inline int result(flags const& state)
112 return state.inside_flag ? 1 : -1;
118 }} // namespace strategy::within
121 }} // namespace boost::geometry
124 #endif // BOOST_GEOMETRY_STRATEGIES_CARTESIAN_POINT_IN_POLY_CROSSINGS_MULTIPLY_HPP