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

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