VisiLibity Namespace Reference

VisiLibity's sole namespace. More...

Classes
class	Angle
	angle in radians represented by a value in the interval [0,2*M_PI] More...
struct	Bounding_Box
	rectangle with sides parallel to the x- and y-axes More...
class	Environment
	environment represented by simple polygonal outer boundary with simple polygonal holes More...
class	Guards
	set of Guards represented by a list of Points More...
class	Line_Segment
	line segment in the plane represented by its endpoints More...
class	Point
	Point in the plane represented by Cartesian coordinates. More...
class	Polar_Point
	Point in the plane packaged together with polar coordinates w.r.t. specified origin. More...
class	Polygon
	simple polygon in the plane represented by list of vertices More...
class	Polyline
	oriented polyline in the plane represented by list of vertices More...
class	Ray
	ray in the plane represented by base Point and bearing Angle More...
class	Shortest_Path_Test
	Utilities for writing shortest path VisiLibity unit tests. More...
class	Unit_Test
	Utilities for writing VisiLibity unit tests. More...
class	Visibility_Graph
	visibility graph of points in an Environment, represented by adjacency matrix More...
class	Visibility_Polygon
	visibility polygon of a Point in an Environment or Polygon More...

Functions
double	uniform_random_sample (double lower_bound, double upper_bound)
	get a uniform random sample from an (inclusive) interval on the real line More...
bool	operator== (const Point &point1, const Point &point2)
	True iff Points' coordinates are identical. More...
bool	operator!= (const Point &point1, const Point &point2)
	True iff Points' coordinates are not identical.
bool	operator< (const Point &point1, const Point &point2)
	compare lexicographic order of points More...
bool	operator> (const Point &point1, const Point &point2)
	compare lexicographic order of points More...
bool	operator>= (const Point &point1, const Point &point2)
	compare lexicographic order of points More...
bool	operator<= (const Point &point1, const Point &point2)
	compare lexicographic order of points More...
Point	operator+ (const Point &point1, const Point &point2)
	vector addition of Points
Point	operator- (const Point &point1, const Point &point2)
	vector subtraction of Points
Point	operator* (const Point &point1, const Point &point2)
Point	operator* (double scalar, const Point &point2)
	simple scaling treats the Point as a vector
Point	operator* (const Point &point1, double scalar)
	simple scaling treats the Point as a vector
double	cross (const Point &point1, const Point &point2)
	cross product (signed) magnitude treats the Points as vectors More...
double	distance (const Point &point1, const Point &point2)
	Euclidean distance between Points. More...
double	distance (const Point &point_temp, const Line_Segment &line_segment_temp)
	Euclidean distance between a Point and a Line_Segment. More...
double	distance (const Line_Segment &line_segment_temp, const Point &point_temp)
	Euclidean distance between a Point and a Line_Segment. More...
double	distance (const Point &point_temp, const Ray &ray_temp)
	Euclidean distance between a Point and a Ray. More...
double	distance (const Ray &ray_temp, const Point &point_temp)
	Euclidean distance between a Point and a Ray. More...
double	distance (const Point &point_temp, const Polyline &polyline_temp)
	Euclidean distance between a Point and a Polyline. More...
double	distance (const Polyline &polyline_temp, const Point &point_temp)
	Euclidean distance between a Point and a Polyline. More...
double	boundary_distance (const Point &point_temp, const Polygon &polygon_temp)
	Euclidean distance between a Point and a Polygon's boundary. More...
double	boundary_distance (const Polygon &polygon_temp, const Point &point_temp)
	Euclidean distance between a Point and a Polygon's boundary. More...
double	boundary_distance (const Point &point_temp, const Environment &environment_temp)
	Euclidean distance between a Point and a Environment's boundary. More...
double	boundary_distance (const Environment &environment_temp, const Point &point_temp)
	Euclidean distance between a Point and a Environment's boundary. More...
std::ostream &	operator<< (std::ostream &outs, const Point &point_temp)
	print a Point
