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