Chris@102: // Boost.Geometry (aka GGL, Generic Geometry Library)
Chris@102: 
Chris@102: // Copyright (c) 2007-2015 Barend Gehrels, Amsterdam, the Netherlands.
Chris@102: 
Chris@102: // This file was modified by Oracle on 2013, 2014, 2015.
Chris@102: // Modifications copyright (c) 2013-2015 Oracle and/or its affiliates.
Chris@102: 
Chris@102: // Contributed and/or modified by Adam Wulkiewicz, on behalf of Oracle
Chris@102: // Contributed and/or modified by Menelaos Karavelas, on behalf of Oracle
Chris@102: 
Chris@102: // Use, modification and distribution is subject to the Boost Software License,
Chris@102: // Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
Chris@102: // http://www.boost.org/LICENSE_1_0.txt)
Chris@102: 
Chris@102: #ifndef BOOST_GEOMETRY_ALGORITHMS_DETAIL_RELATE_TURNS_HPP
Chris@102: #define BOOST_GEOMETRY_ALGORITHMS_DETAIL_RELATE_TURNS_HPP
Chris@102: 
Chris@102: #include <boost/geometry/strategies/distance.hpp>
Chris@102: #include <boost/geometry/algorithms/detail/overlay/do_reverse.hpp>
Chris@102: #include <boost/geometry/algorithms/detail/overlay/get_turns.hpp>
Chris@102: #include <boost/geometry/algorithms/detail/overlay/get_turn_info.hpp>
Chris@102: 
Chris@102: #include <boost/geometry/policies/robustness/get_rescale_policy.hpp>
Chris@102: #include <boost/geometry/policies/robustness/no_rescale_policy.hpp>
Chris@102: 
Chris@102: #include <boost/type_traits/is_base_of.hpp>
Chris@102: 
Chris@102: 
Chris@102: namespace boost { namespace geometry {
Chris@102: 
Chris@102: #ifndef DOXYGEN_NO_DETAIL
Chris@102: namespace detail { namespace relate { namespace turns {
Chris@102: 
Chris@102: template <bool IncludeDegenerate = false>
Chris@102: struct assign_policy
Chris@102:     : overlay::assign_null_policy
Chris@102: {
Chris@102:     static bool const include_degenerate = IncludeDegenerate;
Chris@102: };
Chris@102: 
Chris@102: // GET_TURNS
Chris@102: 
Chris@102: template
Chris@102: <
Chris@102:     typename Geometry1,
Chris@102:     typename Geometry2,
Chris@102:     typename GetTurnPolicy = detail::get_turns::get_turn_info_type
Chris@102:         <
Chris@102:             Geometry1, Geometry2, assign_policy<>
Chris@102:         >,
Chris@102:     typename RobustPolicy = detail::no_rescale_policy
Chris@102: >
Chris@102: struct get_turns
Chris@102: {
Chris@102:     typedef typename geometry::point_type<Geometry1>::type point1_type;
Chris@102: 
Chris@102:     typedef overlay::turn_info
Chris@102:             <
Chris@102:                 point1_type,
Chris@102:                 typename segment_ratio_type<point1_type, RobustPolicy>::type,
Chris@102:                 typename detail::get_turns::turn_operation_type
Chris@102:                     <
Chris@102:                         Geometry1, Geometry2,
Chris@102:                         typename segment_ratio_type
Chris@102:                             <
Chris@102:                                 point1_type, RobustPolicy
Chris@102:                             >::type
Chris@102:                     >::type
Chris@102:             > turn_info;
Chris@102: 
Chris@102:     template <typename Turns>
Chris@102:     static inline void apply(Turns & turns,
Chris@102:                              Geometry1 const& geometry1,
Chris@102:                              Geometry2 const& geometry2)
Chris@102:     {
Chris@102:         detail::get_turns::no_interrupt_policy interrupt_policy;
Chris@102: 
Chris@102:         apply(turns, geometry1, geometry2, interrupt_policy);
Chris@102:     }
Chris@102: 
Chris@102:     template <typename Turns, typename InterruptPolicy>
Chris@102:     static inline void apply(Turns & turns,
Chris@102:                              Geometry1 const& geometry1,
Chris@102:                              Geometry2 const& geometry2,
Chris@102:                              InterruptPolicy & interrupt_policy)
Chris@102:     {
Chris@102:         static const bool reverse1 = detail::overlay::do_reverse<geometry::point_order<Geometry1>::value>::value;
Chris@102:         static const bool reverse2 = detail::overlay::do_reverse<geometry::point_order<Geometry2>::value>::value;
Chris@102: 
Chris@102:         RobustPolicy robust_policy = geometry::get_rescale_policy
Chris@102:             <
Chris@102:                 RobustPolicy
Chris@102:             >(geometry1, geometry2);
Chris@102: 
Chris@102: 
Chris@102:         dispatch::get_turns
Chris@102:             <
Chris@102:                 typename geometry::tag<Geometry1>::type,
Chris@102:                 typename geometry::tag<Geometry2>::type,
Chris@102:                 Geometry1,
Chris@102:                 Geometry2,
Chris@102:                 reverse1,
Chris@102:                 reverse2,
Chris@102:                 GetTurnPolicy
Chris@102:             >::apply(0, geometry1, 1, geometry2,
Chris@102:                      robust_policy, turns, interrupt_policy);
Chris@102:     }
Chris@102: };
Chris@102: 
Chris@102: // TURNS SORTING AND SEARCHING
Chris@102: 
Chris@102: template <int N = 0, int U = 1, int I = 2, int B = 3, int C = 4, int O = 0>
Chris@102: struct op_to_int
Chris@102: {
Chris@102:     template <typename SegmentRatio>
Chris@102:     inline int operator()(detail::overlay::turn_operation<SegmentRatio> const& op) const
Chris@102:     {
Chris@102:         switch(op.operation)
Chris@102:         {
Chris@102:         case detail::overlay::operation_none : return N;
Chris@102:         case detail::overlay::operation_union : return U;
Chris@102:         case detail::overlay::operation_intersection : return I;
Chris@102:         case detail::overlay::operation_blocked : return B;
Chris@102:         case detail::overlay::operation_continue : return C;
Chris@102:         case detail::overlay::operation_opposite : return O;
Chris@102:         }
Chris@102:         return -1;
Chris@102:     }
Chris@102: };
Chris@102: 
Chris@102: template <std::size_t OpId, typename OpToInt>
Chris@102: struct less_op_xxx_linear
Chris@102: {
Chris@102:     template <typename Turn>
Chris@102:     inline bool operator()(Turn const& left, Turn const& right) const
Chris@102:     {
Chris@102:         static OpToInt op_to_int;
Chris@102:         return op_to_int(left.operations[OpId]) < op_to_int(right.operations[OpId]);
Chris@102:     }
Chris@102: };
Chris@102: 
Chris@102: template <std::size_t OpId>
Chris@102: struct less_op_linear_linear
Chris@102:     : less_op_xxx_linear< OpId, op_to_int<0,2,3,1,4,0> >
Chris@102: {};
Chris@102: 
Chris@102: template <std::size_t OpId>
Chris@102: struct less_op_linear_areal_single
Chris@102: {
Chris@102:     template <typename Turn>
Chris@102:     inline bool operator()(Turn const& left, Turn const& right) const
Chris@102:     {
Chris@102:         static const std::size_t other_op_id = (OpId + 1) % 2;
Chris@102:         static turns::op_to_int<0,2,3,1,4,0> op_to_int_xuic;
Chris@102:         static turns::op_to_int<0,3,2,1,4,0> op_to_int_xiuc;
Chris@102: 
Chris@102:         segment_identifier const& left_other_seg_id = left.operations[other_op_id].seg_id;
Chris@102:         segment_identifier const& right_other_seg_id = right.operations[other_op_id].seg_id;
Chris@102: 
Chris@102:         typedef typename Turn::turn_operation_type operation_type;
Chris@102:         operation_type const& left_operation = left.operations[OpId];
Chris@102:         operation_type const& right_operation = right.operations[OpId];
Chris@102: 
Chris@102:         if ( left_other_seg_id.ring_index == right_other_seg_id.ring_index )
Chris@102:         {
Chris@102:             return op_to_int_xuic(left_operation)
Chris@102:                  < op_to_int_xuic(right_operation);
Chris@102:         }
Chris@102:         else
Chris@102:         {
Chris@102:             return op_to_int_xiuc(left_operation)
Chris@102:                  < op_to_int_xiuc(right_operation);
Chris@102:         }
Chris@102:     }
Chris@102: };
Chris@102: 
Chris@102: template <std::size_t OpId>
Chris@102: struct less_op_areal_linear
Chris@102:     : less_op_xxx_linear< OpId, op_to_int<0,1,0,0,2,0> >
Chris@102: {};
Chris@102: 
Chris@102: template <std::size_t OpId>
Chris@102: struct less_op_areal_areal
Chris@102: {
Chris@102:     template <typename Turn>
Chris@102:     inline bool operator()(Turn const& left, Turn const& right) const
Chris@102:     {
Chris@102:         static const std::size_t other_op_id = (OpId + 1) % 2;
Chris@102:         static op_to_int<0, 1, 2, 3, 4, 0> op_to_int_uixc;
Chris@102:         static op_to_int<0, 2, 1, 3, 4, 0> op_to_int_iuxc;
Chris@102: 
Chris@102:         segment_identifier const& left_other_seg_id = left.operations[other_op_id].seg_id;
Chris@102:         segment_identifier const& right_other_seg_id = right.operations[other_op_id].seg_id;
Chris@102: 
Chris@102:         typedef typename Turn::turn_operation_type operation_type;
Chris@102:         operation_type const& left_operation = left.operations[OpId];
Chris@102:         operation_type const& right_operation = right.operations[OpId];
Chris@102: 
Chris@102:         if ( left_other_seg_id.multi_index == right_other_seg_id.multi_index )
Chris@102:         {
Chris@102:             if ( left_other_seg_id.ring_index == right_other_seg_id.ring_index )
Chris@102:             {
Chris@102:                 return op_to_int_uixc(left_operation) < op_to_int_uixc(right_operation);
Chris@102:             }
Chris@102:             else
Chris@102:             {
Chris@102:                 if ( left_other_seg_id.ring_index == -1 )
Chris@102:                 {
Chris@102:                     if ( left_operation.operation == overlay::operation_union )
Chris@102:                         return false;
Chris@102:                     else if ( left_operation.operation == overlay::operation_intersection )
Chris@102:                         return true;
Chris@102:                 }
Chris@102:                 else if ( right_other_seg_id.ring_index == -1 )
Chris@102:                 {
Chris@102:                     if ( right_operation.operation == overlay::operation_union )
Chris@102:                         return true;
Chris@102:                     else if ( right_operation.operation == overlay::operation_intersection )
Chris@102:                         return false;
Chris@102:                 }
Chris@102:                 
Chris@102:                 return op_to_int_iuxc(left_operation) < op_to_int_iuxc(right_operation);
Chris@102:             }
Chris@102:         }
Chris@102:         else
Chris@102:         {
Chris@102:             return op_to_int_uixc(left_operation) < op_to_int_uixc(right_operation);
Chris@102:         }
Chris@102:     }
Chris@102: };
Chris@102: 
Chris@102: template <std::size_t OpId>
Chris@102: struct less_other_multi_index
Chris@102: {
Chris@102:     static const std::size_t other_op_id = (OpId + 1) % 2;
Chris@102: 
Chris@102:     template <typename Turn>
Chris@102:     inline bool operator()(Turn const& left, Turn const& right) const
Chris@102:     {
Chris@102:         return left.operations[other_op_id].seg_id.multi_index
Chris@102:              < right.operations[other_op_id].seg_id.multi_index;
Chris@102:     }
Chris@102: };
Chris@102: 
Chris@102: // sort turns by G1 - source_index == 0 by:
Chris@102: // seg_id -> distance -> operation
Chris@102: template <std::size_t OpId = 0,
Chris@102:           typename LessOp = less_op_xxx_linear< OpId, op_to_int<> > >
Chris@102: struct less
Chris@102: {
Chris@102:     BOOST_STATIC_ASSERT(OpId < 2);
Chris@102: 
Chris@102:     template <typename Turn>
Chris@102:     static inline bool use_fraction(Turn const& left, Turn const& right)
Chris@102:     {
Chris@102:         static LessOp less_op;
Chris@102: 
Chris@102:         return left.operations[OpId].fraction < right.operations[OpId].fraction
Chris@102:             || ( left.operations[OpId].fraction == right.operations[OpId].fraction
Chris@102:               && less_op(left, right) );
Chris@102:     }
Chris@102: 
Chris@102:     template <typename Turn>
Chris@102:     inline bool operator()(Turn const& left, Turn const& right) const
Chris@102:     {
Chris@102:         segment_identifier const& sl = left.operations[OpId].seg_id;
Chris@102:         segment_identifier const& sr = right.operations[OpId].seg_id;
Chris@102: 
Chris@102:         return sl < sr || ( sl == sr && use_fraction(left, right) );
Chris@102:     }
Chris@102: };
Chris@102: 
Chris@102: }}} // namespace detail::relate::turns
Chris@102: #endif // DOXYGEN_NO_DETAIL
Chris@102: 
Chris@102: }} // namespace boost::geometry
Chris@102: 
Chris@102: #endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_RELATE_TURNS_HPP