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_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_, // for backward compatibility 51 typename PointOfSegment_ = Point_, // for backward compatibility 52 typename CalculationType = void 53 > 54 class crossings_multiply 55 { 56 template <typename Point, typename PointOfSegment> 57 struct calculation_type 58 : select_calculation_type 59 < 60 Point, 61 PointOfSegment, 62 CalculationType 63 > 64 {}; 65 66 class flags 67 { 68 bool inside_flag; 69 bool first; 70 bool yflag0; 71 72 public : 73 74 friend class crossings_multiply; 75 flags()76 inline flags() 77 : inside_flag(false) 78 , first(true) 79 , yflag0(false) 80 {} 81 }; 82 83 public : 84 85 typedef flags state_type; 86 87 template <typename Point, typename PointOfSegment> apply(Point const & point,PointOfSegment const & seg1,PointOfSegment const & seg2,flags & state)88 static inline bool apply(Point const& point, 89 PointOfSegment const& seg1, PointOfSegment const& seg2, 90 flags& state) 91 { 92 typedef typename calculation_type<Point, PointOfSegment>::type calc_t; 93 94 calc_t const tx = get<0>(point); 95 calc_t const ty = get<1>(point); 96 calc_t const x0 = get<0>(seg1); 97 calc_t const y0 = get<1>(seg1); 98 calc_t const x1 = get<0>(seg2); 99 calc_t const y1 = get<1>(seg2); 100 101 if (state.first) 102 { 103 state.first = false; 104 state.yflag0 = y0 >= ty; 105 } 106 107 108 bool yflag1 = y1 >= ty; 109 if (state.yflag0 != yflag1) 110 { 111 if ( ((y1-ty) * (x0-x1) >= (x1-tx) * (y0-y1)) == yflag1 ) 112 { 113 state.inside_flag = ! state.inside_flag; 114 } 115 } 116 state.yflag0 = yflag1; 117 return true; 118 } 119 result(flags const & state)120 static inline int result(flags const& state) 121 { 122 return state.inside_flag ? 1 : -1; 123 } 124 }; 125 126 127 128 }} // namespace strategy::within 129 130 131 }} // namespace boost::geometry 132 133 134 #endif // BOOST_GEOMETRY_STRATEGIES_CARTESIAN_POINT_IN_POLY_CROSSINGS_MULTIPLY_HPP 135