ceph/src/boost/libs/geometry/include/boost/geometry/algorithms/detail/within/within_no_turns.hpp

   1 // Boost.Geometry (aka GGL, Generic Geometry Library)
   2
   3 // Copyright (c) 2007-2012 Barend Gehrels, Amsterdam, the Netherlands.
   4 // Copyright (c) 2008-2012 Bruno Lalande, Paris, France.
   5 // Copyright (c) 2009-2012 Mateusz Loskot, London, UK.
   6
   7 // This file was modified by Oracle on 2013.
   8 // Modifications copyright (c) 2013, Oracle and/or its affiliates.
   9
  10 // Parts of Boost.Geometry are redesigned from Geodan's Geographic Library
  11 // (geolib/GGL), copyright (c) 1995-2010 Geodan, Amsterdam, the Netherlands.
  12
  13 // Use, modification and distribution is subject to the Boost Software License,
  14 // Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
  15 // http://www.boost.org/LICENSE_1_0.txt)
  16
  17 #ifndef BOOST_GEOMETRY_ALGORITHMS_DETAIL_WITHIN_WITHIN_NO_TURNS_HPP
  18 #define BOOST_GEOMETRY_ALGORITHMS_DETAIL_WITHIN_WITHIN_NO_TURNS_HPP
  19
  20 #include <boost/geometry/algorithms/detail/point_on_border.hpp>
  21 #include <boost/geometry/algorithms/detail/within/point_in_geometry.hpp>
  22
  23 namespace boost { namespace geometry {
  24
  25 #ifndef DOXYGEN_NO_DETAIL
  26 namespace detail_dispatch { namespace within {
  27
  28 // returns true if G1 is within G2
  29 // this function should be called only if there are no intersection points
  30 // otherwise it may return invalid result
  31 // e.g. when non-first point of G1 is outside G2 or when some rings of G1 are the same as rings of G2
  32
  33 template <typename Geometry1,
  34           typename Geometry2,
  35           typename Tag1 = typename geometry::tag<Geometry1>::type,
  36           typename Tag2 = typename geometry::tag<Geometry2>::type>
  37 struct within_no_turns
  38 {
  39     template <typename Strategy> static inline
  40     bool apply(Geometry1 const& geometry1, Geometry2 const& geometry2, Strategy const& strategy)
  41     {
  42         typedef typename geometry::point_type<Geometry1>::type point1_type;
  43         point1_type p;
  44         if ( !geometry::point_on_border(p, geometry1) )
  45             return false;
  46
  47         return detail::within::point_in_geometry(p, geometry2, strategy) >= 0;
  48     }
  49 };
  50
  51 template <typename Geometry1, typename Geometry2>
  52 struct within_no_turns<Geometry1, Geometry2, ring_tag, polygon_tag>
  53 {
  54     template <typename Strategy> static inline
  55     bool apply(Geometry1 const& geometry1, Geometry2 const& geometry2, Strategy const& strategy)
  56     {
  57         typedef typename geometry::point_type<Geometry1>::type point1_type;
  58         typedef typename geometry::point_type<Geometry2>::type point2_type;
  59         point1_type p;
  60         if ( !geometry::point_on_border(p, geometry1) )
  61             return false;
  62         // check if one of ring points is outside the polygon
  63         if ( detail::within::point_in_geometry(p, geometry2, strategy) < 0 )
  64             return false;
  65         // Now check if holes of G2 aren't inside G1
  66         typedef typename boost::range_const_iterator
  67             <
  68                 typename geometry::interior_type<Geometry2>::type
  69             >::type iterator;
  70         for ( iterator it = boost::begin(geometry::interior_rings(geometry2)) ;
  71               it != boost::end(geometry::interior_rings(geometry2)) ;
  72               ++it )
  73         {
  74             point2_type p;
  75             if ( !geometry::point_on_border(p, *it) )
  76                 return false;
  77             if ( detail::within::point_in_geometry(p, geometry1, strategy) > 0 )
  78                 return false;
  79         }
  80         return true;
  81     }
  82 };
  83
  84 template <typename Geometry1, typename Geometry2>
  85 struct within_no_turns<Geometry1, Geometry2, polygon_tag, polygon_tag>
  86 {
  87     template <typename Strategy> static inline
  88     bool apply(Geometry1 const& geometry1, Geometry2 const& geometry2, Strategy const& strategy)
  89     {
  90         typedef typename geometry::point_type<Geometry1>::type point1_type;
  91         typedef typename geometry::point_type<Geometry2>::type point2_type;
  92         point1_type p;
  93         if ( !geometry::point_on_border(p, geometry1) )
  94             return false;
  95         // check if one of ring points is outside the polygon
  96         if ( detail::within::point_in_geometry(p, geometry2, strategy) < 0 )
  97             return false;
  98         // Now check if holes of G2 aren't inside G1
  99         typedef typename boost::range_const_iterator
 100             <
 101                 typename geometry::interior_type<Geometry2>::type
 102             >::type iterator2;
 103         for ( iterator2 it = boost::begin(geometry::interior_rings(geometry2)) ;
 104               it != boost::end(geometry::interior_rings(geometry2)) ;
 105               ++it )
 106         {
 107             point2_type p2;
 108             if ( !geometry::point_on_border(p2, *it) )
 109                 return false;
 110             // if the hole of G2 is inside G1
 111             if ( detail::within::point_in_geometry(p2, geometry1, strategy) > 0 )
 112             {
 113                 // if it's also inside one of the G1 holes, it's ok
 114                 bool ok = false;
 115                 typedef typename boost::range_const_iterator
 116                     <
 117                         typename geometry::interior_type<Geometry1>::type
 118                     >::type iterator1;
 119                 for ( iterator1 it1 = boost::begin(geometry::interior_rings(geometry1)) ;
 120                       it1 != boost::end(geometry::interior_rings(geometry1)) ;
 121                       ++it1 )
 122                 {
 123                     if ( detail::within::point_in_geometry(p2, *it1, strategy) < 0 )
 124                     {
 125                         ok = true;
 126                         break;
 127                     }
 128                 }
 129                 if ( !ok )
 130                     return false;
 131             }
 132         }
 133         return true;
 134     }
 135 };
 136
 137 template <typename Geometry1,
 138           typename Geometry2,
 139           typename Tag1 = typename geometry::tag<Geometry1>::type,
 140           typename Tag2 = typename geometry::tag<Geometry2>::type,
 141           bool IsMulti1 = boost::is_base_of<geometry::multi_tag, Tag1>::value,
 142           bool IsMulti2 = boost::is_base_of<geometry::multi_tag, Tag2>::value>
 143 struct within_no_turns_multi
 144 {
 145     template <typename Strategy> static inline
 146     bool apply(Geometry1 const& geometry1, Geometry2 const& geometry2, Strategy const& strategy)
 147     {
 148         return within_no_turns<Geometry1, Geometry2>::apply(geometry1, geometry2, strategy);
 149     }
 150 };
 151
 152 template <typename Geometry1, typename Geometry2, typename Tag1, typename Tag2>
 153 struct within_no_turns_multi<Geometry1, Geometry2, Tag1, Tag2, true, false>
 154 {
 155     template <typename Strategy> static inline
 156     bool apply(Geometry1 const& geometry1, Geometry2 const& geometry2, Strategy const& strategy)
 157     {
 158         // All values of G1 must be inside G2
 159         typedef typename boost::range_value<Geometry1>::type subgeometry1;
 160         typedef typename boost::range_const_iterator<Geometry1>::type iterator;
 161         for ( iterator it = boost::begin(geometry1) ; it != boost::end(geometry1) ; ++it )
 162         {
 163             if ( !within_no_turns<subgeometry1, Geometry2>::apply(*it, geometry2, strategy) )
 164                 return false;
 165         }
 166         return true;
 167     }
 168 };
 169
 170 template <typename Geometry1, typename Geometry2, typename Tag1, typename Tag2>
 171 struct within_no_turns_multi<Geometry1, Geometry2, Tag1, Tag2, false, true>
 172 {
 173     template <typename Strategy> static inline
 174     bool apply(Geometry1 const& geometry1, Geometry2 const& geometry2, Strategy const& strategy)
 175     {
 176         // G1 must be within at least one value of G2
 177         typedef typename boost::range_value<Geometry2>::type subgeometry2;
 178         typedef typename boost::range_const_iterator<Geometry2>::type iterator;
 179         for ( iterator it = boost::begin(geometry2) ; it != boost::end(geometry2) ; ++it )
 180         {
 181             if ( within_no_turns<Geometry1, subgeometry2>::apply(geometry1, *it, strategy) )
 182                 return true;
 183         }
 184         return false;
 185     }
 186 };
 187
 188 template <typename Geometry1, typename Geometry2, typename Tag1, typename Tag2>
 189 struct within_no_turns_multi<Geometry1, Geometry2, Tag1, Tag2, true, true>
 190 {
 191     template <typename Strategy> static inline
 192     bool apply(Geometry1 const& geometry1, Geometry2 const& geometry2, Strategy const& strategy)
 193     {
 194         // each value of G1 must be inside at least one value of G2
 195         typedef typename boost::range_value<Geometry1>::type subgeometry1;
 196         typedef typename boost::range_const_iterator<Geometry1>::type iterator;
 197         for ( iterator it = boost::begin(geometry1) ; it != boost::end(geometry1) ; ++it )
 198         {
 199             if ( !within_no_turns_multi<subgeometry1, Geometry2>::apply(*it, geometry2, strategy) )
 200                 return false;
 201         }
 202         return true;
 203     }
 204 };
 205
 206 }} // namespace detail_dispatch::within
 207
 208 namespace detail { namespace within {
 209
 210 template <typename Geometry1, typename Geometry2, typename Strategy>
 211 inline bool within_no_turns(Geometry1 const& geometry1, Geometry2 const& geometry2, Strategy const& strategy)
 212 {
 213     return detail_dispatch::within::within_no_turns_multi<Geometry1, Geometry2>::apply(geometry1, geometry2, strategy);
 214 }
 215
 216 }} // namespace detail::within
 217 #endif // DOXYGEN_NO_DETAIL
 218
 219 }} // namespace boost::geometry
 220
 221 #endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_WITHIN_WITHIN_NO_TURNS_HPP