bool	operator== (const Line_Segment &line_segment1, const Line_Segment &line_segment2)
	true iff endpoint coordinates are exactly equal, but false if either Line_Segment has size 0 More...
bool	operator!= (const Line_Segment &line_segment1, const Line_Segment &line_segment2)
	true iff endpoint coordinates are not ==
bool	equivalent (Line_Segment line_segment1, Line_Segment line_segment2, double epsilon=0)
	true iff line segments' endpoints match up w/in a (closed) epsilon ball of each other, but false if either Line_Segment has size 0 More...
double	distance (const Line_Segment &line_segment1, const Line_Segment &line_segment2)
	Euclidean distance between Line_Segments. More...
double	boundary_distance (const Line_Segment &line_segment, const Polygon &polygon)
	Euclidean distance between a Line_Segment and the boundary of a Polygon. More...
double	boundary_distance (const Polygon &polygon, const Line_Segment &line_segment)
	Euclidean distance between a Line_Segment and the boundary of a Polygon. More...
bool	intersect (const Line_Segment &line_segment1, const Line_Segment &line_segment2, double epsilon=0.0)
	true iff the Euclidean distance between Line_Segments is no greater than epsilon, false if either line segment has size 0 More...
bool	intersect_proper (const Line_Segment &line_segment1, const Line_Segment &line_segment2, double epsilon=0.0)
	true iff line segments intersect properly w/in epsilon, false if either line segment has size 0 More...
Line_Segment	intersection (const Line_Segment &line_segment1, const Line_Segment &line_segment2, double epsilon=0.0)
	intersection of Line_Segments More...
std::ostream &	operator<< (std::ostream &outs, const Line_Segment &line_segment_temp)
	print a Line_Segment
bool	operator== (const Angle &angle1, const Angle &angle2)
	compare angle radians
bool	operator!= (const Angle &angle1, const Angle &angle2)
	compare angle radians
bool	operator> (const Angle &angle1, const Angle &angle2)
	compare angle radians
bool	operator< (const Angle &angle1, const Angle &angle2)
	compare angle radians
bool	operator>= (const Angle &angle1, const Angle &angle2)
	compare angle radians
bool	operator<= (const Angle &angle1, const Angle &angle2)
	compare angle radians
Angle	operator+ (const Angle &angle1, const Angle &angle2)
	add angles' radians and mod into [0, 2*M_PI)
Angle	operator- (const Angle &angle1, const Angle &angle2)
	subtract angles' radians and mod into [0, 2*M_PI)
double	geodesic_distance (const Angle &angle1, const Angle &angle2)
	geodesic distance in radians between Angles More...
double	geodesic_direction (const Angle &angle1, const Angle &angle2)
	1.0 => geodesic path from angle1 to angle2 is couterclockwise, -1.0 => clockwise More...
std::ostream &	operator<< (std::ostream &outs, const Angle &angle_temp)
	print Angle
bool	operator== (const Polar_Point &polar_point1, const Polar_Point &polar_point2)
	compare member data More...
bool	operator!= (const Polar_Point &polar_point1, const Polar_Point &polar_point2)
bool	operator> (const Polar_Point &polar_point1, const Polar_Point &polar_point2)
	compare according to polar lexicographic order (smaller bearing, then smaller range) More...
bool	operator< (const Polar_Point &polar_point1, const Polar_Point &polar_point2)
	compare according to polar lexicographic order (smaller bearing, then smaller range) More...
bool	operator>= (const Polar_Point &polar_point1, const Polar_Point &polar_point2)
	compare according to polar lexicographic order (smaller bearing, then smaller range) More...
bool	operator<= (const Polar_Point &polar_point1, const Polar_Point &polar_point2)
	compare according to polar lexicographic order (smaller bearing, then smaller range) More...
std::ostream &	operator<< (std::ostream &outs, const Polar_Point &polar_point_temp)
	print Polar_Point
