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