1 // Boost.Geometry (aka GGL, Generic Geometry Library)
3 // Copyright (c) 2007-2012 Barend Gehrels, Amsterdam, the Netherlands.
5 // This file was modified by Oracle on 2013, 2014, 2015, 2017, 2018, 2019.
6 // Modifications copyright (c) 2013-2019 Oracle and/or its affiliates.
8 // Contributed and/or modified by Adam Wulkiewicz, on behalf of Oracle
10 // Use, modification and distribution is subject to the Boost Software License,
11 // Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
12 // http://www.boost.org/LICENSE_1_0.txt)
14 #ifndef BOOST_GEOMETRY_ALGORITHMS_DETAIL_RELATE_LINEAR_LINEAR_HPP
15 #define BOOST_GEOMETRY_ALGORITHMS_DETAIL_RELATE_LINEAR_LINEAR_HPP
19 #include <boost/core/ignore_unused.hpp>
20 #include <boost/range/size.hpp>
22 #include <boost/geometry/core/assert.hpp>
24 #include <boost/geometry/util/condition.hpp>
25 #include <boost/geometry/util/range.hpp>
27 #include <boost/geometry/algorithms/detail/sub_range.hpp>
28 #include <boost/geometry/algorithms/detail/single_geometry.hpp>
30 #include <boost/geometry/algorithms/detail/relate/point_geometry.hpp>
31 #include <boost/geometry/algorithms/detail/relate/result.hpp>
32 #include <boost/geometry/algorithms/detail/relate/turns.hpp>
33 #include <boost/geometry/algorithms/detail/relate/boundary_checker.hpp>
34 #include <boost/geometry/algorithms/detail/relate/follow_helpers.hpp>
36 namespace boost { namespace geometry
39 #ifndef DOXYGEN_NO_DETAIL
40 namespace detail { namespace relate {
42 template <typename Result, typename BoundaryChecker, bool TransposeResult>
43 class disjoint_linestring_pred
45 typedef typename BoundaryChecker::equals_strategy_type equals_strategy_type;
48 disjoint_linestring_pred(Result & res,
49 BoundaryChecker const& boundary_checker)
51 , m_boundary_checker(boundary_checker)
54 if ( ! may_update<interior, exterior, '1', TransposeResult>(m_result) )
58 if ( ! may_update<boundary, exterior, '0', TransposeResult>(m_result) )
64 template <typename Linestring>
65 bool operator()(Linestring const& linestring)
72 std::size_t const count = boost::size(linestring);
78 // TODO: throw an exception?
82 // point-like linestring
84 && equals::equals_point_point(range::front(linestring),
85 range::back(linestring),
86 equals_strategy_type()) )
88 update<interior, exterior, '0', TransposeResult>(m_result);
92 update<interior, exterior, '1', TransposeResult>(m_result);
95 // check if there is a boundary
97 && ( m_boundary_checker.template
98 is_endpoint_boundary<boundary_front>(range::front(linestring))
99 || m_boundary_checker.template
100 is_endpoint_boundary<boundary_back>(range::back(linestring)) ) )
102 update<boundary, exterior, '0', TransposeResult>(m_result);
108 && ! m_result.interrupt;
113 BoundaryChecker const& m_boundary_checker;
117 template <typename Geometry1, typename Geometry2>
120 static const bool interruption_enabled = true;
122 typedef typename geometry::point_type<Geometry1>::type point1_type;
123 typedef typename geometry::point_type<Geometry2>::type point2_type;
125 template <typename Result, typename IntersectionStrategy>
126 static inline void apply(Geometry1 const& geometry1, Geometry2 const& geometry2,
128 IntersectionStrategy const& intersection_strategy)
130 typedef typename IntersectionStrategy::cs_tag cs_tag;
132 // The result should be FFFFFFFFF
133 relate::set<exterior, exterior, result_dimension<Geometry1>::value>(result);// FFFFFFFFd, d in [1,9] or T
134 if ( BOOST_GEOMETRY_CONDITION( result.interrupt ) )
137 // get and analyse turns
138 typedef typename turns::get_turns
141 >::template turn_info_type<IntersectionStrategy>::type turn_type;
142 std::vector<turn_type> turns;
144 interrupt_policy_linear_linear<Result> interrupt_policy(result);
150 detail::get_turns::get_turn_info_type<Geometry1, Geometry2, turns::assign_policy<true> >
151 >::apply(turns, geometry1, geometry2, interrupt_policy, intersection_strategy);
153 if ( BOOST_GEOMETRY_CONDITION( result.interrupt ) )
156 typedef boundary_checker
159 typename IntersectionStrategy::point_in_point_strategy_type
160 > boundary_checker1_type;
161 boundary_checker1_type boundary_checker1(geometry1);
162 disjoint_linestring_pred<Result, boundary_checker1_type, false> pred1(result, boundary_checker1);
163 for_each_disjoint_geometry_if<0, Geometry1>::apply(turns.begin(), turns.end(), geometry1, pred1);
164 if ( BOOST_GEOMETRY_CONDITION( result.interrupt ) )
167 typedef boundary_checker
170 typename IntersectionStrategy::point_in_point_strategy_type
171 > boundary_checker2_type;
172 boundary_checker2_type boundary_checker2(geometry2);
173 disjoint_linestring_pred<Result, boundary_checker2_type, true> pred2(result, boundary_checker2);
174 for_each_disjoint_geometry_if<1, Geometry2>::apply(turns.begin(), turns.end(), geometry2, pred2);
175 if ( BOOST_GEOMETRY_CONDITION( result.interrupt ) )
181 // TODO: turns must be sorted and followed only if it's possible to go out and in on the same point
182 // for linear geometries union operation must be detected which I guess would be quite often
184 if ( may_update<interior, interior, '1'>(result)
185 || may_update<interior, boundary, '0'>(result)
186 || may_update<interior, exterior, '1'>(result)
187 || may_update<boundary, interior, '0'>(result)
188 || may_update<boundary, boundary, '0'>(result)
189 || may_update<boundary, exterior, '0'>(result) )
191 typedef turns::less<0, turns::less_op_linear_linear<0>, cs_tag> less;
192 std::sort(turns.begin(), turns.end(), less());
194 turns_analyser<turn_type, 0> analyser;
195 analyse_each_turn(result, analyser,
196 turns.begin(), turns.end(),
197 geometry1, geometry2,
198 boundary_checker1, boundary_checker2);
201 if ( BOOST_GEOMETRY_CONDITION( result.interrupt ) )
204 if ( may_update<interior, interior, '1', true>(result)
205 || may_update<interior, boundary, '0', true>(result)
206 || may_update<interior, exterior, '1', true>(result)
207 || may_update<boundary, interior, '0', true>(result)
208 || may_update<boundary, boundary, '0', true>(result)
209 || may_update<boundary, exterior, '0', true>(result) )
211 typedef turns::less<1, turns::less_op_linear_linear<1>, cs_tag> less;
212 std::sort(turns.begin(), turns.end(), less());
214 turns_analyser<turn_type, 1> analyser;
215 analyse_each_turn(result, analyser,
216 turns.begin(), turns.end(),
217 geometry2, geometry1,
218 boundary_checker2, boundary_checker1);
222 template <typename Result>
223 class interrupt_policy_linear_linear
226 static bool const enabled = true;
228 explicit interrupt_policy_linear_linear(Result & result)
232 // TODO: since we update result for some operations here, we may not do it in the analyser!
234 template <typename Range>
235 inline bool apply(Range const& turns)
237 typedef typename boost::range_iterator<Range const>::type iterator;
239 for (iterator it = boost::begin(turns) ; it != boost::end(turns) ; ++it)
241 if ( it->operations[0].operation == overlay::operation_intersection
242 || it->operations[1].operation == overlay::operation_intersection )
244 update<interior, interior, '1'>(m_result);
246 else if ( ( it->operations[0].operation == overlay::operation_union
247 || it->operations[0].operation == overlay::operation_blocked
248 || it->operations[1].operation == overlay::operation_union
249 || it->operations[1].operation == overlay::operation_blocked )
250 && it->operations[0].position == overlay::position_middle
251 && it->operations[1].position == overlay::position_middle )
253 // TODO: here we could also check the boundaries and set IB,BI,BB at this point
254 update<interior, interior, '0'>(m_result);
258 return m_result.interrupt;
265 // This analyser should be used like Input or SinglePass Iterator
266 template <typename TurnInfo, std::size_t OpId>
269 typedef typename TurnInfo::point_type turn_point_type;
271 static const std::size_t op_id = OpId;
272 static const std::size_t other_op_id = (OpId + 1) % 2;
273 static const bool transpose_result = OpId != 0;
277 : m_previous_turn_ptr(NULL)
278 , m_previous_operation(overlay::operation_none)
279 , m_degenerated_turn_ptr(NULL)
280 , m_collinear_spike_exit(false)
283 template <typename Result,
286 typename OtherGeometry,
287 typename BoundaryChecker,
288 typename OtherBoundaryChecker>
289 void apply(Result & res, TurnIt it,
290 Geometry const& geometry,
291 OtherGeometry const& other_geometry,
292 BoundaryChecker const& boundary_checker,
293 OtherBoundaryChecker const& other_boundary_checker)
295 typedef typename BoundaryChecker::equals_strategy_type equals_strategy_type;
297 overlay::operation_type const op = it->operations[op_id].operation;
299 segment_identifier const& seg_id = it->operations[op_id].seg_id;
300 segment_identifier const& other_id = it->operations[other_op_id].seg_id;
302 bool const first_in_range = m_seg_watcher.update(seg_id);
304 if ( op != overlay::operation_union
305 && op != overlay::operation_intersection
306 && op != overlay::operation_blocked )
309 if ( op == overlay::operation_continue
310 && it->method == overlay::method_none
311 && m_exit_watcher.is_outside(*it)
312 /*&& ( m_exit_watcher.get_exit_operation() == overlay::operation_none
313 || ! turn_on_the_same_ip<op_id>(m_exit_watcher.get_exit_turn(), *it) )*/ )
315 // TODO: rewrite the above condition
317 // WARNING! For spikes the above condition may be TRUE
318 // When degenerated turns are be marked in a different way than c,c/c
319 // different condition will be checked
321 handle_degenerated(res, *it,
322 geometry, other_geometry,
323 boundary_checker, other_boundary_checker,
326 // TODO: not elegant solution! should be rewritten.
327 if ( it->operations[op_id].position == overlay::position_back )
329 m_previous_operation = overlay::operation_blocked;
330 m_exit_watcher.reset_detected_exit();
338 m_degenerated_turn_ptr = NULL;
340 // handle possible exit
341 bool fake_enter_detected = false;
342 if ( m_exit_watcher.get_exit_operation() == overlay::operation_union )
344 // real exit point - may be multiple
345 // we know that we entered and now we exit
346 if ( ! turn_on_the_same_ip<op_id>(m_exit_watcher.get_exit_turn(),
348 equals_strategy_type()) )
350 m_exit_watcher.reset_detected_exit();
353 update<interior, exterior, '1', transpose_result>(res);
355 // fake exit point, reset state
356 else if ( op == overlay::operation_intersection )
358 m_exit_watcher.reset_detected_exit();
359 fake_enter_detected = true;
362 else if ( m_exit_watcher.get_exit_operation() == overlay::operation_blocked )
364 // ignore multiple BLOCKs
365 if ( op == overlay::operation_blocked )
368 if ( op == overlay::operation_intersection
369 && turn_on_the_same_ip<op_id>(m_exit_watcher.get_exit_turn(),
371 equals_strategy_type()) )
373 fake_enter_detected = true;
376 m_exit_watcher.reset_detected_exit();
380 if ( op == overlay::operation_intersection )
382 bool const was_outside = m_exit_watcher.is_outside();
383 m_exit_watcher.enter(*it);
385 // interiors overlaps
386 update<interior, interior, '1', transpose_result>(res);
388 bool const this_b = it->operations[op_id].position == overlay::position_front // ignore spikes!
389 && is_ip_on_boundary<boundary_front>(it->point,
390 it->operations[op_id],
394 // going inside on boundary point
398 // may be front and back
399 bool const other_b = is_ip_on_boundary<boundary_any>(it->point,
400 it->operations[other_op_id],
401 other_boundary_checker,
404 // it's also the boundary of the other geometry
407 update<boundary, boundary, '0', transpose_result>(res);
411 update<boundary, interior, '0', transpose_result>(res);
414 // going inside on non-boundary point
417 // if we didn't enter in the past, we were outside
419 && ! fake_enter_detected
420 && it->operations[op_id].position != overlay::position_front
421 && ! m_collinear_spike_exit )
423 update<interior, exterior, '1', transpose_result>(res);
425 // if it's the first IP then the first point is outside
426 if ( first_in_range )
428 bool const front_b = is_endpoint_on_boundary<boundary_front>(
429 range::front(sub_range(geometry, seg_id)),
432 // if there is a boundary on the first point
435 update<boundary, exterior, '0', transpose_result>(res);
441 m_collinear_spike_exit = false;
443 // u/i, u/u, u/x, x/i, x/u, x/x
444 else if ( op == overlay::operation_union || op == overlay::operation_blocked )
446 // TODO: is exit watcher still needed?
447 // couldn't is_collinear and some going inside counter be used instead?
449 bool const is_collinear = it->operations[op_id].is_collinear;
450 bool const was_outside = m_exit_watcher.is_outside()
451 && m_exit_watcher.get_exit_operation() == overlay::operation_none;
452 // TODO: move the above condition into the exit_watcher?
454 // to exit we must be currently inside and the current segment must be collinear
455 if ( !was_outside && is_collinear )
457 m_exit_watcher.exit(*it, false);
458 // if the position is not set to back it must be a spike
459 if ( it->operations[op_id].position != overlay::position_back )
461 m_collinear_spike_exit = true;
465 bool const op_blocked = op == overlay::operation_blocked;
467 // we're inside and going out from inside
468 // possibly going out right now
469 if ( ! was_outside && is_collinear )
472 && it->operations[op_id].position == overlay::position_back ) // ignore spikes!
474 // check if this is indeed the boundary point
475 // NOTE: is_ip_on_boundary<>() should be called here but the result will be the same
476 if ( is_endpoint_on_boundary<boundary_back>(it->point, boundary_checker) )
478 // may be front and back
479 bool const other_b = is_ip_on_boundary<boundary_any>(it->point,
480 it->operations[other_op_id],
481 other_boundary_checker,
483 // it's also the boundary of the other geometry
486 update<boundary, boundary, '0', transpose_result>(res);
490 update<boundary, interior, '0', transpose_result>(res);
495 // we're outside or intersects some segment from the outside
498 // if we are truly outside
500 && it->operations[op_id].position != overlay::position_front
501 && ! m_collinear_spike_exit
502 /*&& !is_collinear*/ )
504 update<interior, exterior, '1', transpose_result>(res);
507 // boundaries don't overlap - just an optimization
508 if ( it->method == overlay::method_crosses )
510 // the L1 is going from one side of the L2 to the other through the point
511 update<interior, interior, '0', transpose_result>(res);
513 // it's the first point in range
514 if ( first_in_range )
516 bool const front_b = is_endpoint_on_boundary<boundary_front>(
517 range::front(sub_range(geometry, seg_id)),
520 // if there is a boundary on the first point
523 update<boundary, exterior, '0', transpose_result>(res);
527 // method other than crosses, check more conditions
530 bool const this_b = is_ip_on_boundary<boundary_any>(it->point,
531 it->operations[op_id],
535 bool const other_b = is_ip_on_boundary<boundary_any>(it->point,
536 it->operations[other_op_id],
537 other_boundary_checker,
540 // if current IP is on boundary of the geometry
543 // it's also the boundary of the other geometry
546 update<boundary, boundary, '0', transpose_result>(res);
550 update<boundary, interior, '0', transpose_result>(res);
553 // if current IP is not on boundary of the geometry
556 // it's also the boundary of the other geometry
559 update<interior, boundary, '0', transpose_result>(res);
563 update<interior, interior, '0', transpose_result>(res);
567 // first IP on the last segment point - this means that the first point is outside
569 && ( !this_b || op_blocked )
571 && it->operations[op_id].position != overlay::position_front
572 && ! m_collinear_spike_exit
573 /*&& !is_collinear*/ )
575 bool const front_b = is_endpoint_on_boundary<boundary_front>(
576 range::front(sub_range(geometry, seg_id)),
579 // if there is a boundary on the first point
582 update<boundary, exterior, '0', transpose_result>(res);
590 // store ref to previously analysed (valid) turn
591 m_previous_turn_ptr = boost::addressof(*it);
592 // and previously analysed (valid) operation
593 m_previous_operation = op;
597 template <typename Result,
600 typename OtherGeometry,
601 typename BoundaryChecker,
602 typename OtherBoundaryChecker>
603 void apply(Result & res,
604 TurnIt first, TurnIt last,
605 Geometry const& geometry,
606 OtherGeometry const& /*other_geometry*/,
607 BoundaryChecker const& boundary_checker,
608 OtherBoundaryChecker const& /*other_boundary_checker*/)
610 boost::ignore_unused(first, last);
611 //BOOST_GEOMETRY_ASSERT( first != last );
613 // here, the possible exit is the real one
614 // we know that we entered and now we exit
615 if ( /*m_exit_watcher.get_exit_operation() == overlay::operation_union // THIS CHECK IS REDUNDANT
616 ||*/ m_previous_operation == overlay::operation_union
617 || m_degenerated_turn_ptr )
619 update<interior, exterior, '1', transpose_result>(res);
621 BOOST_GEOMETRY_ASSERT(first != last);
623 const TurnInfo * turn_ptr = NULL;
624 if ( m_degenerated_turn_ptr )
625 turn_ptr = m_degenerated_turn_ptr;
626 else if ( m_previous_turn_ptr )
627 turn_ptr = m_previous_turn_ptr;
631 segment_identifier const& prev_seg_id = turn_ptr->operations[op_id].seg_id;
633 //BOOST_GEOMETRY_ASSERT(!boost::empty(sub_range(geometry, prev_seg_id)));
634 bool const prev_back_b = is_endpoint_on_boundary<boundary_back>(
635 range::back(sub_range(geometry, prev_seg_id)),
638 // if there is a boundary on the last point
641 update<boundary, exterior, '0', transpose_result>(res);
647 // reset exit watcher before the analysis of the next Linestring
648 // note that if there are some enters stored there may be some error above
649 m_exit_watcher.reset();
651 m_previous_turn_ptr = NULL;
652 m_previous_operation = overlay::operation_none;
653 m_degenerated_turn_ptr = NULL;
655 // actually if this is set to true here there is some error
656 // in get_turns_ll or relate_ll, an assert could be checked here
657 m_collinear_spike_exit = false;
660 template <typename Result,
663 typename OtherGeometry,
664 typename BoundaryChecker,
665 typename OtherBoundaryChecker>
666 void handle_degenerated(Result & res,
668 Geometry const& geometry,
669 OtherGeometry const& other_geometry,
670 BoundaryChecker const& boundary_checker,
671 OtherBoundaryChecker const& /*other_boundary_checker*/,
674 typedef typename BoundaryChecker::equals_strategy_type
675 equals_strategy1_type;
676 typedef typename OtherBoundaryChecker::equals_strategy_type
677 equals_strategy2_type;
679 typename detail::single_geometry_return_type<Geometry const>::type
680 ls1_ref = detail::single_geometry(geometry, turn.operations[op_id].seg_id);
681 typename detail::single_geometry_return_type<OtherGeometry const>::type
682 ls2_ref = detail::single_geometry(other_geometry, turn.operations[other_op_id].seg_id);
684 // only one of those should be true:
686 if ( turn.operations[op_id].position == overlay::position_front )
688 // valid, point-sized
689 if ( boost::size(ls2_ref) == 2 )
691 bool const front_b = is_endpoint_on_boundary<boundary_front>(turn.point, boundary_checker);
695 update<boundary, interior, '0', transpose_result>(res);
699 update<interior, interior, '0', transpose_result>(res);
702 // operation 'c' should be last for the same IP so we know that the next point won't be the same
703 update<interior, exterior, '1', transpose_result>(res);
705 m_degenerated_turn_ptr = boost::addressof(turn);
708 else if ( turn.operations[op_id].position == overlay::position_back )
710 // valid, point-sized
711 if ( boost::size(ls2_ref) == 2 )
713 update<interior, exterior, '1', transpose_result>(res);
715 bool const back_b = is_endpoint_on_boundary<boundary_back>(turn.point, boundary_checker);
719 update<boundary, interior, '0', transpose_result>(res);
723 update<interior, interior, '0', transpose_result>(res);
726 if ( first_in_range )
728 //BOOST_GEOMETRY_ASSERT(!boost::empty(ls1_ref));
729 bool const front_b = is_endpoint_on_boundary<boundary_front>(
730 range::front(ls1_ref), boundary_checker);
733 update<boundary, exterior, '0', transpose_result>(res);
738 else if ( turn.operations[op_id].position == overlay::position_middle
739 && turn.operations[other_op_id].position == overlay::position_middle )
741 update<interior, interior, '0', transpose_result>(res);
743 // here we don't know which one is degenerated
745 bool const is_point1 = boost::size(ls1_ref) == 2
746 && equals::equals_point_point(range::front(ls1_ref),
747 range::back(ls1_ref),
748 equals_strategy1_type());
749 bool const is_point2 = boost::size(ls2_ref) == 2
750 && equals::equals_point_point(range::front(ls2_ref),
751 range::back(ls2_ref),
752 equals_strategy2_type());
754 // if the second one is degenerated
755 if ( !is_point1 && is_point2 )
757 update<interior, exterior, '1', transpose_result>(res);
759 if ( first_in_range )
761 //BOOST_GEOMETRY_ASSERT(!boost::empty(ls1_ref));
762 bool const front_b = is_endpoint_on_boundary<boundary_front>(
763 range::front(ls1_ref), boundary_checker);
766 update<boundary, exterior, '0', transpose_result>(res);
770 m_degenerated_turn_ptr = boost::addressof(turn);
774 // NOTE: other.position == front and other.position == back
775 // will be handled later, for the other geometry
779 exit_watcher<TurnInfo, OpId> m_exit_watcher;
780 segment_watcher<same_single> m_seg_watcher;
781 const TurnInfo * m_previous_turn_ptr;
782 overlay::operation_type m_previous_operation;
783 const TurnInfo * m_degenerated_turn_ptr;
784 bool m_collinear_spike_exit;
787 template <typename Result,
791 typename OtherGeometry,
792 typename BoundaryChecker,
793 typename OtherBoundaryChecker>
794 static inline void analyse_each_turn(Result & res,
796 TurnIt first, TurnIt last,
797 Geometry const& geometry,
798 OtherGeometry const& other_geometry,
799 BoundaryChecker const& boundary_checker,
800 OtherBoundaryChecker const& other_boundary_checker)
805 for ( TurnIt it = first ; it != last ; ++it )
807 analyser.apply(res, it,
808 geometry, other_geometry,
809 boundary_checker, other_boundary_checker);
811 if ( BOOST_GEOMETRY_CONDITION( res.interrupt ) )
815 analyser.apply(res, first, last,
816 geometry, other_geometry,
817 boundary_checker, other_boundary_checker);
821 }} // namespace detail::relate
822 #endif // DOXYGEN_NO_DETAIL
824 }} // namespace boost::geometry
826 #endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_RELATE_LINEAR_LINEAR_HPP