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 intersects(double x1,double y1,double x2,double y2,double a1,double b1,double a2,double b2,double epsilon=0.000001)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 > is_straight_line_drawing(const Graph & g,GridPositionMap drawing,VertexIndexMap)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> is_straight_line_drawing(const Graph & g,GridPositionMap drawing)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