1 // Boost.Geometry Index
2 //
3 // n-dimensional box-linestring intersection
4 //
5 // Copyright (c) 2011-2017 Adam Wulkiewicz, Lodz, Poland.
6 //
7 // This file was modified by Oracle on 2020.
8 // Modifications copyright (c) 2020 Oracle and/or its affiliates.
9 // Contributed and/or modified by Adam Wulkiewicz, on behalf of Oracle
10 //
11 // Use, modification and distribution is subject to the Boost Software License,
12 // Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
13 // http://www.boost.org/LICENSE_1_0.txt)
14
15 #ifndef BOOST_GEOMETRY_INDEX_DETAIL_ALGORITHMS_PATH_INTERSECTION_HPP
16 #define BOOST_GEOMETRY_INDEX_DETAIL_ALGORITHMS_PATH_INTERSECTION_HPP
17
18
19 #include <boost/geometry/core/static_assert.hpp>
20
21 #include <boost/geometry/index/detail/algorithms/segment_intersection.hpp>
22
23 #include <boost/geometry/strategies/default_length_result.hpp>
24
25
26 namespace boost { namespace geometry { namespace index { namespace detail {
27
28 namespace dispatch {
29
30 template <typename Indexable, typename Geometry, typename IndexableTag, typename GeometryTag>
31 struct path_intersection
32 {
33 BOOST_GEOMETRY_STATIC_ASSERT_FALSE(
34 "Not implemented for this Geometry or Indexable.",
35 Indexable, Geometry, IndexableTag, GeometryTag);
36 };
37
38 // TODO: FP type must be used as a relative distance type!
39 // and default_distance_result can be some user-defined int type
40 // BUT! This code is experimental and probably won't be released at all
41 // since more flexible user-defined-nearest predicate should be added instead
42
43 template <typename Indexable, typename Segment>
44 struct path_intersection<Indexable, Segment, box_tag, segment_tag>
45 {
46 typedef typename default_distance_result<typename point_type<Segment>::type>::type comparable_distance_type;
47
applyboost::geometry::index::detail::dispatch::path_intersection48 static inline bool apply(Indexable const& b, Segment const& segment, comparable_distance_type & comparable_distance)
49 {
50 typedef typename point_type<Segment>::type point_type;
51 point_type p1, p2;
52 geometry::detail::assign_point_from_index<0>(segment, p1);
53 geometry::detail::assign_point_from_index<1>(segment, p2);
54 return index::detail::segment_intersection(b, p1, p2, comparable_distance);
55 }
56 };
57
58 template <typename Indexable, typename Linestring>
59 struct path_intersection<Indexable, Linestring, box_tag, linestring_tag>
60 {
61 typedef typename default_length_result<Linestring>::type comparable_distance_type;
62
applyboost::geometry::index::detail::dispatch::path_intersection63 static inline bool apply(Indexable const& b, Linestring const& path, comparable_distance_type & comparable_distance)
64 {
65 typedef typename ::boost::range_value<Linestring>::type point_type;
66 typedef typename ::boost::range_const_iterator<Linestring>::type const_iterator;
67 typedef typename ::boost::range_size<Linestring>::type size_type;
68
69 const size_type count = ::boost::size(path);
70
71 if ( count == 2 )
72 {
73 return index::detail::segment_intersection(b, *::boost::begin(path), *(::boost::begin(path)+1), comparable_distance);
74 }
75 else if ( 2 < count )
76 {
77 const_iterator it0 = ::boost::begin(path);
78 const_iterator it1 = ::boost::begin(path) + 1;
79 const_iterator last = ::boost::end(path);
80
81 comparable_distance = 0;
82
83 for ( ; it1 != last ; ++it0, ++it1 )
84 {
85 typename default_distance_result<point_type, point_type>::type
86 dist = geometry::distance(*it0, *it1);
87
88 comparable_distance_type rel_dist;
89 if ( index::detail::segment_intersection(b, *it0, *it1, rel_dist) )
90 {
91 comparable_distance += dist * rel_dist;
92 return true;
93 }
94 else
95 comparable_distance += dist;
96 }
97 }
98
99 return false;
100 }
101 };
102
103 } // namespace dispatch
104
105 template <typename Indexable, typename SegmentOrLinestring>
106 struct default_path_intersection_distance_type
107 {
108 typedef typename dispatch::path_intersection<
109 Indexable, SegmentOrLinestring,
110 typename tag<Indexable>::type,
111 typename tag<SegmentOrLinestring>::type
112 >::comparable_distance_type type;
113 };
114
115 template <typename Indexable, typename SegmentOrLinestring> inline
path_intersection(Indexable const & b,SegmentOrLinestring const & path,typename default_path_intersection_distance_type<Indexable,SegmentOrLinestring>::type & comparable_distance)116 bool path_intersection(Indexable const& b,
117 SegmentOrLinestring const& path,
118 typename default_path_intersection_distance_type<Indexable, SegmentOrLinestring>::type & comparable_distance)
119 {
120 // TODO check Indexable and Linestring concepts
121
122 return dispatch::path_intersection<
123 Indexable, SegmentOrLinestring,
124 typename tag<Indexable>::type,
125 typename tag<SegmentOrLinestring>::type
126 >::apply(b, path, comparable_distance);
127 }
128
129 }}}} // namespace boost::geometry::index::detail
130
131 #endif // BOOST_GEOMETRY_INDEX_DETAIL_ALGORITHMS_PATH_INTERSECTION_HPP
132