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.

Creation

rat_point	p;	introduces a variable p of type rat_point initialized to the point (0,0).
rat_point	p(rational a, 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 != 0.
rat_point	p(rat_vector v);	introduces a variable p of type rat_point initialized to the point (v[0],v[1]). Precondition: : v.dim() = 2.

Operations

point	p.to_point()	returns a floating point approximation of p.
rat_vector	p.to_vector()	returns the vector extending from the origin to p.
rational	p.xcoord()	returns the x-coordinate of p.
rational	p.ycoord()	returns the y-coordinate of p.
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().
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(rat_point q)	returns p rotated by 90 degrees about q.
rat_point	p.rotate90()	returns p rotated by 90 degrees about the origin.
rat_point	p.reflect(rat_point p, rat_point q)
		returns p reflected across the straight line passing through p and q. Precondition: p != q.
rat_point	p.reflect(rat_point q)	returns p reflected across point q.
rat_point	p.translate(rational dx, 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(rat_vector v)	returns p + v, i.e., p translated by vector v. Precondition: v.dim() = 2.
rat_point	p + rat_vector v	returns p translated by vector v.
rat_point	p - rat_vector v	returns p translated by vector -v.
rational	p.sqr_dist(rat_point q)	returns the squared distance between p and q.
rational	p.xdist(rat_point q)	returns the horizontal distance between p and q.
rational	p.ydist(rat_point q)	returns the vertical distance between p and q.
rat_vector	p - q	returns the difference vector of the coordinates.
ostream&	ostream& O << p	writes the homogeneous coordinates (x,y,w) of p to output stream O.
istream&	istream& I >> rat_point& p
		reads the homogeneous coordinates (x,y,w) of p from input stream I.

Non-Member Functions

int	orientation(rat_point a, rat_point b, 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_signed_dist(rat_point a, rat_point b, rat_point c, 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.
rat_point	midpoint(rat_point a, rat_point b)
		returns the midpoint of a and b.
rational	area(rat_point a, rat_point b, 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(rat_point a, rat_point b, 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(rat_point a, rat_point b, 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(rat_point a, rat_point b, 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_circle(rat_point a, rat_point b, rat_point c, 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	inside_circle(rat_point a, rat_point b, rat_point c, 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	outside_circle(rat_point a, rat_point b, rat_point c, 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(rat_point a, rat_point b, rat_point c, rat_point d)
		returns true if points a, b, c, and d are corcircular.
bool	cocircular(rat_point a, rat_point b, rat_point c, rat_point d)
		returns true if points a, b, c, and d are corcircular.
bool	affinely_independent(array<rat_point> A)
		decides whether the points in A are affinely independent.
bool	contained_in_simplex(array<rat_point> A, rat_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<rat_point> A, rat_point p)
		determines whether p is contained in the affine hull of the points in A.

Point Generators

rat_point	random_rat_point_in_square(int maxc)
		returns a point whose x and y-coordinates are random integers in $[-maxc \, .. \, maxc]$. The z-coordinate is zero. In 2d, this function is equivalent to random_rat_point_in_cube.
void	random_rat_points_in_square(int n, int maxc, list<rat_point>& L)
		returns a list L of n points ... .
rat_point	random_rat_point_in_disc(int R)
		returns a random point with integer x and y-coordinates in the disc with radius R centered at the origin. The z-coordinate is zero. In 2d this is the same as the function random_rat_point_in_ball. Precondition: R <= 2^14.
void	random_rat_points_in_disc(int n, int R, list<rat_point>& L)
		returns a list L of n points ... .
rat_point	random_rat_point_on_circle(int R)
		returns a random point with integer coordinates that lies close to the circle with radius R centered at the origin.
void	random_rat_points_on_circle(int m, int R, list<rat_point>& L)
		returns a list L of n points ... .
rat_point	random_rat_point_on_unit_circle(int D = 16383)
		returns a point close to the unit circle whose coordinates are random rationals of the form i/D where i is a random integer in the range $[0 \, .. \, D]$. The default value of D is 2^14 - 1.
void	random_rat_points_on_unit_circle(int m, int D, list<rat_point>& L)
		returns a list L of n points ... .
void	random_rat_points_on_unit_circle(int m, list<rat_point>& L)
		returns a list L of n points ... . The default value of D is used.
void	lattice_rat_points(int n, int maxc, list<rat_point>& L)
		returns a list L of approximately n points. The points have integer coordinates id/maxc for an appropriately chosen d and -maxc/d <= i <= maxc/d.
void	random_rat_points_on_segment(int n, int maxc, list<rat_point>& L)
		generates n points on the diagonal whose coordinates are random integer in the range from -maxc to maxc.