bool	operator== (const Ray &ray1, const Ray &ray2)
	compare member data More...
bool	operator!= (const Ray &ray1, const Ray &ray2)
	compare member data More...
Line_Segment	intersection (const Ray ray_temp, const Line_Segment &line_segment_temp, double epsilon=0.0)
	compute the intersection of a Line_Segment with a Ray More...
Line_Segment	intersection (const Line_Segment &line_segment_temp, const Ray &ray_temp, double epsilon=0.0)
	compute the intersection of a Line_Segment with a Ray More...
std::ostream &	operator<< (std::ostream &outs, const Polyline &polyline_temp)
bool	operator== (Polygon polygon1, Polygon polygon2)
	true iff vertex lists are identical, but false if either Polygon has size 0 More...
bool	operator!= (Polygon polygon1, Polygon polygon2)
bool	equivalent (Polygon polygon1, Polygon polygon2, double epsilon=0.0)
	true iff the Polygon's vertices match up w/in a (closed) epsilon ball of each other, but false if either Polygon has size 0 More...
double	boundary_distance (const Polygon &polygon1, const Polygon &polygon2)
	Euclidean distance between Polygons' boundaries. More...
std::ostream &	operator<< (std::ostream &outs, const Polygon &polygon_temp)
std::ostream &	operator<< (std::ostream &outs, const Environment &environment_temp)
	printing Environment
std::ostream &	operator<< (std::ostream &outs, const Guards &guards)
	print Guards
std::ostream &	operator<< (std::ostream &outs, const Visibility_Graph &visibility_graph)
	print Visibility_Graph adjacency matrix

Variables
const int	FIOS_PRECISION = 10
	floating-point display precision. More...

Detailed Description

VisiLibity's sole namespace.

Function Documentation

boundary_distance() [1/7]

double VisiLibity::boundary_distance	(	const Environment &	environment_temp,
		const Point &	point_temp
	)

Euclidean distance between a Point and a Environment's boundary.

Author

Karl J. Obermeyer

Precondition

Point's data are numbers and the Environment is nonempty

boundary_distance() [2/7]

double VisiLibity::boundary_distance	(	const Line_Segment &	line_segment,
		const Polygon &	polygon
	)

Euclidean distance between a Line_Segment and the boundary of a Polygon.

Author

Karl J. Obermeyer

Precondition

line_segment.size() > 0 and polygon.n() > 0

boundary_distance() [3/7]

double VisiLibity::boundary_distance	(	const Point &	point_temp,
		const Environment &	environment_temp
	)

Euclidean distance between a Point and a Environment's boundary.

Author

Karl J. Obermeyer

Precondition

Point's data are numbers and the Environment is nonempty

boundary_distance() [4/7]

double VisiLibity::boundary_distance	(	const Point &	point_temp,
		const Polygon &	polygon_temp
	)

Euclidean distance between a Point and a Polygon's boundary.

Author

Karl J. Obermeyer

Precondition

Point's data are numbers and the Polygon is nonempty

boundary_distance() [5/7]

double VisiLibity::boundary_distance	(	const Polygon &	polygon,
		const Line_Segment &	line_segment
	)

Euclidean distance between a Line_Segment and the boundary of a Polygon.

Author

Karl J. Obermeyer

Precondition

line_segment.size() > 0 and polygon.n() > 0

boundary_distance() [6/7]

double VisiLibity::boundary_distance	(	const Polygon &	polygon1,
		const Polygon &	polygon2
	)

Euclidean distance between Polygons' boundaries.

Author

Karl J. Obermeyer

Precondition

polygon1 and polygon2 each have greater than 0 vertices

boundary_distance() [7/7]

double VisiLibity::boundary_distance	(	const Polygon &	polygon_temp,
		const Point &	point_temp
	)

Euclidean distance between a Point and a Polygon's boundary.

Author

Karl J. Obermeyer

Precondition

Point's data are numbers and the Polygon is nonempty

