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_CHECK_ENRICH_HPP
10 #define BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_CHECK_ENRICH_HPP
11 
12 
13 #include <cstddef>
14 
15 #include <boost/range.hpp>
16 
17 #include <boost/geometry/algorithms/detail/ring_identifier.hpp>
18 
19 
20 namespace boost { namespace geometry
21 {
22 
23 #ifndef DOXYGEN_NO_DETAIL
24 namespace detail { namespace overlay
25 {
26 
27 
28 template<typename Turn>
29 struct meta_turn
30 {
31     int index;
32     Turn const* turn;
33     bool handled[2];
34 
meta_turnboost::geometry::detail::overlay::meta_turn35     inline meta_turn(int i, Turn const& t)
36         : index(i), turn(&t)
37     {
38         handled[0] = false;
39         handled[1] = false;
40     }
41 };
42 
43 
44 template <typename MetaTurn>
display(MetaTurn const & meta_turn,std::string const & reason="")45 inline void display(MetaTurn const& meta_turn, std::string const& reason = "")
46 {
47 #ifdef BOOST_GEOMETRY_DEBUG_ENRICH
48     std::cout << meta_turn.index
49         << "\tMethods: " << method_char(meta_turn.turn->method)
50         << " operations: "  << operation_char(meta_turn.turn->operations[0].operation)
51                 << operation_char(meta_turn.turn->operations[1].operation)
52         << " travels to " << meta_turn.turn->operations[0].enriched.travels_to_ip_index
53         << " and " << meta_turn.turn->operations[1].enriched.travels_to_ip_index
54         //<< " -> " << op_index
55         << " " << reason
56         << std::endl;
57 #endif
58 }
59 
60 
61 template <typename MetaTurns, typename MetaTurn>
check_detailed(MetaTurns & meta_turns,MetaTurn const & meta_turn,int op_index,int cycle,int start,operation_type for_operation,bool & error)62 inline void check_detailed(MetaTurns& meta_turns, MetaTurn const& meta_turn,
63             int op_index, int cycle, int start, operation_type for_operation,
64             bool& error)
65 {
66     display(meta_turn);
67     int const ip_index = meta_turn.turn->operations[op_index].enriched.travels_to_ip_index;
68     if (ip_index >= 0)
69     {
70         bool found = false;
71 
72         if (ip_index == start)
73         {
74             display(meta_turns[ip_index], " FINISH");
75             return;
76         }
77 
78         // check on continuing, or on same-operation-on-same-geometry
79         if (! meta_turns[ip_index].handled[op_index]
80             && (meta_turns[ip_index].turn->operations[op_index].operation == operation_continue
81                 || meta_turns[ip_index].turn->operations[op_index].operation == for_operation)
82             )
83         {
84             meta_turns[ip_index].handled[op_index] = true;
85             check_detailed(meta_turns, meta_turns[ip_index], op_index, cycle, start, for_operation, error);
86             found = true;
87         }
88         // check on other geometry
89         if (! found)
90         {
91             int const other_index = 1 - op_index;
92             if (! meta_turns[ip_index].handled[other_index]
93                 && meta_turns[ip_index].turn->operations[other_index].operation == for_operation)
94             {
95                 meta_turns[ip_index].handled[other_index] = true;
96                 check_detailed(meta_turns, meta_turns[ip_index], other_index, cycle, start, for_operation, error);
97                 found = true;
98             }
99         }
100 
101         if (! found)
102         {
103             display(meta_turns[ip_index], " STOP");
104             error = true;
105 #ifndef BOOST_GEOMETRY_DEBUG_ENRICH
106             //std::cout << " STOP";
107 #endif
108         }
109     }
110 }
111 
112 
113 template <typename TurnPoints>
check_graph(TurnPoints & turn_points,operation_type for_operation)114 inline bool check_graph(TurnPoints& turn_points, operation_type for_operation)
115 {
116     typedef typename boost::range_value<TurnPoints>::type turn_point_type;
117 
118     bool error = false;
119     int index = 0;
120 
121     std::vector<meta_turn<turn_point_type> > meta_turns;
122     for (typename boost::range_iterator<TurnPoints const>::type
123             it = boost::begin(turn_points);
124          it != boost::end(turn_points);
125          ++it, ++index)
126     {
127         meta_turns.push_back(meta_turn<turn_point_type>(index, *it));
128     }
129 
130     int cycle = 0;
131     for (typename boost::range_iterator<std::vector<meta_turn<turn_point_type> > > ::type
132             it = boost::begin(meta_turns);
133          it != boost::end(meta_turns);
134          ++it)
135     {
136         if (! (it->turn->blocked() || it->turn->discarded))
137         {
138             for (int i = 0 ; i < 2; i++)
139             {
140                 if (! it->handled[i]
141                     && it->turn->operations[i].operation == for_operation)
142                 {
143 #ifdef BOOST_GEOMETRY_DEBUG_ENRICH
144                     std::cout << "CYCLE " << cycle << std::endl;
145 #endif
146                     it->handled[i] = true;
147                     check_detailed(meta_turns, *it, i, cycle++, it->index, for_operation, error);
148 #ifdef BOOST_GEOMETRY_DEBUG_ENRICH
149                     std::cout <<" END CYCLE " << it->index << std::endl;
150 #endif
151                 }
152             }
153         }
154     }
155     return error;
156 }
157 
158 
159 
160 }} // namespace detail::overlay
161 #endif //DOXYGEN_NO_DETAIL
162 
163 
164 
165 }} // namespace boost::geometry
166 
167 
168 #endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_CHECK_ENRICH_HPP
169