1 // Boost.Geometry (aka GGL, Generic Geometry Library) 2 3 // Copyright (c) 2020 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_STRATEGIES_CARTESIAN_TURN_IN_RING_WINDING_HPP 10 #define BOOST_GEOMETRY_STRATEGIES_CARTESIAN_TURN_IN_RING_WINDING_HPP 11 12 #include <boost/geometry/core/access.hpp> 13 #include <boost/geometry/core/config.hpp> 14 #include <boost/geometry/algorithms/detail/make/make.hpp> 15 #include <boost/geometry/util/math.hpp> 16 17 namespace boost { namespace geometry 18 { 19 20 namespace strategy { namespace buffer 21 { 22 23 #ifndef DOXYGEN_NO_DETAIL 24 25 enum place_on_ring_type 26 { 27 // +----offsetted----> (offsetted is considered as outside) 28 // | | 29 // | | 30 // left right (first point outside, rest inside) 31 // | | 32 // | | 33 // <-----original----+ (original is considered as inside) 34 place_on_ring_offsetted, 35 place_on_ring_original, 36 place_on_ring_to_offsetted, 37 place_on_ring_from_offsetted, 38 }; 39 40 template <typename CalculationType> 41 class turn_in_ring_winding 42 { 43 44 // Implements the winding rule. 45 // Basic calculations (on a clockwise ring of 5 segments) 46 // (as everywhere in BG, -1 = right, 0 = on segment, +1 = left) 47 // +--------2--------+ // P : For 1/3, nothing happens, it returns 48 // | | // For 2, side is right (-1), multiplier=2, -2 49 // | P | // For 4, side is right (-1), multiplier=1, -1 50 // 1 3 // For 5, side is right (-1), multiplier=1, -1, total -4 51 // | Q | // Q : For 2: -2, for 4: -2, total -4 52 // | | // R : For 2: -2, for 5: +2, total 0 53 // +----5---*----4---+ // S : For 2: -1, 3: nothing, 4: +1, total 0 54 // 55 // R S 56 // 57 58 59 public: 60 61 struct counter 62 { counterboost::geometry::strategy::buffer::turn_in_ring_winding::counter63 inline counter() 64 : m_count(0) 65 , m_min_distance(0) 66 , m_close_to_offset(false) 67 {} 68 69 //! Returns -1 for outside, 1 for inside codeboost::geometry::strategy::buffer::turn_in_ring_winding::counter70 inline int code() const 71 { 72 return m_count == 0 ? -1 : 1; 73 } 74 75 //! Counter, is increased if point is left of a segment (outside), 76 //! and decreased if point is right of a segment (inside) 77 int m_count; 78 79 //! Indicate an indication of distance. It is always set, unless 80 //! the point is located on the border-part of the original. 81 //! It is not guaranteed to be the minimum distance, because it is only 82 //! calculated for a selection of the offsetted ring. 83 CalculationType m_min_distance; 84 bool m_close_to_offset; 85 }; 86 87 typedef counter state_type; 88 89 template <typename Point, typename PointOfSegment> in_vertical_range(Point const & point,PointOfSegment const & s1,PointOfSegment const & s2)90 static inline bool in_vertical_range(Point const& point, 91 PointOfSegment const& s1, 92 PointOfSegment const& s2) 93 { 94 CalculationType const py = get<1>(point); 95 CalculationType const s1y = get<1>(s1); 96 CalculationType const s2y = get<1>(s2); 97 98 return (s1y >= py && s2y <= py) 99 || (s2y >= py && s1y <= py); 100 } 101 102 template <typename Dm, typename Point, typename PointOfSegment> apply_on_boundary(Point const & point,PointOfSegment const & s1,PointOfSegment const & s2,place_on_ring_type place_on_ring,counter & the_state)103 static inline void apply_on_boundary(Point const& point, 104 PointOfSegment const& s1, 105 PointOfSegment const& s2, 106 place_on_ring_type place_on_ring, 107 counter& the_state) 108 { 109 if (place_on_ring == place_on_ring_offsetted) 110 { 111 // Consider the point as "outside" 112 the_state.m_count = 0; 113 the_state.m_close_to_offset = true; 114 the_state.m_min_distance = 0; 115 } 116 else if (place_on_ring == place_on_ring_to_offsetted 117 || place_on_ring == place_on_ring_from_offsetted) 118 { 119 // Check distance from "point" to either s1 or s2 120 // on a line perpendicular to s1-s2 121 typedef model::infinite_line<CalculationType> line_type; 122 123 line_type const line 124 = detail::make::make_perpendicular_line<CalculationType>(s1, s2, 125 place_on_ring == place_on_ring_to_offsetted ? s2 : s1); 126 127 Dm perp; 128 perp.measure = arithmetic::side_value(line, point); 129 130 // If it is to the utmost point s1 or s2, it is "outside" 131 the_state.m_count = perp.is_zero() ? 0 : 1; 132 the_state.m_close_to_offset = true; 133 the_state.m_min_distance = geometry::math::abs(perp.measure); 134 } 135 else 136 { 137 // It is on the border, the part of the original 138 // Consider it as "inside". 139 the_state.m_count = 1; 140 } 141 } 142 143 template <typename Dm, typename Point, typename PointOfSegment> apply(Point const & point,PointOfSegment const & s1,PointOfSegment const & s2,Dm const & dm,place_on_ring_type place_on_ring,counter & the_state)144 static inline bool apply(Point const& point, 145 PointOfSegment const& s1, 146 PointOfSegment const& s2, 147 Dm const& dm, 148 place_on_ring_type place_on_ring, 149 counter& the_state) 150 { 151 CalculationType const px = get<0>(point); 152 CalculationType const s1x = get<0>(s1); 153 CalculationType const s2x = get<0>(s2); 154 155 bool const in_horizontal_range 156 = (s1x >= px && s2x <= px) 157 || (s2x >= px && s1x <= px); 158 159 bool const vertical = s1x == s2x; 160 bool const measured_on_boundary = dm.is_zero(); 161 162 if (measured_on_boundary 163 && (in_horizontal_range 164 || (vertical && in_vertical_range(point, s1, s2)))) 165 { 166 apply_on_boundary<Dm>(point, s1, s2, place_on_ring, the_state); 167 // Indicate that no further processing is necessary. 168 return false; 169 } 170 171 bool const is_on_right_side = dm.is_negative(); 172 173 if (place_on_ring == place_on_ring_offsetted 174 && is_on_right_side 175 && (! the_state.m_close_to_offset 176 || -dm.measure < the_state.m_min_distance)) 177 { 178 // This part of the ring was the offsetted part, 179 // keep track of the distance WITHIN the ring 180 // with respect to the offsetted part 181 // NOTE: this is also done if it is NOT in the horizontal range. 182 the_state.m_min_distance = -dm.measure; 183 the_state.m_close_to_offset = true; 184 } 185 186 if (in_horizontal_range) 187 { 188 // Use only absolute comparisons, because the ring is continuous - 189 // what was missed is there earlier or later, and turns should 190 // not be counted twice (which can happen if an epsilon is used). 191 bool const eq1 = s1x == px; 192 bool const eq2 = s2x == px; 193 194 // Account for 1 or 2 for left side (outside) 195 // and for -1 or -2 for right side (inside) 196 int const side = is_on_right_side ? -1 : 1; 197 int const multiplier = eq1 || eq2 ? 1 : 2; 198 199 the_state.m_count += side * multiplier; 200 } 201 202 return true; 203 } 204 }; 205 206 #endif // DOXYGEN_NO_DETAIL 207 208 }} // namespace strategy::buffer 209 210 }} // namespace boost::geometry 211 212 #endif // BOOST_GEOMETRY_STRATEGIES_CARTESIAN_TURN_IN_RING_WINDING_HPP 213 214