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