boost/graph/is_straight_line_drawing.hpp

0001 //=======================================================================
0002 // Copyright 2007 Aaron Windsor
0003 //
0004 // Distributed under the Boost Software License, Version 1.0. (See
0005 // accompanying file LICENSE_1_0.txt or copy at
0006 // http://www.boost.org/LICENSE_1_0.txt)
0007 //=======================================================================
0008 #ifndef __IS_STRAIGHT_LINE_DRAWING_HPP__
0009 #define __IS_STRAIGHT_LINE_DRAWING_HPP__
0010
0011 #include <boost/config.hpp>
0012 #include <boost/next_prior.hpp>
0013 #include <boost/tuple/tuple.hpp>
0014 #include <boost/tuple/tuple_comparison.hpp>
0015 #include <boost/property_map/property_map.hpp>
0016 #include <boost/graph/properties.hpp>
0017 #include <boost/graph/planar_detail/bucket_sort.hpp>
0018
0019 #include <boost/geometry/algorithms/crosses.hpp>
0020 #include <boost/geometry/geometries/linestring.hpp>
0021 #include <boost/geometry/core/coordinate_type.hpp>
0022
0023 #include <boost/numeric/conversion/cast.hpp>
0024
0025 #include <algorithm>
0026 #include <vector>
0027 #include <map>
0028
0029 namespace boost
0030 {
0031 // Overload of make from Boost.Geometry.
0032 template<typename Geometry, typename Graph, typename GridPositionMap>
0033 Geometry make(typename graph_traits<Graph>::edge_descriptor e,
0034               Graph const &g,
0035               GridPositionMap const &drawing)
0036 {
0037     auto e_source(source(e, g));
0038     auto e_target(target(e, g));
0039     using Float = typename geometry::coordinate_type<Geometry>::type;
0040     return {{numeric_cast<Float>(drawing[e_source].x), numeric_cast<Float>(drawing[e_source].y)},
0041             {numeric_cast<Float>(drawing[e_target].x), numeric_cast<Float>(drawing[e_target].y)}};
0042 }
0043
0044 // Overload of crosses from Boost.Geometry.
0045 template<typename Graph, typename GridPositionMap>
0046 bool crosses(typename graph_traits<Graph>::edge_descriptor e,
0047              typename graph_traits<Graph>::edge_descriptor f,
0048              Graph const &g,
0049              GridPositionMap const &drawing)
0050 {
0051     using geometry::crosses;
0052     using geometry::model::linestring;
0053     using geometry::model::d2::point_xy;
0054     using linestring2d = geometry::model::linestring<geometry::model::d2::point_xy<double>>;
0055     return crosses(make<linestring2d>(e, g, drawing),
0056                    make<linestring2d>(f, g, drawing));
0057 }
0058
0059 template < typename Graph, typename GridPositionMap, typename VertexIndexMap >
0060 bool is_straight_line_drawing(
0061     const Graph& g, GridPositionMap drawing, VertexIndexMap)
0062 {
0063
0064     typedef typename graph_traits< Graph >::vertex_descriptor vertex_t;
0065     typedef typename graph_traits< Graph >::edge_descriptor edge_t;
0066     typedef typename graph_traits< Graph >::edge_iterator edge_iterator_t;
0067
0068     typedef std::size_t x_coord_t;
0069     typedef std::size_t y_coord_t;
0070     typedef boost::tuple< edge_t, x_coord_t, y_coord_t > edge_event_t;
0071     typedef typename std::vector< edge_event_t > edge_event_queue_t;
0072
0073     typedef tuple< y_coord_t, y_coord_t, x_coord_t, x_coord_t >
0074         active_map_key_t;
0075     typedef edge_t active_map_value_t;
0076     typedef std::map< active_map_key_t, active_map_value_t > active_map_t;
0077     typedef typename active_map_t::iterator active_map_iterator_t;
0078
0079     edge_event_queue_t edge_event_queue;
0080     active_map_t active_edges;
0081
0082     edge_iterator_t ei, ei_end;
0083     for (boost::tie(ei, ei_end) = edges(g); ei != ei_end; ++ei)
0084     {
0085         edge_t e(*ei);
0086         vertex_t s(source(e, g));
0087         vertex_t t(target(e, g));
0088         edge_event_queue.push_back(
0089             make_tuple(e, static_cast< std::size_t >(drawing[s].x),
0090                 static_cast< std::size_t >(drawing[s].y)));
0091         edge_event_queue.push_back(
0092             make_tuple(e, static_cast< std::size_t >(drawing[t].x),
0093                 static_cast< std::size_t >(drawing[t].y)));
0094     }
0095
0096     // Order by edge_event_queue by first, then second coordinate
0097     // (bucket_sort is a stable sort.)
0098     bucket_sort(edge_event_queue.begin(), edge_event_queue.end(),
0099         property_map_tuple_adaptor< edge_event_t, 2 >());
0100
0101     bucket_sort(edge_event_queue.begin(), edge_event_queue.end(),
0102         property_map_tuple_adaptor< edge_event_t, 1 >());
0103
0104     typedef typename edge_event_queue_t::iterator event_queue_iterator_t;
0105     event_queue_iterator_t itr_end = edge_event_queue.end();
0106     for (event_queue_iterator_t itr = edge_event_queue.begin(); itr != itr_end;
0107          ++itr)
0108     {
0109         edge_t e(get< 0 >(*itr));
0110         vertex_t source_v(source(e, g));
0111         vertex_t target_v(target(e, g));
0112         if (drawing[source_v].y > drawing[target_v].y)
0113             std::swap(source_v, target_v);
0114
0115         active_map_key_t key(get(drawing, source_v).y, get(drawing, target_v).y,
0116             get(drawing, source_v).x, get(drawing, target_v).x);
0117
0118         active_map_iterator_t a_itr = active_edges.find(key);
0119         if (a_itr == active_edges.end())
0120         {
0121             active_edges[key] = e;
0122         }
0123         else
0124         {
0125             active_map_iterator_t before, after;
0126             if (a_itr == active_edges.begin())
0127                 before = active_edges.end();
0128             else
0129                 before = prior(a_itr);
0130             after = boost::next(a_itr);
0131
0132             if (before != active_edges.end())
0133             {
0134                 edge_t f = before->second;
0135                 if (crosses(e, f, g, drawing))
0136                     return false;
0137             }
0138
0139             if (after != active_edges.end())
0140             {
0141                 edge_t f = after->second;
0142                 if (crosses(e, f, g, drawing))
0143                     return false;
0144             }
0145
0146             active_edges.erase(a_itr);
0147         }
0148     }
0149
0150     return true;
0151 }
0152
0153 template < typename Graph, typename GridPositionMap >
0154 bool is_straight_line_drawing(const Graph& g, GridPositionMap drawing)
0155 {
0156     return is_straight_line_drawing(g, drawing, get(vertex_index, g));
0157 }
0158
0159 }
0160
0161 #endif // __IS_STRAIGHT_LINE_DRAWING_HPP__