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_FRANKLIN_HPP
15 #define BOOST_GEOMETRY_STRATEGIES_CARTESIAN_POINT_IN_POLY_FRANKLIN_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 \author adapted from Randolph Franklin algorithm
35 \author Barend and Maarten, 1995
36 \author Revised for templatized library, Barend Gehrels, 2007
37 \return true if point is in ring, works for closed rings in both directions
38 \note Does NOT work correctly for point ON border
42 [link geometry.reference.algorithms.within.within_3_with_strategy within (with strategy)]
49 typename PointOfSegment = Point,
50 typename CalculationType = void
54 typedef typename select_calculation_type
59 >::type calculation_type;
61 /*! subclass to keep state */
68 friend class franklin;
76 typedef Point point_type;
77 typedef PointOfSegment segment_point_type;
78 typedef crossings state_type;
80 static inline bool apply(Point const& point,
81 PointOfSegment const& seg1, PointOfSegment const& seg2,
84 calculation_type const& px = get<0>(point);
85 calculation_type const& py = get<1>(point);
86 calculation_type const& x1 = get<0>(seg1);
87 calculation_type const& y1 = get<1>(seg1);
88 calculation_type const& x2 = get<0>(seg2);
89 calculation_type const& y2 = get<1>(seg2);
92 ( (y2 <= py && py < y1) || (y1 <= py && py < y2) )
93 && (px < (x1 - x2) * (py - y2) / (y1 - y2) + x2)
96 state.crosses = ! state.crosses;
101 static inline int result(crossings const& state)
103 return state.crosses ? 1 : -1;
109 }} // namespace strategy::within
115 }} // namespace boost::geometry
118 #endif // BOOST_GEOMETRY_STRATEGIES_CARTESIAN_POINT_IN_POLY_FRANKLIN_HPP