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