<HTML> <!-- 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) --> <Head> <Title>Boost Graph Library: is_straight_line_drawing</Title> <BODY BGCOLOR="#ffffff" LINK="#0000ee" TEXT="#000000" VLINK="#551a8b" ALINK="#ff0000"> <IMG SRC="../../../boost.png" ALT="C++ Boost" width="277" height="86"> <BR Clear> <H1><tt>is_straight_line_drawing</tt></H1> <p> <pre> template <typename Graph, typename GridPositionMap, typename VertexIndexMap> bool is_straight_line_drawing(const Graph& g, GridPositionMap drawing, VertexIndexMap vm); </pre> <p> If <tt>drawing</tt> is a property map modeling the PositionMap concept, <tt>is_straight_line_drawing</tt> returns true exactly when no two of the line segments induced by edges in the graph under <tt>drawing</tt> 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 <tt> <a href="straight_line_drawing.html">chrobak_payne_straight_line_embedding.</a> </tt> <p> <h3>Complexity</h3> Runs in time <i>O(n log n)</i> on a planar graph with <i>n</i> vertices. <H3>Where Defined</H3> <P> <a href="../../../boost/graph/is_straight_line_drawing.hpp"><TT>boost/graph/is_straight_line_drawing.hpp</TT></a> <h3>Parameters</h3> IN: <tt>Graph& g</tt> <blockquote> An undirected graph. The graph type must be a model of <a href="EdgeListGraph.html">Edge List Graph</a> </blockquote> IN: <tt>PositionMap</tt> <blockquote> A <a href="../../property_map/doc/LvaluePropertyMap.html">Readable LValue Property Map</a> that models the Position Map concept. The Position Map concept requires that the value mapped to be an object that has members <tt>x</tt> and <tt>y</tt>. For example, if <tt>p</tt> models PositionMap and <tt>v</tt> is a vertex in the graph, <tt>p[v].x</tt> and <tt>p[v].y</tt> are valid expressions. The type of <tt>x</tt> and <tt>y</tt> must be implicitly convertable to <tt>std::size_t</tt>. </blockquote> IN: <tt>VertexIndexMap vm</tt> <blockquote> A <a href="../../property_map/doc/ReadablePropertyMap.html">Readable Property Map</a> that maps vertices from <tt>g</tt> to distinct integers in the range <tt>[0, num_vertices(g) )</tt><br> <b>Default</b>: <tt>get(vertex_index,g)</tt><br> </blockquote> <H3>Example</H3> <P> <a href="../example/straight_line_drawing.cpp"><TT>examples/straight_line_drawing.cpp</TT></a> <h3>See Also</h3> <p> <ul> <li><a href="planar_graphs.html">Planar Graphs in the Boost Graph Library</a> <li><a href="straight_line_drawing.html"> <tt>chrobak_payne_straight_line_drawing</tt></a> </ul> <br> <HR> Copyright © 2007 Aaron Windsor (<a href="mailto:aaron.windsor@gmail.com">aaron.windsor@gmail.com</a>) </BODY> </HTML>