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 CalculationType \tparam_calculation
0038 \author adapted from Randolph Franklin algorithm
0039 \author Barend and Maarten, 1995
0040 \author Revised for templatized library, Barend Gehrels, 2007
0041 \return true if point is in ring, works for closed rings in both directions
0042 \note Does NOT work correctly for point ON border
0043
0044 \qbk{
0045 [heading See also]
0046 [link geometry.reference.algorithms.within.within_3_with_strategy within (with strategy)]
0047 }
0048  */
0049
0050 template
0051 <
0052     typename Point_,                   // for backward compatibility
0053     typename PointOfSegment_ = Point_, // for backward compatibility
0054     typename CalculationType = void
0055 >
0056 class franklin
0057 {
0058     template <typename Point, typename PointOfSegment>
0059     struct calculation_type
0060         : select_calculation_type
0061             <
0062                 Point,
0063                 PointOfSegment,
0064                 CalculationType
0065             >
0066     {};
0067
0068     /*! subclass to keep state */
0069     class crossings
0070     {
0071         bool crosses;
0072
0073     public :
0074
0075         friend class franklin;
0076         inline crossings()
0077             : crosses(false)
0078         {}
0079     };
0080
0081 public :
0082
0083     typedef crossings state_type;
0084
0085     template <typename Point, typename PointOfSegment>
0086     static inline bool apply(Point const& point,
0087             PointOfSegment const& seg1, PointOfSegment const& seg2,
0088             crossings& state)
0089     {
0090         typedef typename calculation_type<Point, PointOfSegment>::type calc_t;
0091
0092         calc_t const& px = get<0>(point);
0093         calc_t const& py = get<1>(point);
0094         calc_t const& x1 = get<0>(seg1);
0095         calc_t const& y1 = get<1>(seg1);
0096         calc_t const& x2 = get<0>(seg2);
0097         calc_t const& y2 = get<1>(seg2);
0098
0099         if (
0100             ( (y2 <= py && py < y1) || (y1 <= py && py < y2) )
0101             && (px < (x1 - x2) * (py - y2) / (y1 - y2) + x2)
0102             )
0103         {
0104             state.crosses = ! state.crosses;
0105         }
0106         return true;
0107     }
0108
0109     static inline int result(crossings const& state)
0110     {
0111         return state.crosses ? 1 : -1;
0112     }
0113 };
0114
0115
0116
0117 }} // namespace strategy::within
0118
0119
0120
0121
0122
0123 }} // namespace boost::geometry
0124
0125
0126 #endif // BOOST_GEOMETRY_STRATEGIES_CARTESIAN_POINT_IN_POLY_FRANKLIN_HPP