1 // Boost.Geometry (aka GGL, Generic Geometry Library) 2 3 // Copyright (c) 2007-2012 Barend Gehrels, Amsterdam, the Netherlands. 4 5 // This file was modified by Oracle on 2017. 6 // Modifications copyright (c) 2017 Oracle and/or its affiliates. 7 8 // Contributed and/or modified by Adam Wulkiewicz, on behalf of Oracle 9 10 // Use, modification and distribution is subject to the Boost Software License, 11 // Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at 12 // http://www.boost.org/LICENSE_1_0.txt) 13 14 #ifndef BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_GET_RELATIVE_ORDER_HPP 15 #define BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_GET_RELATIVE_ORDER_HPP 16 17 18 #include <boost/geometry/strategies/intersection_strategies.hpp> 19 20 21 namespace boost { namespace geometry 22 { 23 24 25 #ifndef DOXYGEN_NO_DETAIL 26 namespace detail { namespace overlay 27 { 28 29 30 /*! 31 \brief Get relative order 32 \details Can indicate which of two segments R and S, 33 both crossing a common segment P, comes first. 34 If the two segments cross P very close (e.g. in a spike), 35 the distance between the intersection points can be zero, 36 but we still need to know which comes first. 37 Therefore, it is useful that using sides we are able to discover this. 38 */ 39 struct get_relative_order 40 { 41 template <typename Point, typename SideStrategy> value_via_productboost::geometry::detail::overlay::get_relative_order42 static inline int value_via_product(Point const& ti, Point const& tj, 43 Point const& ui, Point const& uj, int factor, 44 SideStrategy const& strategy) 45 { 46 int const side_ti_u = strategy.apply(ti, tj, ui); 47 int const side_tj_u = strategy.apply(ti, tj, uj); 48 49 #ifdef BOOST_GEOMETRY_DEBUG_RELATIVE_ORDER 50 std::cout << (factor == 1 ? " r//s " : " s//r ") 51 << side_ti_u << " / " << side_tj_u; 52 #endif 53 54 return side_ti_u * side_tj_u >= 0 55 ? factor * (side_ti_u != 0 ? side_ti_u : side_tj_u) 56 : 0; 57 } 58 59 60 template <typename Point1, typename SideStrategy> applyboost::geometry::detail::overlay::get_relative_order61 static inline int apply( 62 Point1 const& pi, Point1 const& pj, 63 Point1 const& ri, Point1 const& rj, 64 Point1 const& si, Point1 const& sj, 65 SideStrategy const& strategy) 66 { 67 int const side_ri_p = strategy.apply(pi, pj, ri); 68 int const side_si_p = strategy.apply(pi, pj, si); 69 70 #ifdef BOOST_GEOMETRY_DEBUG_RELATIVE_ORDER 71 int const side_rj_p = strategy::apply(pi, pj, rj); 72 int const side_sj_p = strategy::apply(pi, pj, sj); 73 std::cout << "r//p: " << side_ri_p << " / " << side_rj_p; 74 std::cout << " s//p: " << side_si_p << " / " << side_sj_p; 75 #endif 76 77 int value = value_via_product(si, sj, ri, rj, 1, strategy); 78 if (value == 0) 79 { 80 value = value_via_product(ri, rj, si, sj, -1, strategy); 81 } 82 83 int const order = side_ri_p * side_ri_p * side_si_p * value; 84 85 #ifdef BOOST_GEOMETRY_DEBUG_RELATIVE_ORDER 86 std::cout 87 << " o: " << order 88 << std::endl << std::endl; 89 #endif 90 91 return order; 92 } 93 }; 94 95 96 }} // namespace detail::overlay 97 #endif //DOXYGEN_NO_DETAIL 98 99 100 }} // namespace boost::geometry 101 102 103 #endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_GET_RELATIVE_ORDER_HPP 104