Rational Points ( rat_point )

Definition

An instance of data type rat_point is a point with rational coordinates in the two-dimensional plane. A point with cartesian coordinates (a, b) is represented by homogeneous coordinates (x, y, w) of arbitrary length integers (see Integers of Arbitrary Length) such that a = x/w and b = y/w and w > 0.

#include < LEDA/geo/rat_point.h >

Types

rat_point::coord_type	the coordinate type (rational).
rat_point::point_type	the point type (rat_point).
rat_point::float_type	the corresponding floating-point type (point).

Creation

rat_point	p	introduces a variable p of type rat_point initialized to the point (0, 0).
rat_point	p(const rational& a, const rational& b)
		introduces a variable p of type rat_point initialized to the point (a, b).
rat_point	p(integer a, integer b)	introduces a variable p of type rat_point initialized to the point (a, b).
rat_point	p(integer x, integer y, integer w)
		introduces a variable p of type rat_point initialized to the point with homogeneous coordinates (x, y, w) if w > 0 and to point (- x, - y, - w) if w < 0. Precondition w $\not=$ 0.
rat_point	p(const rat_vector& v)	introduces a variable p of type rat_point initialized to the point (v[0], v[1]). Precondition: v.dim() = 2.
rat_point	p(const point& p1, int prec = rat_point::default_precision)
		introduces a variable p of type rat_point initialized to the point with homogeneous coordinates ($\lfloor$P*x$\rfloor$,$\lfloor$P*y$\rfloor$, P), where p1 = (x, y) and P = 2prec. If prec is non-positive, the conversion is without loss of precision, i.e., P is chosen as a sufficiently large power of two such that P*x and P*y are integers.
rat_point	p(double x, double y, int prec = rat_point::default_precision)
		see constructor above with p = (x, y).

Operations

point	p.to_float()	returns a floating point approximation of p.
rat_vector	p.to_vector()	returns the vector extending from the origin to p.
void	p.normalize()	simplifies the homogenous representation by dividing all coordinates by gcd (X, Y, W).
integer	p.X()	returns the first homogeneous coordinate of p.
integer	p.Y()	returns the second homogeneous coordinate of p.
integer	p.W()	returns the third homogeneous coordinate of p.
double	p.XD()	returns a floating point approximation of p.X().
double	p.YD()	returns a floating point approximation of p.Y().
double	p.WD()	returns a floating point approximation of p.W().
rational	p.xcoord()	returns the x-coordinate of p.
rational	p.ycoord()	returns the y-coordinate of p.
double	p.xcoordD()	returns a floating point approximation of p.xcoord().
double	p.ycoordD()	returns a floating point approximation of p.ycoord().
rat_point	p.rotate90(const rat_point& q, int i = 1)
		returns p rotated by i x 90 degrees about q. If i > 0 the rotation is counter-clockwise otherwise it is clockwise.
rat_point	p.rotate90(int i = 1)	returns p rotated by i x 90 degrees about the origin. If i > 0 the rotation is counter-clockwise otherwise it is clockwise.
rat_point	p.reflect(const rat_point& p, const rat_point& q)
		returns p reflected across the straight line passing through p and q. Precondition p $\not=$q.
rat_point	p.reflect(const rat_point& q)
		returns p reflected across point q.
rat_point	p.translate(const rational& dx, const rational& dy)
		returns p translated by vector (dx, dy).
rat_point	p.translate(integer dx, integer dy, integer dw)
		returns p translated by vector (dx/dw, dy/dw).
rat_point	p.translate(const rat_vector& v)
		returns p + v, i.e., p translated by vector v. Precondition v.dim() = 2.
rat_point	p + const rat_vector& v	returns p translated by vector v.
rat_point	p - const rat_vector& v	returns p translated by vector - v.
rational	p.sqr_dist(const rat_point& q)
		returns the squared distance between p and q.
int	p.cmp_dist(const rat_point& q, const rat_point& r)
		returns compare(p.sqr$\_$dist(q), p.sqr$\_$dist(r)).
rational	p.xdist(const rat_point& q)
		returns the horizontal distance between p and q.
rational	p.ydist(const rat_point& q)
		returns the vertical distance between p and q.
int	p.orientation(const rat_point& q, const rat_point& r)
		returns orientation(p, q, r) (see below).
rational	p.area(const rat_point& q, const rat_point& r)
		returns area(p, q, r) (see below).
rat_vector	p - const rat_point& q	returns the difference vector of the coordinates.

Non-Member Functions

int	cmp_signed_dist(const rat_point& a, const rat_point& b, const rat_point& c, const rat_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.
int	orientation(const rat_point& a, const rat_point& b, const rat_point& c)
		computes the orientation of points a, b, c as the sign of the determinant $\left\vert\begin{array}{ccc} a_x & a_y & a_w\\ b_x & b_y & b_w\\ c_x & c_y & c_w \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_distances(const rat_point& p1, const rat_point& p2, const rat_point& p3, const rat_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.
rat_point	midpoint(const rat_point& a, const rat_point& b)
		returns the midpoint of a and b.
rational	area(const rat_point& a, const rat_point& b, const rat_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(const rat_point& a, const rat_point& b, const rat_point& c)
		returns true if points a, b, c are collinear, i.e., orientation(a, b, c) = 0, and false otherwise.
bool	right_turn(const rat_point& a, const rat_point& b, const rat_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(const rat_point& a, const rat_point& b, const rat_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(const rat_point& a, const rat_point& b, const rat_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(const rat_point& a, const rat_point& b, const rat_point& c, const rat_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	incircle(const rat_point& a, const rat_point& b, const rat_point& c, const rat_point& d)
		returns true if point d lies in the interior of the circle through points a, b, and c, and false otherwise.
bool	outcircle(const rat_point& a, const rat_point& b, const rat_point& c, const rat_point& d)
		returns true if point d lies outside of the circle through points a, b, and c, and false otherwise.
bool	on_circle(const rat_point& a, const rat_point& b, const rat_point& c, const rat_point& d)
		returns true if points a, b, c, and d are cocircular.
bool	cocircular(const rat_point& a, const rat_point& b, const rat_point& c, const rat_point& d)
		returns true if points a, b, c, and d are cocircular.
int	compare_by_angle(const rat_point& a, const rat_point& b, const rat_point& c, const rat_point& d)
		compares vectors b-a and d-c by angle (more efficient than calling vector::compare_by_angle(b-a,d-x) on rat_vectors).
bool	affinely_independent(const array<rat_point>& A)
		decides whether the points in A are affinely independent.
bool	contained_in_simplex(const array<rat_point>& A, const rat_point& p)
		determines whether p is contained in the simplex spanned by the points in A. A may consist of up to 3 points. Precondition The points in A are affinely independent.
bool	contained_in_affine_hull(const array<rat_point>& A, const rat_point& p)
		determines whether p is contained in the affine hull of the points in A.