ceph/src/boost/boost/geometry/algorithms/detail/overlay/linear_linear.hpp

   1 // Boost.Geometry (aka GGL, Generic Geometry Library)
   2
   3 // Copyright (c) 2014-2020, Oracle and/or its affiliates.
   4 // Contributed and/or modified by Menelaos Karavelas, on behalf of Oracle
   5 // Contributed and/or modified by Adam Wulkiewicz, on behalf of Oracle
   6
   7 // Licensed under the Boost Software License version 1.0.
   8 // http://www.boost.org/users/license.html
   9
  10 #ifndef BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_LINEAR_LINEAR_HPP
  11 #define BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_LINEAR_LINEAR_HPP
  12
  13 #include <algorithm>
  14 #include <vector>
  15
  16 #include <boost/range/begin.hpp>
  17 #include <boost/range/end.hpp>
  18
  19 #include <boost/geometry/core/tag.hpp>
  20 #include <boost/geometry/core/tags.hpp>
  21
  22 #include <boost/geometry/algorithms/detail/relate/turns.hpp>
  23
  24 #include <boost/geometry/algorithms/detail/turns/compare_turns.hpp>
  25 #include <boost/geometry/algorithms/detail/turns/filter_continue_turns.hpp>
  26 #include <boost/geometry/algorithms/detail/turns/remove_duplicate_turns.hpp>
  27
  28 #include <boost/geometry/algorithms/detail/overlay/overlay_type.hpp>
  29 #include <boost/geometry/algorithms/detail/overlay/follow_linear_linear.hpp>
  30
  31 #include <boost/geometry/algorithms/convert.hpp>
  32
  33
  34
  35 namespace boost { namespace geometry
  36 {
  37
  38
  39 #ifndef DOXYGEN_NO_DETAIL
  40 namespace detail { namespace overlay
  41 {
  42
  43
  44 template
  45 <
  46     typename LineStringOut,
  47     overlay_type OverlayType,
  48     typename Geometry,
  49     typename GeometryTag
  50 >
  51 struct linear_linear_no_intersections;
  52
  53
  54 template <typename LineStringOut, typename LineString>
  55 struct linear_linear_no_intersections
  56     <
  57         LineStringOut, overlay_difference, LineString, linestring_tag
  58     >
  59 {
  60     template <typename OutputIterator>
  61     static inline OutputIterator apply(LineString const& linestring,
  62                                        OutputIterator oit)
  63     {
  64         LineStringOut ls_out;
  65         geometry::convert(linestring, ls_out);
  66         *oit++ = ls_out;
  67         return oit;
  68     }
  69 };
  70
  71
  72 template <typename LineStringOut, typename MultiLineString>
  73 struct linear_linear_no_intersections
  74     <
  75         LineStringOut,
  76         overlay_difference,
  77         MultiLineString,
  78         multi_linestring_tag
  79     >
  80 {
  81     template <typename OutputIterator>
  82     static inline OutputIterator apply(MultiLineString const& multilinestring,
  83                                        OutputIterator oit)
  84     {
  85         for (typename boost::range_iterator<MultiLineString const>::type
  86                  it = boost::begin(multilinestring);
  87              it != boost::end(multilinestring); ++it)
  88         {
  89             LineStringOut ls_out;
  90             geometry::convert(*it, ls_out);
  91             *oit++ = ls_out;
  92         }
  93         return oit;
  94     }
  95 };
  96
  97
  98 template <typename LineStringOut, typename Geometry, typename GeometryTag>
  99 struct linear_linear_no_intersections
 100     <
 101         LineStringOut, overlay_intersection, Geometry, GeometryTag
 102     >
 103 {
 104     template <typename OutputIterator>
 105     static inline OutputIterator apply(Geometry const&,
 106                                        OutputIterator oit)
 107     {
 108         return oit;
 109     }
 110 };
 111
 112
 113
 114
 115
 116
 117
 118 template
 119 <
 120     typename Linear1,
 121     typename Linear2,
 122     typename LinestringOut,
 123     overlay_type OverlayType,
 124     bool EnableFilterContinueTurns = false,
 125     bool EnableRemoveDuplicateTurns = false,
 126     bool EnableDegenerateTurns = true,
 127 #ifdef BOOST_GEOMETRY_INTERSECTION_DO_NOT_INCLUDE_ISOLATED_POINTS
 128     bool EnableFollowIsolatedPoints = false
 129 #else
 130     bool EnableFollowIsolatedPoints = true
 131 #endif
 132 >
 133 class linear_linear_linestring
 134 {
 135 protected:
 136     struct assign_policy
 137     {
 138         static bool const include_no_turn = false;
 139         static bool const include_degenerate = EnableDegenerateTurns;
 140         static bool const include_opposite = false;
 141         static bool const include_start_turn = false;
 142     };
 143
 144
 145     template
 146     <
 147         typename Turns,
 148         typename LinearGeometry1,
 149         typename LinearGeometry2,
 150         typename Strategy,
 151         typename RobustPolicy
 152     >
 153     static inline void compute_turns(Turns& turns,
 154                                      LinearGeometry1 const& linear1,
 155                                      LinearGeometry2 const& linear2,
 156                                      Strategy const& strategy,
 157                                      RobustPolicy const& robust_policy)
 158     {
 159         turns.clear();
 160
 161         detail::get_turns::no_interrupt_policy interrupt_policy;
 162
 163         geometry::detail::relate::turns::get_turns
 164             <
 165                 LinearGeometry1,
 166                 LinearGeometry2,
 167                 detail::get_turns::get_turn_info_type
 168                 <
 169                     LinearGeometry1,
 170                     LinearGeometry2,
 171                     assign_policy
 172                 >
 173             >::apply(turns, linear1, linear2, interrupt_policy, strategy, robust_policy);
 174     }
 175
 176
 177     template
 178     <
 179         overlay_type OverlayTypeForFollow,
 180         bool FollowIsolatedPoints,
 181         typename Turns,
 182         typename LinearGeometry1,
 183         typename LinearGeometry2,
 184         typename OutputIterator,
 185         typename Strategy
 186     >
 187     static inline OutputIterator
 188     sort_and_follow_turns(Turns& turns,
 189                           LinearGeometry1 const& linear1,
 190                           LinearGeometry2 const& linear2,
 191                           OutputIterator oit,
 192                           Strategy const& strategy)
 193     {
 194         // remove turns that have no added value
 195         turns::filter_continue_turns
 196             <
 197                 Turns,
 198                 EnableFilterContinueTurns && OverlayType != overlay_intersection
 199             >::apply(turns);
 200
 201         // sort by seg_id, distance, and operation
 202         std::sort(boost::begin(turns), boost::end(turns),
 203                   detail::turns::less_seg_fraction_other_op<>());
 204
 205         // remove duplicate turns
 206         turns::remove_duplicate_turns
 207             <
 208                 Turns, EnableRemoveDuplicateTurns
 209             >::apply(turns);
 210
 211         return detail::overlay::following::linear::follow
 212             <
 213                 LinestringOut,
 214                 LinearGeometry1,
 215                 LinearGeometry2,
 216                 OverlayTypeForFollow,
 217                 FollowIsolatedPoints,
 218                 !EnableFilterContinueTurns || OverlayType == overlay_intersection
 219             >::apply(linear1, linear2, boost::begin(turns), boost::end(turns),
 220                      oit, strategy);
 221     }
 222
 223 public:
 224     template
 225     <
 226         typename RobustPolicy, typename OutputIterator, typename Strategy
 227     >
 228     static inline OutputIterator apply(Linear1 const& linear1,
 229                                        Linear2 const& linear2,
 230                                        RobustPolicy const& robust_policy,
 231                                        OutputIterator oit,
 232                                        Strategy const& strategy)
 233     {
 234         typedef typename detail::relate::turns::get_turns
 235             <
 236                 Linear1,
 237                 Linear2,
 238                 detail::get_turns::get_turn_info_type
 239                     <
 240                         Linear1,
 241                         Linear2,
 242                         assign_policy
 243                     >
 244             >::template turn_info_type<Strategy, RobustPolicy>::type turn_info;
 245
 246         typedef std::vector<turn_info> turns_container;
 247
 248         turns_container turns;
 249         compute_turns(turns, linear1, linear2, strategy, robust_policy);
 250
 251         if ( turns.empty() )
 252         {
 253             // the two linear geometries are disjoint
 254             return linear_linear_no_intersections
 255                 <
 256                     LinestringOut,
 257                     OverlayType,
 258                     Linear1,
 259                     typename tag<Linear1>::type
 260                 >::apply(linear1, oit);
 261         }
 262
 263         return sort_and_follow_turns
 264             <
 265                 OverlayType,
 266                 EnableFollowIsolatedPoints
 267                 && OverlayType == overlay_intersection
 268             >(turns, linear1, linear2, oit, strategy);
 269     }
 270 };
 271
 272
 273
 274
 275 template
 276 <
 277     typename Linear1,
 278     typename Linear2,
 279     typename LinestringOut,
 280     bool EnableFilterContinueTurns,
 281     bool EnableRemoveDuplicateTurns,
 282     bool EnableDegenerateTurns,
 283     bool EnableFollowIsolatedPoints
 284 >
 285 struct linear_linear_linestring
 286     <
 287         Linear1, Linear2, LinestringOut, overlay_union,
 288         EnableFilterContinueTurns, EnableRemoveDuplicateTurns,
 289         EnableDegenerateTurns, EnableFollowIsolatedPoints
 290     >
 291 {
 292     template
 293     <
 294         typename RobustPolicy, typename OutputIterator, typename Strategy
 295     >
 296     static inline OutputIterator apply(Linear1 const& linear1,
 297                                        Linear2 const& linear2,
 298                                        RobustPolicy const& robust_policy,
 299                                        OutputIterator oit,
 300                                        Strategy const& strategy)
 301     {
 302         oit = linear_linear_no_intersections
 303             <
 304                 LinestringOut,
 305                 overlay_difference,
 306                 Linear1,
 307                 typename tag<Linear1>::type
 308             >::apply(linear1, oit);
 309
 310         return linear_linear_linestring
 311             <
 312                 Linear2, Linear1, LinestringOut, overlay_difference,
 313                 EnableFilterContinueTurns, EnableRemoveDuplicateTurns,
 314                 EnableDegenerateTurns, EnableFollowIsolatedPoints
 315             >::apply(linear2, linear1, robust_policy, oit, strategy);
 316     }
 317 };
 318
 319
 320
 321
 322 }} // namespace detail::overlay
 323 #endif // DOXYGEN_NO_DETAIL
 324
 325
 326 }} // namespace boost::geometry
 327
 328
 329
 330 #endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_LINEAR_LINEAR_HPP