1 // Boost.Geometry (aka GGL, Generic Geometry Library)
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.
8 // This file was modified by Oracle on 2013-2021.
9 // Modifications copyright (c) 2013-2021, Oracle and/or its affiliates.
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
15 // Parts of Boost.Geometry are redesigned from Geodan's Geographic Library
16 // (geolib/GGL), copyright (c) 1995-2010 Geodan, Amsterdam, the Netherlands.
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)
22 #ifndef BOOST_GEOMETRY_ALGORITHMS_DETAIL_DISJOINT_SEGMENT_BOX_HPP
23 #define BOOST_GEOMETRY_ALGORITHMS_DETAIL_DISJOINT_SEGMENT_BOX_HPP
27 #include <boost/geometry/core/tags.hpp>
28 #include <boost/geometry/core/radian_access.hpp>
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>
37 #include <boost/geometry/formulas/vertex_longitude.hpp>
39 #include <boost/geometry/geometries/box.hpp>
41 // Temporary, for envelope_segment_impl
42 #include <boost/geometry/strategy/spherical/envelope_segment.hpp>
44 namespace boost { namespace geometry
48 #ifndef DOXYGEN_NO_DETAIL
49 namespace detail { namespace disjoint
52 template <typename CS_Tag>
53 struct disjoint_segment_box_sphere_or_spheroid
63 disjoint_info(type t) : m_(t){}
64 operator type () const {return m_;}
67 //prevent automatic conversion for any other built-in types
74 typename Segment, typename Box,
75 typename AzimuthStrategy,
76 typename NormalizeStrategy,
77 typename DisjointPointBoxStrategy,
78 typename DisjointBoxBoxStrategy
80 static inline bool apply(Segment const& segment,
82 AzimuthStrategy const& azimuth_strategy,
83 NormalizeStrategy const& normalize_strategy,
84 DisjointPointBoxStrategy const& disjoint_point_box_strategy,
85 DisjointBoxBoxStrategy const& disjoint_box_box_strategy)
87 typedef typename point_type<Segment>::type segment_point;
89 return apply(segment, box, vertex,
92 disjoint_point_box_strategy,
93 disjoint_box_box_strategy) != disjoint_info::intersect;
98 typename Segment, typename Box,
100 typename AzimuthStrategy,
101 typename NormalizeStrategy,
102 typename DisjointPointBoxStrategy,
103 typename DisjointBoxBoxStrategy
105 static inline disjoint_info apply(Segment const& segment,
108 AzimuthStrategy const& azimuth_strategy,
109 NormalizeStrategy const& ,
110 DisjointPointBoxStrategy const& disjoint_point_box_strategy,
111 DisjointBoxBoxStrategy const& disjoint_box_box_strategy)
113 assert_dimension_equal<Segment, Box>();
115 typedef typename point_type<Segment>::type segment_point_type;
117 segment_point_type p0, p1;
118 geometry::detail::assign_point_from_index<0>(segment, p0);
119 geometry::detail::assign_point_from_index<1>(segment, p1);
121 //vertex not computed here
122 disjoint_info disjoint_return_value = disjoint_info::disjoint_no_vertex;
124 // Simplest cases first
126 // Case 1: if box contains one of segment's endpoints then they are not disjoint
127 if ( ! disjoint_point_box(p0, box, disjoint_point_box_strategy)
128 || ! disjoint_point_box(p1, box, disjoint_point_box_strategy) )
130 return disjoint_info::intersect;
133 // Case 2: disjoint if bounding boxes are disjoint
135 typedef typename coordinate_type<segment_point_type>::type CT;
137 segment_point_type p0_normalized;
138 NormalizeStrategy::apply(p0, p0_normalized);
139 segment_point_type p1_normalized;
140 NormalizeStrategy::apply(p1, p1_normalized);
142 CT lon1 = geometry::get_as_radian<0>(p0_normalized);
143 CT lat1 = geometry::get_as_radian<1>(p0_normalized);
144 CT lon2 = geometry::get_as_radian<0>(p1_normalized);
145 CT lat2 = geometry::get_as_radian<1>(p1_normalized);
149 std::swap(lon1, lon2);
150 std::swap(lat1, lat2);
153 geometry::model::box<segment_point_type> box_seg;
155 strategy::envelope::detail::envelope_segment_impl
158 >::template apply<geometry::radian>(lon1, lat1,
163 if (disjoint_box_box(box, box_seg, disjoint_box_box_strategy))
165 return disjoint_return_value;
168 // Case 3: test intersection by comparing angles
170 CT alp1, a_b0, a_b1, a_b2, a_b3;
172 CT b_lon_min = geometry::get_as_radian<geometry::min_corner, 0>(box);
173 CT b_lat_min = geometry::get_as_radian<geometry::min_corner, 1>(box);
174 CT b_lon_max = geometry::get_as_radian<geometry::max_corner, 0>(box);
175 CT b_lat_max = geometry::get_as_radian<geometry::max_corner, 1>(box);
177 azimuth_strategy.apply(lon1, lat1, lon2, lat2, alp1);
178 azimuth_strategy.apply(lon1, lat1, b_lon_min, b_lat_min, a_b0);
179 azimuth_strategy.apply(lon1, lat1, b_lon_max, b_lat_min, a_b1);
180 azimuth_strategy.apply(lon1, lat1, b_lon_min, b_lat_max, a_b2);
181 azimuth_strategy.apply(lon1, lat1, b_lon_max, b_lat_max, a_b3);
183 int s0 = formula::azimuth_side_value(alp1, a_b0);
184 int s1 = formula::azimuth_side_value(alp1, a_b1);
185 int s2 = formula::azimuth_side_value(alp1, a_b2);
186 int s3 = formula::azimuth_side_value(alp1, a_b3);
188 if (s0 == 0 || s1 == 0 || s2 == 0 || s3 == 0)
190 return disjoint_info::intersect;
193 bool s0_positive = s0 > 0;
194 bool s1_positive = s1 > 0;
195 bool s2_positive = s2 > 0;
196 bool s3_positive = s3 > 0;
198 bool all_positive = s0_positive && s1_positive && s2_positive && s3_positive;
199 bool all_non_positive = !(s0_positive || s1_positive || s2_positive || s3_positive);
200 bool vertex_north = lat1 + lat2 > 0;
202 if ((all_positive && vertex_north) || (all_non_positive && !vertex_north))
204 return disjoint_info::disjoint_no_vertex;
207 if (!all_positive && !all_non_positive)
209 return disjoint_info::intersect;
212 // Case 4: The only intersection case not covered above is when all four
213 // points of the box are above (below) the segment in northern (southern)
214 // hemisphere. Then we have to compute the vertex of the segment
218 if ((lat1 < b_lat_min && vertex_north)
219 || (lat1 > b_lat_max && !vertex_north))
221 CT b_lat_below; //latitude of box closest to equator
225 vertex_lat = geometry::get_as_radian<geometry::max_corner, 1>(box_seg);
226 b_lat_below = b_lat_min;
228 vertex_lat = geometry::get_as_radian<geometry::min_corner, 1>(box_seg);
229 b_lat_below = b_lat_max;
232 //optimization TODO: computing the spherical longitude should suffice for
233 // the majority of cases
234 CT vertex_lon = geometry::formula::vertex_longitude<CT, CS_Tag>
241 geometry::set_from_radian<0>(vertex, vertex_lon);
242 geometry::set_from_radian<1>(vertex, vertex_lat);
243 disjoint_return_value = disjoint_info::disjoint_vertex; //vertex_computed
245 // Check if the vertex point is within the band defined by the
246 // minimum and maximum longitude of the box; if yes, then return
247 // false if the point is above the min latitude of the box; return
248 // true in all other cases
249 if (vertex_lon >= b_lon_min && vertex_lon <= b_lon_max
250 && std::abs(vertex_lat) > std::abs(b_lat_below))
252 return disjoint_info::intersect;
256 return disjoint_return_value;
260 struct disjoint_segment_box
262 template <typename Segment, typename Box, typename Strategy>
263 static inline bool apply(Segment const& segment,
265 Strategy const& strategy)
267 return strategy.disjoint(segment, box).apply(segment, box);
271 }} // namespace detail::disjoint
272 #endif // DOXYGEN_NO_DETAIL
275 #ifndef DOXYGEN_NO_DISPATCH
280 template <typename Segment, typename Box, std::size_t DimensionCount>
281 struct disjoint<Segment, Box, DimensionCount, segment_tag, box_tag, false>
282 : detail::disjoint::disjoint_segment_box
286 } // namespace dispatch
287 #endif // DOXYGEN_NO_DISPATCH
290 }} // namespace boost::geometry
293 #endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_DISJOINT_SEGMENT_BOX_HPP