environment represented by simple polygonal outer boundary with simple polygonal holes More...

#include <visilibity.hpp>

Classes
class	Shortest_Path_Node

Public Member Functions
	Environment ()
	default to empty

	Environment (const Polygon &polygon_temp)
	construct Environment without holes More...

	Environment (const std::vector< Polygon > &polygons)
	construct Environment with holes from STL vector of Polygons More...

	Environment (const std::string &filename)

const Polygon &	operator[] (unsigned i) const
	raw access to Polygons More...

const Point &	operator() (unsigned k) const
	raw access to vertices via flattened index More...

unsigned	h () const
	hole count

unsigned	n () const
	vertex count More...

unsigned	r () const
	total reflex vertex count (nonconvex vertices) More...

bool	is_in_standard_form () const
	true iff lexicographically smallest vertex is first in each list of vertices representing a Polygon of the Environment More...

bool	is_valid (double epsilon=0.0) const
	true iff epsilon -valid More...

double	boundary_length () const
	sum of perimeter lengths of outer boundary and holes More...

double	area () const
	(obstacle/hole free) area of the Environment More...

double	diameter () const
	Euclidean diameter. More...

Bounding_Box	bbox () const
	box which fits snugly around the Environment More...

std::vector< Point >	random_points (const unsigned &count, double epsilon=0.0) const
	get STL vector of count Points randomly situated within epsilon of the Environment More...

Polyline	shortest_path (const Point &start, const Point &finish, const Visibility_Graph &visibility_graph, double epsilon=0.0)
	compute a shortest path between 2 Points More...

Polyline	shortest_path (const Point &start, const Point &finish, double epsilon=0.0)
	compute shortest path between 2 Points More...

std::vector< Polygon >	compute_partition_cells (std::vector< Line_Segment > partition_inducing_segments, double epsilon=0.0)
	compute the faces (partition cells) of an arrangement of Line_Segments inside the Environment More...

void	write_to_file (const std::string &filename, int fios_precision_temp=FIOS_PRECISION)
	write lists of vertices to *.environment file More...

Polygon &	operator[] (unsigned i)
	raw access to Polygons More...

Point &	operator() (unsigned k)
	raw access to vertices via flattened index More...

void	set_outer_boundary (const Polygon &polygon_temp)
	set outer boundary

void	add_hole (const Polygon &polygon_temp)
	add hole

void	enforce_standard_form ()
	enforces outer boundary vertices are listed ccw and holes listed cw, and that these lists begin with respective lexicographically smallest vertex More...

void	eliminate_redundant_vertices (double epsilon=0.0)
	eliminates vertices which are (epsilon) - colinear with their respective neighbors More...

void	reverse_holes ()
	reverse (cyclic) order of vertices belonging to holes only More...

Private Member Functions
void	update_flattened_index_key ()

std::pair< unsigned, unsigned >	one_to_two (unsigned k) const

Private Attributes
Polygon	outer_boundary_

std::vector< Polygon >	holes_

std::vector< std::pair< unsigned, unsigned > >	flattened_index_key_

Friends
class	Point

Detailed Description

environment represented by simple polygonal outer boundary with simple polygonal holes

Remarks: For methods to work correctly, the outer boundary vertices must be listed ccw and the hole vertices cw

Constructor & Destructor Documentation

◆ Environment() [1/3]

VisiLibity::Environment::Environment ( const Polygon & polygon_temp )

inline

construct Environment without holes

Remarks: time complexity O(n), where n is the number of vertices representing the Environment

◆ Environment() [2/3]

VisiLibity::Environment::Environment ( const std::vector< Polygon > & polygons )

construct Environment with holes from STL vector of Polygons

the first Polygon in the vector becomes the outer boundary, the rest become the holes

Remarks: time complexity O(n), where n is the number of vertices representing the Environment

◆ Environment() [3/3]

VisiLibity::Environment::Environment ( const std::string & filename )

construct from *.environment file.

Author: Karl J. Obermeyer

Remarks: time complexity O(n), where n is the number of vertices representing the Environment

Member Function Documentation

◆ area()

double VisiLibity::Environment::area ( ) const

(obstacle/hole free) area of the Environment

Author: Karl J. Obermeyer

Remarks: O(n) time complexity, where n is the number of vertices representing the Environment

◆ bbox()

Bounding_Box VisiLibity::Environment::bbox ( ) const

inline

box which fits snugly around the Environment

Author: Karl J. Obermeyer

Precondition: Environment has greater than 0 vertices

◆ boundary_length()

double VisiLibity::Environment::boundary_length ( ) const

sum of perimeter lengths of outer boundary and holes

Author: Karl J. Obermeyer

Remarks: O(n) time complexity, where n is the number of vertices representing the Environment

◆ compute_partition_cells()

std::vector< Polygon > VisiLibity::Environment::compute_partition_cells	(	std::vector< Line_Segment >	partition_inducing_segments,
		double	epsilon = `0.0`
	)

inline

compute the faces (partition cells) of an arrangement of Line_Segments inside the Environment

Author: Karl J. Obermeyer

Todo:: finish this

◆ diameter()

double VisiLibity::Environment::diameter ( ) const

inline

Euclidean diameter.

Author: Karl J. Obermeyer

Precondition: Environment has greater than 0 vertices

Returns: maximum Euclidean distance between all pairs of vertices

Remarks: time complexity O(n^2), where n is the number of vertices representing the Environment

◆ eliminate_redundant_vertices()

void VisiLibity::Environment::eliminate_redundant_vertices ( double epsilon = 0.0 )

eliminates vertices which are (epsilon) - colinear with their respective neighbors

Author: Karl J. Obermeyer

