| //======================================================================= |
| // 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/utility.hpp> //for next and prior |
| #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> |
| |
| |
| |
| 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. |
| |
| 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>::vertex_iterator vertex_iterator_t; |
| typedef typename graph_traits<Graph>::edge_descriptor edge_t; |
| typedef typename graph_traits<Graph>::edge_iterator edge_iterator_t; |
| typedef typename graph_traits<Graph>::edges_size_type e_size_t; |
| typedef typename graph_traits<Graph>::vertices_size_type v_size_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(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__ |