algorithms/detail/position_code.hpp

0001 // Boost.Geometry
0002
0003 // Copyright (c) 2025 Barend Gehrels, Amsterdam, the Netherlands.
0004
0005 // Use, modification and distribution is subject to the Boost Software License,
0006 // Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
0007 // http://www.boost.org/LICENSE_1_0.txt)
0008
0009 #ifndef BOOST_GEOMETRY_ALGORITHMS_DETAIL_POSITION_CODE_HPP
0010 #define BOOST_GEOMETRY_ALGORITHMS_DETAIL_POSITION_CODE_HPP
0011
0012 #include <boost/geometry/algorithms/detail/direction_code.hpp>
0013
0014 namespace boost { namespace geometry
0015 {
0016
0017 #ifndef DOXYGEN_NO_DETAIL
0018 namespace detail
0019 {
0020
0021 // Position coding of the point with respect to a segment.
0022 // This is a combination of side and direction_code.
0023 // It is counter clockwise from the segment.
0024 // (because polygons are on the right side of a segment, and this way
0025 // we can walk through the ranks ascending.
0026 //
0027 //        3
0028 //        |
0029 //   4    *    2    *: p2
0030 //        |
0031 //        1
0032 //        ^         ^: p1
0033 template <typename Point, typename SideStrategy>
0034 int get_position_code(Point const& p1, Point const& p2, Point const& point, SideStrategy const& side_strategy)
0035 {
0036     using cs_tag = typename SideStrategy::cs_tag;
0037     auto const side = side_strategy.apply(p1, p2, point);
0038     if (side == 1)
0039     {
0040         // left of [p1..p2]
0041         return 4;
0042     }
0043     else if (side == -1)
0044     {
0045         // right of [p1..p2]
0046         return 2;
0047     }
0048
0049     // collinear with [p1..p2]
0050     auto const dir_code = direction_code<cs_tag>(p1, p2, point);
0051     if (dir_code == -1)
0052     {
0053         // collinear, on [p1..p2] or before p1
0054         return 1;
0055     }
0056     else if (dir_code == 1)
0057     {
0058         // collinear with [p1..p2], but farther than p2
0059         return 3;
0060     }
0061
0062     // The segment is degenerate
0063     return 0;
0064 }
0065
0066 } // namespace detail
0067 #endif //DOXYGEN_NO_DETAIL
0068
0069 }} // namespace boost::geometry
0070
0071 #endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_POSITION_CODE_HPP