Back to home page

EIC code displayed by LXR
 
 

    

File indexing completed on 2025-11-04 09:46:27 

0001 // Boost.Geometry (aka GGL, Generic Geometry Library)
0002 
0003 // Copyright (c) 2007-2015 Barend Gehrels, Amsterdam, the Netherlands.
0004 
0005 // This file was modified by Oracle on 2013-2024.
0006 // Modifications copyright (c) 2013-2024 Oracle and/or its affiliates.
0007 // Contributed and/or modified by Vissarion Fysikopoulos, on behalf of Oracle
0008 // Contributed and/or modified by Menelaos Karavelas, on behalf of Oracle
0009 // Contributed and/or modified by Adam Wulkiewicz, on behalf of Oracle
0010 
0011 // Use, modification and distribution is subject to the Boost Software License,
0012 // Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
0013 // http://www.boost.org/LICENSE_1_0.txt)
0014 
0015 #ifndef BOOST_GEOMETRY_ALGORITHMS_DETAIL_RELATE_TURNS_HPP
0016 #define BOOST_GEOMETRY_ALGORITHMS_DETAIL_RELATE_TURNS_HPP
0017 
0018 
0019 #include <boost/geometry/algorithms/detail/overlay/do_reverse.hpp>
0020 #include <boost/geometry/algorithms/detail/overlay/get_turns.hpp>
0021 #include <boost/geometry/algorithms/detail/overlay/get_turn_info.hpp>
0022 
0023 #include <boost/geometry/geometries/helper_geometry.hpp>
0024 
0025 #include <boost/geometry/strategies/cartesian/point_in_point.hpp>
0026 #include <boost/geometry/strategies/spherical/point_in_point.hpp>
0027 #include <boost/geometry/strategies/distance.hpp>
0028 
0029 
0030 namespace boost { namespace geometry {
0031 
0032 #ifndef DOXYGEN_NO_DETAIL
0033 namespace detail { namespace relate { namespace turns {
0034 
0035 template <bool IncludeDegenerate = false>
0036 struct assign_policy
0037     : overlay::assign_null_policy
0038 {
0039     static bool const include_degenerate = IncludeDegenerate;
0040 };
0041 
0042 // turn retriever, calling get_turns
0043 
0044 template
0045 <
0046     typename Geometry1,
0047     typename Geometry2,
0048     typename GetTurnPolicy = detail::get_turns::get_turn_info_type
0049         <
0050             Geometry1, Geometry2, assign_policy<>
0051         >
0052 >
0053 struct get_turns
0054 {
0055     using turn_point_type = typename helper_geometry
0056         <
0057             geometry::point_type_t<Geometry1>
0058         >::type;
0059 
0060     template
0061     <
0062         typename Strategy
0063     >
0064     struct turn_info_type
0065     {
0066         using ratio_type = typename segment_ratio_type<turn_point_type>::type;
0067         using type = overlay::turn_info
0068             <
0069                 turn_point_type,
0070                 ratio_type,
0071                 typename detail::get_turns::turn_operation_type
0072                     <
0073                         Geometry1, Geometry2, turn_point_type, ratio_type
0074                     >::type
0075             >;
0076     };
0077 
0078     template <typename Turns, typename InterruptPolicy, typename Strategy>
0079     static inline void apply(Turns & turns,
0080                              Geometry1 const& geometry1,
0081                              Geometry2 const& geometry2,
0082                              InterruptPolicy & interrupt_policy,
0083                              Strategy const& strategy)
0084     {
0085         static const bool reverse1 = detail::overlay::do_reverse
0086             <
0087                 geometry::point_order<Geometry1>::value
0088             >::value;
0089 
0090         static const bool reverse2 = detail::overlay::do_reverse
0091             <
0092                 geometry::point_order<Geometry2>::value
0093             >::value;
0094 
0095         dispatch::get_turns
0096             <
0097                 geometry::tag_t<Geometry1>,
0098                 geometry::tag_t<Geometry2>,
0099                 Geometry1,
0100                 Geometry2,
0101                 reverse1,
0102                 reverse2,
0103                 GetTurnPolicy
0104             >::apply(0, geometry1, 1, geometry2,
0105                      strategy,
0106                      turns, interrupt_policy);
0107     }
0108 };
0109 
0110 // TURNS SORTING AND SEARCHING
0111 
0112 template <int N = 0, int U = 1, int I = 2, int B = 3, int C = 4, int O = 0>
0113 struct op_to_int
0114 {
0115     template <typename Operation>
0116     inline int operator()(Operation const& op) const
0117     {
0118         switch(op.operation)
0119         {
0120         case detail::overlay::operation_none : return N;
0121         case detail::overlay::operation_union : return U;
0122         case detail::overlay::operation_intersection : return I;
0123         case detail::overlay::operation_blocked : return B;
0124         case detail::overlay::operation_continue : return C;
0125         case detail::overlay::operation_opposite : return O;
0126         }
0127         return -1;
0128     }
0129 };
0130 
0131 template <std::size_t OpId, typename OpToInt>
0132 struct less_op_xxx_linear
0133 {
0134     template <typename Turn>
0135     inline bool operator()(Turn const& left, Turn const& right) const
0136     {
0137         static OpToInt op_to_int;
0138         return op_to_int(left.operations[OpId]) < op_to_int(right.operations[OpId]);
0139     }
0140 };
0141 
0142 template <std::size_t OpId>
0143 struct less_op_linear_linear
0144     : less_op_xxx_linear< OpId, op_to_int<0,2,3,1,4,0> > // xuic
0145 {};
0146 
0147 template <std::size_t OpId>
0148 struct less_op_linear_areal_single
0149 {
0150     template <typename Turn>
0151     inline bool operator()(Turn const& left, Turn const& right) const
0152     {
0153         static const std::size_t other_op_id = (OpId + 1) % 2;
0154         static turns::op_to_int<0,2,3,1,4,0> op_to_int_xuic;
0155         static turns::op_to_int<0,3,2,1,4,0> op_to_int_xiuc;
0156 
0157         segment_identifier const& left_other_seg_id = left.operations[other_op_id].seg_id;
0158         segment_identifier const& right_other_seg_id = right.operations[other_op_id].seg_id;
0159 
0160         typedef typename Turn::turn_operation_type operation_type;
0161         operation_type const& left_operation = left.operations[OpId];
0162         operation_type const& right_operation = right.operations[OpId];
0163 
0164         if ( left_other_seg_id.ring_index == right_other_seg_id.ring_index )
0165         {
0166             return op_to_int_xuic(left_operation)
0167                  < op_to_int_xuic(right_operation);
0168         }
0169         else
0170         {
0171             return op_to_int_xiuc(left_operation)
0172                  < op_to_int_xiuc(right_operation);
0173         }
0174     }
0175 };
0176 
0177 template <std::size_t OpId>
0178 struct less_op_areal_linear
0179     : less_op_xxx_linear< OpId, op_to_int<0,1,0,0,2,0> >
0180 {};
0181 
0182 template <std::size_t OpId>
0183 struct less_op_areal_areal
0184 {
0185     template <typename Turn>
0186     inline bool operator()(Turn const& left, Turn const& right) const
0187     {
0188         static const std::size_t other_op_id = (OpId + 1) % 2;
0189         static op_to_int<0, 1, 2, 3, 4, 0> op_to_int_uixc;
0190         static op_to_int<0, 2, 1, 3, 4, 0> op_to_int_iuxc;
0191 
0192         segment_identifier const& left_other_seg_id = left.operations[other_op_id].seg_id;
0193         segment_identifier const& right_other_seg_id = right.operations[other_op_id].seg_id;
0194 
0195         typedef typename Turn::turn_operation_type operation_type;
0196         operation_type const& left_operation = left.operations[OpId];
0197         operation_type const& right_operation = right.operations[OpId];
0198 
0199         if ( left_other_seg_id.multi_index == right_other_seg_id.multi_index )
0200         {
0201             if ( left_other_seg_id.ring_index == right_other_seg_id.ring_index )
0202             {
0203                 return op_to_int_uixc(left_operation) < op_to_int_uixc(right_operation);
0204             }
0205             else
0206             {
0207                 if ( left_other_seg_id.ring_index == -1 )
0208                 {
0209                     if ( left_operation.operation == overlay::operation_union )
0210                         return false;
0211                     else if ( left_operation.operation == overlay::operation_intersection )
0212                         return true;
0213                 }
0214                 else if ( right_other_seg_id.ring_index == -1 )
0215                 {
0216                     if ( right_operation.operation == overlay::operation_union )
0217                         return true;
0218                     else if ( right_operation.operation == overlay::operation_intersection )
0219                         return false;
0220                 }
0221 
0222                 return op_to_int_iuxc(left_operation) < op_to_int_iuxc(right_operation);
0223             }
0224         }
0225         else
0226         {
0227             return op_to_int_uixc(left_operation) < op_to_int_uixc(right_operation);
0228         }
0229     }
0230 };
0231 
0232 template <std::size_t OpId>
0233 struct less_other_multi_index
0234 {
0235     static const std::size_t other_op_id = (OpId + 1) % 2;
0236 
0237     template <typename Turn>
0238     inline bool operator()(Turn const& left, Turn const& right) const
0239     {
0240         return left.operations[other_op_id].seg_id.multi_index
0241              < right.operations[other_op_id].seg_id.multi_index;
0242     }
0243 };
0244 
0245 // sort turns by G1 - source_index == 0 by:
0246 // seg_id -> distance and coordinates -> operation
0247 template <std::size_t OpId, typename LessOp, typename Strategy>
0248 struct less
0249 {
0250     BOOST_STATIC_ASSERT(OpId < 2);
0251 
0252     template <typename Turn>
0253     static inline bool use_fraction(Turn const& left, Turn const& right)
0254     {
0255         using eq_pp_strategy_type = decltype(std::declval<Strategy>().relate(
0256             detail::dummy_point(), detail::dummy_point()));
0257 
0258         static LessOp less_op;
0259 
0260         // NOTE: Assuming fraction is more permissive and faster than
0261         //       comparison of points with strategy.
0262         return geometry::math::equals(left.operations[OpId].fraction,
0263                                       right.operations[OpId].fraction)
0264                 && eq_pp_strategy_type::apply(left.point, right.point)
0265              ?
0266              less_op(left, right)
0267              :
0268              (left.operations[OpId].fraction < right.operations[OpId].fraction)
0269              ;
0270     }
0271 
0272     template <typename Turn>
0273     inline bool operator()(Turn const& left, Turn const& right) const
0274     {
0275         segment_identifier const& sl = left.operations[OpId].seg_id;
0276         segment_identifier const& sr = right.operations[OpId].seg_id;
0277 
0278         return sl < sr || ( sl == sr && use_fraction(left, right) );
0279     }
0280 };
0281 
0282 }}} // namespace detail::relate::turns
0283 #endif // DOXYGEN_NO_DETAIL
0284 
0285 }} // namespace boost::geometry
0286 
0287 #endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_RELATE_TURNS_HPP
[ Source navigation ] [ Diff markup ] [ Identifier search ] [ general search ]

This page was automatically generated by the 2.3.7 LXR engine.

The LXR team
Valid CSS 2.1! Valid HTML 4.01!