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
26namespace 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

source code of boost/boost/graph/is_straight_line_drawing.hpp