Points ( point )

Definition

An instance of the data type point is a point in the two-dimensional plane $\hbox$R². We use (x, y) to denote a point with first (or x-) coordinate x and second (or y-) coordinate y.

#include < LEDA/point.h >

Types

point::coord_type	the coordinate type (double).
point::point_type	the point type (point).

Creation

point	p	introduces a variable p of type point initialized to the point (0, 0).
point	p(double x, double y)	introduces a variable p of type point initialized to the point (x, y).
point	p(vector v)	introduces a variable p of type point initialized to the point (v[0], v[1]). Precondition: v.dim() = 2.
point	p(point p, int prec)	introduces a variable p of type point initialized to the point with coordinates ($\lfloor$P*x$\rfloor$/P,$\lfloor$P*x$\rfloor$/P), where p = (x, y) and P = 2prec. If prec is non-positive, the new point has coordinates x and y.

Operations

double	p.xcoord()	returns the first coordinate of p.
double	p.ycoord()	returns the second coordinate of p.
vector	p.to_vector()	returns the vector $\vec{xy}\,$.
int	p.orientation(point q, point r)
		returns orientation(p, q, r).
double	p.area(point q, point r)	returns area(p, q, r).
double	p.sqr_dist(point q)	returns the square of the Euclidean distance between p and q.
int	p.cmp_dist(point q, point r)
		returns compare(p.sqr$\_$dist(q), p.sqr$\_$dist(r)).
double	p.xdist(point q)	returns the horizontal distance between p and q.
double	p.ydist(point q)	returns the vertical distance between p and q.
double	p.distance(point q)	returns the Euclidean distance between p and q.
double	p.distance()	returns the Euclidean distance between p and (0, 0).
double	p.angle(point q, point r)	returns the angle between $\vec{p q}\,$ and $\vec{p r}\,$.
point	p.translate_by_angle(double alpha, double d)
		returns p translated in direction alpha by distance d. The direction is given by its angle with a right oriented horizontal ray.
point	p.translate(double dx, double dy)
		returns p translated by vector (dx, dy).
point	p.translate(vector v)	returns p+ v, i.e., p translated by vector v. Precondition v.dim() = 2.
point	p + vector v	returns p translated by vector v.
point	p - vector v	returns p translated by vector - v.
point	p.rotate(point q, double a)
		returns p rotated about q by angle a.
point	p.rotate(double a)	returns p.rotate( point(0, 0), a).
point	p.rotate90(point q, int i=1)
		returns p rotated about q by an angle of i x 90 degrees. If i > 0 the rotation is counter-clockwise otherwise it is clockwise.
point	p.rotate90(int i=1)	returns p.rotate90( point(0, 0), i).
point	p.reflect(point q, point r)
		returns p reflected across the straight line passing through q and r.
point	p.reflect(point q)	returns p reflected across point q.
vector	p - q	returns the difference vector of the coordinates.

Non-Member Functions

int	cmp_distances(point p1, point p2, point p3, point p4)
		compares the distances (p1,p2) and (p3,p4). Returns +1 (-1) if distance (p1,p2) is larger (smaller) than distance (p3,p4), otherwise 0.
point	center(point a, point b)	returns the center of a and b, i.e. a + $\vec{ab}\,$/2.
point	midpoint(point a, point b)
		returns the center of a and b.
int	orientation(point a, point b, point c)
		computes the orientation of points a, b, and c as the sign of the determinant $\left\vert\begin{array}{ccc} a_x & a_y & 1\\ b_x & b_y & 1\\ c_x & c_y & 1 \end{array} \right\vert$ i.e., it returns +1 if point c lies left of the directed line through a and b, 0 if a,b, and c are collinear, and -1 otherwise.
int	cmp_signed_dist(point a, point b, point c, point d)
		compares (signed) distances of c and d to the straight line passing through a and b (directed from a to b). Returns +1 (-1)if c has larger (smaller) distance than d and 0 if distances are equal.
double	area(point a, point b, point c)
		computes the signed area of the triangle determined by a,b,c, positive if orientation(a, b, c) > 0 and negative otherwise.
bool	collinear(point a, point b, point c)
		returns true if points a, b, c are collinear, i.e., orientation(a, b, c) = 0, and false otherwise.
bool	right_turn(point a, point b, point c)
		returns true if points a, b, c form a righ turn, i.e., orientation(a, b, c) < 0, and false otherwise.
bool	left_turn(point a, point b, point c)
		returns true if points a, b, c form a left turn, i.e., orientation(a, b, c) > 0, and false otherwise.
int	side_of_halfspace(point a, point b, point c)
		returns the sign of the scalar product (b - a)*(c - a). If b $\not=$a this amounts to: Let h be the open halfspace orthogonal to the vector b - a, containing b, and having a in its boundary. Returns +1 if c is contained in h, returns 0 is c lies on the the boundary of h, and returns -1 is c is contained in the interior of the complement of h.
int	side_of_circle(point a, point b, point c, point d)
		returns +1 if point d lies left of the directed circle through points a, b, and c, 0 if a,b,c,and d are cocircular, and -1 otherwise.
bool	inside_circle(point a, point b, point c, point d)
		returns true if point d lies in the interior of the circle through points a, b, and c, and false otherwise.
bool	outside_circle(point a, point b, point c, point d)
		returns true if point d lies outside of the circle through points a, b, and c, and false otherwise.
bool	on_circle(point a, point b, point c, point d)
		returns true if points a, b, c, and d are corcircular.
bool	cocircular(point a, point b, point c, point d)
		returns true if points a, b, c, and d are corcircular.
int	compare_by_angle(point a, point b, point c, point d)
		compares vectors b-a and d-c by angle (more efficient than calling compare_by_angle(b-a,d-x) on vectors).
bool	affinely_independent(array<point> A)
		decides whether the points in A are affinely independent.
bool	contained_in_simplex(array<point> A, point p)
		determines whether p is contained in the simplex spanned by the points in A. A may consists of up to 3 points. Precondition The points in A are affinely independent.
bool	contained_in_affine_hull(array<point> A, point p)
		determines whether p is contained in the affine hull of the points in A.