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-2017.
   9 // Modifications copyright (c) 2013-2017, 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     /*!
  65     \tparam Strategy point_in_geometry strategy
  66     */
  67     template <typename Strategy>
  68     static inline bool apply(Geometry1 const& g1, Geometry2 const& g2, Strategy const& strategy)
  69     {
  70         typedef typename point_type<Geometry1>::type point1_type;
  71         point1_type p;
  72         geometry::point_on_border(p, g1);
  73
  74         return !geometry::covered_by(p, g2, strategy);
  75     }
  76 };
  77
  78 template <typename Geometry1, typename Geometry2, typename Tag1>
  79 struct disjoint_no_intersections_policy<Geometry1, Geometry2, Tag1, multi_tag>
  80 {
  81     /*!
  82     \tparam Strategy point_in_geometry strategy
  83     */
  84     template <typename Strategy>
  85     static inline bool apply(Geometry1 const& g1, Geometry2 const& g2, Strategy const& strategy)
  86     {
  87         // TODO: use partition or rtree on g2
  88         typedef typename boost::range_iterator<Geometry1 const>::type iterator;
  89         for ( iterator it = boost::begin(g1) ; it != boost::end(g1) ; ++it )
  90         {
  91             typedef typename boost::range_value<Geometry1 const>::type value_type;
  92             if ( ! disjoint_no_intersections_policy<value_type const, Geometry2>
  93                     ::apply(*it, g2, strategy) )
  94             {
  95                 return false;
  96             }
  97         }
  98         return true;
  99     }
 100 };
 101
 102
 103 template<typename Geometry1, typename Geometry2,
 104          typename NoIntersectionsPolicy
 105                     = disjoint_no_intersections_policy<Geometry1, Geometry2> >
 106 struct disjoint_linear_areal
 107 {
 108     /*!
 109     \tparam Strategy relate (segments intersection) strategy
 110     */
 111     template <typename Strategy>
 112     static inline bool apply(Geometry1 const& g1, Geometry2 const& g2, Strategy const& strategy)
 113     {
 114         // if there are intersections - return false
 115         if ( !disjoint_linear<Geometry1, Geometry2>::apply(g1, g2, strategy) )
 116         {
 117             return false;
 118         }
 119
 120         return NoIntersectionsPolicy
 121                 ::apply(g1, g2,
 122                         strategy.template get_point_in_geometry_strategy<Geometry1, Geometry2>());
 123     }
 124 };
 125
 126
 127
 128
 129 template
 130 <
 131     typename Segment,
 132     typename Areal,
 133     typename Tag = typename tag<Areal>::type
 134 >
 135 struct disjoint_segment_areal
 136     : not_implemented<Segment, Areal>
 137 {};
 138
 139
 140 template <typename Segment, typename Polygon>
 141 class disjoint_segment_areal<Segment, Polygon, polygon_tag>
 142 {
 143 private:
 144     template <typename InteriorRings, typename Strategy>
 145     static inline
 146     bool check_interior_rings(InteriorRings const& interior_rings,
 147                               Segment const& segment,
 148                               Strategy const& strategy)
 149     {
 150         typedef typename boost::range_value<InteriorRings>::type ring_type;
 151
 152         typedef unary_disjoint_geometry_to_query_geometry
 153             <
 154                 Segment,
 155                 Strategy,
 156                 disjoint_range_segment_or_box
 157                     <
 158                         ring_type, closure<ring_type>::value, Segment
 159                     >
 160             > unary_predicate_type;
 161
 162         return check_iterator_range
 163             <
 164                 unary_predicate_type
 165             >::apply(boost::begin(interior_rings),
 166                      boost::end(interior_rings),
 167                      unary_predicate_type(segment, strategy));
 168     }
 169
 170
 171 public:
 172     template <typename IntersectionStrategy>
 173     static inline bool apply(Segment const& segment,
 174                              Polygon const& polygon,
 175                              IntersectionStrategy const& strategy)
 176     {
 177         typedef typename geometry::ring_type<Polygon>::type ring;
 178
 179         if ( !disjoint_range_segment_or_box
 180                  <
 181                      ring, closure<Polygon>::value, Segment
 182                  >::apply(geometry::exterior_ring(polygon), segment, strategy) )
 183         {
 184             return false;
 185         }
 186
 187         if ( !check_interior_rings(geometry::interior_rings(polygon), segment, strategy) )
 188         {
 189             return false;
 190         }
 191
 192         typename point_type<Segment>::type p;
 193         detail::assign_point_from_index<0>(segment, p);
 194
 195         return !geometry::covered_by(p, polygon,
 196                     strategy.template get_point_in_geometry_strategy<Segment, Polygon>());
 197     }
 198 };
 199
 200
 201 template <typename Segment, typename MultiPolygon>
 202 struct disjoint_segment_areal<Segment, MultiPolygon, multi_polygon_tag>
 203 {
 204     template <typename IntersectionStrategy>
 205     static inline bool apply(Segment const& segment, MultiPolygon const& multipolygon,
 206                              IntersectionStrategy const& strategy)
 207     {
 208         return multirange_constant_size_geometry
 209             <
 210                 MultiPolygon, Segment
 211             >::apply(multipolygon, segment, strategy);
 212     }
 213 };
 214
 215
 216 template <typename Segment, typename Ring>
 217 struct disjoint_segment_areal<Segment, Ring, ring_tag>
 218 {
 219     template <typename IntersectionStrategy>
 220     static inline bool apply(Segment const& segment,
 221                              Ring const& ring,
 222                              IntersectionStrategy const& strategy)
 223     {
 224         if ( !disjoint_range_segment_or_box
 225                  <
 226                      Ring, closure<Ring>::value, Segment
 227                  >::apply(ring, segment, strategy) )
 228         {
 229             return false;
 230         }
 231
 232         typename point_type<Segment>::type p;
 233         detail::assign_point_from_index<0>(segment, p);
 234
 235         return !geometry::covered_by(p, ring,
 236                     strategy.template get_point_in_geometry_strategy<Segment, Ring>());
 237     }
 238 };
 239
 240
 241 }} // namespace detail::disjoint
 242 #endif // DOXYGEN_NO_DETAIL
 243
 244
 245
 246
 247 #ifndef DOXYGEN_NO_DISPATCH
 248 namespace dispatch
 249 {
 250
 251
 252 template <typename Linear, typename Areal>
 253 struct disjoint<Linear, Areal, 2, linear_tag, areal_tag, false>
 254     : public detail::disjoint::disjoint_linear_areal<Linear, Areal>
 255 {};
 256
 257
 258 template <typename Areal, typename Linear>
 259 struct disjoint<Areal, Linear, 2, areal_tag, linear_tag, false>
 260 {
 261     template <typename Strategy>
 262     static inline bool apply(Areal const& areal, Linear const& linear,
 263                              Strategy const& strategy)
 264     {
 265         return detail::disjoint::disjoint_linear_areal
 266             <
 267                 Linear, Areal
 268             >::apply(linear, areal, strategy);
 269     }
 270 };
 271
 272
 273 template <typename Areal, typename Segment>
 274 struct disjoint<Areal, Segment, 2, areal_tag, segment_tag, false>
 275 {
 276     template <typename Strategy>
 277     static inline bool apply(Areal const& g1, Segment const& g2,
 278                              Strategy const& strategy)
 279     {
 280         return detail::disjoint::disjoint_segment_areal
 281             <
 282                 Segment, Areal
 283             >::apply(g2, g1, strategy);
 284     }
 285 };
 286
 287
 288 template <typename Segment, typename Areal>
 289 struct disjoint<Segment, Areal, 2, segment_tag, areal_tag, false>
 290     : detail::disjoint::disjoint_segment_areal<Segment, Areal>
 291 {};
 292
 293
 294 } // namespace dispatch
 295 #endif // DOXYGEN_NO_DISPATCH
 296
 297
 298 }} // namespace boost::geometry
 299
 300
 301 #endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_DISJOINT_LINEAR_AREAL_HPP