]>
Commit | Line | Data |
---|---|---|
b32b8144 FG |
1 | // Boost.Geometry (aka GGL, Generic Geometry Library) |
2 | ||
3 | // Copyright (c) 2007-2014 Barend Gehrels, Amsterdam, the Netherlands. | |
4 | // Copyright (c) 2008-2014 Bruno Lalande, Paris, France. | |
5 | // Copyright (c) 2009-2014 Mateusz Loskot, London, UK. | |
6 | // Copyright (c) 2013-2014 Adam Wulkiewicz, Lodz, Poland. | |
7 | ||
92f5a8d4 TL |
8 | // This file was modified by Oracle on 2013-2019. |
9 | // Modifications copyright (c) 2013-2019, Oracle and/or its affiliates. | |
b32b8144 FG |
10 | |
11 | // Contributed and/or modified by Vissarion Fysikopoulos, on behalf of Oracle | |
12 | // Contributed and/or modified by Menelaos Karavelas, on behalf of Oracle | |
13 | // Contributed and/or modified by Adam Wulkiewicz, on behalf of Oracle | |
14 | ||
15 | // Parts of Boost.Geometry are redesigned from Geodan's Geographic Library | |
16 | // (geolib/GGL), copyright (c) 1995-2010 Geodan, Amsterdam, the Netherlands. | |
17 | ||
18 | // Use, modification and distribution is subject to the Boost Software License, | |
19 | // Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at | |
20 | // http://www.boost.org/LICENSE_1_0.txt) | |
21 | ||
22 | #ifndef BOOST_GEOMETRY_ALGORITHMS_DETAIL_DISJOINT_SEGMENT_BOX_HPP | |
23 | #define BOOST_GEOMETRY_ALGORITHMS_DETAIL_DISJOINT_SEGMENT_BOX_HPP | |
24 | ||
25 | #include <cstddef> | |
26 | ||
27 | #include <boost/geometry/core/tags.hpp> | |
28 | #include <boost/geometry/core/radian_access.hpp> | |
29 | ||
30 | #include <boost/geometry/algorithms/detail/assign_indexed_point.hpp> | |
31 | #include <boost/geometry/algorithms/detail/disjoint/point_box.hpp> | |
32 | #include <boost/geometry/algorithms/detail/disjoint/box_box.hpp> | |
33 | #include <boost/geometry/algorithms/detail/envelope/segment.hpp> | |
34 | #include <boost/geometry/algorithms/detail/normalize.hpp> | |
35 | #include <boost/geometry/algorithms/dispatch/disjoint.hpp> | |
92f5a8d4 | 36 | #include <boost/geometry/algorithms/envelope.hpp> |
b32b8144 FG |
37 | |
38 | #include <boost/geometry/formulas/vertex_longitude.hpp> | |
39 | ||
40 | #include <boost/geometry/geometries/box.hpp> | |
41 | ||
92f5a8d4 TL |
42 | // Temporary, for envelope_segment_impl |
43 | #include <boost/geometry/strategies/spherical/envelope_segment.hpp> | |
44 | ||
b32b8144 FG |
45 | namespace boost { namespace geometry |
46 | { | |
47 | ||
48 | ||
49 | #ifndef DOXYGEN_NO_DETAIL | |
50 | namespace detail { namespace disjoint | |
51 | { | |
52 | ||
53 | template <typename CS_Tag> | |
54 | struct disjoint_segment_box_sphere_or_spheroid | |
55 | { | |
92f5a8d4 | 56 | struct disjoint_info |
b32b8144 | 57 | { |
92f5a8d4 TL |
58 | enum type |
59 | { | |
60 | intersect, | |
61 | disjoint_no_vertex, | |
62 | disjoint_vertex | |
63 | }; | |
64 | disjoint_info(type t) : m_(t){} | |
65 | operator type () const {return m_;} | |
66 | type m_; | |
67 | private : | |
68 | //prevent automatic conversion for any other built-in types | |
69 | template <typename T> | |
70 | operator T () const; | |
71 | }; | |
72 | ||
73 | template | |
74 | < | |
75 | typename Segment, typename Box, | |
76 | typename AzimuthStrategy, | |
77 | typename NormalizeStrategy, | |
78 | typename DisjointPointBoxStrategy, | |
79 | typename DisjointBoxBoxStrategy | |
80 | > | |
b32b8144 FG |
81 | static inline bool apply(Segment const& segment, |
82 | Box const& box, | |
92f5a8d4 TL |
83 | AzimuthStrategy const& azimuth_strategy, |
84 | NormalizeStrategy const& normalize_strategy, | |
85 | DisjointPointBoxStrategy const& disjoint_point_box_strategy, | |
86 | DisjointBoxBoxStrategy const& disjoint_box_box_strategy) | |
87 | { | |
88 | typedef typename point_type<Segment>::type segment_point; | |
89 | segment_point vertex; | |
90 | return apply(segment, box, vertex, | |
91 | azimuth_strategy, | |
92 | normalize_strategy, | |
93 | disjoint_point_box_strategy, | |
94 | disjoint_box_box_strategy) != disjoint_info::intersect; | |
95 | } | |
96 | ||
97 | template | |
98 | < | |
99 | typename Segment, typename Box, | |
100 | typename P, | |
101 | typename AzimuthStrategy, | |
102 | typename NormalizeStrategy, | |
103 | typename DisjointPointBoxStrategy, | |
104 | typename DisjointBoxBoxStrategy | |
105 | > | |
106 | static inline disjoint_info apply(Segment const& segment, | |
107 | Box const& box, | |
108 | P& vertex, | |
109 | AzimuthStrategy const& azimuth_strategy, | |
110 | NormalizeStrategy const& , | |
111 | DisjointPointBoxStrategy const& disjoint_point_box_strategy, | |
112 | DisjointBoxBoxStrategy const& disjoint_box_box_strategy) | |
b32b8144 FG |
113 | { |
114 | assert_dimension_equal<Segment, Box>(); | |
115 | ||
116 | typedef typename point_type<Segment>::type segment_point_type; | |
b32b8144 FG |
117 | |
118 | segment_point_type p0, p1; | |
119 | geometry::detail::assign_point_from_index<0>(segment, p0); | |
120 | geometry::detail::assign_point_from_index<1>(segment, p1); | |
121 | ||
92f5a8d4 TL |
122 | //vertex not computed here |
123 | disjoint_info disjoint_return_value = disjoint_info::disjoint_no_vertex; | |
124 | ||
b32b8144 FG |
125 | // Simplest cases first |
126 | ||
127 | // Case 1: if box contains one of segment's endpoints then they are not disjoint | |
92f5a8d4 TL |
128 | if ( ! disjoint_point_box(p0, box, disjoint_point_box_strategy) |
129 | || ! disjoint_point_box(p1, box, disjoint_point_box_strategy) ) | |
b32b8144 | 130 | { |
92f5a8d4 | 131 | return disjoint_info::intersect; |
b32b8144 FG |
132 | } |
133 | ||
134 | // Case 2: disjoint if bounding boxes are disjoint | |
135 | ||
136 | typedef typename coordinate_type<segment_point_type>::type CT; | |
137 | ||
92f5a8d4 TL |
138 | segment_point_type p0_normalized; |
139 | NormalizeStrategy::apply(p0, p0_normalized); | |
140 | segment_point_type p1_normalized; | |
141 | NormalizeStrategy::apply(p1, p1_normalized); | |
b32b8144 FG |
142 | |
143 | CT lon1 = geometry::get_as_radian<0>(p0_normalized); | |
144 | CT lat1 = geometry::get_as_radian<1>(p0_normalized); | |
145 | CT lon2 = geometry::get_as_radian<0>(p1_normalized); | |
146 | CT lat2 = geometry::get_as_radian<1>(p1_normalized); | |
147 | ||
148 | if (lon1 > lon2) | |
149 | { | |
92f5a8d4 TL |
150 | std::swap(lon1, lon2); |
151 | std::swap(lat1, lat2); | |
b32b8144 FG |
152 | } |
153 | ||
b32b8144 FG |
154 | geometry::model::box<segment_point_type> box_seg; |
155 | ||
92f5a8d4 TL |
156 | strategy::envelope::detail::envelope_segment_impl |
157 | < | |
158 | CS_Tag | |
159 | >::template apply<geometry::radian>(lon1, lat1, | |
160 | lon2, lat2, | |
161 | box_seg, | |
162 | azimuth_strategy); | |
163 | ||
164 | if (disjoint_box_box(box, box_seg, disjoint_box_box_strategy)) | |
b32b8144 | 165 | { |
92f5a8d4 | 166 | return disjoint_return_value; |
b32b8144 FG |
167 | } |
168 | ||
169 | // Case 3: test intersection by comparing angles | |
170 | ||
92f5a8d4 | 171 | CT alp1, a_b0, a_b1, a_b2, a_b3; |
b32b8144 FG |
172 | |
173 | CT b_lon_min = geometry::get_as_radian<geometry::min_corner, 0>(box); | |
174 | CT b_lat_min = geometry::get_as_radian<geometry::min_corner, 1>(box); | |
175 | CT b_lon_max = geometry::get_as_radian<geometry::max_corner, 0>(box); | |
176 | CT b_lat_max = geometry::get_as_radian<geometry::max_corner, 1>(box); | |
177 | ||
92f5a8d4 | 178 | azimuth_strategy.apply(lon1, lat1, lon2, lat2, alp1); |
b32b8144 FG |
179 | azimuth_strategy.apply(lon1, lat1, b_lon_min, b_lat_min, a_b0); |
180 | azimuth_strategy.apply(lon1, lat1, b_lon_max, b_lat_min, a_b1); | |
181 | azimuth_strategy.apply(lon1, lat1, b_lon_min, b_lat_max, a_b2); | |
182 | azimuth_strategy.apply(lon1, lat1, b_lon_max, b_lat_max, a_b3); | |
183 | ||
92f5a8d4 TL |
184 | bool b0 = formula::azimuth_side_value(alp1, a_b0) > 0; |
185 | bool b1 = formula::azimuth_side_value(alp1, a_b1) > 0; | |
186 | bool b2 = formula::azimuth_side_value(alp1, a_b2) > 0; | |
187 | bool b3 = formula::azimuth_side_value(alp1, a_b3) > 0; | |
b32b8144 | 188 | |
b32b8144 FG |
189 | if (!(b0 && b1 && b2 && b3) && (b0 || b1 || b2 || b3)) |
190 | { | |
92f5a8d4 | 191 | return disjoint_info::intersect; |
b32b8144 FG |
192 | } |
193 | ||
194 | // Case 4: The only intersection case not covered above is when all four | |
195 | // points of the box are above (below) the segment in northern (southern) | |
196 | // hemisphere. Then we have to compute the vertex of the segment | |
197 | ||
198 | CT vertex_lat; | |
199 | CT lat_sum = lat1 + lat2; | |
200 | ||
92f5a8d4 TL |
201 | if ((lat1 < b_lat_min && lat_sum > CT(0)) |
202 | || (lat1 > b_lat_max && lat_sum < CT(0))) | |
b32b8144 FG |
203 | { |
204 | CT b_lat_below; //latitude of box closest to equator | |
205 | ||
206 | if (lat_sum > CT(0)) | |
207 | { | |
208 | vertex_lat = geometry::get_as_radian<geometry::max_corner, 1>(box_seg); | |
209 | b_lat_below = b_lat_min; | |
210 | } else { | |
211 | vertex_lat = geometry::get_as_radian<geometry::min_corner, 1>(box_seg); | |
212 | b_lat_below = b_lat_max; | |
213 | } | |
214 | ||
215 | //optimization TODO: computing the spherical longitude should suffice for | |
216 | // the majority of cases | |
217 | CT vertex_lon = geometry::formula::vertex_longitude<CT, CS_Tag> | |
218 | ::apply(lon1, lat1, | |
219 | lon2, lat2, | |
220 | vertex_lat, | |
221 | alp1, | |
222 | azimuth_strategy); | |
223 | ||
92f5a8d4 TL |
224 | geometry::set_from_radian<0>(vertex, vertex_lon); |
225 | geometry::set_from_radian<1>(vertex, vertex_lat); | |
226 | disjoint_return_value = disjoint_info::disjoint_vertex; //vertex_computed | |
227 | ||
b32b8144 FG |
228 | // Check if the vertex point is within the band defined by the |
229 | // minimum and maximum longitude of the box; if yes, then return | |
230 | // false if the point is above the min latitude of the box; return | |
231 | // true in all other cases | |
232 | if (vertex_lon >= b_lon_min && vertex_lon <= b_lon_max | |
233 | && std::abs(vertex_lat) > std::abs(b_lat_below)) | |
234 | { | |
92f5a8d4 | 235 | return disjoint_info::intersect; |
b32b8144 FG |
236 | } |
237 | } | |
238 | ||
92f5a8d4 | 239 | return disjoint_return_value; |
b32b8144 FG |
240 | } |
241 | }; | |
242 | ||
243 | struct disjoint_segment_box | |
244 | { | |
245 | template <typename Segment, typename Box, typename Strategy> | |
246 | static inline bool apply(Segment const& segment, | |
247 | Box const& box, | |
248 | Strategy const& strategy) | |
249 | { | |
250 | return strategy.apply(segment, box); | |
251 | } | |
252 | }; | |
253 | ||
254 | }} // namespace detail::disjoint | |
255 | #endif // DOXYGEN_NO_DETAIL | |
256 | ||
257 | ||
258 | #ifndef DOXYGEN_NO_DISPATCH | |
259 | namespace dispatch | |
260 | { | |
261 | ||
262 | ||
263 | template <typename Segment, typename Box, std::size_t DimensionCount> | |
264 | struct disjoint<Segment, Box, DimensionCount, segment_tag, box_tag, false> | |
265 | : detail::disjoint::disjoint_segment_box | |
266 | {}; | |
267 | ||
268 | ||
269 | } // namespace dispatch | |
270 | #endif // DOXYGEN_NO_DISPATCH | |
271 | ||
272 | ||
273 | }} // namespace boost::geometry | |
274 | ||
275 | ||
276 | #endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_DISJOINT_SEGMENT_BOX_HPP |