Chris@16: //======================================================================= Chris@16: // Copyright 2007 Aaron Windsor Chris@16: // Chris@16: // Distributed under the Boost Software License, Version 1.0. (See Chris@16: // accompanying file LICENSE_1_0.txt or copy at Chris@16: // http://www.boost.org/LICENSE_1_0.txt) Chris@16: //======================================================================= Chris@16: #ifndef __IS_STRAIGHT_LINE_DRAWING_HPP__ Chris@16: #define __IS_STRAIGHT_LINE_DRAWING_HPP__ Chris@16: Chris@16: #include Chris@16: #include Chris@16: #include Chris@16: #include Chris@16: #include Chris@16: #include Chris@16: #include Chris@16: Chris@16: #include Chris@16: #include Chris@16: #include Chris@16: #include Chris@16: Chris@16: Chris@16: Chris@16: namespace boost Chris@16: { Chris@16: Chris@16: // Return true exactly when the line segments s1 = ((x1,y1), (x2,y2)) and Chris@16: // s2 = ((a1,b1), (a2,b2)) intersect in a point other than the endpoints of Chris@16: // the line segments. The one exception to this rule is when s1 = s2, in Chris@16: // which case false is returned - this is to accomodate multiple edges Chris@16: // between the same pair of vertices, which shouldn't invalidate the straight Chris@16: // line embedding. A tolerance variable epsilon can also be used, which Chris@16: // defines how far away from the endpoints of s1 and s2 we want to consider Chris@16: // an intersection. Chris@16: Chris@16: inline bool intersects(double x1, double y1, Chris@16: double x2, double y2, Chris@16: double a1, double b1, Chris@16: double a2, double b2, Chris@16: double epsilon = 0.000001 Chris@16: ) Chris@16: { Chris@16: Chris@16: if (x1 - x2 == 0) Chris@16: { Chris@16: std::swap(x1,a1); Chris@16: std::swap(y1,b1); Chris@16: std::swap(x2,a2); Chris@16: std::swap(y2,b2); Chris@16: } Chris@16: Chris@16: if (x1 - x2 == 0) Chris@16: { Chris@16: BOOST_USING_STD_MAX(); Chris@16: BOOST_USING_STD_MIN(); Chris@16: Chris@16: //two vertical line segments Chris@16: double min_y = min BOOST_PREVENT_MACRO_SUBSTITUTION(y1,y2); Chris@16: double max_y = max BOOST_PREVENT_MACRO_SUBSTITUTION(y1,y2); Chris@16: double min_b = min BOOST_PREVENT_MACRO_SUBSTITUTION(b1,b2); Chris@16: double max_b = max BOOST_PREVENT_MACRO_SUBSTITUTION(b1,b2); Chris@16: if ((max_y > max_b && max_b > min_y) || Chris@16: (max_b > max_y && max_y > min_b) Chris@16: ) Chris@16: return true; Chris@16: else Chris@16: return false; Chris@16: } Chris@16: Chris@16: double x_diff = x1 - x2; Chris@16: double y_diff = y1 - y2; Chris@16: double a_diff = a2 - a1; Chris@16: double b_diff = b2 - b1; Chris@16: Chris@16: double beta_denominator = b_diff - (y_diff/((double)x_diff)) * a_diff; Chris@16: Chris@16: if (beta_denominator == 0) Chris@16: { Chris@16: //parallel lines Chris@16: return false; Chris@16: } Chris@16: Chris@16: double beta = (b2 - y2 - (y_diff/((double)x_diff)) * (a2 - x2)) / Chris@16: beta_denominator; Chris@16: double alpha = (a2 - x2 - beta*(a_diff))/x_diff; Chris@16: Chris@16: double upper_bound = 1 - epsilon; Chris@16: double lower_bound = 0 + epsilon; Chris@16: Chris@16: return (beta < upper_bound && beta > lower_bound && Chris@16: alpha < upper_bound && alpha > lower_bound); Chris@16: Chris@16: } Chris@16: Chris@16: Chris@16: template Chris@16: bool is_straight_line_drawing(const Graph& g, Chris@16: GridPositionMap drawing, Chris@16: VertexIndexMap Chris@16: ) Chris@16: { Chris@16: Chris@16: typedef typename graph_traits::vertex_descriptor vertex_t; Chris@16: typedef typename graph_traits::edge_descriptor edge_t; Chris@16: typedef typename graph_traits::edge_iterator edge_iterator_t; Chris@16: Chris@16: typedef std::size_t x_coord_t; Chris@16: typedef std::size_t y_coord_t; Chris@16: typedef boost::tuple edge_event_t; Chris@16: typedef typename std::vector< edge_event_t > edge_event_queue_t; Chris@16: Chris@16: typedef tuple active_map_key_t; Chris@16: typedef edge_t active_map_value_t; Chris@16: typedef std::map< active_map_key_t, active_map_value_t > active_map_t; Chris@16: typedef typename active_map_t::iterator active_map_iterator_t; Chris@16: Chris@16: Chris@16: edge_event_queue_t edge_event_queue; Chris@16: active_map_t active_edges; Chris@16: Chris@16: edge_iterator_t ei, ei_end; Chris@16: for(boost::tie(ei,ei_end) = edges(g); ei != ei_end; ++ei) Chris@16: { Chris@16: edge_t e(*ei); Chris@16: vertex_t s(source(e,g)); Chris@16: vertex_t t(target(e,g)); Chris@16: edge_event_queue.push_back Chris@16: (make_tuple(e, Chris@16: static_cast(drawing[s].x), Chris@16: static_cast(drawing[s].y) Chris@16: ) Chris@16: ); Chris@16: edge_event_queue.push_back Chris@16: (make_tuple(e, Chris@16: static_cast(drawing[t].x), Chris@16: static_cast(drawing[t].y) Chris@16: ) Chris@16: ); Chris@16: } Chris@16: Chris@16: // Order by edge_event_queue by first, then second coordinate Chris@16: // (bucket_sort is a stable sort.) Chris@16: bucket_sort(edge_event_queue.begin(), edge_event_queue.end(), Chris@16: property_map_tuple_adaptor() Chris@16: ); Chris@16: Chris@16: bucket_sort(edge_event_queue.begin(), edge_event_queue.end(), Chris@16: property_map_tuple_adaptor() Chris@16: ); Chris@16: Chris@16: typedef typename edge_event_queue_t::iterator event_queue_iterator_t; Chris@16: event_queue_iterator_t itr_end = edge_event_queue.end(); Chris@16: for(event_queue_iterator_t itr = edge_event_queue.begin(); Chris@16: itr != itr_end; ++itr Chris@16: ) Chris@16: { Chris@16: edge_t e(get<0>(*itr)); Chris@16: vertex_t source_v(source(e,g)); Chris@16: vertex_t target_v(target(e,g)); Chris@16: if (drawing[source_v].y > drawing[target_v].y) Chris@16: std::swap(source_v, target_v); Chris@16: Chris@16: active_map_key_t key(get(drawing, source_v).y, Chris@16: get(drawing, target_v).y, Chris@16: get(drawing, source_v).x, Chris@16: get(drawing, target_v).x Chris@16: ); Chris@16: Chris@16: active_map_iterator_t a_itr = active_edges.find(key); Chris@16: if (a_itr == active_edges.end()) Chris@16: { Chris@16: active_edges[key] = e; Chris@16: } Chris@16: else Chris@16: { Chris@16: active_map_iterator_t before, after; Chris@16: if (a_itr == active_edges.begin()) Chris@16: before = active_edges.end(); Chris@16: else Chris@16: before = prior(a_itr); Chris@16: after = boost::next(a_itr); Chris@16: Chris@16: if (before != active_edges.end()) Chris@16: { Chris@16: Chris@16: edge_t f = before->second; Chris@16: vertex_t e_source(source(e,g)); Chris@16: vertex_t e_target(target(e,g)); Chris@16: vertex_t f_source(source(f,g)); Chris@16: vertex_t f_target(target(f,g)); Chris@16: Chris@16: if (intersects(drawing[e_source].x, Chris@16: drawing[e_source].y, Chris@16: drawing[e_target].x, Chris@16: drawing[e_target].y, Chris@16: drawing[f_source].x, Chris@16: drawing[f_source].y, Chris@16: drawing[f_target].x, Chris@16: drawing[f_target].y Chris@16: ) Chris@16: ) Chris@16: return false; Chris@16: } Chris@16: Chris@16: if (after != active_edges.end()) Chris@16: { Chris@16: Chris@16: edge_t f = after->second; Chris@16: vertex_t e_source(source(e,g)); Chris@16: vertex_t e_target(target(e,g)); Chris@16: vertex_t f_source(source(f,g)); Chris@16: vertex_t f_target(target(f,g)); Chris@16: Chris@16: if (intersects(drawing[e_source].x, Chris@16: drawing[e_source].y, Chris@16: drawing[e_target].x, Chris@16: drawing[e_target].y, Chris@16: drawing[f_source].x, Chris@16: drawing[f_source].y, Chris@16: drawing[f_target].x, Chris@16: drawing[f_target].y Chris@16: ) Chris@16: ) Chris@16: return false; Chris@16: } Chris@16: Chris@16: active_edges.erase(a_itr); Chris@16: Chris@16: } Chris@16: } Chris@16: Chris@16: return true; Chris@16: Chris@16: } Chris@16: Chris@16: Chris@16: template Chris@16: bool is_straight_line_drawing(const Graph& g, GridPositionMap drawing) Chris@16: { Chris@16: return is_straight_line_drawing(g, drawing, get(vertex_index,g)); Chris@16: } Chris@16: Chris@16: } Chris@16: Chris@16: #endif // __IS_STRAIGHT_LINE_DRAWING_HPP__