]>
Commit | Line | Data |
---|---|---|
7c673cae FG |
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(x1,a1); | |
49 | std::swap(y1,b1); | |
50 | std::swap(x2,a2); | |
51 | std::swap(y2,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(y1,y2); | |
61 | double max_y = max BOOST_PREVENT_MACRO_SUBSTITUTION(y1,y2); | |
62 | double min_b = min BOOST_PREVENT_MACRO_SUBSTITUTION(b1,b2); | |
63 | double max_b = max BOOST_PREVENT_MACRO_SUBSTITUTION(b1,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__ |