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_FRANKLIN_HPP 20 #define BOOST_GEOMETRY_STRATEGIES_CARTESIAN_POINT_IN_POLY_FRANKLIN_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 \author adapted from Randolph Franklin algorithm 41 \author Barend and Maarten, 1995 42 \author Revised for templatized library, Barend Gehrels, 2007 43 \return true if point is in ring, works for closed rings in both directions 44 \note Does NOT work correctly for point ON border 45 46 \qbk{ 47 [heading See also] 48 [link geometry.reference.algorithms.within.within_3_with_strategy within (with strategy)] 49 } 50 */ 51 52 template 53 < 54 typename Point_, // for backward compatibility 55 typename PointOfSegment_ = Point_, // for backward compatibility 56 typename CalculationType = void 57 > 58 class franklin 59 { 60 template <typename Point, typename PointOfSegment> 61 struct calculation_type 62 : select_calculation_type 63 < 64 Point, 65 PointOfSegment, 66 CalculationType 67 > 68 {}; 69 70 /*! subclass to keep state */ 71 class crossings 72 { 73 bool crosses; 74 75 public : 76 77 friend class franklin; crossings()78 inline crossings() 79 : crosses(false) 80 {} 81 }; 82 83 public : 84 85 typedef crossings state_type; 86 87 template <typename Point, typename PointOfSegment> apply(Point const & point,PointOfSegment const & seg1,PointOfSegment const & seg2,crossings & state)88 static inline bool apply(Point const& point, 89 PointOfSegment const& seg1, PointOfSegment const& seg2, 90 crossings& state) 91 { 92 typedef typename calculation_type<Point, PointOfSegment>::type calc_t; 93 94 calc_t const& px = get<0>(point); 95 calc_t const& py = get<1>(point); 96 calc_t const& x1 = get<0>(seg1); 97 calc_t const& y1 = get<1>(seg1); 98 calc_t const& x2 = get<0>(seg2); 99 calc_t const& y2 = get<1>(seg2); 100 101 if ( 102 ( (y2 <= py && py < y1) || (y1 <= py && py < y2) ) 103 && (px < (x1 - x2) * (py - y2) / (y1 - y2) + x2) 104 ) 105 { 106 state.crosses = ! state.crosses; 107 } 108 return true; 109 } 110 result(crossings const & state)111 static inline int result(crossings const& state) 112 { 113 return state.crosses ? 1 : -1; 114 } 115 }; 116 117 118 119 }} // namespace strategy::within 120 121 122 123 124 125 }} // namespace boost::geometry 126 127 128 #endif // BOOST_GEOMETRY_STRATEGIES_CARTESIAN_POINT_IN_POLY_FRANKLIN_HPP 129