ceph/src/boost/libs/geometry/include/boost/geometry/algorithms/detail/disjoint/linear_areal.hpp

   1 // Boost.Geometry (aka GGL, Generic Geometry Library)
   2
   3 // Copyright (c) 2007-2014 Barend Gehrels, Amsterdam, the Netherlands.
   4 // Copyright (c) 2008-2014 Bruno Lalande, Paris, France.
   5 // Copyright (c) 2009-2014 Mateusz Loskot, London, UK.
   6 // Copyright (c) 2013-2014 Adam Wulkiewicz, Lodz, Poland.
   7
   8 // This file was modified by Oracle on 2013-2015.
   9 // Modifications copyright (c) 2013-2015, Oracle and/or its affiliates.
  10
  11 // Contributed and/or modified by Adam Wulkiewicz, on behalf of Oracle
  12 // Contributed and/or modified by Menelaos Karavelas, on behalf of Oracle
  13
  14 // Parts of Boost.Geometry are redesigned from Geodan's Geographic Library
  15 // (geolib/GGL), copyright (c) 1995-2010 Geodan, Amsterdam, the Netherlands.
  16
  17 // Use, modification and distribution is subject to the Boost Software License,
  18 // Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
  19 // http://www.boost.org/LICENSE_1_0.txt)
  20
  21 #ifndef BOOST_GEOMETRY_ALGORITHMS_DETAIL_DISJOINT_LINEAR_AREAL_HPP
  22 #define BOOST_GEOMETRY_ALGORITHMS_DETAIL_DISJOINT_LINEAR_AREAL_HPP
  23
  24 #include <iterator>
  25
  26 #include <boost/range.hpp>
  27
  28 #include <boost/geometry/core/closure.hpp>
  29 #include <boost/geometry/core/point_type.hpp>
  30 #include <boost/geometry/core/ring_type.hpp>
  31 #include <boost/geometry/core/exterior_ring.hpp>
  32 #include <boost/geometry/core/interior_rings.hpp>
  33 #include <boost/geometry/core/tag.hpp>
  34 #include <boost/geometry/core/tag_cast.hpp>
  35 #include <boost/geometry/core/tags.hpp>
  36
  37 #include <boost/geometry/algorithms/covered_by.hpp>
  38 #include <boost/geometry/algorithms/not_implemented.hpp>
  39
  40 #include <boost/geometry/algorithms/detail/assign_indexed_point.hpp>
  41 #include <boost/geometry/algorithms/detail/check_iterator_range.hpp>
  42 #include <boost/geometry/algorithms/detail/point_on_border.hpp>
  43
  44 #include <boost/geometry/algorithms/detail/disjoint/multirange_geometry.hpp>
  45 #include <boost/geometry/algorithms/detail/disjoint/linear_segment_or_box.hpp>
  46 #include <boost/geometry/algorithms/detail/disjoint/point_box.hpp>
  47 #include <boost/geometry/algorithms/detail/disjoint/segment_box.hpp>
  48
  49 #include <boost/geometry/algorithms/dispatch/disjoint.hpp>
  50
  51
  52 namespace boost { namespace geometry
  53 {
  54
  55 #ifndef DOXYGEN_NO_DETAIL
  56 namespace detail { namespace disjoint
  57 {
  58
  59 template <typename Geometry1, typename Geometry2,
  60           typename Tag1 = typename tag<Geometry1>::type,
  61           typename Tag1OrMulti = typename tag_cast<Tag1, multi_tag>::type>
  62 struct disjoint_no_intersections_policy
  63 {
  64     static inline bool apply(Geometry1 const& g1, Geometry2 const& g2)
  65     {
  66         typedef typename point_type<Geometry1>::type point1_type;
  67         point1_type p;
  68         geometry::point_on_border(p, g1);
  69         return !geometry::covered_by(p, g2);
  70     }
  71 };
  72
  73 template <typename Geometry1, typename Geometry2, typename Tag1>
  74 struct disjoint_no_intersections_policy<Geometry1, Geometry2, Tag1, multi_tag>
  75 {
  76     static inline bool apply(Geometry1 const& g1, Geometry2 const& g2)
  77     {
  78         // TODO: use partition or rtree on g2
  79         typedef typename boost::range_iterator<Geometry1 const>::type iterator;
  80         for ( iterator it = boost::begin(g1) ; it != boost::end(g1) ; ++it )
  81         {
  82             typedef typename boost::range_value<Geometry1 const>::type value_type;
  83             if ( ! disjoint_no_intersections_policy<value_type const, Geometry2>
  84                     ::apply(*it, g2) )
  85             {
  86                 return false;
  87             }
  88         }
  89         return true;
  90     }
  91 };
  92
  93
  94 template<typename Geometry1, typename Geometry2,
  95          typename NoIntersectionsPolicy
  96                     = disjoint_no_intersections_policy<Geometry1, Geometry2> >
  97 struct disjoint_linear_areal
  98 {
  99     static inline bool apply(Geometry1 const& g1, Geometry2 const& g2)
 100     {
 101         // if there are intersections - return false
 102         if ( !disjoint_linear<Geometry1, Geometry2>::apply(g1, g2) )
 103         {
 104             return false;
 105         }
 106
 107         return NoIntersectionsPolicy::apply(g1, g2);
 108     }
 109 };
 110
 111
 112
 113
 114 template
 115 <
 116     typename Segment,
 117     typename Areal,
 118     typename Tag = typename tag<Areal>::type
 119 >
 120 struct disjoint_segment_areal
 121     : not_implemented<Segment, Areal>
 122 {};
 123
 124
 125 template <typename Segment, typename Polygon>
 126 class disjoint_segment_areal<Segment, Polygon, polygon_tag>
 127 {
 128 private:
 129     template <typename InteriorRings>
 130     static inline
 131     bool check_interior_rings(InteriorRings const& interior_rings,
 132                               Segment const& segment)
 133     {
 134         typedef typename boost::range_value<InteriorRings>::type ring_type;
 135
 136         typedef unary_disjoint_geometry_to_query_geometry
 137             <
 138                 Segment,
 139                 disjoint_range_segment_or_box
 140                     <
 141                         ring_type, closure<ring_type>::value, Segment
 142                     >
 143             > unary_predicate_type;
 144
 145         return check_iterator_range
 146             <
 147                 unary_predicate_type
 148             >::apply(boost::begin(interior_rings),
 149                      boost::end(interior_rings),
 150                      unary_predicate_type(segment));
 151     }
 152
 153
 154 public:
 155     static inline bool apply(Segment const& segment, Polygon const& polygon)
 156     {
 157         typedef typename geometry::ring_type<Polygon>::type ring;
 158
 159         if ( !disjoint_range_segment_or_box
 160                  <
 161                      ring, closure<Polygon>::value, Segment
 162                  >::apply(geometry::exterior_ring(polygon), segment) )
 163         {
 164             return false;
 165         }
 166
 167         if ( !check_interior_rings(geometry::interior_rings(polygon), segment) )
 168         {
 169             return false;
 170         }
 171
 172         typename point_type<Segment>::type p;
 173         detail::assign_point_from_index<0>(segment, p);
 174
 175         return !geometry::covered_by(p, polygon);
 176     }
 177 };
 178
 179
 180 template <typename Segment, typename MultiPolygon>
 181 struct disjoint_segment_areal<Segment, MultiPolygon, multi_polygon_tag>
 182 {
 183     static inline
 184     bool apply(Segment const& segment, MultiPolygon const& multipolygon)
 185     {
 186         return multirange_constant_size_geometry
 187             <
 188                 MultiPolygon, Segment
 189             >::apply(multipolygon, segment);
 190     }
 191 };
 192
 193
 194 template <typename Segment, typename Ring>
 195 struct disjoint_segment_areal<Segment, Ring, ring_tag>
 196 {
 197     static inline bool apply(Segment const& segment, Ring const& ring)
 198     {
 199         if ( !disjoint_range_segment_or_box
 200                  <
 201                      Ring, closure<Ring>::value, Segment
 202                  >::apply(ring, segment) )
 203         {
 204             return false;
 205         }
 206
 207         typename point_type<Segment>::type p;
 208         detail::assign_point_from_index<0>(segment, p);
 209
 210         return !geometry::covered_by(p, ring);
 211     }
 212 };
 213
 214
 215 }} // namespace detail::disjoint
 216 #endif // DOXYGEN_NO_DETAIL
 217
 218
 219
 220
 221 #ifndef DOXYGEN_NO_DISPATCH
 222 namespace dispatch
 223 {
 224
 225
 226 template <typename Linear, typename Areal>
 227 struct disjoint<Linear, Areal, 2, linear_tag, areal_tag, false>
 228     : public detail::disjoint::disjoint_linear_areal<Linear, Areal>
 229 {};
 230
 231
 232 template <typename Areal, typename Linear>
 233 struct disjoint<Areal, Linear, 2, areal_tag, linear_tag, false>
 234 {
 235     static inline
 236     bool apply(Areal const& areal, Linear const& linear)
 237     {
 238         return detail::disjoint::disjoint_linear_areal
 239             <
 240                 Linear, Areal
 241             >::apply(linear, areal);
 242     }
 243 };
 244
 245
 246 template <typename Areal, typename Segment>
 247 struct disjoint<Areal, Segment, 2, areal_tag, segment_tag, false>
 248 {
 249     static inline bool apply(Areal const& g1, Segment const& g2)
 250     {
 251         return detail::disjoint::disjoint_segment_areal
 252             <
 253                 Segment, Areal
 254             >::apply(g2, g1);
 255     }
 256 };
 257
 258
 259 template <typename Segment, typename Areal>
 260 struct disjoint<Segment, Areal, 2, segment_tag, areal_tag, false>
 261     : detail::disjoint::disjoint_segment_areal<Segment, Areal>
 262 {};
 263
 264
 265 } // namespace dispatch
 266 #endif // DOXYGEN_NO_DISPATCH
 267
 268
 269 }} // namespace boost::geometry
 270
 271
 272 #endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_DISJOINT_LINEAR_AREAL_HPP