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