is_straight_line_drawing
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.
ComplexityRuns in time O(n log n) on a planar graph with n vertices.Where Definedboost/graph/is_straight_line_drawing.hpp ParametersIN: Graph& gAn undirected graph. The graph type must be a model of Edge List GraphIN: 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) ) Exampleexamples/straight_line_drawing.cpp See Also
Copyright © 2007 Aaron Windsor (aaron.windsor@gmail.com) |