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 #if defined(BOOST_GEOMETRY_USE_RESCALING)
0081         CalculationType inside_min_measure{(std::numeric_limits<CalculationType>::max)()};
0082 #endif
0083
0084         inline bool is_inside() const
0085         {
0086             return count < 0 || count_on_origin > 0;
0087         }
0088
0089         inline bool is_on_boundary() const
0090         {
0091             return count_on_origin == 0
0092                 && (count_on_offsetted > 0
0093                 || (count_on_edge > 0 && edge_min_fraction < 1.0e-3)
0094 #if defined(BOOST_GEOMETRY_USE_RESCALING)
0095                 || (count < 0 && inside_min_measure < 1.0e-5)
0096 #endif
0097                 );
0098         }
0099
0100     };
0101
0102     using state_type = counter;
0103
0104     template <typename Point, typename PointOfSegment>
0105     static inline bool is_in_vertical_range(Point const& point,
0106                              PointOfSegment const& s1,
0107                              PointOfSegment const& s2)
0108     {
0109         CalculationType const py = get<1>(point);
0110         CalculationType const s1y = get<1>(s1);
0111         CalculationType const s2y = get<1>(s2);
0112
0113         return s1y < s2y ? (py >= s1y && py <= s2y) : (py >= s2y && py <= s1y);
0114     }
0115
0116     template <typename Point, typename PointOfSegment>
0117     static inline void apply_on_boundary(Point const& point,
0118                              PointOfSegment const& s1,
0119                              PointOfSegment const& s2,
0120                              place_on_ring_type place_on_ring,
0121                              counter& the_state)
0122     {
0123         if (place_on_ring == place_on_ring_offsetted)
0124         {
0125             the_state.count_on_offsetted++;
0126         }
0127         else if (place_on_ring == place_on_ring_to_offsetted
0128             || place_on_ring == place_on_ring_from_offsetted)
0129         {
0130             the_state.count_on_edge++;
0131
0132             auto const line1 = detail::make::make_perpendicular_line<CalculationType>(s1, s2, s1);
0133             auto const line2 = detail::make::make_perpendicular_line<CalculationType>(s2, s1, s2);
0134
0135             auto const value1 = arithmetic::side_value(line1, point);
0136             auto const value2 = arithmetic::side_value(line2, point);
0137             if (value1 >= 0 && value2 >= 0)
0138             {
0139                 auto const length_value = value1 + value2;
0140                 if (length_value > 0)
0141                 {
0142                     // If it is to the utmost point s1 or s2, it is "outside"
0143                     auto const fraction = (place_on_ring == place_on_ring_to_offsetted ? value2 : value1) / length_value;
0144                     if (fraction < the_state.edge_min_fraction)
0145                     {
0146                         the_state.edge_min_fraction = fraction;
0147                     }
0148                 }
0149             }
0150         }
0151         else
0152         {
0153             the_state.count_on_origin++;
0154         }
0155     }
0156
0157     template <typename Point, typename PointOfSegment>
0158     static inline bool apply(Point const& point,
0159                              PointOfSegment const& s1,
0160                              PointOfSegment const& s2,
0161                              place_on_ring_type place_on_ring,
0162                              bool is_convex,
0163                              counter& the_state)
0164     {
0165         int const side = strategy::side::side_rounded_input<CalculationType>::apply(s1, s2, point);
0166
0167         if (is_convex && side > 0)
0168         {
0169             // If the point is left of this segment of a convex piece, it can never be inside.
0170             // Stop further processing
0171             the_state.count = 1;
0172             return false;
0173         }
0174
0175         CalculationType const px = get<0>(point);
0176         CalculationType const s1x = get<0>(s1);
0177         CalculationType const s2x = get<0>(s2);
0178
0179         bool const in_horizontal_range = s1x < s2x ? (px >= s1x && px <= s2x) : (px >= s2x && px <= s1x);
0180
0181         bool const vertical = s1x == s2x;
0182
0183         if (in_horizontal_range || (vertical && is_in_vertical_range(point, s1, s2)))
0184         {
0185             if (side == 0)
0186             {
0187                 apply_on_boundary(point, s1, s2, place_on_ring, the_state);
0188             }
0189 #if defined(BOOST_GEOMETRY_USE_RESCALING)
0190             else if (side == -1)
0191             {
0192                 auto const line = detail::make::make_infinite_line<CalculationType>(s1, s2);
0193                 auto const value = -arithmetic::side_value(line, point);
0194                 if (value > 0 && value < the_state.inside_min_measure) { the_state.inside_min_measure = value; }
0195
0196             }
0197 #endif
0198         }
0199
0200         if (in_horizontal_range)
0201         {
0202             auto const on_boundary = the_state.count_on_offsetted + the_state.count_on_edge + the_state.count_on_origin;
0203             if (on_boundary == 0)
0204             {
0205                 // Use only absolute comparisons, because the ring is continuous -
0206                 // what was missed is there earlier or later, and turns should
0207                 // not be counted twice (which can happen if an epsilon is used).
0208                 bool const eq1 = s1x == px;
0209                 bool const eq2 = s2x == px;
0210
0211                 // Account for  1 or  2 for left side (outside)
0212                 //     and for -1 or -2 for right side (inside)
0213                 int const multiplier = eq1 || eq2 ? 1 : 2;
0214
0215                 the_state.count += side * multiplier;
0216             }
0217         }
0218
0219         return true;
0220     }
0221 };
0222
0223 #endif // DOXYGEN_NO_DETAIL
0224
0225 }} // namespace strategy::buffer
0226
0227 }} // namespace boost::geometry
0228
0229 #endif // BOOST_GEOMETRY_STRATEGIES_CARTESIAN_TURN_IN_RING_WINDING_HPP
0230