2 <!-- Copyright 2007 Aaron Windsor
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)
10 <Title>Boost Graph Library: is_straight_line_drawing
</Title>
11 <BODY BGCOLOR=
"#ffffff" LINK=
"#0000ee" TEXT=
"#000000" VLINK=
"#551a8b"
13 <IMG SRC=
"../../../boost.png"
14 ALT=
"C++ Boost" width=
"277" height=
"86">
18 <H1><tt>is_straight_line_drawing
</tt></H1>
22 template
<typename Graph, typename GridPositionMap, typename VertexIndexMap
>
23 bool is_straight_line_drawing(const Graph& g, GridPositionMap drawing, VertexIndexMap vm);
27 If
<tt>drawing
</tt> is a property map modeling the PositionMap
28 concept,
<tt>is_straight_line_drawing
</tt> returns true exactly when no two of
29 the line segments induced by edges in the graph under
<tt>drawing
</tt>
30 intersect. This function works correctly in the presence of self-loops and
31 parallel edges, and can be used to verify the output of the function
33 <a href=
"straight_line_drawing.html">chrobak_payne_straight_line_embedding.
</a>
40 Runs in time
<i>O(n log n)
</i> on a planar graph with
<i>n
</i> vertices.
42 <H3>Where Defined
</H3>
45 <a href=
"../../../boost/graph/is_straight_line_drawing.hpp"><TT>boost/graph/is_straight_line_drawing.hpp
</TT></a>
49 IN:
<tt>Graph
& g
</tt>
52 An undirected graph. The graph type must be a model of
<a
53 href=
"EdgeListGraph.html">Edge List Graph
</a>
56 IN:
<tt>PositionMap
</tt>
59 A
<a href=
"../../property_map/doc/LvaluePropertyMap.html">Readable LValue Property
60 Map
</a> that models the Position Map concept. The Position Map concept requires
61 that 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>
63 is a vertex in the graph,
<tt>p[v].x
</tt> and
<tt>p[v].y
</tt> are valid
64 expressions. The type of
<tt>x
</tt> and
<tt>y
</tt> must be implicitly
65 convertable to
<tt>std::size_t
</tt>.
68 IN:
<tt>VertexIndexMap vm
</tt>
71 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>
72 <b>Default
</b>:
<tt>get(vertex_index,g)
</tt><br>
78 <a href=
"../example/straight_line_drawing.cpp"><TT>examples/straight_line_drawing.cpp
</TT></a>
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>
91 Copyright
© 2007 Aaron Windsor (
<a href=
"mailto:aaron.windsor@gmail.com">aaron.windsor@gmail.com
</a>)