detail/overlay/get_relative_order.hpp

0001 // Boost.Geometry (aka GGL, Generic Geometry Library)
0002
0003 // Copyright (c) 2007-2012 Barend Gehrels, Amsterdam, the Netherlands.
0004
0005 // This file was modified by Oracle on 2017.
0006 // Modifications copyright (c) 2017 Oracle and/or its affiliates.
0007
0008 // Contributed and/or modified by Adam Wulkiewicz, on behalf of Oracle
0009
0010 // Use, modification and distribution is subject to the Boost Software License,
0011 // Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
0012 // http://www.boost.org/LICENSE_1_0.txt)
0013
0014 #ifndef BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_GET_RELATIVE_ORDER_HPP
0015 #define BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_GET_RELATIVE_ORDER_HPP
0016
0017
0018 #include <boost/geometry/strategies/intersection_strategies.hpp>
0019
0020
0021 namespace boost { namespace geometry
0022 {
0023
0024
0025 #ifndef DOXYGEN_NO_DETAIL
0026 namespace detail { namespace overlay
0027 {
0028
0029
0030 /*!
0031     \brief Get relative order
0032     \details Can indicate which of two segments R and S,
0033         both crossing a common segment P, comes first.
0034         If the two segments cross P very close (e.g. in a spike),
0035         the distance between the intersection points can be zero,
0036         but we still need to know which comes first.
0037         Therefore, it is useful that using sides we are able to discover this.
0038  */
0039 struct get_relative_order
0040 {
0041     template <typename Point, typename SideStrategy>
0042     static inline int value_via_product(Point const& ti, Point const& tj,
0043                                         Point const& ui, Point const& uj, int factor,
0044                                         SideStrategy const& strategy)
0045     {
0046         int const side_ti_u = strategy.apply(ti, tj, ui);
0047         int const side_tj_u = strategy.apply(ti, tj, uj);
0048
0049 #ifdef BOOST_GEOMETRY_DEBUG_RELATIVE_ORDER
0050         std::cout << (factor == 1  ? " r//s " :  " s//r ")
0051             << side_ti_u << " / " << side_tj_u;
0052 #endif
0053
0054         return side_ti_u * side_tj_u >= 0
0055             ? factor * (side_ti_u != 0 ? side_ti_u : side_tj_u)
0056             : 0;
0057     }
0058
0059
0060     template <typename Point1, typename SideStrategy>
0061     static inline int apply(
0062                 Point1 const& pi, Point1 const& pj,
0063                 Point1 const& ri, Point1 const& rj,
0064                 Point1 const& si, Point1 const& sj,
0065                 SideStrategy const& strategy)
0066     {
0067         int const side_ri_p = strategy.apply(pi, pj, ri);
0068         int const side_si_p = strategy.apply(pi, pj, si);
0069
0070 #ifdef BOOST_GEOMETRY_DEBUG_RELATIVE_ORDER
0071         int const side_rj_p = strategy::apply(pi, pj, rj);
0072         int const side_sj_p = strategy::apply(pi, pj, sj);
0073         std::cout << "r//p: " << side_ri_p << " / " << side_rj_p;
0074         std::cout << " s//p: " << side_si_p << " / " << side_sj_p;
0075 #endif
0076
0077         int value = value_via_product(si, sj, ri, rj, 1, strategy);
0078         if (value == 0)
0079         {
0080             value = value_via_product(ri, rj, si, sj, -1, strategy);
0081         }
0082
0083         int const order = side_ri_p * side_ri_p * side_si_p * value;
0084
0085 #ifdef BOOST_GEOMETRY_DEBUG_RELATIVE_ORDER
0086         std::cout
0087             << " o: " << order
0088             << std::endl << std::endl;
0089 #endif
0090
0091         return order;
0092     }
0093 };
0094
0095
0096 }} // namespace detail::overlay
0097 #endif //DOXYGEN_NO_DETAIL
0098
0099
0100 }} // namespace boost::geometry
0101
0102
0103 #endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_GET_RELATIVE_ORDER_HPP