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