detail/overlay/linear_linear.hpp

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