cross()

double VisiLibity::cross	(	const Point &	point1,
		const Point &	point2
	)

cross product (signed) magnitude treats the Points as vectors

Author

Karl J. Obermeyer

Precondition

Points' data are numbers

Remarks

This is equal to the (signed) area of the parallelogram created by the Points viewed as vectors.

distance() [1/8]

double VisiLibity::distance	(	const Line_Segment &	line_segment1,
		const Line_Segment &	line_segment2
	)

Euclidean distance between Line_Segments.

Author

Karl J. Obermeyer

Precondition

line_segment1.size() > 0 and line_segment2.size() > 0

distance() [2/8]

double VisiLibity::distance	(	const Line_Segment &	line_segment_temp,
		const Point &	point_temp
	)

Euclidean distance between a Point and a Line_Segment.

Author

Karl J. Obermeyer

Precondition

Point's data are numbers and the Line_Segment is nonempty

distance() [3/8]

double VisiLibity::distance	(	const Point &	point1,
		const Point &	point2
	)

Euclidean distance between Points.

Precondition

Points' data are numbers

distance() [4/8]

double VisiLibity::distance	(	const Point &	point_temp,
		const Line_Segment &	line_segment_temp
	)

Euclidean distance between a Point and a Line_Segment.

Author

Karl J. Obermeyer

Precondition

Point's data are numbers and the Line_Segment is nonempty

distance() [5/8]

double VisiLibity::distance	(	const Point &	point_temp,
		const Polyline &	polyline_temp
	)

Euclidean distance between a Point and a Polyline.

Author

Karl J. Obermeyer

Precondition

Point's data are numbers and the Polyline is nonempty

distance() [6/8]

double VisiLibity::distance	(	const Point &	point_temp,
		const Ray &	ray_temp
	)

Euclidean distance between a Point and a Ray.

Author

Karl J. Obermeyer

Precondition

Point's and Ray's data are numbers

distance() [7/8]

double VisiLibity::distance	(	const Polyline &	polyline_temp,
		const Point &	point_temp
	)

Euclidean distance between a Point and a Polyline.

Author

Karl J. Obermeyer

Precondition

Point's data are numbers and the Polyline is nonempty

distance() [8/8]

double VisiLibity::distance	(	const Ray &	ray_temp,
		const Point &	point_temp
	)

Euclidean distance between a Point and a Ray.

Author

Karl J. Obermeyer

Precondition

Point's and Ray's data are numbers

equivalent() [1/2]

bool VisiLibity::equivalent	(	Line_Segment	line_segment1,
		Line_Segment	line_segment2,
		double	epsilon = 0
	)

true iff line segments' endpoints match up w/in a (closed) epsilon ball of each other, but false if either Line_Segment has size 0

Author

Karl J. Obermeyer

Remarks

this function will return true even if it has to flip the orientation of one of the segments to get the vertices to match up

equivalent() [2/2]

bool VisiLibity::equivalent	(	Polygon	polygon1,
		Polygon	polygon2,
		double	epsilon = 0.0
	)

true iff the Polygon's vertices match up w/in a (closed) epsilon ball of each other, but false if either Polygon has size 0

Respects number, ordering, and orientation of vertices, i.e., even if the (conceptual) polygons represented by two Polygons are identical, they are not considered epsilon - equivalent unless the number of vertices is the same, the orientations are the same (cw vs. ccw list), and the Points of the vertex lists match up within epsilon. This function does attempt to match the polygons for all possible cyclic permutations, hence the quadratic time complexity.

Author

Karl J. Obermeyer

Remarks

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

geodesic_direction()

double VisiLibity::geodesic_direction	(	const Angle &	angle1,
		const Angle &	angle2
	)

1.0 => geodesic path from angle1 to angle2 is couterclockwise, -1.0 => clockwise

Author

Karl J. Obermeyer

Precondition

angle1 and angle2 data are numbers

geodesic_distance()

