1<HTML> 2<!-- Copyright 2007 Aaron Windsor 3 4 Distributed under the Boost Software License, Version 1.0. 5 (See accompanying file LICENSE_1_0.txt or copy at 6 http://www.boost.org/LICENSE_1_0.txt) 7 8 --> 9<Head> 10<Title>Boost Graph Library: is_straight_line_drawing</Title> 11<BODY BGCOLOR="#ffffff" LINK="#0000ee" TEXT="#000000" VLINK="#551a8b" 12 ALINK="#ff0000"> 13<IMG SRC="../../../boost.png" 14 ALT="C++ Boost" width="277" height="86"> 15 16<BR Clear> 17 18<H1><tt>is_straight_line_drawing</tt></H1> 19 20<p> 21<pre> 22template <typename Graph, typename GridPositionMap, typename VertexIndexMap> 23bool is_straight_line_drawing(const Graph& g, GridPositionMap drawing, VertexIndexMap vm); 24</pre> 25 26<p> 27If <tt>drawing</tt> is a property map modeling the PositionMap 28concept, <tt>is_straight_line_drawing</tt> returns true exactly when no two of 29the line segments induced by edges in the graph under <tt>drawing</tt> 30intersect. This function works correctly in the presence of self-loops and 31parallel edges, and can be used to verify the output of the function 32<tt> 33<a href="straight_line_drawing.html">chrobak_payne_straight_line_embedding.</a> 34</tt> 35 36<p> 37 38<h3>Complexity</h3> 39 40Runs in time <i>O(n log n)</i> on a planar graph with <i>n</i> vertices. 41 42<H3>Where Defined</H3> 43 44<P> 45<a href="../../../boost/graph/is_straight_line_drawing.hpp"><TT>boost/graph/is_straight_line_drawing.hpp</TT></a> 46 47<h3>Parameters</h3> 48 49IN: <tt>Graph& g</tt> 50 51<blockquote> 52An undirected graph. The graph type must be a model of <a 53href="EdgeListGraph.html">Edge List Graph</a> 54</blockquote> 55 56IN: <tt>PositionMap</tt> 57 58<blockquote> 59A <a href="../../property_map/doc/LvaluePropertyMap.html">Readable LValue Property 60Map</a> that models the Position Map concept. The Position Map concept requires 61that the value mapped to be an object that has members <tt>x</tt> and 62<tt>y</tt>. For example, if <tt>p</tt> models PositionMap and <tt>v</tt> 63is a vertex in the graph, <tt>p[v].x</tt> and <tt>p[v].y</tt> are valid 64expressions. The type of <tt>x</tt> and <tt>y</tt> must be implicitly 65convertable to <tt>std::size_t</tt>. 66</blockquote> 67 68IN: <tt>VertexIndexMap vm</tt> 69 70<blockquote> 71A <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> 72<b>Default</b>: <tt>get(vertex_index,g)</tt><br> 73</blockquote> 74 75<H3>Example</H3> 76 77<P> 78<a href="../example/straight_line_drawing.cpp"><TT>examples/straight_line_drawing.cpp</TT></a> 79 80<h3>See Also</h3> 81 82<p> 83<ul> 84<li><a href="planar_graphs.html">Planar Graphs in the Boost Graph Library</a> 85<li><a href="straight_line_drawing.html"> 86<tt>chrobak_payne_straight_line_drawing</tt></a> 87</ul> 88 89<br> 90<HR> 91Copyright © 2007 Aaron Windsor (<a href="mailto:aaron.windsor@gmail.com">aaron.windsor@gmail.com</a>) 92</BODY> 93</HTML> 94
