1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
|
// Boost.Geometry
// Copyright (c) 2021 Oracle and/or its affiliates.
// Contributed and/or modified by Adam Wulkiewicz, on behalf of Oracle
// Licensed under the Boost Software License version 1.0.
// http://www.boost.org/users/license.html
#ifndef BOOST_GEOMETRY_ALGORITHMS_DETAIL_DISTANCE_GEOMETRY_COLLECTION_HPP
#define BOOST_GEOMETRY_ALGORITHMS_DETAIL_DISTANCE_GEOMETRY_COLLECTION_HPP
#include <vector>
#include <boost/geometry/algorithms/dispatch/distance.hpp>
#include <boost/geometry/algorithms/detail/visit.hpp>
#include <boost/geometry/core/assert.hpp>
#include <boost/geometry/core/point_type.hpp>
#include <boost/geometry/index/rtree.hpp>
#include <boost/geometry/strategies/distance.hpp>
#include <boost/geometry/strategies/distance_result.hpp>
namespace boost { namespace geometry
{
#ifndef DOXYGEN_NO_DETAIL
namespace detail { namespace distance
{
template <typename Geometry, typename GeometryCollection, typename Strategies>
inline auto geometry_to_collection(Geometry const& geometry,
GeometryCollection const& collection,
Strategies const& strategies)
{
using result_t = typename geometry::distance_result<Geometry, GeometryCollection, Strategies>::type;
result_t result = 0;
bool is_first = true;
detail::visit_breadth_first([&](auto const& g)
{
result_t r = dispatch::distance
<
Geometry, util::remove_cref_t<decltype(g)>, Strategies
>::apply(geometry, g, strategies);
if (is_first)
{
result = r;
is_first = false;
}
else if (r < result)
{
result = r;
}
return result > result_t(0);
}, collection);
return result;
}
template <typename GeometryCollection1, typename GeometryCollection2, typename Strategies>
inline auto collection_to_collection(GeometryCollection1 const& collection1,
GeometryCollection2 const& collection2,
Strategies const& strategies)
{
using result_t = typename geometry::distance_result<GeometryCollection1, GeometryCollection2, Strategies>::type;
using point1_t = typename geometry::point_type<GeometryCollection1>::type;
using box1_t = model::box<point1_t>;
using point2_t = typename geometry::point_type<GeometryCollection2>::type;
using box2_t = model::box<point2_t>;
using rtree_value_t = std::pair<box1_t, typename boost::range_iterator<GeometryCollection1 const>::type>;
using rtree_params_t = index::parameters<index::rstar<4>, Strategies>;
using rtree_t = index::rtree<rtree_value_t, rtree_params_t>;
rtree_params_t rtree_params(index::rstar<4>(), strategies);
rtree_t rtree(rtree_params);
// Build rtree of boxes and iterators of elements of GC1
// TODO: replace this with visit_breadth_first_iterator to avoid creating an unnecessary container?
{
std::vector<rtree_value_t> values;
visit_breadth_first_impl<true>::apply([&](auto & g1, auto it)
{
box1_t b1 = geometry::return_envelope<box1_t>(g1, strategies);
geometry::detail::expand_by_epsilon(b1);
values.emplace_back(b1, it);
return true;
}, collection1);
rtree_t rt(values.begin(), values.end(), rtree_params);
rtree = std::move(rt);
}
result_t const zero = 0;
auto const rtree_qend = rtree.qend();
result_t result = 0;
bool is_first = true;
visit_breadth_first([&](auto const& g2)
{
box2_t b2 = geometry::return_envelope<box2_t>(g2, strategies);
geometry::detail::expand_by_epsilon(b2);
for (auto it = rtree.qbegin(index::nearest(b2, rtree.size())) ; it != rtree_qend ; ++it)
{
// If the distance between boxes is greater than or equal to previously found
// distance between geometries then stop processing the current b2 because no
// closer b1 will be found
if (! is_first)
{
result_t const bd = dispatch::distance
<
box1_t, box2_t, Strategies
>::apply(it->first, b2, strategies);
if (bd >= result)
{
break;
}
}
// Boxes are closer than the previously found distance (or it's the first time),
// calculate the new distance between geometries and check if it's closer (or assign it).
traits::iter_visit<GeometryCollection1>::apply([&](auto const& g1)
{
result_t const d = dispatch::distance
<
util::remove_cref_t<decltype(g1)>, util::remove_cref_t<decltype(g2)>,
Strategies
>::apply(g1, g2, strategies);
if (is_first)
{
result = d;
is_first = false;
}
else if (d < result)
{
result = d;
}
}, it->second);
// The smallest possible distance found, end searching.
if (! is_first && result <= zero)
{
return false;
}
}
// Just in case
return is_first || result > zero;
}, collection2);
return result;
}
}} // namespace detail::distance
#endif // DOXYGEN_NO_DETAIL
#ifndef DOXYGEN_NO_DISPATCH
namespace dispatch
{
template
<
typename Geometry, typename GeometryCollection, typename Strategies, typename Tag1
>
struct distance
<
Geometry, GeometryCollection, Strategies,
Tag1, geometry_collection_tag, void, false
>
{
static inline auto apply(Geometry const& geometry,
GeometryCollection const& collection,
Strategies const& strategies)
{
assert_dimension_equal<Geometry, GeometryCollection>();
return detail::distance::geometry_to_collection(geometry, collection, strategies);
}
};
template
<
typename GeometryCollection, typename Geometry, typename Strategies, typename Tag2
>
struct distance
<
GeometryCollection, Geometry, Strategies,
geometry_collection_tag, Tag2, void, false
>
{
static inline auto apply(GeometryCollection const& collection,
Geometry const& geometry,
Strategies const& strategies)
{
assert_dimension_equal<Geometry, GeometryCollection>();
return detail::distance::geometry_to_collection(geometry, collection, strategies);
}
};
template
<
typename GeometryCollection1, typename GeometryCollection2, typename Strategies
>
struct distance
<
GeometryCollection1, GeometryCollection2, Strategies,
geometry_collection_tag, geometry_collection_tag, void, false
>
{
static inline auto apply(GeometryCollection1 const& collection1,
GeometryCollection2 const& collection2,
Strategies const& strategies)
{
assert_dimension_equal<GeometryCollection1, GeometryCollection2>();
// Build the rtree for the smaller GC (ignoring recursive GCs)
return boost::size(collection1) <= boost::size(collection2)
? detail::distance::collection_to_collection(collection1, collection2, strategies)
: detail::distance::collection_to_collection(collection2, collection1, strategies);
}
};
} // namespace dispatch
#endif // DOXYGEN_NO_DISPATCH
}} // namespace boost::geometry
#endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_DISTANCE_SEGMENT_TO_BOX_HPP
|
