detail/within/point_in_geometry.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 // Copyright (c) 2014 Adam Wulkiewicz, Lodz, Poland.
0007
0008 // This file was modified by Oracle on 2013-2021.
0009 // Modifications copyright (c) 2013-2021, Oracle and/or its affiliates.
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_ALGORITHMS_DETAIL_WITHIN_POINT_IN_GEOMETRY_HPP
0020 #define BOOST_GEOMETRY_ALGORITHMS_DETAIL_WITHIN_POINT_IN_GEOMETRY_HPP
0021
0022
0023 #include <boost/core/ignore_unused.hpp>
0024 #include <boost/range/begin.hpp>
0025 #include <boost/range/end.hpp>
0026 #include <boost/range/size.hpp>
0027 #include <boost/range/value_type.hpp>
0028
0029 #include <boost/geometry/core/assert.hpp>
0030
0031 #include <boost/geometry/algorithms/detail/assign_indexed_point.hpp>
0032 #include <boost/geometry/algorithms/detail/equals/point_point.hpp>
0033
0034 #include <boost/geometry/geometries/concepts/check.hpp>
0035 #include <boost/geometry/strategies/concepts/within_concept.hpp>
0036
0037 #include <boost/geometry/util/range.hpp>
0038 #include <boost/geometry/views/detail/closed_clockwise_view.hpp>
0039
0040 namespace boost { namespace geometry {
0041
0042 #ifndef DOXYGEN_NO_DETAIL
0043 namespace detail { namespace within {
0044
0045
0046 template <typename Point, typename Range, typename Strategy> inline
0047 int point_in_range(Point const& point, Range const& range, Strategy const& strategy)
0048 {
0049     typename Strategy::state_type state;
0050
0051     auto it = boost::begin(range);
0052     auto const end = boost::end(range);
0053
0054     for (auto previous = it++; it != end; ++previous, ++it)
0055     {
0056         if (! strategy.apply(point, *previous, *it, state))
0057         {
0058             break;
0059         }
0060     }
0061
0062     return strategy.result(state);
0063 }
0064
0065 }} // namespace detail::within
0066
0067 namespace detail_dispatch { namespace within {
0068
0069 // checks the relation between a point P and geometry G
0070 // returns 1 if P is in the interior of G
0071 // returns 0 if P is on the boundry of G
0072 // returns -1 if P is in the exterior of G
0073
0074 template <typename Geometry,
0075           typename Tag = typename geometry::tag<Geometry>::type>
0076 struct point_in_geometry
0077     : not_implemented<Tag>
0078 {};
0079
0080 template <typename Point2>
0081 struct point_in_geometry<Point2, point_tag>
0082 {
0083     template <typename Point1, typename Strategy> static inline
0084     int apply(Point1 const& point1, Point2 const& point2, Strategy const& strategy)
0085     {
0086         typedef decltype(strategy.relate(point1, point2)) strategy_type;
0087         return strategy_type::apply(point1, point2) ? 1 : -1;
0088     }
0089 };
0090
0091 template <typename Segment>
0092 struct point_in_geometry<Segment, segment_tag>
0093 {
0094     template <typename Point, typename Strategy> static inline
0095     int apply(Point const& point, Segment const& segment, Strategy const& strategy)
0096     {
0097         typedef typename geometry::point_type<Segment>::type point_type;
0098         point_type p0, p1;
0099 // TODO: don't copy points
0100         detail::assign_point_from_index<0>(segment, p0);
0101         detail::assign_point_from_index<1>(segment, p1);
0102
0103         auto const s = strategy.relate(point, segment);
0104         typename decltype(s)::state_type state;
0105         s.apply(point, p0, p1, state);
0106         int r = s.result(state);
0107
0108         if ( r != 0 )
0109             return -1; // exterior
0110
0111         // if the point is equal to the one of the terminal points
0112         if ( detail::equals::equals_point_point(point, p0, strategy)
0113           || detail::equals::equals_point_point(point, p1, strategy) )
0114             return 0; // boundary
0115         else
0116             return 1; // interior
0117     }
0118 };
0119
0120
0121 template <typename Linestring>
0122 struct point_in_geometry<Linestring, linestring_tag>
0123 {
0124     template <typename Point, typename Strategy> static inline
0125     int apply(Point const& point, Linestring const& linestring, Strategy const& strategy)
0126     {
0127         std::size_t count = boost::size(linestring);
0128         if ( count > 1 )
0129         {
0130             if ( detail::within::point_in_range(point, linestring,
0131                                     strategy.relate(point, linestring)) != 0 )
0132             {
0133                 return -1; // exterior
0134             }
0135
0136             typedef typename boost::range_value<Linestring>::type point_type;
0137             point_type const& front = range::front(linestring);
0138             point_type const& back = range::back(linestring);
0139
0140             // if the linestring doesn't have a boundary
0141             if ( detail::equals::equals_point_point(front, back, strategy) )
0142             {
0143                 return 1; // interior
0144             }
0145             // else if the point is equal to the one of the terminal points
0146             else if ( detail::equals::equals_point_point(point, front, strategy)
0147                    || detail::equals::equals_point_point(point, back, strategy) )
0148             {
0149                 return 0; // boundary
0150             }
0151             else
0152             {
0153                 return 1; // interior
0154             }
0155         }
0156 // TODO: for now degenerated linestrings are ignored
0157 //       throw an exception here?
0158         /*else if ( count == 1 )
0159         {
0160             if ( detail::equals::equals_point_point(point, front, strategy) )
0161                 return 1;
0162         }*/
0163
0164         return -1; // exterior
0165     }
0166 };
0167
0168 template <typename Ring>
0169 struct point_in_geometry<Ring, ring_tag>
0170 {
0171     template <typename Point, typename Strategy> static inline
0172     int apply(Point const& point, Ring const& ring, Strategy const& strategy)
0173     {
0174         if ( boost::size(ring) < core_detail::closure::minimum_ring_size
0175                                     <
0176                                         geometry::closure<Ring>::value
0177                                     >::value )
0178         {
0179             return -1;
0180         }
0181
0182         detail::closed_clockwise_view<Ring const> view(ring);
0183         return detail::within::point_in_range(point, view,
0184                                               strategy.relate(point, ring));
0185     }
0186 };
0187
0188 // Polygon: in exterior ring, and if so, not within interior ring(s)
0189 template <typename Polygon>
0190 struct point_in_geometry<Polygon, polygon_tag>
0191 {
0192     template <typename Point, typename Strategy>
0193     static inline int apply(Point const& point, Polygon const& polygon,
0194                             Strategy const& strategy)
0195     {
0196         int const code = point_in_geometry
0197             <
0198                 typename ring_type<Polygon>::type
0199             >::apply(point, exterior_ring(polygon), strategy);
0200
0201         if (code == 1)
0202         {
0203             auto const& rings = interior_rings(polygon);
0204             for (auto it = boost::begin(rings); it != boost::end(rings); ++it)
0205             {
0206                 int const interior_code = point_in_geometry
0207                     <
0208                         typename ring_type<Polygon>::type
0209                     >::apply(point, *it, strategy);
0210
0211                 if (interior_code != -1)
0212                 {
0213                     // If 0, return 0 (touch)
0214                     // If 1 (inside hole) return -1 (outside polygon)
0215                     // If -1 (outside hole) check other holes if any
0216                     return -interior_code;
0217                 }
0218             }
0219         }
0220         return code;
0221     }
0222 };
0223
0224 template <typename Geometry>
0225 struct point_in_geometry<Geometry, multi_point_tag>
0226 {
0227     template <typename Point, typename Strategy> static inline
0228     int apply(Point const& point, Geometry const& geometry, Strategy const& strategy)
0229     {
0230         typedef typename boost::range_value<Geometry>::type point_type;
0231         for (auto it = boost::begin(geometry); it != boost::end(geometry); ++it)
0232         {
0233             int pip = point_in_geometry<point_type>::apply(point, *it, strategy);
0234
0235             //BOOST_GEOMETRY_ASSERT(pip != 0);
0236             if (pip > 0)
0237             {
0238                 // inside
0239                 return 1;
0240             }
0241         }
0242
0243         return -1; // outside
0244     }
0245 };
0246
0247 template <typename Geometry>
0248 struct point_in_geometry<Geometry, multi_linestring_tag>
0249 {
0250     template <typename Point, typename Strategy> static inline
0251     int apply(Point const& point, Geometry const& geometry, Strategy const& strategy)
0252     {
0253         int pip = -1; // outside
0254
0255         typedef typename boost::range_value<Geometry>::type linestring_type;
0256         typedef typename boost::range_value<linestring_type>::type point_type;
0257         auto it = boost::begin(geometry);
0258         for ( ; it != boost::end(geometry); ++it)
0259         {
0260             pip = point_in_geometry<linestring_type>::apply(point, *it, strategy);
0261
0262             // inside or on the boundary
0263             if (pip >= 0)
0264             {
0265                 ++it;
0266                 break;
0267             }
0268         }
0269
0270         // outside
0271         if (pip < 0)
0272         {
0273             return -1;
0274         }
0275
0276         // TODO: the following isn't needed for covered_by()
0277
0278         unsigned boundaries = pip == 0 ? 1 : 0;
0279
0280         for (; it != boost::end(geometry); ++it)
0281         {
0282             if (boost::size(*it) < 2)
0283             {
0284                 continue;
0285             }
0286
0287             point_type const& front = range::front(*it);
0288             point_type const& back = range::back(*it);
0289
0290             // is closed_ring - no boundary
0291             if (detail::equals::equals_point_point(front, back, strategy))
0292             {
0293                 continue;
0294             }
0295
0296             // is point on boundary
0297             if ( detail::equals::equals_point_point(point, front, strategy)
0298               || detail::equals::equals_point_point(point, back, strategy) )
0299             {
0300                 ++boundaries;
0301             }
0302         }
0303
0304         // if the number of boundaries is odd, the point is on the boundary
0305         return boundaries % 2 ? 0 : 1;
0306     }
0307 };
0308
0309 template <typename Geometry>
0310 struct point_in_geometry<Geometry, multi_polygon_tag>
0311 {
0312     template <typename Point, typename Strategy> static inline
0313     int apply(Point const& point, Geometry const& geometry, Strategy const& strategy)
0314     {
0315         // For invalid multipolygons
0316         //int res = -1; // outside
0317
0318         typedef typename boost::range_value<Geometry>::type polygon_type;
0319         for (auto it = boost::begin(geometry); it != boost::end(geometry); ++it)
0320         {
0321             int pip = point_in_geometry<polygon_type>::apply(point, *it, strategy);
0322
0323             // inside or on the boundary
0324             if (pip >= 0)
0325             {
0326                 return pip;
0327             }
0328
0329             // For invalid multi-polygons
0330             //if ( 1 == pip ) // inside polygon
0331             //    return 1;
0332             //else if ( res < pip ) // point must be inside at least one polygon
0333             //    res = pip;
0334         }
0335
0336         return -1; // for valid multipolygons
0337         //return res; // for invalid multipolygons
0338     }
0339 };
0340
0341 }} // namespace detail_dispatch::within
0342
0343 namespace detail { namespace within {
0344
0345 // 1 - in the interior
0346 // 0 - in the boundry
0347 // -1 - in the exterior
0348 template <typename Point, typename Geometry, typename Strategy>
0349 inline int point_in_geometry(Point const& point, Geometry const& geometry, Strategy const& strategy)
0350 {
0351     concepts::within::check<Point, Geometry, Strategy>();
0352
0353     return detail_dispatch::within::point_in_geometry<Geometry>::apply(point, geometry, strategy);
0354 }
0355
0356 template <typename Point, typename Geometry, typename Strategy>
0357 inline bool within_point_geometry(Point const& point, Geometry const& geometry, Strategy const& strategy)
0358 {
0359     return point_in_geometry(point, geometry, strategy) > 0;
0360 }
0361
0362 template <typename Point, typename Geometry, typename Strategy>
0363 inline bool covered_by_point_geometry(Point const& point, Geometry const& geometry, Strategy const& strategy)
0364 {
0365     return point_in_geometry(point, geometry, strategy) >= 0;
0366 }
0367
0368 }} // namespace detail::within
0369 #endif // DOXYGEN_NO_DETAIL
0370
0371 }} // namespace boost::geometry
0372
0373 #endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_WITHIN_POINT_IN_GEOMETRY_HPP