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 namespace boost
25 {
26
27 // Return true exactly when the line segments s1 = ((x1,y1), (x2,y2)) and
28 // s2 = ((a1,b1), (a2,b2)) intersect in a point other than the endpoints of
29 // the line segments. The one exception to this rule is when s1 = s2, in
30 // which case false is returned - this is to accomodate multiple edges
31 // between the same pair of vertices, which shouldn't invalidate the straight
32 // line embedding. A tolerance variable epsilon can also be used, which
33 // defines how far away from the endpoints of s1 and s2 we want to consider
34 // an intersection.
35
intersects(double x1,double y1,double x2,double y2,double a1,double b1,double a2,double b2,double epsilon=0.000001)36 inline bool intersects(double x1, double y1, double x2, double y2, double a1,
37 double b1, double a2, double b2, double epsilon = 0.000001)
38 {
39
40 if (x1 - x2 == 0)
41 {
42 std::swap(x1, a1);
43 std::swap(y1, b1);
44 std::swap(x2, a2);
45 std::swap(y2, b2);
46 }
47
48 if (x1 - x2 == 0)
49 {
50 BOOST_USING_STD_MAX();
51 BOOST_USING_STD_MIN();
52
53 // two vertical line segments
54 double min_y = min BOOST_PREVENT_MACRO_SUBSTITUTION(y1, y2);
55 double max_y = max BOOST_PREVENT_MACRO_SUBSTITUTION(y1, y2);
56 double min_b = min BOOST_PREVENT_MACRO_SUBSTITUTION(b1, b2);
57 double max_b = max BOOST_PREVENT_MACRO_SUBSTITUTION(b1, b2);
58 if ((max_y > max_b && max_b > min_y)
59 || (max_b > max_y && max_y > min_b))
60 return true;
61 else
62 return false;
63 }
64
65 double x_diff = x1 - x2;
66 double y_diff = y1 - y2;
67 double a_diff = a2 - a1;
68 double b_diff = b2 - b1;
69
70 double beta_denominator = b_diff - (y_diff / ((double)x_diff)) * a_diff;
71
72 if (beta_denominator == 0)
73 {
74 // parallel lines
75 return false;
76 }
77
78 double beta = (b2 - y2 - (y_diff / ((double)x_diff)) * (a2 - x2))
79 / beta_denominator;
80 double alpha = (a2 - x2 - beta * (a_diff)) / x_diff;
81
82 double upper_bound = 1 - epsilon;
83 double lower_bound = 0 + epsilon;
84
85 return (beta < upper_bound && beta > lower_bound && alpha < upper_bound
86 && alpha > lower_bound);
87 }
88
89 template < typename Graph, typename GridPositionMap, typename VertexIndexMap >
is_straight_line_drawing(const Graph & g,GridPositionMap drawing,VertexIndexMap)90 bool is_straight_line_drawing(
91 const Graph& g, GridPositionMap drawing, VertexIndexMap)
92 {
93
94 typedef typename graph_traits< Graph >::vertex_descriptor vertex_t;
95 typedef typename graph_traits< Graph >::edge_descriptor edge_t;
96 typedef typename graph_traits< Graph >::edge_iterator edge_iterator_t;
97
98 typedef std::size_t x_coord_t;
99 typedef std::size_t y_coord_t;
100 typedef boost::tuple< edge_t, x_coord_t, y_coord_t > edge_event_t;
101 typedef typename std::vector< edge_event_t > edge_event_queue_t;
102
103 typedef tuple< y_coord_t, y_coord_t, x_coord_t, x_coord_t >
104 active_map_key_t;
105 typedef edge_t active_map_value_t;
106 typedef std::map< active_map_key_t, active_map_value_t > active_map_t;
107 typedef typename active_map_t::iterator active_map_iterator_t;
108
109 edge_event_queue_t edge_event_queue;
110 active_map_t active_edges;
111
112 edge_iterator_t ei, ei_end;
113 for (boost::tie(ei, ei_end) = edges(g); ei != ei_end; ++ei)
114 {
115 edge_t e(*ei);
116 vertex_t s(source(e, g));
117 vertex_t t(target(e, g));
118 edge_event_queue.push_back(
119 make_tuple(e, static_cast< std::size_t >(drawing[s].x),
120 static_cast< std::size_t >(drawing[s].y)));
121 edge_event_queue.push_back(
122 make_tuple(e, static_cast< std::size_t >(drawing[t].x),
123 static_cast< std::size_t >(drawing[t].y)));
124 }
125
126 // Order by edge_event_queue by first, then second coordinate
127 // (bucket_sort is a stable sort.)
128 bucket_sort(edge_event_queue.begin(), edge_event_queue.end(),
129 property_map_tuple_adaptor< edge_event_t, 2 >());
130
131 bucket_sort(edge_event_queue.begin(), edge_event_queue.end(),
132 property_map_tuple_adaptor< edge_event_t, 1 >());
133
134 typedef typename edge_event_queue_t::iterator event_queue_iterator_t;
135 event_queue_iterator_t itr_end = edge_event_queue.end();
136 for (event_queue_iterator_t itr = edge_event_queue.begin(); itr != itr_end;
137 ++itr)
138 {
139 edge_t e(get< 0 >(*itr));
140 vertex_t source_v(source(e, g));
141 vertex_t target_v(target(e, g));
142 if (drawing[source_v].y > drawing[target_v].y)
143 std::swap(source_v, target_v);
144
145 active_map_key_t key(get(drawing, source_v).y, get(drawing, target_v).y,
146 get(drawing, source_v).x, get(drawing, target_v).x);
147
148 active_map_iterator_t a_itr = active_edges.find(key);
149 if (a_itr == active_edges.end())
150 {
151 active_edges[key] = e;
152 }
153 else
154 {
155 active_map_iterator_t before, after;
156 if (a_itr == active_edges.begin())
157 before = active_edges.end();
158 else
159 before = prior(a_itr);
160 after = boost::next(a_itr);
161
162 if (before != active_edges.end())
163 {
164
165 edge_t f = before->second;
166 vertex_t e_source(source(e, g));
167 vertex_t e_target(target(e, g));
168 vertex_t f_source(source(f, g));
169 vertex_t f_target(target(f, g));
170
171 if (intersects(drawing[e_source].x, drawing[e_source].y,
172 drawing[e_target].x, drawing[e_target].y,
173 drawing[f_source].x, drawing[f_source].y,
174 drawing[f_target].x, drawing[f_target].y))
175 return false;
176 }
177
178 if (after != active_edges.end())
179 {
180
181 edge_t f = after->second;
182 vertex_t e_source(source(e, g));
183 vertex_t e_target(target(e, g));
184 vertex_t f_source(source(f, g));
185 vertex_t f_target(target(f, g));
186
187 if (intersects(drawing[e_source].x, drawing[e_source].y,
188 drawing[e_target].x, drawing[e_target].y,
189 drawing[f_source].x, drawing[f_source].y,
190 drawing[f_target].x, drawing[f_target].y))
191 return false;
192 }
193
194 active_edges.erase(a_itr);
195 }
196 }
197
198 return true;
199 }
200
201 template < typename Graph, typename GridPositionMap >
is_straight_line_drawing(const Graph & g,GridPositionMap drawing)202 bool is_straight_line_drawing(const Graph& g, GridPositionMap drawing)
203 {
204 return is_straight_line_drawing(g, drawing, get(vertex_index, g));
205 }
206
207 }
208
209 #endif // __IS_STRAIGHT_LINE_DRAWING_HPP__
210