Boost C++ Libraries of the most highly regarded and expertly designed C++ library projects in the world. Herb Sutter and Andrei Alexandrescu, C++ Coding Standards

C++ Boost


template <typename Graph, typename GridPositionMap, typename VertexIndexMap>
bool is_straight_line_drawing(const Graph& g, GridPositionMap drawing, VertexIndexMap vm);

If drawing is a property map modeling the PositionMap concept, is_straight_line_drawing returns true exactly when no two of the line segments induced by edges in the graph under drawing intersect. This function works correctly in the presence of self-loops and parallel edges, and can be used to verify the output of the function chrobak_payne_straight_line_embedding.


Runs in time O(n log n) on a planar graph with n vertices.

Where Defined



IN: Graph& g
An undirected graph. The graph type must be a model of Edge List Graph
IN: PositionMap
A Readable LValue Property Map that models the Position Map concept. The Position Map concept requires that the value mapped to be an object that has members x and y. For example, if p models PositionMap and v is a vertex in the graph, p[v].x and p[v].y are valid expressions. The type of x and y must be implicitly convertable to std::size_t.
IN: VertexIndexMap vm
A Readable Property Map that maps vertices from g to distinct integers in the range [0, num_vertices(g) )
Default: get(vertex_index,g)



See Also

Copyright © 2007 Aaron Windsor (