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. 8 // Modifications copyright (c) 2018, 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_CROSSINGS_MULTIPLY_HPP 20 #define BOOST_GEOMETRY_STRATEGIES_CARTESIAN_POINT_IN_POLY_CROSSINGS_MULTIPLY_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 \see http://tog.acm.org/resources/GraphicsGems/gemsiv/ptpoly_haines/ptinpoly.c 41 \note Does NOT work correctly for point ON border 42 \qbk{ 43 [heading See also] 44 [link geometry.reference.algorithms.within.within_3_with_strategy within (with strategy)] 45 } 46 */ 47 48 template 49 < 50 typename Point, 51 typename PointOfSegment = Point, 52 typename CalculationType = void 53 > 54 class crossings_multiply 55 { 56 typedef typename select_calculation_type 57 < 58 Point, 59 PointOfSegment, 60 CalculationType 61 >::type calculation_type; 62 63 class flags 64 { 65 bool inside_flag; 66 bool first; 67 bool yflag0; 68 69 public : 70 71 friend class crossings_multiply; 72 flags()73 inline flags() 74 : inside_flag(false) 75 , first(true) 76 , yflag0(false) 77 {} 78 }; 79 80 public : 81 82 typedef Point point_type; 83 typedef PointOfSegment segment_point_type; 84 typedef flags state_type; 85 apply(Point const & point,PointOfSegment const & seg1,PointOfSegment const & seg2,flags & state)86 static inline bool apply(Point const& point, 87 PointOfSegment const& seg1, PointOfSegment const& seg2, 88 flags& state) 89 { 90 calculation_type const tx = get<0>(point); 91 calculation_type const ty = get<1>(point); 92 calculation_type const x0 = get<0>(seg1); 93 calculation_type const y0 = get<1>(seg1); 94 calculation_type const x1 = get<0>(seg2); 95 calculation_type const y1 = get<1>(seg2); 96 97 if (state.first) 98 { 99 state.first = false; 100 state.yflag0 = y0 >= ty; 101 } 102 103 104 bool yflag1 = y1 >= ty; 105 if (state.yflag0 != yflag1) 106 { 107 if ( ((y1-ty) * (x0-x1) >= (x1-tx) * (y0-y1)) == yflag1 ) 108 { 109 state.inside_flag = ! state.inside_flag; 110 } 111 } 112 state.yflag0 = yflag1; 113 return true; 114 } 115 result(flags const & state)116 static inline int result(flags const& state) 117 { 118 return state.inside_flag ? 1 : -1; 119 } 120 }; 121 122 123 124 }} // namespace strategy::within 125 126 127 }} // namespace boost::geometry 128 129 130 #endif // BOOST_GEOMETRY_STRATEGIES_CARTESIAN_POINT_IN_POLY_CROSSINGS_MULTIPLY_HPP 131