1 // Boost.Geometry (aka GGL, Generic Geometry Library)
2
3 // Copyright (c) 2007-2015 Barend Gehrels, Amsterdam, the Netherlands.
4 // Copyright (c) 2008-2015 Bruno Lalande, Paris, France.
5 // Copyright (c) 2009-2015 Mateusz Loskot, London, UK.
6 // Copyright (c) 2013-2015 Adam Wulkiewicz, Lodz, Poland.
7
8 // This file was modified by Oracle on 2015, 2017.
9 // Modifications copyright (c) 2015-2017 Oracle and/or its affiliates.
10
11 // Contributed and/or modified by Menelaos Karavelas, on behalf of Oracle
12 // Contributed and/or modified by Adam Wulkiewicz, on behalf of Oracle
13
14 // Use, modification and distribution is subject to the Boost Software License,
15 // Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
16 // http://www.boost.org/LICENSE_1_0.txt)
17
18 #ifndef BOOST_GEOMETRY_ALGORITHMS_DETAIL_POINT_IS_EQUAL_OR_SPIKE_HPP
19 #define BOOST_GEOMETRY_ALGORITHMS_DETAIL_POINT_IS_EQUAL_OR_SPIKE_HPP
20
21 #include <boost/geometry/algorithms/detail/direction_code.hpp>
22 #include <boost/geometry/algorithms/detail/recalculate.hpp>
23 #include <boost/geometry/core/cs.hpp>
24 #include <boost/geometry/policies/robustness/robust_point_type.hpp>
25 #include <boost/geometry/strategies/side.hpp>
26 #include <boost/geometry/util/condition.hpp>
27 #include <boost/geometry/util/math.hpp>
28
29
30 namespace boost { namespace geometry
31 {
32
33
34 #ifndef DOXYGEN_NO_DETAIL
35 namespace detail
36 {
37
38 template <typename Point1, typename Point2, typename Point3>
collinear_point_is_spike_or_equal(Point1 const & last_point,Point2 const & segment_a,Point3 const & segment_b)39 inline bool collinear_point_is_spike_or_equal(Point1 const& last_point,
40 Point2 const& segment_a,
41 Point3 const& segment_b)
42 {
43 // Check if segment is equal
44 int const sgn_x1 = sign_of_difference<0>(last_point, segment_b);
45 int const sgn_y1 = sign_of_difference<1>(last_point, segment_b);
46 if (sgn_x1 == 0 && sgn_y1 == 0)
47 {
48 return true;
49 }
50
51 // Check if segment moves forward
52 int const sgn_x2 = sign_of_difference<0>(segment_b, segment_a);
53 int const sgn_y2 = sign_of_difference<1>(segment_b, segment_a);
54
55 return sgn_x1 != sgn_x2 || sgn_y1 != sgn_y2;
56 }
57
58 // Checks if a point ("last_point") causes a spike w.r.t.
59 // the specified two other points (segment_a, segment_b)
60 //
61 // x-------x------x
62 // a lp b
63 //
64 // Above, lp generates a spike w.r.t. segment(a,b)
65 // So specify last point first, then (a,b)
66 // The segment's orientation does matter: if lp is to the right of b
67 // no spike is reported
68 template
69 <
70 typename Point1, typename Point2, typename Point3,
71 typename SideStrategy
72 >
point_is_spike_or_equal(Point1 const & last_point,Point2 const & segment_a,Point3 const & segment_b,SideStrategy const & strategy)73 static inline bool point_is_spike_or_equal(Point1 const& last_point, // prev | back
74 Point2 const& segment_a, // next | back - 2
75 Point3 const& segment_b, // curr | back - 1 | spike's vertex
76 SideStrategy const& strategy)
77 {
78 int const side = strategy.apply(segment_a, segment_b, last_point);
79 if (side == 0)
80 {
81 // Last point is collinear w.r.t previous segment.
82 #ifdef BOOST_GEOMETRY_ENABLE_POINT_IS_SPIKE_OR_EQUAL_TEST
83 bool r1 = collinear_point_is_spike_or_equal(last_point, segment_a, segment_b);
84 bool r2 = direction_code(segment_a, segment_b, last_point) < 1;
85 if (r1 != r2)
86 std::cout << "spike detection failure with: " << r1 << " " << r2 << std::endl;
87 return r2;
88 #else
89 return direction_code(segment_a, segment_b, last_point) < 1;
90 #endif
91 }
92 return false;
93 }
94
95 template
96 <
97 typename Point1,
98 typename Point2,
99 typename Point3,
100 typename SideStrategy,
101 typename RobustPolicy
102 >
point_is_spike_or_equal(Point1 const & last_point,Point2 const & segment_a,Point3 const & segment_b,SideStrategy const & strategy,RobustPolicy const & robust_policy)103 static inline bool point_is_spike_or_equal(Point1 const& last_point,
104 Point2 const& segment_a,
105 Point3 const& segment_b,
106 SideStrategy const& strategy,
107 RobustPolicy const& robust_policy)
108 {
109 if (point_is_spike_or_equal(last_point, segment_a, segment_b, strategy))
110 {
111 return true;
112 }
113
114 if (BOOST_GEOMETRY_CONDITION(! RobustPolicy::enabled))
115 {
116 return false;
117 }
118
119 // Try using specified robust policy
120 typedef typename geometry::robust_point_type
121 <
122 Point1,
123 RobustPolicy
124 >::type robust_point_type;
125
126 robust_point_type last_point_rob, segment_a_rob, segment_b_rob;
127 geometry::recalculate(last_point_rob, last_point, robust_policy);
128 geometry::recalculate(segment_a_rob, segment_a, robust_policy);
129 geometry::recalculate(segment_b_rob, segment_b, robust_policy);
130
131 return point_is_spike_or_equal
132 (
133 last_point_rob,
134 segment_a_rob,
135 segment_b_rob,
136 strategy
137 );
138 }
139
140
141 } // namespace detail
142 #endif
143
144 }} // namespace boost::geometry
145
146
147 #endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_POINT_IS_EQUAL_OR_SPIKE_HPP
148