1 | //======================================================================= |
2 | // Copyright 2007 Aaron Windsor |
3 | // |
4 | // Distributed under the Boost Software License, Version 1.0. (See |
5 | // accompanying file LICENSE_1_0.txt or copy at |
6 | // http://www.boost.org/LICENSE_1_0.txt) |
7 | //======================================================================= |
8 | #ifndef __IS_STRAIGHT_LINE_DRAWING_HPP__ |
9 | #define __IS_STRAIGHT_LINE_DRAWING_HPP__ |
10 | |
11 | #include <boost/config.hpp> |
12 | #include <boost/next_prior.hpp> |
13 | #include <boost/tuple/tuple.hpp> |
14 | #include <boost/tuple/tuple_comparison.hpp> |
15 | #include <boost/property_map/property_map.hpp> |
16 | #include <boost/graph/properties.hpp> |
17 | #include <boost/graph/planar_detail/bucket_sort.hpp> |
18 | |
19 | #include <algorithm> |
20 | #include <vector> |
21 | #include <set> |
22 | #include <map> |
23 | |
24 | |
25 | |
26 | namespace boost |
27 | { |
28 | |
29 | // Return true exactly when the line segments s1 = ((x1,y1), (x2,y2)) and |
30 | // s2 = ((a1,b1), (a2,b2)) intersect in a point other than the endpoints of |
31 | // the line segments. The one exception to this rule is when s1 = s2, in |
32 | // which case false is returned - this is to accomodate multiple edges |
33 | // between the same pair of vertices, which shouldn't invalidate the straight |
34 | // line embedding. A tolerance variable epsilon can also be used, which |
35 | // defines how far away from the endpoints of s1 and s2 we want to consider |
36 | // an intersection. |
37 | |
38 | inline bool intersects(double x1, double y1, |
39 | double x2, double y2, |
40 | double a1, double b1, |
41 | double a2, double b2, |
42 | double epsilon = 0.000001 |
43 | ) |
44 | { |
45 | |
46 | if (x1 - x2 == 0) |
47 | { |
48 | std::swap(a&: x1,b&: a1); |
49 | std::swap(a&: y1,b&: b1); |
50 | std::swap(a&: x2,b&: a2); |
51 | std::swap(a&: y2,b&: b2); |
52 | } |
53 | |
54 | if (x1 - x2 == 0) |
55 | { |
56 | BOOST_USING_STD_MAX(); |
57 | BOOST_USING_STD_MIN(); |
58 | |
59 | //two vertical line segments |
60 | double min_y = min BOOST_PREVENT_MACRO_SUBSTITUTION(a: y1,b: y2); |
61 | double max_y = max BOOST_PREVENT_MACRO_SUBSTITUTION(a: y1,b: y2); |
62 | double min_b = min BOOST_PREVENT_MACRO_SUBSTITUTION(a: b1,b: b2); |
63 | double max_b = max BOOST_PREVENT_MACRO_SUBSTITUTION(a: b1,b: b2); |
64 | if ((max_y > max_b && max_b > min_y) || |
65 | (max_b > max_y && max_y > min_b) |
66 | ) |
67 | return true; |
68 | else |
69 | return false; |
70 | } |
71 | |
72 | double x_diff = x1 - x2; |
73 | double y_diff = y1 - y2; |
74 | double a_diff = a2 - a1; |
75 | double b_diff = b2 - b1; |
76 | |
77 | double beta_denominator = b_diff - (y_diff/((double)x_diff)) * a_diff; |
78 | |
79 | if (beta_denominator == 0) |
80 | { |
81 | //parallel lines |
82 | return false; |
83 | } |
84 | |
85 | double beta = (b2 - y2 - (y_diff/((double)x_diff)) * (a2 - x2)) / |
86 | beta_denominator; |
87 | double alpha = (a2 - x2 - beta*(a_diff))/x_diff; |
88 | |
89 | double upper_bound = 1 - epsilon; |
90 | double lower_bound = 0 + epsilon; |
91 | |
92 | return (beta < upper_bound && beta > lower_bound && |
93 | alpha < upper_bound && alpha > lower_bound); |
94 | |
95 | } |
96 | |
97 | |
98 | template <typename Graph, |
99 | typename GridPositionMap, |
100 | typename VertexIndexMap |
101 | > |
102 | bool is_straight_line_drawing(const Graph& g, |
103 | GridPositionMap drawing, |
104 | VertexIndexMap |
105 | ) |
106 | { |
107 | |
108 | typedef typename graph_traits<Graph>::vertex_descriptor vertex_t; |
109 | typedef typename graph_traits<Graph>::edge_descriptor edge_t; |
110 | typedef typename graph_traits<Graph>::edge_iterator edge_iterator_t; |
111 | |
112 | typedef std::size_t x_coord_t; |
113 | typedef std::size_t y_coord_t; |
114 | typedef boost::tuple<edge_t, x_coord_t, y_coord_t> edge_event_t; |
115 | typedef typename std::vector< edge_event_t > edge_event_queue_t; |
116 | |
117 | typedef tuple<y_coord_t, y_coord_t, x_coord_t, x_coord_t> active_map_key_t; |
118 | typedef edge_t active_map_value_t; |
119 | typedef std::map< active_map_key_t, active_map_value_t > active_map_t; |
120 | typedef typename active_map_t::iterator active_map_iterator_t; |
121 | |
122 | |
123 | edge_event_queue_t edge_event_queue; |
124 | active_map_t active_edges; |
125 | |
126 | edge_iterator_t ei, ei_end; |
127 | for(boost::tie(ei,ei_end) = edges(g); ei != ei_end; ++ei) |
128 | { |
129 | edge_t e(*ei); |
130 | vertex_t s(source(e,g)); |
131 | vertex_t t(target(e,g)); |
132 | edge_event_queue.push_back |
133 | (make_tuple(e, |
134 | static_cast<std::size_t>(drawing[s].x), |
135 | static_cast<std::size_t>(drawing[s].y) |
136 | ) |
137 | ); |
138 | edge_event_queue.push_back |
139 | (make_tuple(e, |
140 | static_cast<std::size_t>(drawing[t].x), |
141 | static_cast<std::size_t>(drawing[t].y) |
142 | ) |
143 | ); |
144 | } |
145 | |
146 | // Order by edge_event_queue by first, then second coordinate |
147 | // (bucket_sort is a stable sort.) |
148 | bucket_sort(edge_event_queue.begin(), edge_event_queue.end(), |
149 | property_map_tuple_adaptor<edge_event_t, 2>() |
150 | ); |
151 | |
152 | bucket_sort(edge_event_queue.begin(), edge_event_queue.end(), |
153 | property_map_tuple_adaptor<edge_event_t, 1>() |
154 | ); |
155 | |
156 | typedef typename edge_event_queue_t::iterator event_queue_iterator_t; |
157 | event_queue_iterator_t itr_end = edge_event_queue.end(); |
158 | for(event_queue_iterator_t itr = edge_event_queue.begin(); |
159 | itr != itr_end; ++itr |
160 | ) |
161 | { |
162 | edge_t e(get<0>(*itr)); |
163 | vertex_t source_v(source(e,g)); |
164 | vertex_t target_v(target(e,g)); |
165 | if (drawing[source_v].y > drawing[target_v].y) |
166 | std::swap(source_v, target_v); |
167 | |
168 | active_map_key_t key(get(drawing, source_v).y, |
169 | get(drawing, target_v).y, |
170 | get(drawing, source_v).x, |
171 | get(drawing, target_v).x |
172 | ); |
173 | |
174 | active_map_iterator_t a_itr = active_edges.find(key); |
175 | if (a_itr == active_edges.end()) |
176 | { |
177 | active_edges[key] = e; |
178 | } |
179 | else |
180 | { |
181 | active_map_iterator_t before, after; |
182 | if (a_itr == active_edges.begin()) |
183 | before = active_edges.end(); |
184 | else |
185 | before = prior(a_itr); |
186 | after = boost::next(a_itr); |
187 | |
188 | if (before != active_edges.end()) |
189 | { |
190 | |
191 | edge_t f = before->second; |
192 | vertex_t e_source(source(e,g)); |
193 | vertex_t e_target(target(e,g)); |
194 | vertex_t f_source(source(f,g)); |
195 | vertex_t f_target(target(f,g)); |
196 | |
197 | if (intersects(drawing[e_source].x, |
198 | drawing[e_source].y, |
199 | drawing[e_target].x, |
200 | drawing[e_target].y, |
201 | drawing[f_source].x, |
202 | drawing[f_source].y, |
203 | drawing[f_target].x, |
204 | drawing[f_target].y |
205 | ) |
206 | ) |
207 | return false; |
208 | } |
209 | |
210 | if (after != active_edges.end()) |
211 | { |
212 | |
213 | edge_t f = after->second; |
214 | vertex_t e_source(source(e,g)); |
215 | vertex_t e_target(target(e,g)); |
216 | vertex_t f_source(source(f,g)); |
217 | vertex_t f_target(target(f,g)); |
218 | |
219 | if (intersects(drawing[e_source].x, |
220 | drawing[e_source].y, |
221 | drawing[e_target].x, |
222 | drawing[e_target].y, |
223 | drawing[f_source].x, |
224 | drawing[f_source].y, |
225 | drawing[f_target].x, |
226 | drawing[f_target].y |
227 | ) |
228 | ) |
229 | return false; |
230 | } |
231 | |
232 | active_edges.erase(a_itr); |
233 | |
234 | } |
235 | } |
236 | |
237 | return true; |
238 | |
239 | } |
240 | |
241 | |
242 | template <typename Graph, typename GridPositionMap> |
243 | bool is_straight_line_drawing(const Graph& g, GridPositionMap drawing) |
244 | { |
245 | return is_straight_line_drawing(g, drawing, get(vertex_index,g)); |
246 | } |
247 | |
248 | } |
249 | |
250 | #endif // __IS_STRAIGHT_LINE_DRAWING_HPP__ |
251 | |