Back to home page

EIC code displayed by LXR
 
 

    

File indexing completed on 2025-01-18 09:35:16 

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-2022.
0006 // Modifications copyright (c) 2013-2022 Oracle and/or its affiliates.
0007 
0008 // Contributed and/or modified by Adam Wulkiewicz, on behalf of Oracle
0009 // Contributed and/or modified by Menelaos Karavelas, 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/policies/robustness/get_rescale_policy.hpp>
0026 #include <boost/geometry/policies/robustness/segment_ratio_type.hpp>
0027 
0028 #include <boost/geometry/strategies/cartesian/point_in_point.hpp>
0029 #include <boost/geometry/strategies/spherical/point_in_point.hpp>
0030 #include <boost/geometry/strategies/distance.hpp>
0031 
0032 
0033 namespace boost { namespace geometry {
0034 
0035 #ifndef DOXYGEN_NO_DETAIL
0036 namespace detail { namespace relate { namespace turns {
0037 
0038 template <bool IncludeDegenerate = false>
0039 struct assign_policy
0040     : overlay::assign_null_policy
0041 {
0042     static bool const include_degenerate = IncludeDegenerate;
0043 };
0044 
0045 // turn retriever, calling get_turns
0046 
0047 template
0048 <
0049     typename Geometry1,
0050     typename Geometry2,
0051     typename GetTurnPolicy = detail::get_turns::get_turn_info_type
0052         <
0053             Geometry1, Geometry2, assign_policy<>
0054         >
0055 >
0056 struct get_turns
0057 {
0058     using turn_point_type = typename helper_geometry
0059         <
0060             typename geometry::point_type<Geometry1>::type
0061         >::type;
0062 
0063     template <typename Strategy>
0064     struct robust_policy_type
0065         : geometry::rescale_overlay_policy_type
0066             <
0067                 Geometry1,
0068                 Geometry2,
0069                 typename Strategy::cs_tag
0070             >
0071     {};
0072 
0073     template
0074     <
0075         typename Strategy,
0076         typename RobustPolicy = typename robust_policy_type<Strategy>::type
0077     >
0078     struct turn_info_type
0079     {
0080         using ratio_type = typename segment_ratio_type<turn_point_type, RobustPolicy>::type;
0081         using type = overlay::turn_info
0082             <
0083                 turn_point_type,
0084                 ratio_type,
0085                 typename detail::get_turns::turn_operation_type
0086                     <
0087                         Geometry1, Geometry2, turn_point_type, ratio_type
0088                     >::type
0089             >;
0090     };
0091 
0092     template <typename Turns, typename InterruptPolicy, typename Strategy>
0093     static inline void apply(Turns & turns,
0094                              Geometry1 const& geometry1,
0095                              Geometry2 const& geometry2,
0096                              InterruptPolicy & interrupt_policy,
0097                              Strategy const& strategy)
0098     {
0099         typedef typename robust_policy_type<Strategy>::type robust_policy_t;
0100 
0101         robust_policy_t robust_policy
0102                 = geometry::get_rescale_policy<robust_policy_t>(
0103                     geometry1, geometry2, strategy);
0104 
0105         apply(turns, geometry1, geometry2, interrupt_policy, strategy, robust_policy);
0106     }
0107 
0108     template <typename Turns, typename InterruptPolicy, typename Strategy, typename RobustPolicy>
0109     static inline void apply(Turns & turns,
0110                              Geometry1 const& geometry1,
0111                              Geometry2 const& geometry2,
0112                              InterruptPolicy & interrupt_policy,
0113                              Strategy const& strategy,
0114                              RobustPolicy const& robust_policy)
0115     {
0116         static const bool reverse1 = detail::overlay::do_reverse
0117             <
0118                 geometry::point_order<Geometry1>::value
0119             >::value;
0120 
0121         static const bool reverse2 = detail::overlay::do_reverse
0122             <
0123                 geometry::point_order<Geometry2>::value
0124             >::value;
0125 
0126         dispatch::get_turns
0127             <
0128                 typename geometry::tag<Geometry1>::type,
0129                 typename geometry::tag<Geometry2>::type,
0130                 Geometry1,
0131                 Geometry2,
0132                 reverse1,
0133                 reverse2,
0134                 GetTurnPolicy
0135             >::apply(0, geometry1, 1, geometry2,
0136                      strategy, robust_policy,
0137                      turns, interrupt_policy);
0138     }
0139 };
0140 
0141 // TURNS SORTING AND SEARCHING
0142 
0143 template <int N = 0, int U = 1, int I = 2, int B = 3, int C = 4, int O = 0>
0144 struct op_to_int
0145 {
0146     template <typename Operation>
0147     inline int operator()(Operation const& op) const
0148     {
0149         switch(op.operation)
0150         {
0151         case detail::overlay::operation_none : return N;
0152         case detail::overlay::operation_union : return U;
0153         case detail::overlay::operation_intersection : return I;
0154         case detail::overlay::operation_blocked : return B;
0155         case detail::overlay::operation_continue : return C;
0156         case detail::overlay::operation_opposite : return O;
0157         }
0158         return -1;
0159     }
0160 };
0161 
0162 template <std::size_t OpId, typename OpToInt>
0163 struct less_op_xxx_linear
0164 {
0165     template <typename Turn>
0166     inline bool operator()(Turn const& left, Turn const& right) const
0167     {
0168         static OpToInt op_to_int;
0169         return op_to_int(left.operations[OpId]) < op_to_int(right.operations[OpId]);
0170     }
0171 };
0172 
0173 template <std::size_t OpId>
0174 struct less_op_linear_linear
0175     : less_op_xxx_linear< OpId, op_to_int<0,2,3,1,4,0> > // xuic
0176 {};
0177 
0178 template <std::size_t OpId>
0179 struct less_op_linear_areal_single
0180 {
0181     template <typename Turn>
0182     inline bool operator()(Turn const& left, Turn const& right) const
0183     {
0184         static const std::size_t other_op_id = (OpId + 1) % 2;
0185         static turns::op_to_int<0,2,3,1,4,0> op_to_int_xuic;
0186         static turns::op_to_int<0,3,2,1,4,0> op_to_int_xiuc;
0187 
0188         segment_identifier const& left_other_seg_id = left.operations[other_op_id].seg_id;
0189         segment_identifier const& right_other_seg_id = right.operations[other_op_id].seg_id;
0190 
0191         typedef typename Turn::turn_operation_type operation_type;
0192         operation_type const& left_operation = left.operations[OpId];
0193         operation_type const& right_operation = right.operations[OpId];
0194 
0195         if ( left_other_seg_id.ring_index == right_other_seg_id.ring_index )
0196         {
0197             return op_to_int_xuic(left_operation)
0198                  < op_to_int_xuic(right_operation);
0199         }
0200         else
0201         {
0202             return op_to_int_xiuc(left_operation)
0203                  < op_to_int_xiuc(right_operation);
0204         }
0205     }
0206 };
0207 
0208 template <std::size_t OpId>
0209 struct less_op_areal_linear
0210     : less_op_xxx_linear< OpId, op_to_int<0,1,0,0,2,0> >
0211 {};
0212 
0213 template <std::size_t OpId>
0214 struct less_op_areal_areal
0215 {
0216     template <typename Turn>
0217     inline bool operator()(Turn const& left, Turn const& right) const
0218     {
0219         static const std::size_t other_op_id = (OpId + 1) % 2;
0220         static op_to_int<0, 1, 2, 3, 4, 0> op_to_int_uixc;
0221         static op_to_int<0, 2, 1, 3, 4, 0> op_to_int_iuxc;
0222 
0223         segment_identifier const& left_other_seg_id = left.operations[other_op_id].seg_id;
0224         segment_identifier const& right_other_seg_id = right.operations[other_op_id].seg_id;
0225 
0226         typedef typename Turn::turn_operation_type operation_type;
0227         operation_type const& left_operation = left.operations[OpId];
0228         operation_type const& right_operation = right.operations[OpId];
0229 
0230         if ( left_other_seg_id.multi_index == right_other_seg_id.multi_index )
0231         {
0232             if ( left_other_seg_id.ring_index == right_other_seg_id.ring_index )
0233             {
0234                 return op_to_int_uixc(left_operation) < op_to_int_uixc(right_operation);
0235             }
0236             else
0237             {
0238                 if ( left_other_seg_id.ring_index == -1 )
0239                 {
0240                     if ( left_operation.operation == overlay::operation_union )
0241                         return false;
0242                     else if ( left_operation.operation == overlay::operation_intersection )
0243                         return true;
0244                 }
0245                 else if ( right_other_seg_id.ring_index == -1 )
0246                 {
0247                     if ( right_operation.operation == overlay::operation_union )
0248                         return true;
0249                     else if ( right_operation.operation == overlay::operation_intersection )
0250                         return false;
0251                 }
0252 
0253                 return op_to_int_iuxc(left_operation) < op_to_int_iuxc(right_operation);
0254             }
0255         }
0256         else
0257         {
0258             return op_to_int_uixc(left_operation) < op_to_int_uixc(right_operation);
0259         }
0260     }
0261 };
0262 
0263 template <std::size_t OpId>
0264 struct less_other_multi_index
0265 {
0266     static const std::size_t other_op_id = (OpId + 1) % 2;
0267 
0268     template <typename Turn>
0269     inline bool operator()(Turn const& left, Turn const& right) const
0270     {
0271         return left.operations[other_op_id].seg_id.multi_index
0272              < right.operations[other_op_id].seg_id.multi_index;
0273     }
0274 };
0275 
0276 // sort turns by G1 - source_index == 0 by:
0277 // seg_id -> distance and coordinates -> operation
0278 template <std::size_t OpId, typename LessOp, typename Strategy>
0279 struct less
0280 {
0281     BOOST_STATIC_ASSERT(OpId < 2);
0282 
0283     template <typename Turn>
0284     static inline bool use_fraction(Turn const& left, Turn const& right)
0285     {
0286         using eq_pp_strategy_type = decltype(std::declval<Strategy>().relate(
0287             detail::dummy_point(), detail::dummy_point()));
0288 
0289         static LessOp less_op;
0290 
0291         // NOTE: Assuming fraction is more permissive and faster than
0292         //       comparison of points with strategy.
0293         return geometry::math::equals(left.operations[OpId].fraction,
0294                                       right.operations[OpId].fraction)
0295                 && eq_pp_strategy_type::apply(left.point, right.point)
0296              ?
0297              less_op(left, right)
0298              :
0299              (left.operations[OpId].fraction < right.operations[OpId].fraction)
0300              ;
0301     }
0302 
0303     template <typename Turn>
0304     inline bool operator()(Turn const& left, Turn const& right) const
0305     {
0306         segment_identifier const& sl = left.operations[OpId].seg_id;
0307         segment_identifier const& sr = right.operations[OpId].seg_id;
0308 
0309         return sl < sr || ( sl == sr && use_fraction(left, right) );
0310     }
0311 };
0312 
0313 }}} // namespace detail::relate::turns
0314 #endif // DOXYGEN_NO_DETAIL
0315 
0316 }} // namespace boost::geometry
0317 
0318 #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!