strategies/cartesian/turn_in_ring_winding.hpp

0001 // Boost.Geometry (aka GGL, Generic Geometry Library)
0002
0003 // Copyright (c) 2020 Barend Gehrels, Amsterdam, the Netherlands.
0004 // Copyright (c) 2023 Adam Wulkiewicz, Lodz, Poland.
0005
0006 // This file was modified by Oracle on 2023.
0007 // Modifications copyright (c) 2023 Oracle and/or its affiliates.
0008 // Contributed and/or modified by Vissarion Fysikopoulos, 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_STRATEGIES_CARTESIAN_TURN_IN_RING_WINDING_HPP
0015 #define BOOST_GEOMETRY_STRATEGIES_CARTESIAN_TURN_IN_RING_WINDING_HPP
0016
0017 #include <boost/geometry/arithmetic/infinite_line_functions.hpp>
0018 #include <boost/geometry/core/access.hpp>
0019 #include <boost/geometry/core/config.hpp>
0020 #include <boost/geometry/algorithms/detail/make/make.hpp>
0021 #include <boost/geometry/util/math.hpp>
0022
0023 #include <boost/geometry/strategies/cartesian/side_rounded_input.hpp>
0024
0025 namespace boost { namespace geometry
0026 {
0027
0028 namespace strategy { namespace buffer
0029 {
0030
0031 #ifndef DOXYGEN_NO_DETAIL
0032
0033 enum place_on_ring_type
0034 {
0035     // +----offsetted----> (offsetted is considered as outside)
0036     // |                 |
0037     // |                 |
0038     // left              right (first point outside, rest inside)
0039     // |                 |
0040     // |                 |
0041     // <-----original----+ (original is considered as inside)
0042     place_on_ring_offsetted,
0043     place_on_ring_original,
0044     place_on_ring_to_offsetted,
0045     place_on_ring_from_offsetted,
0046 };
0047
0048 template <typename CalculationType>
0049 class turn_in_ring_winding
0050 {
0051
0052     // Implements the winding rule.
0053     // Basic calculations (on a clockwise ring of 5 segments)
0054     // (as everywhere in BG, -1 = right, 0 = on segment, +1 = left)
0055     // +--------2--------+  // P : For 1/3, nothing happens, it returns
0056     // |                 |  //     For 2, side is right (-1), multiplier=2, -2
0057     // |        P        |  //     For 4, side is right (-1), multiplier=1, -1
0058     // 1                 3  //     For 5, side is right (-1), multiplier=1, -1, total -4
0059     // |             Q   |  // Q : For 2: -2, for 4: -2, total -4
0060     // |                 |  // R : For 2: -2, for 5: +2, total 0
0061     // +----5---*----4---+  // S : For 2: -1, 3: nothing, 4: +1, total 0
0062     //
0063     //     R             S
0064     //
0065
0066
0067 public:
0068
0069     struct counter
0070     {
0071         //! Counter, is increased if point is left of a segment (outside),
0072         //! and decreased if point is right of a segment (inside)
0073         int count{0};
0074
0075         int count_on_offsetted{0};
0076         int count_on_origin{0};
0077         int count_on_edge{0};
0078
0079         CalculationType edge_min_fraction{(std::numeric_limits<CalculationType>::max)()};
0080
0081         inline bool is_inside() const
0082         {
0083             return count < 0 || count_on_origin > 0;
0084         }
0085
0086         inline bool is_on_boundary() const
0087         {
0088             return count_on_origin == 0
0089                 && (count_on_offsetted > 0
0090                 || (count_on_edge > 0 && edge_min_fraction < 1.0e-3)
0091                 );
0092         }
0093
0094     };
0095
0096     using state_type = counter;
0097
0098     template <typename Point, typename PointOfSegment>
0099     static inline bool is_in_vertical_range(Point const& point,
0100                              PointOfSegment const& s1,
0101                              PointOfSegment const& s2)
0102     {
0103         CalculationType const py = get<1>(point);
0104         CalculationType const s1y = get<1>(s1);
0105         CalculationType const s2y = get<1>(s2);
0106
0107         return s1y < s2y ? (py >= s1y && py <= s2y) : (py >= s2y && py <= s1y);
0108     }
0109
0110     template <typename Point, typename PointOfSegment>
0111     static inline void apply_on_boundary(Point const& point,
0112                              PointOfSegment const& s1,
0113                              PointOfSegment const& s2,
0114                              place_on_ring_type place_on_ring,
0115                              counter& the_state)
0116     {
0117         if (place_on_ring == place_on_ring_offsetted)
0118         {
0119             the_state.count_on_offsetted++;
0120         }
0121         else if (place_on_ring == place_on_ring_to_offsetted
0122             || place_on_ring == place_on_ring_from_offsetted)
0123         {
0124             the_state.count_on_edge++;
0125
0126             auto const line1 = detail::make::make_perpendicular_line<CalculationType>(s1, s2, s1);
0127             auto const line2 = detail::make::make_perpendicular_line<CalculationType>(s2, s1, s2);
0128
0129             auto const value1 = arithmetic::side_value(line1, point);
0130             auto const value2 = arithmetic::side_value(line2, point);
0131             if (value1 >= 0 && value2 >= 0)
0132             {
0133                 auto const length_value = value1 + value2;
0134                 if (length_value > 0)
0135                 {
0136                     // If it is to the utmost point s1 or s2, it is "outside"
0137                     auto const fraction = (place_on_ring == place_on_ring_to_offsetted ? value2 : value1) / length_value;
0138                     if (fraction < the_state.edge_min_fraction)
0139                     {
0140                         the_state.edge_min_fraction = fraction;
0141                     }
0142                 }
0143             }
0144         }
0145         else
0146         {
0147             the_state.count_on_origin++;
0148         }
0149     }
0150
0151     template <typename Point, typename PointOfSegment>
0152     static inline bool apply(Point const& point,
0153                              PointOfSegment const& s1,
0154                              PointOfSegment const& s2,
0155                              place_on_ring_type place_on_ring,
0156                              bool is_convex,
0157                              counter& the_state)
0158     {
0159         int const side = strategy::side::side_rounded_input<CalculationType>::apply(s1, s2, point);
0160
0161         if (is_convex && side > 0)
0162         {
0163             // If the point is left of this segment of a convex piece, it can never be inside.
0164             // Stop further processing
0165             the_state.count = 1;
0166             return false;
0167         }
0168
0169         CalculationType const px = get<0>(point);
0170         CalculationType const s1x = get<0>(s1);
0171         CalculationType const s2x = get<0>(s2);
0172
0173         bool const in_horizontal_range = s1x < s2x ? (px >= s1x && px <= s2x) : (px >= s2x && px <= s1x);
0174
0175         bool const vertical = s1x == s2x;
0176
0177         if (in_horizontal_range || (vertical && is_in_vertical_range(point, s1, s2)))
0178         {
0179             if (side == 0)
0180             {
0181                 apply_on_boundary(point, s1, s2, place_on_ring, the_state);
0182             }
0183         }
0184
0185         if (in_horizontal_range)
0186         {
0187             auto const on_boundary = the_state.count_on_offsetted + the_state.count_on_edge + the_state.count_on_origin;
0188             if (on_boundary == 0)
0189             {
0190                 // Use only absolute comparisons, because the ring is continuous -
0191                 // what was missed is there earlier or later, and turns should
0192                 // not be counted twice (which can happen if an epsilon is used).
0193                 bool const eq1 = s1x == px;
0194                 bool const eq2 = s2x == px;
0195
0196                 // Account for  1 or  2 for left side (outside)
0197                 //     and for -1 or -2 for right side (inside)
0198                 int const multiplier = eq1 || eq2 ? 1 : 2;
0199
0200                 the_state.count += side * multiplier;
0201             }
0202         }
0203
0204         return true;
0205     }
0206 };
0207
0208 #endif // DOXYGEN_NO_DETAIL
0209
0210 }} // namespace strategy::buffer
0211
0212 }} // namespace boost::geometry
0213
0214 #endif // BOOST_GEOMETRY_STRATEGIES_CARTESIAN_TURN_IN_RING_WINDING_HPP
0215