ceph/src/boost/libs/geometry/include/boost/geometry/algorithms/detail/intersection/multi.hpp

   1 // Boost.Geometry (aka GGL, Generic Geometry Library)
   2
   3 // Copyright (c) 2007-2015 Barend Gehrels, Amsterdam, the Netherlands.
   4
   5 // This file was modified by Oracle on 2014.
   6 // Modifications copyright (c) 2014-2015, Oracle and/or its affiliates.
   7
   8 // Contributed and/or modified by Adam Wulkiewicz, on behalf of Oracle
   9
  10 // Use, modification and distribution is subject to the Boost Software License,
  11 // Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
  12 // http://www.boost.org/LICENSE_1_0.txt)
  13
  14 #ifndef BOOST_GEOMETRY_ALGORITHMS_DETAIL_INTERSECTION_MULTI_HPP
  15 #define BOOST_GEOMETRY_ALGORITHMS_DETAIL_INTERSECTION_MULTI_HPP
  16
  17 #include <boost/geometry/core/closure.hpp>
  18 #include <boost/geometry/core/geometry_id.hpp>
  19 #include <boost/geometry/core/is_areal.hpp>
  20 #include <boost/geometry/core/point_order.hpp>
  21 #include <boost/geometry/core/tags.hpp>
  22 #include <boost/geometry/geometries/concepts/check.hpp>
  23
  24 // TODO: those headers probably may be removed
  25 #include <boost/geometry/algorithms/detail/overlay/get_ring.hpp>
  26 #include <boost/geometry/algorithms/detail/overlay/get_turns.hpp>
  27 #include <boost/geometry/algorithms/detail/overlay/copy_segments.hpp>
  28 #include <boost/geometry/algorithms/detail/overlay/copy_segment_point.hpp>
  29 #include <boost/geometry/algorithms/detail/overlay/select_rings.hpp>
  30 #include <boost/geometry/algorithms/detail/sections/range_by_section.hpp>
  31 #include <boost/geometry/algorithms/detail/sections/sectionalize.hpp>
  32
  33 #include <boost/geometry/algorithms/detail/intersection/interface.hpp>
  34
  35 #include <boost/geometry/algorithms/covered_by.hpp>
  36 #include <boost/geometry/algorithms/envelope.hpp>
  37 #include <boost/geometry/algorithms/num_points.hpp>
  38
  39
  40 namespace boost { namespace geometry
  41 {
  42
  43 #ifndef DOXYGEN_NO_DETAIL
  44 namespace detail { namespace intersection
  45 {
  46
  47
  48 template <typename PointOut>
  49 struct intersection_multi_linestring_multi_linestring_point
  50 {
  51     template
  52     <
  53         typename MultiLinestring1, typename MultiLinestring2,
  54         typename RobustPolicy,
  55         typename OutputIterator, typename Strategy
  56     >
  57     static inline OutputIterator apply(MultiLinestring1 const& ml1,
  58             MultiLinestring2 const& ml2,
  59             RobustPolicy const& robust_policy,
  60             OutputIterator out,
  61             Strategy const& strategy)
  62     {
  63         // Note, this loop is quadratic w.r.t. number of linestrings per input.
  64         // Future Enhancement: first do the sections of each, then intersect.
  65         for (typename boost::range_iterator
  66                 <
  67                     MultiLinestring1 const
  68                 >::type it1 = boost::begin(ml1);
  69             it1 != boost::end(ml1);
  70             ++it1)
  71         {
  72             for (typename boost::range_iterator
  73                     <
  74                         MultiLinestring2 const
  75                     >::type it2 = boost::begin(ml2);
  76                 it2 != boost::end(ml2);
  77                 ++it2)
  78             {
  79                 out = intersection_linestring_linestring_point<PointOut>
  80                       ::apply(*it1, *it2, robust_policy, out, strategy);
  81             }
  82         }
  83
  84         return out;
  85     }
  86 };
  87
  88
  89 template <typename PointOut>
  90 struct intersection_linestring_multi_linestring_point
  91 {
  92     template
  93     <
  94         typename Linestring, typename MultiLinestring,
  95         typename RobustPolicy,
  96         typename OutputIterator, typename Strategy
  97     >
  98     static inline OutputIterator apply(Linestring const& linestring,
  99             MultiLinestring const& ml,
 100             RobustPolicy const& robust_policy,
 101             OutputIterator out,
 102             Strategy const& strategy)
 103     {
 104         for (typename boost::range_iterator
 105                 <
 106                     MultiLinestring const
 107                 >::type it = boost::begin(ml);
 108             it != boost::end(ml);
 109             ++it)
 110         {
 111             out = intersection_linestring_linestring_point<PointOut>
 112                   ::apply(linestring, *it, robust_policy, out, strategy);
 113         }
 114
 115         return out;
 116     }
 117 };
 118
 119
 120 // This loop is quite similar to the loop above, but beacuse the iterator
 121 // is second (above) or first (below) argument, it is not trivial to merge them.
 122 template
 123 <
 124     bool ReverseAreal,
 125     typename LineStringOut,
 126     overlay_type OverlayType
 127 >
 128 struct intersection_of_multi_linestring_with_areal
 129 {
 130     template
 131     <
 132         typename MultiLinestring, typename Areal,
 133         typename RobustPolicy,
 134         typename OutputIterator, typename Strategy
 135     >
 136     static inline OutputIterator apply(MultiLinestring const& ml, Areal const& areal,
 137             RobustPolicy const& robust_policy,
 138             OutputIterator out,
 139             Strategy const& strategy)
 140     {
 141         for (typename boost::range_iterator
 142                 <
 143                     MultiLinestring const
 144                 >::type it = boost::begin(ml);
 145             it != boost::end(ml);
 146             ++it)
 147         {
 148             out = intersection_of_linestring_with_areal
 149                 <
 150                     ReverseAreal, LineStringOut, OverlayType
 151                 >::apply(*it, areal, robust_policy, out, strategy);
 152         }
 153
 154         return out;
 155
 156     }
 157 };
 158
 159 // This one calls the one above with reversed arguments
 160 template
 161 <
 162     bool ReverseAreal,
 163     typename LineStringOut,
 164     overlay_type OverlayType
 165 >
 166 struct intersection_of_areal_with_multi_linestring
 167 {
 168     template
 169     <
 170         typename Areal, typename MultiLinestring,
 171         typename RobustPolicy,
 172         typename OutputIterator, typename Strategy
 173     >
 174     static inline OutputIterator apply(Areal const& areal, MultiLinestring const& ml,
 175             RobustPolicy const& robust_policy,
 176             OutputIterator out,
 177             Strategy const& strategy)
 178     {
 179         return intersection_of_multi_linestring_with_areal
 180             <
 181                 ReverseAreal, LineStringOut, OverlayType
 182             >::apply(ml, areal, robust_policy, out, strategy);
 183     }
 184 };
 185
 186
 187
 188 template <typename LinestringOut>
 189 struct clip_multi_linestring
 190 {
 191     template
 192     <
 193         typename MultiLinestring, typename Box,
 194         typename RobustPolicy,
 195         typename OutputIterator, typename Strategy
 196     >
 197     static inline OutputIterator apply(MultiLinestring const& multi_linestring,
 198             Box const& box,
 199             RobustPolicy const& robust_policy,
 200             OutputIterator out, Strategy const& )
 201     {
 202         typedef typename point_type<LinestringOut>::type point_type;
 203         strategy::intersection::liang_barsky<Box, point_type> lb_strategy;
 204         for (typename boost::range_iterator<MultiLinestring const>::type it
 205             = boost::begin(multi_linestring);
 206             it != boost::end(multi_linestring); ++it)
 207         {
 208             out = detail::intersection::clip_range_with_box
 209                 <LinestringOut>(box, *it, robust_policy, out, lb_strategy);
 210         }
 211         return out;
 212     }
 213 };
 214
 215
 216 }} // namespace detail::intersection
 217 #endif // DOXYGEN_NO_DETAIL
 218
 219
 220 #ifndef DOXYGEN_NO_DISPATCH
 221 namespace dispatch
 222 {
 223
 224
 225 // Linear
 226 template
 227 <
 228     typename MultiLinestring1, typename MultiLinestring2,
 229     typename GeometryOut,
 230     overlay_type OverlayType,
 231     bool Reverse1, bool Reverse2, bool ReverseOut
 232 >
 233 struct intersection_insert
 234     <
 235         MultiLinestring1, MultiLinestring2,
 236         GeometryOut,
 237         OverlayType,
 238         Reverse1, Reverse2, ReverseOut,
 239         multi_linestring_tag, multi_linestring_tag, point_tag,
 240         false, false, false
 241     > : detail::intersection::intersection_multi_linestring_multi_linestring_point
 242             <
 243                 GeometryOut
 244             >
 245 {};
 246
 247
 248 template
 249 <
 250     typename Linestring, typename MultiLinestring,
 251     typename GeometryOut,
 252     overlay_type OverlayType,
 253     bool Reverse1, bool Reverse2, bool ReverseOut
 254 >
 255 struct intersection_insert
 256     <
 257         Linestring, MultiLinestring,
 258         GeometryOut,
 259         OverlayType,
 260         Reverse1, Reverse2, ReverseOut,
 261         linestring_tag, multi_linestring_tag, point_tag,
 262         false, false, false
 263     > : detail::intersection::intersection_linestring_multi_linestring_point
 264             <
 265                 GeometryOut
 266             >
 267 {};
 268
 269
 270 template
 271 <
 272     typename MultiLinestring, typename Box,
 273     typename GeometryOut,
 274     overlay_type OverlayType,
 275     bool Reverse1, bool Reverse2, bool ReverseOut
 276 >
 277 struct intersection_insert
 278     <
 279         MultiLinestring, Box,
 280         GeometryOut,
 281         OverlayType,
 282         Reverse1, Reverse2, ReverseOut,
 283         multi_linestring_tag, box_tag, linestring_tag,
 284         false, true, false
 285     > : detail::intersection::clip_multi_linestring
 286             <
 287                 GeometryOut
 288             >
 289 {};
 290
 291
 292 template
 293 <
 294     typename Linestring, typename MultiPolygon,
 295     typename GeometryOut,
 296     overlay_type OverlayType,
 297     bool ReverseLinestring, bool ReverseMultiPolygon, bool ReverseOut
 298 >
 299 struct intersection_insert
 300     <
 301         Linestring, MultiPolygon,
 302         GeometryOut,
 303         OverlayType,
 304         ReverseLinestring, ReverseMultiPolygon, ReverseOut,
 305         linestring_tag, multi_polygon_tag, linestring_tag,
 306         false, true, false
 307     > : detail::intersection::intersection_of_linestring_with_areal
 308             <
 309                 ReverseMultiPolygon,
 310                 GeometryOut,
 311                 OverlayType
 312             >
 313 {};
 314
 315
 316 // Derives from areal/mls because runtime arguments are in that order.
 317 // areal/mls reverses it itself to mls/areal
 318 template
 319 <
 320     typename Polygon, typename MultiLinestring,
 321     typename GeometryOut,
 322     overlay_type OverlayType,
 323     bool ReversePolygon, bool ReverseMultiLinestring, bool ReverseOut
 324 >
 325 struct intersection_insert
 326     <
 327         Polygon, MultiLinestring,
 328         GeometryOut,
 329         OverlayType,
 330         ReversePolygon, ReverseMultiLinestring, ReverseOut,
 331         polygon_tag, multi_linestring_tag, linestring_tag,
 332         true, false, false
 333     > : detail::intersection::intersection_of_areal_with_multi_linestring
 334             <
 335                 ReversePolygon,
 336                 GeometryOut,
 337                 OverlayType
 338             >
 339 {};
 340
 341
 342 template
 343 <
 344     typename MultiLinestring, typename Ring,
 345     typename GeometryOut,
 346     overlay_type OverlayType,
 347     bool ReverseMultiLinestring, bool ReverseRing, bool ReverseOut
 348 >
 349 struct intersection_insert
 350     <
 351         MultiLinestring, Ring,
 352         GeometryOut,
 353         OverlayType,
 354         ReverseMultiLinestring, ReverseRing, ReverseOut,
 355         multi_linestring_tag, ring_tag, linestring_tag,
 356         false, true, false
 357     > : detail::intersection::intersection_of_multi_linestring_with_areal
 358             <
 359                 ReverseRing,
 360                 GeometryOut,
 361                 OverlayType
 362             >
 363 {};
 364
 365 template
 366 <
 367     typename MultiLinestring, typename Polygon,
 368     typename GeometryOut,
 369     overlay_type OverlayType,
 370     bool ReverseMultiLinestring, bool ReverseRing, bool ReverseOut
 371 >
 372 struct intersection_insert
 373     <
 374         MultiLinestring, Polygon,
 375         GeometryOut,
 376         OverlayType,
 377         ReverseMultiLinestring, ReverseRing, ReverseOut,
 378         multi_linestring_tag, polygon_tag, linestring_tag,
 379         false, true, false
 380     > : detail::intersection::intersection_of_multi_linestring_with_areal
 381             <
 382                 ReverseRing,
 383                 GeometryOut,
 384                 OverlayType
 385             >
 386 {};
 387
 388
 389
 390 template
 391 <
 392     typename MultiLinestring, typename MultiPolygon,
 393     typename GeometryOut,
 394     overlay_type OverlayType,
 395     bool ReverseMultiLinestring, bool ReverseMultiPolygon, bool ReverseOut
 396 >
 397 struct intersection_insert
 398     <
 399         MultiLinestring, MultiPolygon,
 400         GeometryOut,
 401         OverlayType,
 402         ReverseMultiLinestring, ReverseMultiPolygon, ReverseOut,
 403         multi_linestring_tag, multi_polygon_tag, linestring_tag,
 404         false, true, false
 405     > : detail::intersection::intersection_of_multi_linestring_with_areal
 406             <
 407                 ReverseMultiPolygon,
 408                 GeometryOut,
 409                 OverlayType
 410             >
 411 {};
 412
 413
 414 } // namespace dispatch
 415 #endif
 416
 417 }} // namespace boost::geometry
 418
 419
 420 #endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_INTERSECTION_MULTI_HPP
 421