VisiLibity::Visibility_Graph Class Reference

visibility graph of points in an Environment, represented by adjacency matrix More...

#include <visilibity.hpp>

Public Member Functions
	Visibility_Graph ()
	default to empty
	Visibility_Graph (const Visibility_Graph &vg2)
	copy
	Visibility_Graph (const Environment &environment, double epsilon=0.0)
	construct the visibility graph of Environment vertices More...
	Visibility_Graph (const std::vector< Point > points, const Environment &environment, double epsilon=0.0)
	construct the visibility graph of Points in an Environment More...
	Visibility_Graph (const Guards &guards, const Environment &environment, double epsilon=0.0)
	construct the visibility graph of Guards in an Environment More...
bool	operator() (unsigned i1, unsigned j1, unsigned i2, unsigned j2) const
	raw access to adjacency matrix data More...
bool	operator() (unsigned k1, unsigned k2) const
	raw access to adjacency matrix data via flattened indices More...
unsigned	n () const
	total number of vertices in corresponding Environment
bool &	operator() (unsigned i1, unsigned j1, unsigned i2, unsigned j2)
	raw access to adjacency matrix data More...
bool &	operator() (unsigned k1, unsigned k2)
	raw access to adjacency matrix data via flattened indices More...
Visibility_Graph &	operator= (const Visibility_Graph &visibility_graph_temp)
	assignment operator
virtual	~Visibility_Graph ()
	destructor

Private Member Functions
unsigned	two_to_one (unsigned i, unsigned j) const

Private Attributes
unsigned	n_
std::vector< unsigned >	vertex_counts_
bool **	adjacency_matrix_

Detailed Description

visibility graph of points in an Environment, represented by adjacency matrix

Remarks

used for shortest path planning in the Environment::shortest_path() method

Todo:

Add method to prune edges for faster shortest path calculation, e.g., exclude concave vertices and only include tangent edges as described in ``Robot Motion Planning" (Ch. 4 Sec. 1) by J.C. Latombe.

Constructor & Destructor Documentation

Visibility_Graph() [1/3]

VisiLibity::Visibility_Graph::Visibility_Graph	(	const Environment &	environment,
		double	epsilon = 0.0
	)

construct the visibility graph of Environment vertices

Author

Karl J. Obermeyer

Precondition

environment must be epsilon -valid. Test with Environment::is_valid(epsilon).

Remarks

Currently this constructor simply computes the Visibility_Polygon of each vertex and checks inclusion of the other vertices, taking time complexity O(n^3), where n is the number of vertices representing the Environment. This time complexity is not optimal. As mentioned in ``Robot Motion Planning" by J.C. Latombe p.157, there are algorithms able to construct a visibility graph for a polygonal environment with holes in time O(n^2). The nonoptimal algorithm is being used temporarily because of (1) its ease to implement using the Visibility_Polygon class, and (2) its apparent robustness. Implementing the optimal algorithm robustly is future work.

Visibility_Graph() [2/3]

VisiLibity::Visibility_Graph::Visibility_Graph	(	const std::vector< Point >	points,
		const Environment &	environment,
		double	epsilon = 0.0
	)

construct the visibility graph of Points in an Environment

Precondition

environment must be epsilon -valid. Test with Environment::is_valid(epsilon).

Author

Karl J. Obermeyer

Remarks

Currently this constructor simply computes the Visibility_Polygon of each Point and checks inclusion of the other Points, taking time complexity O(N n log(n) + N^2 n), where N is the number of Points and n is the number of vertices representing the Environment. This time complexity is not optimal, but has been used for simplicity. More efficient algorithms are discussed in ``Robot Motion Planning" by J.C. Latombe p.157.

Visibility_Graph() [3/3]

VisiLibity::Visibility_Graph::Visibility_Graph	(	const Guards &	guards,
		const Environment &	environment,
		double	epsilon = 0.0
	)

construct the visibility graph of Guards in an Environment

Precondition

start and finish must be in the environment. Environment must be epsilon -valid. Test with Environment::is_valid(epsilon).

Author

Karl J. Obermeyer

Remarks

Currently this constructor simply computes the Visibility_Polygon of each guard and checks inclusion of the other guards, taking time complexity O(N n log(n) + N^2 n), where N is the number of guards and n is the number of vertices representing the Environment. This time complexity is not optimal, but has been used for simplicity. More efficient algorithms are discussed in ``Robot Motion Planning" by J.C. Latombe p.157.

Member Function Documentation

operator()() [1/4]

bool & VisiLibity::Visibility_Graph::operator()	(	unsigned	i1,
		unsigned	j1,
		unsigned	i2,
		unsigned	j2
	)

raw access to adjacency matrix data

Author

Karl J. Obermeyer

Parameters

i1	Polygon index of first vertex
j1	index of first vertex within its Polygon
i2	Polygon index of second vertex
j2	index of second vertex within its Polygon

Returns

true iff first vertex is visible from second vertex

Remarks

for efficiency, no bounds check; usually trying to access out of bounds causes a bus error

operator()() [2/4]

bool VisiLibity::Visibility_Graph::operator()	(	unsigned	i1,
		unsigned	j1,
		unsigned	i2,
		unsigned	j2
	)		const

raw access to adjacency matrix data

Author

Karl J. Obermeyer

Parameters

i1	Polygon index of first vertex
j1	index of first vertex within its Polygon
i2	Polygon index of second vertex
j2	index of second vertex within its Polygon

Returns

true iff first vertex is visible from second vertex

Remarks

for efficiency, no bounds check; usually trying to access out of bounds causes a bus error

operator()() [3/4]

bool & VisiLibity::Visibility_Graph::operator()	(	unsigned	k1,
		unsigned	k2
	)

raw access to adjacency matrix data via flattened indices

By flattened index is intended the label given to a vertex if you were to label all the vertices from 0 to n-1 (where n is the number of vertices representing the Environment) starting with the first vertex of the outer boundary and progressing in order through all the remaining vertices of the outer boundary and holes.

Author

Karl J. Obermeyer

Parameters

k1	flattened index of first vertex
k1	flattened index of second vertex

Returns

true iff first vertex is visible from second vertex

Remarks

for efficiency, no bounds check; usually trying to access out of bounds causes a bus error

operator()() [4/4]

bool VisiLibity::Visibility_Graph::operator()	(	unsigned	k1,
		unsigned	k2
	)		const

raw access to adjacency matrix data via flattened indices

By flattened index is intended the label given to a vertex if you were to label all the vertices from 0 to n-1 (where n is the number of vertices representing the Environment) starting with the first vertex of the outer boundary and progressing in order through all the remaining vertices of the outer boundary and holes.

Author

Karl J. Obermeyer

Parameters

k1	flattened index of first vertex
k1	flattened index of second vertex

Returns

true iff first vertex is visible from second vertex

Remarks

for efficiency, no bounds check; usually trying to access out of bounds causes a bus error

---

The documentation for this class was generated from the following files:

• src/visilibity.hpp
• src/visilibity.cpp