Boost Graph Library: is_straight_line_drawing

# `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.`

### Complexity

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

### Where Defined

`boost/graph/is_straight_line_drawing.hpp`

### Parameters

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)`

### Example

`examples/straight_line_drawing.cpp`

### See Also

- Planar Graphs in the Boost Graph Library
- `chrobak_payne_straight_line_drawing`

Copyright © 2007 Aaron Windsor (aaron.windsor@gmail.com)