boost/graph/is_straight_line_drawing.hpp

   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/utility.hpp> //for next and prior
  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
  23
  24
  25 namespace boost
  26 {
  27
  28   // Return true exactly when the line segments s1 = ((x1,y1), (x2,y2)) and
  29   // s2 = ((a1,b1), (a2,b2)) intersect in a point other than the endpoints of
  30   // the line segments. The one exception to this rule is when s1 = s2, in
  31   // which case false is returned - this is to accomodate multiple edges
  32   // between the same pair of vertices, which shouldn't invalidate the straight
  33   // line embedding. A tolerance variable epsilon can also be used, which
  34   // defines how far away from the endpoints of s1 and s2 we want to consider
  35   // an intersection.
  36
  37   bool intersects(double x1, double y1,
  38                   double x2, double y2,
  39                   double a1, double b1,
  40                   double a2, double b2,
  41                   double epsilon = 0.000001
  42                   )
  43   {
  44
  45     if (x1 - x2 == 0)
  46       {
  47         std::swap(x1,a1);
  48         std::swap(y1,b1);
  49         std::swap(x2,a2);
  50         std::swap(y2,b2);
  51       }
  52
  53     if (x1 - x2 == 0)
  54       {
  55         BOOST_USING_STD_MAX();
  56         BOOST_USING_STD_MIN();
  57
  58         //two vertical line segments
  59         double min_y = min BOOST_PREVENT_MACRO_SUBSTITUTION(y1,y2);
  60         double max_y = max BOOST_PREVENT_MACRO_SUBSTITUTION(y1,y2);
  61         double min_b = min BOOST_PREVENT_MACRO_SUBSTITUTION(b1,b2);
  62         double max_b = max BOOST_PREVENT_MACRO_SUBSTITUTION(b1,b2);
  63         if ((max_y > max_b && max_b > min_y) ||
  64             (max_b > max_y && max_y > min_b)
  65             )
  66           return true;
  67         else
  68           return false;
  69       }
  70
  71     double x_diff = x1 - x2;
  72     double y_diff = y1 - y2;
  73     double a_diff = a2 - a1;
  74     double b_diff = b2 - b1;
  75
  76     double beta_denominator = b_diff - (y_diff/((double)x_diff)) * a_diff;
  77
  78     if (beta_denominator == 0)
  79       {
  80         //parallel lines
  81         return false;
  82       }
  83
  84     double beta = (b2 - y2 - (y_diff/((double)x_diff)) * (a2 - x2)) /
  85       beta_denominator;
  86     double alpha = (a2 - x2 - beta*(a_diff))/x_diff;
  87
  88     double upper_bound = 1 - epsilon;
  89     double lower_bound = 0 + epsilon;
  90
  91     return (beta < upper_bound && beta > lower_bound &&
  92             alpha < upper_bound && alpha > lower_bound);
  93
  94   }
  95
  96
  97   template <typename Graph,
  98             typename GridPositionMap,
  99             typename VertexIndexMap
 100             >
 101   bool is_straight_line_drawing(const Graph& g,
 102                                 GridPositionMap drawing,
 103                                 VertexIndexMap vm
 104                                 )
 105   {
 106
 107     typedef typename graph_traits<Graph>::vertex_descriptor vertex_t;
 108     typedef typename graph_traits<Graph>::vertex_iterator vertex_iterator_t;
 109     typedef typename graph_traits<Graph>::edge_descriptor edge_t;
 110     typedef typename graph_traits<Graph>::edge_iterator edge_iterator_t;
 111     typedef typename graph_traits<Graph>::edges_size_type e_size_t;
 112     typedef typename graph_traits<Graph>::vertices_size_type v_size_t;
 113
 114     typedef std::size_t x_coord_t;
 115     typedef std::size_t y_coord_t;
 116     typedef boost::tuple<edge_t, x_coord_t, y_coord_t> edge_event_t;
 117     typedef typename std::vector< edge_event_t > edge_event_queue_t;
 118
 119     typedef tuple<y_coord_t, y_coord_t, x_coord_t, x_coord_t> active_map_key_t;
 120     typedef edge_t active_map_value_t;
 121     typedef std::map< active_map_key_t, active_map_value_t > active_map_t;
 122     typedef typename active_map_t::iterator active_map_iterator_t;
 123
 124
 125     edge_event_queue_t edge_event_queue;
 126     active_map_t active_edges;
 127
 128     edge_iterator_t ei, ei_end;
 129     for(tie(ei,ei_end) = edges(g); ei != ei_end; ++ei)
 130       {
 131         edge_t e(*ei);
 132         vertex_t s(source(e,g));
 133         vertex_t t(target(e,g));
 134         edge_event_queue.push_back
 135           (make_tuple(e,
 136                       static_cast<std::size_t>(drawing[s].x),
 137                       static_cast<std::size_t>(drawing[s].y)
 138                       )
 139            );
 140         edge_event_queue.push_back
 141           (make_tuple(e,
 142                       static_cast<std::size_t>(drawing[t].x),
 143                       static_cast<std::size_t>(drawing[t].y)
 144                       )
 145            );
 146       }
 147
 148     // Order by edge_event_queue by first, then second coordinate
 149     // (bucket_sort is a stable sort.)
 150     bucket_sort(edge_event_queue.begin(), edge_event_queue.end(),
 151                 property_map_tuple_adaptor<edge_event_t, 2>()
 152                 );
 153
 154     bucket_sort(edge_event_queue.begin(), edge_event_queue.end(),
 155                 property_map_tuple_adaptor<edge_event_t, 1>()
 156                 );
 157
 158     typedef typename edge_event_queue_t::iterator event_queue_iterator_t;
 159     event_queue_iterator_t itr_end = edge_event_queue.end();
 160     for(event_queue_iterator_t itr = edge_event_queue.begin();
 161         itr != itr_end; ++itr
 162         )
 163       {
 164         edge_t e(get<0>(*itr));
 165         vertex_t source_v(source(e,g));
 166         vertex_t target_v(target(e,g));
 167         if (drawing[source_v].y > drawing[target_v].y)
 168           std::swap(source_v, target_v);
 169
 170         active_map_key_t key(get(drawing, source_v).y,
 171                              get(drawing, target_v).y,
 172                              get(drawing, source_v).x,
 173                              get(drawing, target_v).x
 174                              );
 175
 176         active_map_iterator_t a_itr = active_edges.find(key);
 177         if (a_itr == active_edges.end())
 178           {
 179             active_edges[key] = e;
 180           }
 181         else
 182           {
 183             active_map_iterator_t before, after;
 184             if (a_itr == active_edges.begin())
 185               before = active_edges.end();
 186             else
 187               before = prior(a_itr);
 188             after = boost::next(a_itr);
 189
 190             if (before != active_edges.end())
 191               {
 192
 193                 edge_t f = before->second;
 194                 vertex_t e_source(source(e,g));
 195                 vertex_t e_target(target(e,g));
 196                 vertex_t f_source(source(f,g));
 197                 vertex_t f_target(target(f,g));
 198
 199                 if (intersects(drawing[e_source].x,
 200                                drawing[e_source].y,
 201                                drawing[e_target].x,
 202                                drawing[e_target].y,
 203                                drawing[f_source].x,
 204                                drawing[f_source].y,
 205                                drawing[f_target].x,
 206                                drawing[f_target].y
 207                                )
 208                     )
 209                   return false;
 210               }
 211
 212             if (after != active_edges.end())
 213               {
 214
 215                 edge_t f = after->second;
 216                 vertex_t e_source(source(e,g));
 217                 vertex_t e_target(target(e,g));
 218                 vertex_t f_source(source(f,g));
 219                 vertex_t f_target(target(f,g));
 220
 221                 if (intersects(drawing[e_source].x,
 222                                drawing[e_source].y,
 223                                drawing[e_target].x,
 224                                drawing[e_target].y,
 225                                drawing[f_source].x,
 226                                drawing[f_source].y,
 227                                drawing[f_target].x,
 228                                drawing[f_target].y
 229                                )
 230                     )
 231                   return false;
 232               }
 233
 234             active_edges.erase(a_itr);
 235
 236           }
 237       }
 238
 239     return true;
 240
 241   }
 242
 243
 244   template <typename Graph, typename GridPositionMap>
 245   bool is_straight_line_drawing(const Graph& g, GridPositionMap drawing)
 246   {
 247     return is_straight_line_drawing(g, drawing, get(vertex_index,g));
 248   }
 249
 250 }
 251
 252 #endif // __IS_STRAIGHT_LINE_DRAWING_HPP__