1 // Boost.Geometry (aka GGL, Generic Geometry Library)
2 
3 // Copyright (c) 2007-2012 Barend Gehrels, Amsterdam, the Netherlands.
4 
5 // Use, modification and distribution is subject to the Boost Software License,
6 // Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
7 // http://www.boost.org/LICENSE_1_0.txt)
8 
9 #ifndef BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_TRAVERSE_HPP
10 #define BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_TRAVERSE_HPP
11 
12 #include <cstddef>
13 
14 #include <boost/geometry/algorithms/detail/overlay/backtrack_check_si.hpp>
15 #include <boost/geometry/algorithms/detail/overlay/traversal_ring_creator.hpp>
16 #include <boost/geometry/algorithms/detail/overlay/traversal_switch_detector.hpp>
17 
18 
19 namespace boost { namespace geometry
20 {
21 
22 #ifndef DOXYGEN_NO_DETAIL
23 namespace detail { namespace overlay
24 {
25 
26 
27 /*!
28     \brief Traverses through intersection points / geometries
29     \ingroup overlay
30  */
31 template
32 <
33     bool Reverse1, bool Reverse2,
34     typename Geometry1,
35     typename Geometry2,
36     overlay_type OverlayType,
37     typename Backtrack = backtrack_check_self_intersections<Geometry1, Geometry2>
38 >
39 class traverse
40 {
41 
42     template <typename Turns>
reset_visits(Turns & turns)43     static void reset_visits(Turns& turns)
44     {
45         for (typename boost::range_iterator<Turns>::type
46             it = boost::begin(turns);
47             it != boost::end(turns);
48             ++it)
49         {
50             for (int i = 0; i < 2; i++)
51             {
52                 it->operations[i].visited.reset();
53             }
54         }
55     }
56 
57 
58 public :
59     template
60     <
61         typename IntersectionStrategy,
62         typename RobustPolicy,
63         typename Turns,
64         typename Rings,
65         typename Visitor,
66         typename Clusters
67     >
apply(Geometry1 const & geometry1,Geometry2 const & geometry2,IntersectionStrategy const & intersection_strategy,RobustPolicy const & robust_policy,Turns & turns,Rings & rings,Clusters & clusters,Visitor & visitor)68     static inline void apply(Geometry1 const& geometry1,
69                 Geometry2 const& geometry2,
70                 IntersectionStrategy const& intersection_strategy,
71                 RobustPolicy const& robust_policy,
72                 Turns& turns, Rings& rings,
73                 Clusters& clusters,
74                 Visitor& visitor)
75     {
76         traversal_switch_detector
77             <
78                 Reverse1, Reverse2, OverlayType,
79                 Geometry1, Geometry2,
80                 Turns, Clusters,
81                 RobustPolicy, Visitor
82             > switch_detector(geometry1, geometry2, turns, clusters,
83                    robust_policy, visitor);
84 
85         switch_detector.iterate();
86         reset_visits(turns);
87 
88         traversal_ring_creator
89             <
90                 Reverse1, Reverse2, OverlayType,
91                 Geometry1, Geometry2,
92                 Turns, Clusters,
93                 IntersectionStrategy,
94                 RobustPolicy, Visitor,
95                 Backtrack
96             > trav(geometry1, geometry2, turns, clusters,
97                    intersection_strategy, robust_policy, visitor);
98 
99         std::size_t finalized_ring_size = boost::size(rings);
100 
101         typename Backtrack::state_type state;
102 
103         trav.iterate(rings, finalized_ring_size, state);
104     }
105 };
106 
107 }} // namespace detail::overlay
108 #endif // DOXYGEN_NO_DETAIL
109 
110 }} // namespace boost::geometry
111 
112 #endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_TRAVERSE_HPP
113