strategies/cartesian/point_in_poly_franklin.hpp

0001 // Boost.Geometry (aka GGL, Generic Geometry Library)
0002
0003 // Copyright (c) 2007-2012 Barend Gehrels, Amsterdam, the Netherlands.
0004 // Copyright (c) 2008-2012 Bruno Lalande, Paris, France.
0005 // Copyright (c) 2009-2012 Mateusz Loskot, London, UK.
0006
0007 // This file was modified by Oracle on 2018, 2019.
0008 // Modifications copyright (c) 2018, 2019, Oracle and/or its affiliates.
0009
0010 // Contributed and/or modified by Adam Wulkiewicz, on behalf of Oracle
0011
0012 // Parts of Boost.Geometry are redesigned from Geodan's Geographic Library
0013 // (geolib/GGL), copyright (c) 1995-2010 Geodan, Amsterdam, the Netherlands.
0014
0015 // Use, modification and distribution is subject to the Boost Software License,
0016 // Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
0017 // http://www.boost.org/LICENSE_1_0.txt)
0018
0019 #ifndef BOOST_GEOMETRY_STRATEGIES_CARTESIAN_POINT_IN_POLY_FRANKLIN_HPP
0020 #define BOOST_GEOMETRY_STRATEGIES_CARTESIAN_POINT_IN_POLY_FRANKLIN_HPP
0021
0022
0023 #include <boost/geometry/core/access.hpp>
0024 #include <boost/geometry/core/coordinate_type.hpp>
0025 #include <boost/geometry/util/select_calculation_type.hpp>
0026
0027
0028 namespace boost { namespace geometry
0029 {
0030
0031 namespace strategy { namespace within
0032 {
0033
0034 /*!
0035 \brief Within detection using cross counting
0036 \ingroup strategies
0037 \tparam Point \tparam_point
0038 \tparam PointOfSegment \tparam_segment_point
0039 \tparam CalculationType \tparam_calculation
0040 \author adapted from Randolph Franklin algorithm
0041 \author Barend and Maarten, 1995
0042 \author Revised for templatized library, Barend Gehrels, 2007
0043 \return true if point is in ring, works for closed rings in both directions
0044 \note Does NOT work correctly for point ON border
0045
0046 \qbk{
0047 [heading See also]
0048 [link geometry.reference.algorithms.within.within_3_with_strategy within (with strategy)]
0049 }
0050  */
0051
0052 template
0053 <
0054     typename Point_,                   // for backward compatibility
0055     typename PointOfSegment_ = Point_, // for backward compatibility
0056     typename CalculationType = void
0057 >
0058 class franklin
0059 {
0060     template <typename Point, typename PointOfSegment>
0061     struct calculation_type
0062         : select_calculation_type
0063             <
0064                 Point,
0065                 PointOfSegment,
0066                 CalculationType
0067             >
0068     {};
0069
0070     /*! subclass to keep state */
0071     class crossings
0072     {
0073         bool crosses;
0074
0075     public :
0076
0077         friend class franklin;
0078         inline crossings()
0079             : crosses(false)
0080         {}
0081     };
0082
0083 public :
0084
0085     typedef crossings state_type;
0086
0087     template <typename Point, typename PointOfSegment>
0088     static inline bool apply(Point const& point,
0089             PointOfSegment const& seg1, PointOfSegment const& seg2,
0090             crossings& state)
0091     {
0092         typedef typename calculation_type<Point, PointOfSegment>::type calc_t;
0093
0094         calc_t const& px = get<0>(point);
0095         calc_t const& py = get<1>(point);
0096         calc_t const& x1 = get<0>(seg1);
0097         calc_t const& y1 = get<1>(seg1);
0098         calc_t const& x2 = get<0>(seg2);
0099         calc_t const& y2 = get<1>(seg2);
0100
0101         if (
0102             ( (y2 <= py && py < y1) || (y1 <= py && py < y2) )
0103             && (px < (x1 - x2) * (py - y2) / (y1 - y2) + x2)
0104             )
0105         {
0106             state.crosses = ! state.crosses;
0107         }
0108         return true;
0109     }
0110
0111     static inline int result(crossings const& state)
0112     {
0113         return state.crosses ? 1 : -1;
0114     }
0115 };
0116
0117
0118
0119 }} // namespace strategy::within
0120
0121
0122
0123
0124
0125 }} // namespace boost::geometry
0126
0127
0128 #endif // BOOST_GEOMETRY_STRATEGIES_CARTESIAN_POINT_IN_POLY_FRANKLIN_HPP