detail/within/within_no_turns.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 2013-2023.
0008 // Modifications copyright (c) 2013-2023, Oracle and/or its affiliates.
0009 // Contributed and/or modified by Vissarion Fysikopoulos, on behalf of Oracle
0010
0011 // Parts of Boost.Geometry are redesigned from Geodan's Geographic Library
0012 // (geolib/GGL), copyright (c) 1995-2010 Geodan, Amsterdam, the Netherlands.
0013
0014 // Use, modification and distribution is subject to the Boost Software License,
0015 // Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
0016 // http://www.boost.org/LICENSE_1_0.txt)
0017
0018 #ifndef BOOST_GEOMETRY_ALGORITHMS_DETAIL_WITHIN_WITHIN_NO_TURNS_HPP
0019 #define BOOST_GEOMETRY_ALGORITHMS_DETAIL_WITHIN_WITHIN_NO_TURNS_HPP
0020
0021 #include <boost/geometry/algorithms/detail/point_on_border.hpp>
0022 #include <boost/geometry/algorithms/detail/within/point_in_geometry.hpp>
0023
0024 namespace boost { namespace geometry {
0025
0026 #ifndef DOXYGEN_NO_DETAIL
0027 namespace detail_dispatch { namespace within {
0028
0029 // returns true if G1 is within G2
0030 // this function should be called only if there are no intersection points
0031 // otherwise it may return invalid result
0032 // e.g. when non-first point of G1 is outside G2 or when some rings of G1 are the same as rings of G2
0033
0034 template <typename Geometry1,
0035           typename Geometry2,
0036           typename Tag1 = typename geometry::tag<Geometry1>::type,
0037           typename Tag2 = typename geometry::tag<Geometry2>::type>
0038 struct within_no_turns
0039 {
0040     template <typename Strategy> static inline
0041     bool apply(Geometry1 const& geometry1, Geometry2 const& geometry2, Strategy const& strategy)
0042     {
0043         typedef typename geometry::point_type<Geometry1>::type point1_type;
0044         point1_type p;
0045         if (! geometry::point_on_border(p, geometry1))
0046         {
0047             return false;
0048         }
0049
0050         return detail::within::point_in_geometry(p, geometry2, strategy) >= 0;
0051     }
0052 };
0053
0054 template <typename Geometry1, typename Geometry2>
0055 struct within_no_turns<Geometry1, Geometry2, ring_tag, polygon_tag>
0056 {
0057     template <typename Strategy> static inline
0058     bool apply(Geometry1 const& geometry1, Geometry2 const& geometry2, Strategy const& strategy)
0059     {
0060         typedef typename geometry::point_type<Geometry1>::type point1_type;
0061         typedef typename geometry::point_type<Geometry2>::type point2_type;
0062         point1_type p;
0063         if (! geometry::point_on_border(p, geometry1))
0064         {
0065             return false;
0066         }
0067         // check if one of ring points is outside the polygon
0068         if (detail::within::point_in_geometry(p, geometry2, strategy) < 0)
0069         {
0070             return false;
0071         }
0072         // Now check if holes of G2 aren't inside G1
0073         auto const& rings2 = geometry::interior_rings(geometry2);
0074         for (auto it = boost::begin(rings2); it != boost::end(rings2); ++it)
0075         {
0076             point2_type p;
0077             if (! geometry::point_on_border(p, *it))
0078             {
0079                 return false;
0080             }
0081             if (detail::within::point_in_geometry(p, geometry1, strategy) > 0)
0082             {
0083                 return false;
0084             }
0085         }
0086         return true;
0087     }
0088 };
0089
0090 template <typename Geometry1, typename Geometry2>
0091 struct within_no_turns<Geometry1, Geometry2, polygon_tag, polygon_tag>
0092 {
0093     template <typename Strategy> static inline
0094     bool apply(Geometry1 const& geometry1, Geometry2 const& geometry2, Strategy const& strategy)
0095     {
0096         typedef typename geometry::point_type<Geometry1>::type point1_type;
0097         typedef typename geometry::point_type<Geometry2>::type point2_type;
0098         point1_type p;
0099         if (! geometry::point_on_border(p, geometry1))
0100         {
0101             return false;
0102         }
0103         // check if one of ring points is outside the polygon
0104         if (detail::within::point_in_geometry(p, geometry2, strategy) < 0)
0105         {
0106             return false;
0107         }
0108         // Now check if holes of G2 aren't inside G1
0109         auto const& rings2 = geometry::interior_rings(geometry2);
0110         for (auto it2 = boost::begin(rings2); it2 != boost::end(rings2); ++it2)
0111         {
0112             point2_type p2;
0113             if (! geometry::point_on_border(p2, *it2))
0114             {
0115                 return false;
0116             }
0117             // if the hole of G2 is inside G1
0118             if (detail::within::point_in_geometry(p2, geometry1, strategy) > 0)
0119             {
0120                 // if it's also inside one of the G1 holes, it's ok
0121                 bool ok = false;
0122                 auto const& rings1 = geometry::interior_rings(geometry1);
0123                 for (auto it1 = boost::begin(rings1); it1 != boost::end(rings1); ++it1)
0124                 {
0125                     if (detail::within::point_in_geometry(p2, *it1, strategy) < 0)
0126                     {
0127                         ok = true;
0128                         break;
0129                     }
0130                 }
0131                 if (! ok)
0132                 {
0133                     return false;
0134                 }
0135             }
0136         }
0137         return true;
0138     }
0139 };
0140
0141 template <typename Geometry1,
0142           typename Geometry2,
0143           typename Tag1 = typename geometry::tag<Geometry1>::type,
0144           typename Tag2 = typename geometry::tag<Geometry2>::type,
0145           bool IsMulti1 = boost::is_base_of<geometry::multi_tag, Tag1>::value,
0146           bool IsMulti2 = boost::is_base_of<geometry::multi_tag, Tag2>::value>
0147 struct within_no_turns_multi
0148 {
0149     template <typename Strategy> static inline
0150     bool apply(Geometry1 const& geometry1, Geometry2 const& geometry2, Strategy const& strategy)
0151     {
0152         return within_no_turns<Geometry1, Geometry2>::apply(geometry1, geometry2, strategy);
0153     }
0154 };
0155
0156 template <typename Geometry1, typename Geometry2, typename Tag1, typename Tag2>
0157 struct within_no_turns_multi<Geometry1, Geometry2, Tag1, Tag2, true, false>
0158 {
0159     template <typename Strategy> static inline
0160     bool apply(Geometry1 const& geometry1, Geometry2 const& geometry2, Strategy const& strategy)
0161     {
0162         // All values of G1 must be inside G2
0163         typedef typename boost::range_value<Geometry1>::type subgeometry1;
0164         for (auto it = boost::begin(geometry1) ; it != boost::end(geometry1) ; ++it )
0165         {
0166             if (! within_no_turns<subgeometry1, Geometry2>::apply(*it, geometry2, strategy))
0167             {
0168                 return false;
0169             }
0170         }
0171         return true;
0172     }
0173 };
0174
0175 template <typename Geometry1, typename Geometry2, typename Tag1, typename Tag2>
0176 struct within_no_turns_multi<Geometry1, Geometry2, Tag1, Tag2, false, true>
0177 {
0178     template <typename Strategy> static inline
0179     bool apply(Geometry1 const& geometry1, Geometry2 const& geometry2, Strategy const& strategy)
0180     {
0181         // G1 must be within at least one value of G2
0182         typedef typename boost::range_value<Geometry2>::type subgeometry2;
0183         for (auto it = boost::begin(geometry2); it != boost::end(geometry2); ++it)
0184         {
0185             if (within_no_turns<Geometry1, subgeometry2>::apply(geometry1, *it, strategy))
0186             {
0187                 return true;
0188             }
0189         }
0190         return false;
0191     }
0192 };
0193
0194 template <typename Geometry1, typename Geometry2, typename Tag1, typename Tag2>
0195 struct within_no_turns_multi<Geometry1, Geometry2, Tag1, Tag2, true, true>
0196 {
0197     template <typename Strategy> static inline
0198     bool apply(Geometry1 const& geometry1, Geometry2 const& geometry2, Strategy const& strategy)
0199     {
0200         // each value of G1 must be inside at least one value of G2
0201         typedef typename boost::range_value<Geometry1>::type subgeometry1;
0202         for (auto it = boost::begin(geometry1) ; it != boost::end(geometry1) ; ++it)
0203         {
0204             if (! within_no_turns_multi<subgeometry1, Geometry2>::apply(*it, geometry2, strategy))
0205             {
0206                 return false;
0207             }
0208         }
0209         return true;
0210     }
0211 };
0212
0213 }} // namespace detail_dispatch::within
0214
0215 namespace detail { namespace within {
0216
0217 template <typename Geometry1, typename Geometry2, typename Strategy>
0218 inline bool within_no_turns(Geometry1 const& geometry1, Geometry2 const& geometry2, Strategy const& strategy)
0219 {
0220     return detail_dispatch::within::within_no_turns_multi<Geometry1, Geometry2>::apply(geometry1, geometry2, strategy);
0221 }
0222
0223 }} // namespace detail::within
0224 #endif // DOXYGEN_NO_DETAIL
0225
0226 }} // namespace boost::geometry
0227
0228 #endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_WITHIN_WITHIN_NO_TURNS_HPP