double VisiLibity::geodesic_distance	(	const Angle &	angle1,
		const Angle &	angle2
	)

geodesic distance in radians between Angles

Author

Karl J. Obermeyer

Precondition

angle1 and angle2 data are numbers

intersect()

bool VisiLibity::intersect	(	const Line_Segment &	line_segment1,
		const Line_Segment &	line_segment2,
		double	epsilon = 0.0
	)

true iff the Euclidean distance between Line_Segments is no greater than epsilon, false if either line segment has size 0

Author

Karl J. Obermeyer

intersect_proper()

bool VisiLibity::intersect_proper	(	const Line_Segment &	line_segment1,
		const Line_Segment &	line_segment2,
		double	epsilon = 0.0
	)

true iff line segments intersect properly w/in epsilon, false if either line segment has size 0

Author

Karl J. Obermeyer

Returns

true iff Line_Segments intersect exactly at a single point in their relative interiors. For robustness, here the relative interior of a Line_Segment is consider to be any Point in the Line_Segment which is a distance greater than epsilon from both endpoints.

intersection() [1/3]

Line_Segment VisiLibity::intersection	(	const Line_Segment &	line_segment1,
		const Line_Segment &	line_segment2,
		double	epsilon = 0.0
	)

intersection of Line_Segments

Author

Karl J. Obermeyer

Returns

a Line_Segment of size 0, 1, or 2

Remarks

size 0 results if the distance (or at least the floating-point computed distance) between line_segment1 and line_segment2 is (strictly) greater than epsilon. size 1 results if the segments intersect properly, form a "T" intersection, or "--"" intersection. size 2 results when two or more endpoints are a Euclidean distance no greater than epsilon from the opposite segment, and the overlap of the segments has a length greater than epsilon.

intersection() [2/3]

Line_Segment VisiLibity::intersection	(	const Line_Segment &	line_segment_temp,
		const Ray &	ray_temp,
		double	epsilon = 0.0
	)

compute the intersection of a Line_Segment with a Ray

Author

Karl J. Obermeyer

Precondition

member data of ray_temp has been assigned (numbers) and line_segment_temp has size greater than 0

Remarks

as a convention, if the intersection has positive length, the Line_Segment returned has the first point closest to the Ray's base point

intersection() [3/3]

Line_Segment VisiLibity::intersection	(	const Ray	ray_temp,
		const Line_Segment &	line_segment_temp,
		double	epsilon = 0.0
	)

compute the intersection of a Line_Segment with a Ray

Author

Karl J. Obermeyer

Precondition

member data of ray_temp has been assigned (numbers) and line_segment_temp has size greater than 0

Remarks

as a convention, if the intersection has positive length, the Line_Segment returned has the first point closest to the Ray's base point

operator!=()

bool VisiLibity::operator!=	(	const Ray &	ray1,
		const Ray &	ray2
	)

compare member data

Remarks

negation of ==

operator<() [1/2]

bool VisiLibity::operator<	(	const Point &	point1,
		const Point &	point2
	)

compare lexicographic order of points

For Points p1 and p2, p1 < p2 iff either p1.x() < p2.x() or p1.x()==p2.x() and p1.y()<p2.y(). False if any member data have not been assigned (numbers).

Remarks

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

operator<() [2/2]

bool VisiLibity::operator<	(	const Polar_Point &	polar_point1,
		const Polar_Point &	polar_point2
	)

compare according to polar lexicographic order (smaller bearing, then smaller range)

false if any member data have not been assigned (numbers)

Remarks

lex. comparison is very sensitive to perturbations if two Points nearly define a radial line

operator<=() [1/2]

bool VisiLibity::operator<=	(	const Point &	point1,
		const Point &	point2
	)

compare lexicographic order of points

For Points p1 and p2, p1 < p2 iff either p1.x() < p2.x() or p1.x()==p2.x() and p1.y()<p2.y(). False if any member data have not been assigned (numbers).

Remarks

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

