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