]>
Commit | Line | Data |
---|---|---|
b32b8144 FG |
1 | // Boost.Geometry |
2 | ||
3 | // Copyright (c) 2017 Oracle and/or its affiliates. | |
4 | ||
5 | // Contributed and/or modified by Adam Wulkiewicz, on behalf of Oracle | |
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_ALGORITHMS_DETAIL_RELATE_MULTI_POINT_GEOMETRY_HPP | |
12 | #define BOOST_GEOMETRY_ALGORITHMS_DETAIL_RELATE_MULTI_POINT_GEOMETRY_HPP | |
13 | ||
14 | ||
15 | #include <boost/range.hpp> | |
16 | ||
17 | #include <boost/geometry/algorithms/detail/disjoint/box_box.hpp> | |
18 | #include <boost/geometry/algorithms/detail/disjoint/point_box.hpp> | |
19 | #include <boost/geometry/algorithms/detail/expand_by_epsilon.hpp> | |
20 | #include <boost/geometry/algorithms/detail/relate/result.hpp> | |
21 | #include <boost/geometry/algorithms/detail/relate/topology_check.hpp> | |
22 | #include <boost/geometry/algorithms/detail/within/point_in_geometry.hpp> | |
23 | #include <boost/geometry/algorithms/envelope.hpp> | |
24 | ||
25 | #include <boost/geometry/core/is_areal.hpp> | |
26 | #include <boost/geometry/core/point_type.hpp> | |
27 | ||
28 | #include <boost/geometry/geometries/box.hpp> | |
29 | ||
30 | #include <boost/geometry/index/rtree.hpp> | |
31 | ||
32 | ||
33 | namespace boost { namespace geometry | |
34 | { | |
35 | ||
36 | #ifndef DOXYGEN_NO_DETAIL | |
37 | namespace detail { namespace relate | |
38 | { | |
39 | ||
40 | template | |
41 | < | |
42 | typename Geometry, | |
43 | typename Tag = typename tag<Geometry>::type | |
44 | > | |
45 | struct multi_point_geometry_eb | |
46 | { | |
47 | template <typename MultiPoint> | |
48 | static inline bool apply(MultiPoint const& , | |
49 | detail::relate::topology_check<Geometry> const& ) | |
50 | { | |
51 | return true; | |
52 | } | |
53 | }; | |
54 | ||
55 | template <typename Geometry> | |
56 | struct multi_point_geometry_eb<Geometry, linestring_tag> | |
57 | { | |
58 | template <typename Points> | |
59 | struct boundary_visitor | |
60 | { | |
61 | boundary_visitor(Points const& points) | |
62 | : m_points(points) | |
63 | , m_boundary_found(false) | |
64 | {} | |
65 | ||
66 | template <typename Point> | |
67 | struct find_pred | |
68 | { | |
69 | find_pred(Point const& point) | |
70 | : m_point(point) | |
71 | {} | |
72 | ||
73 | template <typename Pt> | |
74 | bool operator()(Pt const& pt) const | |
75 | { | |
76 | return detail::equals::equals_point_point(pt, m_point); | |
77 | } | |
78 | ||
79 | Point const& m_point; | |
80 | }; | |
81 | ||
82 | template <typename Point> | |
83 | bool apply(Point const& boundary_point) | |
84 | { | |
85 | if (std::find_if(m_points.begin(), m_points.end(), find_pred<Point>(boundary_point)) == m_points.end()) | |
86 | { | |
87 | m_boundary_found = true; | |
88 | return false; | |
89 | } | |
90 | return true; | |
91 | } | |
92 | ||
93 | bool result() const { return m_boundary_found; } | |
94 | ||
95 | private: | |
96 | Points const& m_points; | |
97 | bool m_boundary_found; | |
98 | }; | |
99 | ||
100 | template <typename MultiPoint> | |
101 | static inline bool apply(MultiPoint const& multi_point, | |
102 | detail::relate::topology_check<Geometry> const& tc) | |
103 | { | |
104 | boundary_visitor<MultiPoint> visitor(multi_point); | |
105 | tc.for_each_boundary_point(visitor); | |
106 | return visitor.result(); | |
107 | } | |
108 | }; | |
109 | ||
110 | template <typename Geometry> | |
111 | struct multi_point_geometry_eb<Geometry, multi_linestring_tag> | |
112 | { | |
113 | template <typename Points> | |
114 | struct boundary_visitor | |
115 | { | |
116 | boundary_visitor(Points const& points) | |
117 | : m_points(points) | |
118 | , m_boundary_found(false) | |
119 | {} | |
120 | ||
121 | template <typename Point> | |
122 | bool apply(Point const& boundary_point) | |
123 | { | |
124 | if (! std::binary_search(m_points.begin(), m_points.end(), boundary_point, geometry::less<>())) | |
125 | { | |
126 | m_boundary_found = true; | |
127 | return false; | |
128 | } | |
129 | return true; | |
130 | } | |
131 | ||
132 | bool result() const { return m_boundary_found; } | |
133 | ||
134 | private: | |
135 | Points const& m_points; | |
136 | bool m_boundary_found; | |
137 | }; | |
138 | ||
139 | template <typename MultiPoint> | |
140 | static inline bool apply(MultiPoint const& multi_point, | |
141 | detail::relate::topology_check<Geometry> const& tc) | |
142 | { | |
143 | typedef typename boost::range_value<MultiPoint>::type point_type; | |
144 | typedef std::vector<point_type> points_type; | |
145 | points_type points(boost::begin(multi_point), boost::end(multi_point)); | |
146 | std::sort(points.begin(), points.end(), geometry::less<>()); | |
147 | ||
148 | boundary_visitor<points_type> visitor(points); | |
149 | tc.for_each_boundary_point(visitor); | |
150 | return visitor.result(); | |
151 | } | |
152 | }; | |
153 | ||
154 | // SingleGeometry - Linear or Areal | |
155 | template <typename MultiPoint, typename SingleGeometry, bool Transpose = false> | |
156 | struct multi_point_single_geometry | |
157 | { | |
158 | static const bool interruption_enabled = true; | |
159 | ||
160 | template <typename Result, typename Strategy> | |
161 | static inline void apply(MultiPoint const& multi_point, | |
162 | SingleGeometry const& single_geometry, | |
163 | Result & result, | |
164 | Strategy const& strategy) | |
165 | { | |
166 | typedef typename point_type<SingleGeometry>::type point2_type; | |
167 | typedef model::box<point2_type> box2_type; | |
168 | ||
169 | box2_type box2; | |
170 | geometry::envelope(single_geometry, box2, strategy.get_envelope_strategy()); | |
171 | geometry::detail::expand_by_epsilon(box2); | |
172 | ||
173 | typedef typename boost::range_const_iterator<MultiPoint>::type iterator; | |
174 | for ( iterator it = boost::begin(multi_point) ; it != boost::end(multi_point) ; ++it ) | |
175 | { | |
176 | if (! (relate::may_update<interior, interior, '0', Transpose>(result) | |
177 | || relate::may_update<interior, boundary, '0', Transpose>(result) | |
178 | || relate::may_update<interior, exterior, '0', Transpose>(result) ) ) | |
179 | { | |
180 | break; | |
181 | } | |
182 | ||
183 | // The default strategy is enough for Point/Box | |
184 | if (detail::disjoint::disjoint_point_box(*it, box2)) | |
185 | { | |
186 | relate::set<interior, exterior, '0', Transpose>(result); | |
187 | } | |
188 | else | |
189 | { | |
190 | int in_val = detail::within::point_in_geometry(*it, single_geometry, strategy); | |
191 | ||
192 | if (in_val > 0) // within | |
193 | { | |
194 | relate::set<interior, interior, '0', Transpose>(result); | |
195 | } | |
196 | else if (in_val == 0) | |
197 | { | |
198 | relate::set<interior, boundary, '0', Transpose>(result); | |
199 | } | |
200 | else // in_val < 0 - not within | |
201 | { | |
202 | relate::set<interior, exterior, '0', Transpose>(result); | |
203 | } | |
204 | } | |
205 | ||
206 | if ( BOOST_GEOMETRY_CONDITION(result.interrupt) ) | |
207 | { | |
208 | return; | |
209 | } | |
210 | } | |
211 | ||
212 | typedef detail::relate::topology_check<SingleGeometry> tc_t; | |
213 | if ( relate::may_update<exterior, interior, tc_t::interior, Transpose>(result) | |
214 | || relate::may_update<exterior, boundary, tc_t::boundary, Transpose>(result) ) | |
215 | { | |
216 | tc_t tc(single_geometry); | |
217 | ||
218 | if ( relate::may_update<exterior, interior, tc_t::interior, Transpose>(result) | |
219 | && tc.has_interior() ) | |
220 | { | |
221 | // TODO: this is not true if a linestring is degenerated to a point | |
222 | // then the interior has topological dimension = 0, not 1 | |
223 | relate::set<exterior, interior, tc_t::interior, Transpose>(result); | |
224 | } | |
225 | ||
226 | if ( relate::may_update<exterior, boundary, tc_t::boundary, Transpose>(result) | |
227 | && tc.has_boundary() ) | |
228 | { | |
229 | if (multi_point_geometry_eb<SingleGeometry>::apply(multi_point, tc)) | |
230 | relate::set<exterior, boundary, tc_t::boundary, Transpose>(result); | |
231 | } | |
232 | } | |
233 | ||
234 | relate::set<exterior, exterior, result_dimension<MultiPoint>::value, Transpose>(result); | |
235 | } | |
236 | }; | |
237 | ||
238 | ||
239 | // MultiGeometry - Linear or Areal | |
240 | // part of the algorithm calculating II and IB when no IE has to be calculated | |
241 | // using partition() | |
242 | template <typename MultiPoint, typename MultiGeometry, bool Transpose> | |
243 | class multi_point_multi_geometry_ii_ib | |
244 | { | |
245 | struct expand_box_point | |
246 | { | |
247 | template <typename Box, typename Point> | |
248 | static inline void apply(Box& total, Point const& point) | |
249 | { | |
250 | geometry::expand(total, point); | |
251 | } | |
252 | }; | |
253 | ||
254 | struct expand_box_box_pair | |
255 | { | |
256 | template <typename Box, typename BoxPair> | |
257 | static inline void apply(Box& total, BoxPair const& box_pair) | |
258 | { | |
259 | geometry::expand(total, box_pair.first); | |
260 | } | |
261 | }; | |
262 | ||
263 | struct overlaps_box_point | |
264 | { | |
265 | template <typename Box, typename Point> | |
266 | static inline bool apply(Box const& box, Point const& point) | |
267 | { | |
268 | // The default strategy is enough for Point/Box | |
269 | return ! detail::disjoint::disjoint_point_box(point, box); | |
270 | } | |
271 | }; | |
272 | ||
273 | struct overlaps_box_box_pair | |
274 | { | |
275 | template <typename Box, typename BoxPair> | |
276 | static inline bool apply(Box const& box, BoxPair const& box_pair) | |
277 | { | |
278 | // The default strategy is enough for Box/Box | |
279 | return ! detail::disjoint::disjoint_box_box(box_pair.first, box); | |
280 | } | |
281 | }; | |
282 | ||
283 | template <typename Result, typename PtSegStrategy> | |
284 | class item_visitor_type | |
285 | { | |
286 | public: | |
287 | item_visitor_type(MultiGeometry const& multi_geometry, | |
288 | detail::relate::topology_check<MultiGeometry> const& tc, | |
289 | Result & result, | |
290 | PtSegStrategy const& strategy) | |
291 | : m_multi_geometry(multi_geometry) | |
292 | , m_tc(tc) | |
293 | , m_result(result) | |
294 | , m_strategy(strategy) | |
295 | {} | |
296 | ||
297 | template <typename Point, typename BoxPair> | |
298 | inline bool apply(Point const& point, BoxPair const& box_pair) | |
299 | { | |
300 | // The default strategy is enough for Point/Box | |
301 | if (! detail::disjoint::disjoint_point_box(point, box_pair.first)) | |
302 | { | |
303 | typename boost::range_value<MultiGeometry>::type const& | |
304 | single = range::at(m_multi_geometry, box_pair.second); | |
305 | ||
306 | int in_val = detail::within::point_in_geometry(point, single, m_strategy); | |
307 | ||
308 | if (in_val > 0) // within | |
309 | { | |
310 | relate::set<interior, interior, '0', Transpose>(m_result); | |
311 | } | |
312 | else if (in_val == 0) | |
313 | { | |
314 | if (m_tc.check_boundary_point(point)) | |
315 | relate::set<interior, boundary, '0', Transpose>(m_result); | |
316 | else | |
317 | relate::set<interior, interior, '0', Transpose>(m_result); | |
318 | } | |
319 | } | |
320 | ||
321 | if ( BOOST_GEOMETRY_CONDITION(m_result.interrupt) ) | |
322 | { | |
323 | return false; | |
324 | } | |
325 | ||
326 | if (! (relate::may_update<interior, interior, '0', Transpose>(m_result) | |
327 | || relate::may_update<interior, boundary, '0', Transpose>(m_result) ) ) | |
328 | { | |
329 | return false; | |
330 | } | |
331 | ||
332 | return true; | |
333 | } | |
334 | ||
335 | ||
336 | private: | |
337 | MultiGeometry const& m_multi_geometry; | |
338 | detail::relate::topology_check<MultiGeometry> const& m_tc; | |
339 | Result & m_result; | |
340 | PtSegStrategy const& m_strategy; | |
341 | }; | |
342 | ||
343 | public: | |
344 | typedef typename point_type<MultiPoint>::type point1_type; | |
345 | typedef typename point_type<MultiGeometry>::type point2_type; | |
346 | typedef model::box<point1_type> box1_type; | |
347 | typedef model::box<point2_type> box2_type; | |
348 | typedef std::pair<box2_type, std::size_t> box_pair_type; | |
349 | ||
350 | template <typename Result, typename Strategy> | |
351 | static inline void apply(MultiPoint const& multi_point, | |
352 | MultiGeometry const& multi_geometry, | |
353 | std::vector<box_pair_type> const& boxes, | |
354 | detail::relate::topology_check<MultiGeometry> const& tc, | |
355 | Result & result, | |
356 | Strategy const& strategy) | |
357 | { | |
358 | item_visitor_type<Result, Strategy> visitor(multi_geometry, tc, result, strategy); | |
359 | ||
360 | geometry::partition | |
361 | < | |
362 | box1_type | |
363 | >::apply(multi_point, boxes, visitor, | |
364 | expand_box_point(), | |
365 | overlaps_box_point(), | |
366 | expand_box_box_pair(), | |
367 | overlaps_box_box_pair()); | |
368 | } | |
369 | ||
370 | }; | |
371 | ||
372 | // MultiGeometry - Linear or Areal | |
373 | // part of the algorithm calculating II, IB and IE | |
374 | // using rtree | |
375 | template <typename MultiPoint, typename MultiGeometry, bool Transpose> | |
376 | struct multi_point_multi_geometry_ii_ib_ie | |
377 | { | |
378 | typedef typename point_type<MultiPoint>::type point1_type; | |
379 | typedef typename point_type<MultiGeometry>::type point2_type; | |
380 | typedef model::box<point1_type> box1_type; | |
381 | typedef model::box<point2_type> box2_type; | |
382 | typedef std::pair<box2_type, std::size_t> box_pair_type; | |
383 | typedef std::vector<box_pair_type> boxes_type; | |
384 | typedef typename boxes_type::const_iterator boxes_iterator; | |
385 | ||
386 | template <typename Result, typename Strategy> | |
387 | static inline void apply(MultiPoint const& multi_point, | |
388 | MultiGeometry const& multi_geometry, | |
389 | std::vector<box_pair_type> const& boxes, | |
390 | detail::relate::topology_check<MultiGeometry> const& tc, | |
391 | Result & result, | |
392 | Strategy const& strategy) | |
393 | { | |
394 | index::rtree<box_pair_type, index::rstar<4> > rt(boxes.begin(), boxes.end()); | |
395 | ||
396 | typedef typename boost::range_const_iterator<MultiPoint>::type iterator; | |
397 | for ( iterator it = boost::begin(multi_point) ; it != boost::end(multi_point) ; ++it ) | |
398 | { | |
399 | if (! (relate::may_update<interior, interior, '0', Transpose>(result) | |
400 | || relate::may_update<interior, boundary, '0', Transpose>(result) | |
401 | || relate::may_update<interior, exterior, '0', Transpose>(result) ) ) | |
402 | { | |
403 | return; | |
404 | } | |
405 | ||
406 | typename boost::range_value<MultiPoint>::type const& point = *it; | |
407 | ||
408 | boxes_type boxes_found; | |
409 | rt.query(index::intersects(point), std::back_inserter(boxes_found)); | |
410 | ||
411 | bool found_ii_or_ib = false; | |
412 | for (boxes_iterator bi = boxes_found.begin() ; bi != boxes_found.end() ; ++bi) | |
413 | { | |
414 | typename boost::range_value<MultiGeometry>::type const& | |
415 | single = range::at(multi_geometry, bi->second); | |
416 | ||
417 | int in_val = detail::within::point_in_geometry(point, single, strategy); | |
418 | ||
419 | if (in_val > 0) // within | |
420 | { | |
421 | relate::set<interior, interior, '0', Transpose>(result); | |
422 | found_ii_or_ib = true; | |
423 | } | |
424 | else if (in_val == 0) // on boundary of single | |
425 | { | |
426 | if (tc.check_boundary_point(point)) | |
427 | relate::set<interior, boundary, '0', Transpose>(result); | |
428 | else | |
429 | relate::set<interior, interior, '0', Transpose>(result); | |
430 | found_ii_or_ib = true; | |
431 | } | |
432 | } | |
433 | ||
434 | // neither interior nor boundary found -> exterior | |
435 | if (found_ii_or_ib == false) | |
436 | { | |
437 | relate::set<interior, exterior, '0', Transpose>(result); | |
438 | } | |
439 | ||
440 | if ( BOOST_GEOMETRY_CONDITION(result.interrupt) ) | |
441 | { | |
442 | return; | |
443 | } | |
444 | } | |
445 | } | |
446 | }; | |
447 | ||
448 | // MultiGeometry - Linear or Areal | |
449 | template <typename MultiPoint, typename MultiGeometry, bool Transpose = false> | |
450 | struct multi_point_multi_geometry | |
451 | { | |
452 | static const bool interruption_enabled = true; | |
453 | ||
454 | template <typename Result, typename Strategy> | |
455 | static inline void apply(MultiPoint const& multi_point, | |
456 | MultiGeometry const& multi_geometry, | |
457 | Result & result, | |
458 | Strategy const& strategy) | |
459 | { | |
460 | typedef typename point_type<MultiGeometry>::type point2_type; | |
461 | typedef model::box<point2_type> box2_type; | |
462 | typedef std::pair<box2_type, std::size_t> box_pair_type; | |
463 | ||
464 | typename Strategy::envelope_strategy_type const | |
465 | envelope_strategy = strategy.get_envelope_strategy(); | |
466 | ||
467 | std::size_t count2 = boost::size(multi_geometry); | |
468 | std::vector<box_pair_type> boxes(count2); | |
469 | for (std::size_t i = 0 ; i < count2 ; ++i) | |
470 | { | |
471 | geometry::envelope(range::at(multi_geometry, i), boxes[i].first, envelope_strategy); | |
472 | geometry::detail::expand_by_epsilon(boxes[i].first); | |
473 | boxes[i].second = i; | |
474 | } | |
475 | ||
476 | typedef detail::relate::topology_check<MultiGeometry> tc_t; | |
477 | tc_t tc(multi_geometry); | |
478 | ||
479 | if ( relate::may_update<interior, interior, '0', Transpose>(result) | |
480 | || relate::may_update<interior, boundary, '0', Transpose>(result) | |
481 | || relate::may_update<interior, exterior, '0', Transpose>(result) ) | |
482 | { | |
483 | // If there is no need to calculate IE, use partition | |
484 | if (! relate::may_update<interior, exterior, '0', Transpose>(result) ) | |
485 | { | |
486 | multi_point_multi_geometry_ii_ib<MultiPoint, MultiGeometry, Transpose> | |
487 | ::apply(multi_point, multi_geometry, boxes, tc, result, strategy); | |
488 | } | |
489 | else // otherwise use rtree | |
490 | { | |
491 | multi_point_multi_geometry_ii_ib_ie<MultiPoint, MultiGeometry, Transpose> | |
492 | ::apply(multi_point, multi_geometry, boxes, tc, result, strategy); | |
493 | } | |
494 | } | |
495 | ||
496 | if ( BOOST_GEOMETRY_CONDITION(result.interrupt) ) | |
497 | { | |
498 | return; | |
499 | } | |
500 | ||
501 | if ( relate::may_update<exterior, interior, tc_t::interior, Transpose>(result) | |
502 | || relate::may_update<exterior, boundary, tc_t::boundary, Transpose>(result) ) | |
503 | { | |
504 | if ( relate::may_update<exterior, interior, tc_t::interior, Transpose>(result) | |
505 | && tc.has_interior() ) | |
506 | { | |
507 | // TODO: this is not true if a linestring is degenerated to a point | |
508 | // then the interior has topological dimension = 0, not 1 | |
509 | relate::set<exterior, interior, tc_t::interior, Transpose>(result); | |
510 | } | |
511 | ||
512 | if ( relate::may_update<exterior, boundary, tc_t::boundary, Transpose>(result) | |
513 | && tc.has_boundary() ) | |
514 | { | |
515 | if (multi_point_geometry_eb<MultiGeometry>::apply(multi_point, tc)) | |
516 | relate::set<exterior, boundary, tc_t::boundary, Transpose>(result); | |
517 | } | |
518 | } | |
519 | ||
520 | relate::set<exterior, exterior, result_dimension<MultiPoint>::value, Transpose>(result); | |
521 | } | |
522 | ||
523 | }; | |
524 | ||
525 | ||
526 | template | |
527 | < | |
528 | typename MultiPoint, typename Geometry, | |
529 | bool Transpose = false, | |
530 | bool isMulti = boost::is_same | |
531 | < | |
532 | typename tag_cast | |
533 | < | |
534 | typename tag<Geometry>::type, multi_tag | |
535 | >::type, | |
536 | multi_tag | |
537 | >::value | |
538 | > | |
539 | struct multi_point_geometry | |
540 | : multi_point_single_geometry<MultiPoint, Geometry, Transpose> | |
541 | {}; | |
542 | ||
543 | template <typename MultiPoint, typename Geometry, bool Transpose> | |
544 | struct multi_point_geometry<MultiPoint, Geometry, Transpose, true> | |
545 | : multi_point_multi_geometry<MultiPoint, Geometry, Transpose> | |
546 | {}; | |
547 | ||
548 | ||
549 | // transposed result of multi_point_geometry | |
550 | template <typename Geometry, typename MultiPoint> | |
551 | struct geometry_multi_point | |
552 | { | |
553 | static const bool interruption_enabled = true; | |
554 | ||
555 | template <typename Result, typename Strategy> | |
556 | static inline void apply(Geometry const& geometry, MultiPoint const& multi_point, | |
557 | Result & result, Strategy const& strategy) | |
558 | { | |
559 | multi_point_geometry<MultiPoint, Geometry, true>::apply(multi_point, geometry, result, strategy); | |
560 | } | |
561 | }; | |
562 | ||
563 | }} // namespace detail::relate | |
564 | #endif // DOXYGEN_NO_DETAIL | |
565 | ||
566 | }} // namespace boost::geometry | |
567 | ||
568 | #endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_RELATE_MULTI_POINT_GEOMETRY_HPP |