Postcondition: the Euclidean distance between each vertex and the line segment connecting its neighbors is at least epsilon

Remarks: time complexity O(n), where n is the number of vertices representing the the Environment

◆ enforce_standard_form()

void VisiLibity::Environment::enforce_standard_form ( )

enforces outer boundary vertices are listed ccw and holes listed cw, and that these lists begin with respective lexicographically smallest vertex

Author: Karl J. Obermeyer

Remarks: O(n) time complexity, where n is the number of vertices representing the Environment. Lex. comparison is very sensitive to perturbations if two Points nearly define a line parallel to one of the axes.

◆ is_in_standard_form()

bool VisiLibity::Environment::is_in_standard_form ( ) const

true iff lexicographically smallest vertex is first in each list of vertices representing a Polygon of the Environment

Author: Karl J. Obermeyer

Remarks: lex. comparison is very sensitive to perturbations if two Points nearly define a line parallel to one of the axes

◆ is_valid()

bool VisiLibity::Environment::is_valid ( double epsilon = 0.0 ) const

true iff epsilon -valid

epsilon -valid means (i) the outer boundary and holes are pairwise epsilon -disjoint (no two features should come within epsilon of each other) simple polygons, (ii) outer boundary is oriented ccw, and (iii) holes are oriented cw.

Author: Karl J. Obermeyer

Precondition: Environment has greater than 2 vertices (otherwise it can't even have nonzero area)

Remarks: time complexity O(h^2*n^2), where h is the number of holes and n is the number of vertices representing the Environment

◆ n()

unsigned VisiLibity::Environment::n ( ) const

vertex count

Remarks: time complexity O(h)

◆ operator()() [1/2]

Point & VisiLibity::Environment::operator() ( unsigned k )

raw access to vertices via flattened index

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

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

◆ operator()() [2/2]

const Point & VisiLibity::Environment::operator() ( unsigned k ) const

raw access to vertices via flattened index

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.

Remarks: Time complexity O(1). For efficiency, no bounds check; usually trying to access out of bounds causes a bus error.

◆ operator[]() [1/2]

Polygon & VisiLibity::Environment::operator[] ( unsigned i )

inline

raw access to Polygons

An argument of 0 accesses the outer boundary, 1 and above access the holes.

Author: Karl J. Obermeyer

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

◆ operator[]() [2/2]

const Polygon & VisiLibity::Environment::operator[] ( unsigned i ) const

inline

raw access to Polygons

An argument of 0 accesses the outer boundary, 1 and above access the holes.

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

◆ r()

unsigned VisiLibity::Environment::r ( ) const

total reflex vertex count (nonconvex vertices)

Author: Karl J. Obermeyer

Remarks: time complexity O(n), where n is the number of vertices representing the Environment

◆ random_points()

std::vector< Point > VisiLibity::Environment::random_points	(	const unsigned &	count,
		double	epsilon = `0.0`
	)		const

get STL vector of count Points randomly situated within epsilon of the Environment

Author: Karl J. Obermeyer

Precondition: the Environment has positive area

◆ reverse_holes()

void VisiLibity::Environment::reverse_holes ( )

reverse (cyclic) order of vertices belonging to holes only

Remarks: vertex first in each hole's list is held first

◆ shortest_path() [1/2]

Polyline VisiLibity::Environment::shortest_path	(	const Point &	start,
		const Point &	finish,
		const Visibility_Graph &	visibility_graph,
		double	epsilon = `0.0`
	)

compute a shortest path between 2 Points

Uses the classical visibility graph method as described, e.g., in ``Robot Motion Planning" (Ch. 4 Sec. 1) by J.C. Latombe. Specifically, an A* search is performed on the visibility graph using the Euclidean distance as the heuristic function.

Author: Karl J. Obermeyer

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

Remarks: If multiple shortest path queries are made for the same Envrionment, it is better to precompute the Visibility_Graph. For a precomputed Visibility_Graph, the time complexity of a shortest_path() query is O(n^2), where n is the number of vertices representing the Environment.

Todo:: return not just one, but all shortest paths (w/in epsilon), e.g., returning a std::vector<Polyline>)

◆ shortest_path() [2/2]

Polyline VisiLibity::Environment::shortest_path	(	const Point &	start,
		const Point &	finish,
		double	epsilon = `0.0`
	)

compute shortest path between 2 Points

Author: Karl J. Obermeyer

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

Remarks: For single shortest path query, visibility graph is not precomputed. Time complexity O(n^3), where n is the number of vertices representing the Environment.

◆ write_to_file()

void VisiLibity::Environment::write_to_file	(	const std::string &	filename,
		int	fios_precision_temp = `FIOS_PRECISION`
	)

write lists of vertices to *.environment file

uses intuitive human and computer readable decimal format with display precision fios_precision_temp

Author: Karl J. Obermeyer

Precondition: fios_precision_temp >=1

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

src/visilibity.hpp
src/visilibity.cpp

Classes

Public Member Functions

Private Member Functions

Private Attributes

Friends

Detailed Description

Constructor & Destructor Documentation

◆ Environment() [1/3]

◆ Environment() [2/3]

◆ Environment() [3/3]

Member Function Documentation

◆ area()

◆ bbox()

◆ boundary_length()

◆ compute_partition_cells()

◆ diameter()

◆ eliminate_redundant_vertices()

◆ enforce_standard_form()

◆ is_in_standard_form()

◆ is_valid()

◆ n()

◆ operator()() [1/2]

◆ operator()() [2/2]

◆ operator[]() [1/2]

◆ operator[]() [2/2]

◆ r()

◆ random_points()

◆ reverse_holes()

◆ shortest_path() [1/2]

◆ shortest_path() [2/2]

◆ write_to_file()