1 // Boost.Geometry (aka GGL, Generic Geometry Library)
2 
3 // Copyright (c) 2007-2012 Barend Gehrels, Amsterdam, the Netherlands.
4 // Copyright (c) 2013 Adam Wulkiewicz, Lodz, Poland.
5 
6 // This file was modified by Oracle on 2013-2020.
7 // Modifications copyright (c) 2013-2020 Oracle and/or its affiliates.
8 // Contributed and/or modified by Adam Wulkiewicz, on behalf of Oracle
9 
10 // Parts of Boost.Geometry are redesigned from Geodan's Geographic Library
11 // (geolib/GGL), copyright (c) 1995-2010 Geodan, Amsterdam, the Netherlands.
12 
13 // Use, modification and distribution is subject to the Boost Software License,
14 // Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
15 // http://www.boost.org/LICENSE_1_0.txt)
16 
17 #ifndef BOOST_GEOMETRY_STRATEGY_CARTESIAN_POINT_IN_POLY_WINDING_HPP
18 #define BOOST_GEOMETRY_STRATEGY_CARTESIAN_POINT_IN_POLY_WINDING_HPP
19 
20 
21 #include <boost/geometry/core/tags.hpp>
22 
23 #include <boost/geometry/util/math.hpp>
24 #include <boost/geometry/util/select_calculation_type.hpp>
25 
26 #include <boost/geometry/strategy/cartesian/expand_point.hpp>
27 
28 #include <boost/geometry/strategies/cartesian/point_in_box.hpp>
29 #include <boost/geometry/strategies/cartesian/disjoint_box_box.hpp>
30 #include <boost/geometry/strategies/cartesian/side_by_triangle.hpp>
31 #include <boost/geometry/strategies/covered_by.hpp>
32 #include <boost/geometry/strategies/within.hpp>
33 
34 
35 namespace boost { namespace geometry
36 {
37 
38 namespace strategy { namespace within
39 {
40 
41 
42 /*!
43 \brief Within detection using winding rule in cartesian coordinate system.
44 \ingroup strategies
45 \tparam Point_ \tparam_point
46 \tparam PointOfSegment_ \tparam_segment_point
47 \tparam CalculationType \tparam_calculation
48 \author Barend Gehrels
49 
50 \qbk{
51 [heading See also]
52 [link geometry.reference.algorithms.within.within_3_with_strategy within (with strategy)]
53 }
54  */
55 template
56 <
57     typename Point_ = void, // for backward compatibility
58     typename PointOfSegment_ = Point_, // for backward compatibility
59     typename CalculationType = void
60 >
61 class cartesian_winding
62 {
63     template <typename Point, typename PointOfSegment>
64     struct calculation_type
65         : select_calculation_type
66             <
67                 Point,
68                 PointOfSegment,
69                 CalculationType
70             >
71     {};
72 
73     /*! subclass to keep state */
74     class counter
75     {
76         int m_count;
77         bool m_touches;
78 
code() const79         inline int code() const
80         {
81             return m_touches ? 0 : m_count == 0 ? -1 : 1;
82         }
83 
84     public :
85         friend class cartesian_winding;
86 
counter()87         inline counter()
88             : m_count(0)
89             , m_touches(false)
90         {}
91 
92     };
93 
94 public:
95     typedef cartesian_tag cs_tag;
96 
97     typedef side::side_by_triangle<CalculationType> side_strategy_type;
98 
get_side_strategy()99     static inline side_strategy_type get_side_strategy()
100     {
101         return side_strategy_type();
102     }
103 
104     typedef expand::cartesian_point expand_point_strategy_type;
105 
106     typedef typename side_strategy_type::envelope_strategy_type envelope_strategy_type;
107 
get_envelope_strategy()108     static inline envelope_strategy_type get_envelope_strategy()
109     {
110         return side_strategy_type::get_envelope_strategy();
111     }
112 
113     typedef typename side_strategy_type::disjoint_strategy_type disjoint_strategy_type;
114 
get_disjoint_strategy()115     static inline disjoint_strategy_type get_disjoint_strategy()
116     {
117         return side_strategy_type::get_disjoint_strategy();
118     }
119 
120     typedef typename side_strategy_type::equals_point_point_strategy_type equals_point_point_strategy_type;
get_equals_point_point_strategy()121     static inline equals_point_point_strategy_type get_equals_point_point_strategy()
122     {
123         return side_strategy_type::get_equals_point_point_strategy();
124     }
125 
126     typedef disjoint::cartesian_box_box disjoint_box_box_strategy_type;
get_disjoint_box_box_strategy()127     static inline disjoint_box_box_strategy_type get_disjoint_box_box_strategy()
128     {
129         return disjoint_box_box_strategy_type();
130     }
131 
132     typedef covered_by::cartesian_point_box disjoint_point_box_strategy_type;
133 
134     // Typedefs and static methods to fulfill the concept
135     typedef counter state_type;
136 
137     template <typename Point, typename PointOfSegment>
apply(Point const & point,PointOfSegment const & s1,PointOfSegment const & s2,counter & state)138     static inline bool apply(Point const& point,
139                              PointOfSegment const& s1, PointOfSegment const& s2,
140                              counter& state)
141     {
142         bool eq1 = false;
143         bool eq2 = false;
144 
145         int count = check_segment(point, s1, s2, state, eq1, eq2);
146         if (count != 0)
147         {
148             int side = 0;
149             if (count == 1 || count == -1)
150             {
151                 side = side_equal(point, eq1 ? s1 : s2, count);
152             }
153             else // count == 2 || count == -2
154             {
155                 // 1 left, -1 right
156                 side = side_strategy_type::apply(s1, s2, point);
157             }
158 
159             if (side == 0)
160             {
161                 // Point is lying on segment
162                 state.m_touches = true;
163                 state.m_count = 0;
164                 return false;
165             }
166 
167             // Side is NEG for right, POS for left.
168             // The count is -2 for left, 2 for right (or -1/1)
169             // Side positive thus means RIGHT and LEFTSIDE or LEFT and RIGHTSIDE
170             // See accompagnying figure (TODO)
171             if (side * count > 0)
172             {
173                 state.m_count += count;
174             }
175         }
176         return ! state.m_touches;
177     }
178 
result(counter const & state)179     static inline int result(counter const& state)
180     {
181         return state.code();
182     }
183 
184 private:
185     template <typename Point, typename PointOfSegment>
check_segment(Point const & point,PointOfSegment const & seg1,PointOfSegment const & seg2,counter & state,bool & eq1,bool & eq2)186     static inline int check_segment(Point const& point,
187                                     PointOfSegment const& seg1,
188                                     PointOfSegment const& seg2,
189                                     counter& state,
190                                     bool& eq1, bool& eq2)
191     {
192         if (check_touch(point, seg1, seg2, state, eq1, eq2))
193         {
194             return 0;
195         }
196 
197         return calculate_count(point, seg1, seg2, eq1, eq2);
198     }
199 
200     template <typename Point, typename PointOfSegment>
check_touch(Point const & point,PointOfSegment const & seg1,PointOfSegment const & seg2,counter & state,bool & eq1,bool & eq2)201     static inline bool check_touch(Point const& point,
202                                    PointOfSegment const& seg1,
203                                    PointOfSegment const& seg2,
204                                    counter& state,
205                                    bool& eq1, bool& eq2)
206     {
207         typedef typename calculation_type<Point, PointOfSegment>::type calc_t;
208 
209         calc_t const px = get<0>(point);
210         calc_t const s1x = get<0>(seg1);
211         calc_t const s2x = get<0>(seg2);
212 
213         eq1 = math::equals(s1x, px);
214         eq2 = math::equals(s2x, px);
215 
216         // Both equal p -> segment vertical
217         // The only thing which has to be done is check if point is ON segment
218         if (eq1 && eq2)
219         {
220             calc_t const py = get<1>(point);
221             calc_t const s1y = get<1>(seg1);
222             calc_t const s2y = get<1>(seg2);
223             if ((s1y <= py && s2y >= py) || (s2y <= py && s1y >= py))
224             {
225                 state.m_touches = true;
226             }
227             return true;
228         }
229         return false;
230     }
231 
232     template <typename Point, typename PointOfSegment>
calculate_count(Point const & point,PointOfSegment const & seg1,PointOfSegment const & seg2,bool eq1,bool eq2)233     static inline int calculate_count(Point const& point,
234                                       PointOfSegment const& seg1,
235                                       PointOfSegment const& seg2,
236                                       bool eq1, bool eq2)
237     {
238         typedef typename calculation_type<Point, PointOfSegment>::type calc_t;
239 
240         calc_t const p = get<0>(point);
241         calc_t const s1 = get<0>(seg1);
242         calc_t const s2 = get<0>(seg2);
243 
244         return eq1 ? (s2 > p ?  1 : -1)  // Point on level s1, E/W depending on s2
245              : eq2 ? (s1 > p ? -1 :  1)  // idem
246              : s1 < p && s2 > p ?  2     // Point between s1 -> s2 --> E
247              : s2 < p && s1 > p ? -2     // Point between s2 -> s1 --> W
248              : 0;
249     }
250 
251     template <typename Point, typename PointOfSegment>
side_equal(Point const & point,PointOfSegment const & se,int count)252     static inline int side_equal(Point const& point,
253                                  PointOfSegment const& se,
254                                  int count)
255     {
256         // NOTE: for D=0 the signs would be reversed
257         return math::equals(get<1>(point), get<1>(se)) ?
258                 0 :
259                 get<1>(point) < get<1>(se) ?
260                     // assuming count is equal to 1 or -1
261                     -count : // ( count > 0 ? -1 : 1) :
262                     count;   // ( count > 0 ? 1 : -1) ;
263     }
264 };
265 
266 
267 #ifndef DOXYGEN_NO_STRATEGY_SPECIALIZATIONS
268 
269 namespace services
270 {
271 
272 template <typename PointLike, typename Geometry, typename AnyTag1, typename AnyTag2>
273 struct default_strategy<PointLike, Geometry, AnyTag1, AnyTag2, pointlike_tag, polygonal_tag, cartesian_tag, cartesian_tag>
274 {
275     typedef cartesian_winding<> type;
276 };
277 
278 template <typename PointLike, typename Geometry, typename AnyTag1, typename AnyTag2>
279 struct default_strategy<PointLike, Geometry, AnyTag1, AnyTag2, pointlike_tag, linear_tag, cartesian_tag, cartesian_tag>
280 {
281     typedef cartesian_winding<> type;
282 };
283 
284 } // namespace services
285 
286 #endif
287 
288 
289 }} // namespace strategy::within
290 
291 
292 #ifndef DOXYGEN_NO_STRATEGY_SPECIALIZATIONS
293 namespace strategy { namespace covered_by { namespace services
294 {
295 
296 template <typename PointLike, typename Geometry, typename AnyTag1, typename AnyTag2>
297 struct default_strategy<PointLike, Geometry, AnyTag1, AnyTag2, pointlike_tag, polygonal_tag, cartesian_tag, cartesian_tag>
298 {
299     typedef within::cartesian_winding<> type;
300 };
301 
302 template <typename PointLike, typename Geometry, typename AnyTag1, typename AnyTag2>
303 struct default_strategy<PointLike, Geometry, AnyTag1, AnyTag2, pointlike_tag, linear_tag, cartesian_tag, cartesian_tag>
304 {
305     typedef within::cartesian_winding<> type;
306 };
307 
308 }}} // namespace strategy::covered_by::services
309 #endif
310 
311 
312 }} // namespace boost::geometry
313 
314 
315 #endif // BOOST_GEOMETRY_STRATEGY_CARTESIAN_POINT_IN_POLY_WINDING_HPP
316