VisiLibity v1 Source Code 1.0
Classes | Functions | Variables
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 poperly, 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_boundlower bound of the real interval
upper_boundupper 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.