operator<=() [2/2]

bool VisiLibity::operator<=	(	const Polar_Point &	polar_point1,
		const Polar_Point &	polar_point2
	)

compare according to polar lexicographic order (smaller bearing, then smaller range)

false if any member data have not been assigned (numbers)

Remarks

lex. comparison is very sensitive to perturbations if two Points nearly define a radial line

operator==() [1/5]

bool VisiLibity::operator==	(	const Line_Segment &	line_segment1,
		const Line_Segment &	line_segment2
	)

true iff endpoint coordinates are exactly equal, but false if either Line_Segment has size 0

Remarks

respects ordering of vertices, i.e., even if the line segments overlap exactly, they are not considered == unless the orientations are the same

operator==() [2/5]

bool VisiLibity::operator==	(	const Point &	point1,
		const Point &	point2
	)

True iff Points' coordinates are identical.

Remarks

NAN==NAN returns false, so if either point has not been assigned real number coordinates, they will not be ==

operator==() [3/5]

bool VisiLibity::operator==	(	const Polar_Point &	polar_point1,
		const Polar_Point &	polar_point2
	)

compare member data

Remarks

returns false if any member data are NaN

operator==() [4/5]

bool VisiLibity::operator==	(	const Ray &	ray1,
		const Ray &	ray2
	)

compare member data

Remarks

returns false if any member data are NaN

operator==() [5/5]

bool VisiLibity::operator==	(	Polygon	polygon1,
		Polygon	polygon2
	)

true iff vertex lists are identical, but false if either Polygon has size 0

Remarks

returns false if either Polygon has size 0

O(n) time complexity

operator>() [1/2]

bool VisiLibity::operator>	(	const Point &	point1,
		const Point &	point2
	)

compare lexicographic order of points

For Points p1 and p2, p1 < p2 iff either p1.x() < p2.x() or p1.x()==p2.x() and p1.y()<p2.y(). False if any member data have not been assigned (numbers).

Remarks

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

operator>() [2/2]

bool VisiLibity::operator>	(	const Polar_Point &	polar_point1,
		const Polar_Point &	polar_point2
	)

compare according to polar lexicographic order (smaller bearing, then smaller range)

false if any member data have not been assigned (numbers)

Remarks

lex. comparison is very sensitive to perturbations if two Points nearly define a radial line

operator>=() [1/2]

bool VisiLibity::operator>=	(	const Point &	point1,
		const Point &	point2
	)

compare lexicographic order of points

For Points p1 and p2, p1 < p2 iff either p1.x() < p2.x() or p1.x()==p2.x() and p1.y()<p2.y(). False if any member data have not been assigned (numbers).

Remarks

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

operator>=() [2/2]

bool VisiLibity::operator>=	(	const Polar_Point &	polar_point1,
		const Polar_Point &	polar_point2
	)

compare according to polar lexicographic order (smaller bearing, then smaller range)

false if any member data have not been assigned (numbers)

Remarks

lex. comparison is very sensitive to perturbations if two Points nearly define a radial line

uniform_random_sample()

double VisiLibity::uniform_random_sample	(	double	lower_bound,
		double	upper_bound
	)

get a uniform random sample from an (inclusive) interval on the real line

Author

Karl J. Obermeyer

Parameters

lower_bound	lower bound of the real interval
upper_bound	upper bound of the real interval

Precondition

lower_bound <= upper_bound

Returns

a random sample from a uniform probability distribution on the real interval [lower_bound, upper_bound]

Remarks

Uses the Standard Library's rand() function. rand() should be seeded (only necessary once at the beginning of the program) using the command std::srand( std::time( NULL ) ); rand();

Warning

performance degrades as upper_bound - lower_bound approaches RAND_MAX.

Variable Documentation

FIOS_PRECISION

const int VisiLibity::FIOS_PRECISION = 10

floating-point display precision.

This is the default precision with which floating point numbers are displayed or written to files for classes with a write_to_file() method.