detail/overlay/linear_linear.hpp

0001 // Boost.Geometry (aka GGL, Generic Geometry Library)
0002
0003 // Copyright (c) 2014-2022, Oracle and/or its affiliates.
0004 // Contributed and/or modified by Menelaos Karavelas, on behalf of Oracle
0005 // Contributed and/or modified by Adam Wulkiewicz, on behalf of Oracle
0006
0007 // Licensed under the Boost Software License version 1.0.
0008 // http://www.boost.org/users/license.html
0009
0010 #ifndef BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_LINEAR_LINEAR_HPP
0011 #define BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_LINEAR_LINEAR_HPP
0012
0013 #include <algorithm>
0014 #include <vector>
0015
0016 #include <boost/range/begin.hpp>
0017 #include <boost/range/end.hpp>
0018
0019 #include <boost/geometry/core/tag.hpp>
0020 #include <boost/geometry/core/tags.hpp>
0021
0022 #include <boost/geometry/algorithms/detail/relate/turns.hpp>
0023
0024 #include <boost/geometry/algorithms/detail/turns/compare_turns.hpp>
0025 #include <boost/geometry/algorithms/detail/turns/filter_continue_turns.hpp>
0026 #include <boost/geometry/algorithms/detail/turns/remove_duplicate_turns.hpp>
0027
0028 #include <boost/geometry/algorithms/detail/overlay/overlay_type.hpp>
0029 #include <boost/geometry/algorithms/detail/overlay/follow_linear_linear.hpp>
0030
0031 #include <boost/geometry/algorithms/convert.hpp>
0032
0033 #include <boost/geometry/geometries/helper_geometry.hpp>
0034
0035 namespace boost { namespace geometry
0036 {
0037
0038
0039 #ifndef DOXYGEN_NO_DETAIL
0040 namespace detail { namespace overlay
0041 {
0042
0043
0044 template
0045 <
0046     typename LineStringOut,
0047     overlay_type OverlayType,
0048     typename Geometry,
0049     typename GeometryTag
0050 >
0051 struct linear_linear_no_intersections;
0052
0053
0054 template <typename LineStringOut, typename LineString>
0055 struct linear_linear_no_intersections
0056     <
0057         LineStringOut, overlay_difference, LineString, linestring_tag
0058     >
0059 {
0060     template <typename OutputIterator>
0061     static inline OutputIterator apply(LineString const& linestring,
0062                                        OutputIterator oit)
0063     {
0064         LineStringOut ls_out;
0065         geometry::convert(linestring, ls_out);
0066         *oit++ = ls_out;
0067         return oit;
0068     }
0069 };
0070
0071
0072 template <typename LineStringOut, typename MultiLineString>
0073 struct linear_linear_no_intersections
0074     <
0075         LineStringOut,
0076         overlay_difference,
0077         MultiLineString,
0078         multi_linestring_tag
0079     >
0080 {
0081     template <typename OutputIterator>
0082     static inline OutputIterator apply(MultiLineString const& multilinestring,
0083                                        OutputIterator oit)
0084     {
0085         for (auto it = boost::begin(multilinestring); it != boost::end(multilinestring); ++it)
0086         {
0087             LineStringOut ls_out;
0088             geometry::convert(*it, ls_out);
0089             *oit++ = ls_out;
0090         }
0091         return oit;
0092     }
0093 };
0094
0095
0096 template <typename LineStringOut, typename Geometry, typename GeometryTag>
0097 struct linear_linear_no_intersections
0098     <
0099         LineStringOut, overlay_intersection, Geometry, GeometryTag
0100     >
0101 {
0102     template <typename OutputIterator>
0103     static inline OutputIterator apply(Geometry const&,
0104                                        OutputIterator oit)
0105     {
0106         return oit;
0107     }
0108 };
0109
0110
0111
0112
0113
0114
0115
0116 template
0117 <
0118     typename Linear1,
0119     typename Linear2,
0120     typename LinestringOut,
0121     overlay_type OverlayType,
0122     bool EnableFilterContinueTurns = false,
0123     bool EnableRemoveDuplicateTurns = false,
0124     bool EnableDegenerateTurns = true,
0125 #ifdef BOOST_GEOMETRY_INTERSECTION_DO_NOT_INCLUDE_ISOLATED_POINTS
0126     bool EnableFollowIsolatedPoints = false
0127 #else
0128     bool EnableFollowIsolatedPoints = true
0129 #endif
0130 >
0131 class linear_linear_linestring
0132 {
0133 protected:
0134     struct assign_policy
0135     {
0136         static bool const include_no_turn = false;
0137         static bool const include_degenerate = EnableDegenerateTurns;
0138         static bool const include_opposite = false;
0139         static bool const include_start_turn = false;
0140     };
0141
0142
0143     template
0144     <
0145         typename Turns,
0146         typename LinearGeometry1,
0147         typename LinearGeometry2,
0148         typename Strategy,
0149         typename RobustPolicy
0150     >
0151     static inline void compute_turns(Turns& turns,
0152                                      LinearGeometry1 const& linear1,
0153                                      LinearGeometry2 const& linear2,
0154                                      Strategy const& strategy,
0155                                      RobustPolicy const& robust_policy)
0156     {
0157         turns.clear();
0158
0159         detail::get_turns::no_interrupt_policy interrupt_policy;
0160
0161         geometry::detail::relate::turns::get_turns
0162             <
0163                 LinearGeometry1,
0164                 LinearGeometry2,
0165                 detail::get_turns::get_turn_info_type
0166                 <
0167                     LinearGeometry1,
0168                     LinearGeometry2,
0169                     assign_policy
0170                 >
0171             >::apply(turns, linear1, linear2, interrupt_policy, strategy, robust_policy);
0172     }
0173
0174
0175     template
0176     <
0177         overlay_type OverlayTypeForFollow,
0178         bool FollowIsolatedPoints,
0179         typename Turns,
0180         typename LinearGeometry1,
0181         typename LinearGeometry2,
0182         typename OutputIterator,
0183         typename Strategy
0184     >
0185     static inline OutputIterator
0186     sort_and_follow_turns(Turns& turns,
0187                           LinearGeometry1 const& linear1,
0188                           LinearGeometry2 const& linear2,
0189                           OutputIterator oit,
0190                           Strategy const& strategy)
0191     {
0192         // remove turns that have no added value
0193         turns::filter_continue_turns
0194             <
0195                 Turns,
0196                 EnableFilterContinueTurns && OverlayType != overlay_intersection
0197             >::apply(turns);
0198
0199         // sort by seg_id, distance, and operation
0200         std::sort(boost::begin(turns), boost::end(turns),
0201                   detail::turns::less_seg_fraction_other_op<>());
0202
0203         // remove duplicate turns
0204         turns::remove_duplicate_turns
0205             <
0206                 Turns, EnableRemoveDuplicateTurns
0207             >::apply(turns, strategy);
0208
0209         return detail::overlay::following::linear::follow
0210             <
0211                 LinestringOut,
0212                 LinearGeometry1,
0213                 LinearGeometry2,
0214                 OverlayTypeForFollow,
0215                 FollowIsolatedPoints,
0216                 !EnableFilterContinueTurns || OverlayType == overlay_intersection
0217             >::apply(linear1, linear2, boost::begin(turns), boost::end(turns),
0218                      oit, strategy);
0219     }
0220
0221 public:
0222     template
0223     <
0224         typename RobustPolicy, typename OutputIterator, typename Strategy
0225     >
0226     static inline OutputIterator apply(Linear1 const& linear1,
0227                                        Linear2 const& linear2,
0228                                        RobustPolicy const& robust_policy,
0229                                        OutputIterator oit,
0230                                        Strategy const& strategy)
0231     {
0232         typedef typename detail::relate::turns::get_turns
0233             <
0234                 Linear1,
0235                 Linear2,
0236                 detail::get_turns::get_turn_info_type
0237                     <
0238                         Linear1,
0239                         Linear2,
0240                         assign_policy
0241                     >
0242             >::template turn_info_type<Strategy, RobustPolicy>::type turn_info;
0243
0244         typedef std::vector<turn_info> turns_container;
0245
0246         turns_container turns;
0247         compute_turns(turns, linear1, linear2, strategy, robust_policy);
0248
0249         if ( turns.empty() )
0250         {
0251             // the two linear geometries are disjoint
0252             return linear_linear_no_intersections
0253                 <
0254                     LinestringOut,
0255                     OverlayType,
0256                     Linear1,
0257                     typename tag<Linear1>::type
0258                 >::apply(linear1, oit);
0259         }
0260
0261         return sort_and_follow_turns
0262             <
0263                 OverlayType,
0264                 EnableFollowIsolatedPoints
0265                 && OverlayType == overlay_intersection
0266             >(turns, linear1, linear2, oit, strategy);
0267     }
0268 };
0269
0270
0271
0272
0273 template
0274 <
0275     typename Linear1,
0276     typename Linear2,
0277     typename LinestringOut,
0278     bool EnableFilterContinueTurns,
0279     bool EnableRemoveDuplicateTurns,
0280     bool EnableDegenerateTurns,
0281     bool EnableFollowIsolatedPoints
0282 >
0283 struct linear_linear_linestring
0284     <
0285         Linear1, Linear2, LinestringOut, overlay_union,
0286         EnableFilterContinueTurns, EnableRemoveDuplicateTurns,
0287         EnableDegenerateTurns, EnableFollowIsolatedPoints
0288     >
0289 {
0290     template
0291     <
0292         typename RobustPolicy, typename OutputIterator, typename Strategy
0293     >
0294     static inline OutputIterator apply(Linear1 const& linear1,
0295                                        Linear2 const& linear2,
0296                                        RobustPolicy const& robust_policy,
0297                                        OutputIterator oit,
0298                                        Strategy const& strategy)
0299     {
0300         oit = linear_linear_no_intersections
0301             <
0302                 LinestringOut,
0303                 overlay_difference,
0304                 Linear1,
0305                 typename tag<Linear1>::type
0306             >::apply(linear1, oit);
0307
0308         return linear_linear_linestring
0309             <
0310                 Linear2, Linear1, LinestringOut, overlay_difference,
0311                 EnableFilterContinueTurns, EnableRemoveDuplicateTurns,
0312                 EnableDegenerateTurns, EnableFollowIsolatedPoints
0313             >::apply(linear2, linear1, robust_policy, oit, strategy);
0314     }
0315 };
0316
0317
0318
0319
0320 }} // namespace detail::overlay
0321 #endif // DOXYGEN_NO_DETAIL
0322
0323
0324 }} // namespace boost::geometry
0325
0326
0327
0328 #endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_LINEAR_LINEAR_HPP