1 // Boost.Geometry (aka GGL, Generic Geometry Library)
2 
3 // Copyright (c) 2007-2012 Barend Gehrels, Amsterdam, the Netherlands.
4 
5 // This file was modified by Oracle on 2016.
6 // Modifications copyright (c) 2016 Oracle and/or its affiliates.
7 // Contributed and/or modified by Adam Wulkiewicz, on behalf of Oracle
8 
9 // Use, modification and distribution is subject to the Boost Software License,
10 // Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
11 // http://www.boost.org/LICENSE_1_0.txt)
12 
13 #ifndef BOOST_GEOMETRY_GEOMETRY_POLICIES_RELATE_INTERSECTION_POINTS_HPP
14 #define BOOST_GEOMETRY_GEOMETRY_POLICIES_RELATE_INTERSECTION_POINTS_HPP
15 
16 
17 #include <algorithm>
18 #include <string>
19 
20 #include <boost/geometry/algorithms/detail/assign_indexed_point.hpp>
21 #include <boost/geometry/core/access.hpp>
22 #include <boost/geometry/core/assert.hpp>
23 #include <boost/geometry/strategies/side_info.hpp>
24 
25 namespace boost { namespace geometry
26 {
27 
28 namespace policies { namespace relate
29 {
30 
31 
32 /*!
33 \brief Policy calculating the intersection points themselves
34  */
35 template
36 <
37     typename ReturnType
38 >
39 struct segments_intersection_points
40 {
41     typedef ReturnType return_type;
42 
43     template
44     <
45         typename Segment1,
46         typename Segment2,
47         typename SegmentIntersectionInfo
48     >
segments_crossesboost::geometry::policies::relate::segments_intersection_points49     static inline return_type segments_crosses(side_info const&,
50                     SegmentIntersectionInfo const& sinfo,
51                     Segment1 const& s1, Segment2 const& s2)
52     {
53         return_type result;
54         result.count = 1;
55 
56         bool use_a = true;
57 
58         // Prefer one segment if one is on or near an endpoint
59         bool const a_near_end = sinfo.robust_ra.near_end();
60         bool const b_near_end = sinfo.robust_rb.near_end();
61         if (a_near_end && ! b_near_end)
62         {
63             use_a = true;
64         }
65         else if (b_near_end && ! a_near_end)
66         {
67             use_a = false;
68         }
69         else
70         {
71             // Prefer shorter segment
72             typedef typename SegmentIntersectionInfo::promoted_type ptype;
73             ptype const len_a = sinfo.comparable_length_a();
74             ptype const len_b = sinfo.comparable_length_b();
75             if (len_b < len_a)
76             {
77                 use_a = false;
78             }
79             // else use_a is true but was already assigned like that
80         }
81 
82         if (use_a)
83         {
84             sinfo.assign_a(result.intersections[0], s1, s2);
85         }
86         else
87         {
88             sinfo.assign_b(result.intersections[0], s1, s2);
89         }
90 
91         result.fractions[0].assign(sinfo);
92 
93         return result;
94     }
95 
96     template <typename Segment1, typename Segment2, typename Ratio>
segments_collinearboost::geometry::policies::relate::segments_intersection_points97     static inline return_type segments_collinear(
98         Segment1 const& a, Segment2 const& b, bool /*opposite*/,
99         int a1_wrt_b, int a2_wrt_b, int b1_wrt_a, int b2_wrt_a,
100         Ratio const& ra_from_wrt_b, Ratio const& ra_to_wrt_b,
101         Ratio const& rb_from_wrt_a, Ratio const& rb_to_wrt_a)
102     {
103         return_type result;
104         unsigned int index = 0, count_a = 0, count_b = 0;
105         Ratio on_a[2];
106 
107         // The conditions "index < 2" are necessary for non-robust handling,
108         // if index would be 2 this indicate an (currently uncatched) error
109 
110         // IMPORTANT: the order of conditions is different as in direction.hpp
111         if (a1_wrt_b >= 1 && a1_wrt_b <= 3 // ra_from_wrt_b.on_segment()
112             && index < 2)
113         {
114             //     a1--------->a2
115             // b1----->b2
116             //
117             // ra1 (relative to b) is between 0/1:
118             // -> First point of A is intersection point
119             detail::assign_point_from_index<0>(a, result.intersections[index]);
120             result.fractions[index].assign(Ratio::zero(), ra_from_wrt_b);
121             on_a[index] = Ratio::zero();
122             index++;
123             count_a++;
124         }
125         if (b1_wrt_a == 2 //rb_from_wrt_a.in_segment()
126             && index < 2)
127         {
128             // We take the first intersection point of B
129             // a1--------->a2
130             //         b1----->b2
131             // But only if it is not located on A
132             // a1--------->a2
133             // b1----->b2      rb_from_wrt_a == 0/1 -> a already taken
134 
135             detail::assign_point_from_index<0>(b, result.intersections[index]);
136             result.fractions[index].assign(rb_from_wrt_a, Ratio::zero());
137             on_a[index] = rb_from_wrt_a;
138             index++;
139             count_b++;
140         }
141 
142         if (a2_wrt_b >= 1 && a2_wrt_b <= 3 //ra_to_wrt_b.on_segment()
143             && index < 2)
144         {
145             // Similarly, second IP (here a2)
146             // a1--------->a2
147             //         b1----->b2
148             detail::assign_point_from_index<1>(a, result.intersections[index]);
149             result.fractions[index].assign(Ratio::one(), ra_to_wrt_b);
150             on_a[index] = Ratio::one();
151             index++;
152             count_a++;
153         }
154         if (b2_wrt_a == 2 // rb_to_wrt_a.in_segment()
155             && index < 2)
156         {
157             detail::assign_point_from_index<1>(b, result.intersections[index]);
158             result.fractions[index].assign(rb_to_wrt_a, Ratio::one());
159             on_a[index] = rb_to_wrt_a;
160             index++;
161             count_b++;
162         }
163 
164         // TEMPORARY
165         // If both are from b, and b is reversed w.r.t. a, we swap IP's
166         // to align them w.r.t. a
167         // get_turn_info still relies on some order (in some collinear cases)
168         if (index == 2 && on_a[1] < on_a[0])
169         {
170             std::swap(result.fractions[0], result.fractions[1]);
171             std::swap(result.intersections[0], result.intersections[1]);
172         }
173 
174         result.count = index;
175 
176         return result;
177     }
178 
disjointboost::geometry::policies::relate::segments_intersection_points179     static inline return_type disjoint()
180     {
181         return return_type();
182     }
errorboost::geometry::policies::relate::segments_intersection_points183     static inline return_type error(std::string const&)
184     {
185         return return_type();
186     }
187 
188     // Both degenerate
189     template <typename Segment>
degenerateboost::geometry::policies::relate::segments_intersection_points190     static inline return_type degenerate(Segment const& segment, bool)
191     {
192         return_type result;
193         result.count = 1;
194         set<0>(result.intersections[0], get<0, 0>(segment));
195         set<1>(result.intersections[0], get<0, 1>(segment));
196         return result;
197     }
198 
199     // One degenerate
200     template <typename Segment, typename Ratio>
one_degenerateboost::geometry::policies::relate::segments_intersection_points201     static inline return_type one_degenerate(Segment const& degenerate_segment,
202             Ratio const& ratio, bool a_degenerate)
203     {
204         return_type result;
205         result.count = 1;
206         set<0>(result.intersections[0], get<0, 0>(degenerate_segment));
207         set<1>(result.intersections[0], get<0, 1>(degenerate_segment));
208         if (a_degenerate)
209         {
210             // IP lies on ratio w.r.t. segment b
211             result.fractions[0].assign(Ratio::zero(), ratio);
212         }
213         else
214         {
215             result.fractions[0].assign(ratio, Ratio::zero());
216         }
217         return result;
218     }
219 };
220 
221 
222 }} // namespace policies::relate
223 
224 }} // namespace boost::geometry
225 
226 #endif // BOOST_GEOMETRY_GEOMETRY_POLICIES_RELATE_INTERSECTION_POINTS_HPP
227