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