Next: Rational Planes ( d3_rat_plane Up: Basic Data Types for Previous: Planes ( d3_plane )

Rational Points in 3D-Space ( d3_rat_point )

Definition

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

#include < LEDA/d3 _rat _point.h >

Creation

d3_rat_point p introduces a variable p of type d3_rat_point initialized to the point (0, 0, 0).

d3_rat_point p(rational a, rational b, rational c)

introduces a variable p of type d3_rat_point initialized to the point (a, b, c).

d3_rat_point p(integer a, integer b, integer c)

introduces a variable p of type d3_rat_point initialized to the point (a, b, c).

d3_rat_point p(integer x, integer y, integer z, integer w)

introduces a variable p of type d3_rat_point initialized to the point with homogeneous coordinates (x, y, z, w) if w > 0 and to point (- x, - y, - z, - w) if w < 0.
Precondition: w! = 0.

d3_rat_point p(rat_vector v) introduces a variable p of type d3_rat_point initialized to the point (v[0], v[1], v[2]).
Precondition: : v.dim() = 3.

Operations

d3_point p.to_d3_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.

rational p.zcoord() returns the z-coordinate of p.

rational p[int i] returns the ith cartesian coordinate of p
Precondition: 0 < = i < = 2.

double p.xcoordD() returns a floating point approximation of p.xcoord().

double p.ycoordD() returns a floating point approximation of p.ycoord().

double p.zcoordD() returns a floating point approximation of p.zcoord().

integer p.X() returns the first homogeneous coordinate of p.

integer p.Y() returns the second homogeneous coordinate of p.

integer p.Z() returns the third homogeneous coordinate of p.

integer p.W() returns the fourth homogeneous coordinate of p.

integer p.hcoord(int i) returns the ith homogeneous coordinate of p.
Precondition: 0 < = i < = 3.

double p.XD() returns a floating point approximation of p.X().

double p.YD() returns a floating point approximation of p.Y().

double p.ZD() returns a floating point approximation of p.Z().

double p.WD() returns a floating point approximation of p.W().

rat_point p.project_xy() returns p projected into the xy-plane.

rat_point p.project_yz() returns p projected into the yz-plane.

rat_point p.project_xz() returns p projected into the xz-plane.

d3_rat_point p.reflect(d3_rat_point p, d3_rat_point q, d3_rat_point r)

returns p reflected across the plane passing through p, q and r.
Precondition: p, q and r are not collinear.

d3_rat_point p.reflect(d3_rat_point q) returns p reflected across point q.

d3_rat_point p.translate(rational dx, rational dy, rational dz)

returns p translated by vector (dx, dy, dz).

d3_rat_point p.translate(integer dx, integer dy, integer dz, integer dw)

returns p translated by vector (dx/dw, dy/dw, dz/dw).

d3_rat_point p.translate(rat_vector v) returns p + v, i.e., p translated by vector v
Precondition: v.dim() = 3.

d3_rat_point p + rat_vector v returns p translated by vector v
Precondition: v.dim() = 3.

d3_rat_point p - rat_vector v returns p translated by vector - v
Precondition: v.dim() = 3.

rational p.sqr_dist(d3_rat_point q)

returns the squared distance between p and q.

rational p.xdist(d3_rat_point q) returns the x-distance between p and q.

rational p.ydist(d3_rat_point q) returns the y-distance between p and q.

rational p.zdist(d3_rat_point q) returns the z-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, z, w) of p to output stream O.

istream& istream& I >> d3_rat_point& p

reads the homogeneous coordinates (x, y, z, w) of p from input stream I.

Non-Member Functions

int orientation(d3_rat_point a, d3_rat_point b, d3_rat_point c, d3_rat_point d)

computes the orientation of points a, b, c and d as the sign of the determinant
$\left\Vert \begin{array}{cccc} a_w & b_w & c_w &d_w\\ a_x & b_x & c_x &d_x\\ a_y & b_y & c_y &d_y\\ a_z & b_z & c_z &d_z \end{array} \right\Vert$

i.e., it returns +1 if point d lies left of the directed plane through a, b, c, 0 if a,b, c and d are coplanar, and -1 otherwise.

d3_rat_point midpoint(d3_rat_point a, d3_rat_point b)

returns the midpoint of a and b.

rational volume(d3_rat_point a, d3_rat_point b, d3_rat_point c, d3_rat_point d)

computes the signed volume of the simplex determined by a,b,c, and d, positive if orientation(a, b, c, d ) > 0 and negative otherwise.

bool collinear(d3_rat_point a, d3_rat_point b, d3_rat_point c)

returns true if points a, b, c are collinear, and false otherwise.

bool coplanar(d3_rat_point a, d3_rat_point b, d3_rat_point c, d3_rat_point d)

returns true if points a, b, c, d are coplanar and false otherwise.

int side_of_sphere(d3_rat_point a, d3_rat_point b, d3_rat_point c, d3_rat_point d, d3_rat_point e)

returns +1 (-1) if point e lies on the positive (negative) side of the oriented sphere through points a, b, c, and d, and 0 if e is contained in this sphere.

int region_of_sphere(d3_rat_point a, d3_rat_point b, d3_rat_point c, d3_rat_point d, d3_rat_point x)

determines whether the point x lies inside (= + 1), on (= 0), or outside (= - 1) the sphere through points a, b, c, d, (equivalent to orientation(a,b,c,d) * side_of_sphere(a,b,c,d,x))
Precondition: orientation(A)! = 0

bool contained_in_simplex(d3_rat_point a, d3_rat_point b, d3_rat_point c, d3_rat_point d, d3_rat_point x)

determines whether x is contained in the simplex spanned by the points a, b, c, d.
Precondition: a, b, c, d are affinely independent.

bool contained_in_simplex(array<d3_rat_point> A, d3_rat_point x)

determines whether x is contained in the simplex spanned by the points in A.
Precondition: A must have size < = 4 and the points in A must be affinely independent.

bool contained_in_affine_hull(list<d3_rat_point> L, d3_rat_point x)

determines whether x is contained in the affine hull of the points in L.

bool contained_in_affine_hull(array<d3_rat_point> A, d3_rat_point x)

determines whether x is contained in the affine hull of the points in A.

int affine_rank(array<d3_rat_point> L)

computes the affine rank of the points in L.

int affine_rank(array<d3_rat_point> A)

computes the affine rank of the points in A.

bool affinely_independent(list<d3_rat_point> L)

decides whether the points in A are affinely independent.

bool affinely_independent(array<d3_rat_point> A)

decides whether the points in A are affinely independent.

bool inside_sphere(d3_rat_point a, d3_rat_point b, d3_rat_point c, d3_rat_point d, d3_rat_point e)

returns true if point e lies in the interior of the sphere through points a, b, c, and d, and false otherwise.

bool outside_sphere(d3_rat_point a, d3_rat_point b, d3_rat_point c, d3_rat_point d, d3_rat_point e)

returns true if point e lies in the exterior of the sphere through points a, b, c, and d, and false otherwise.

bool on_sphere(d3_rat_point a, d3_rat_point b, d3_rat_point c, d3_rat_point d, d3_rat_point e)

returns true if points a, b, c, d, and e lie on a common sphere.

d3_rat_point point_on_positive_side(d3_rat_point a, d3_rat_point b, d3_rat_point c)

returns a point d with orientation(a, b, c, d ) > 0.

Point Generators

d3_rat_point random_d3_rat_point_in_cube(int maxc)

returns a point whose coordinates are random integers in [- maxc .. maxc].

void random_d3_rat_points_in_cube(int n, int maxc, list<d3_rat_point>& L)

returns a list L of n points ... .

d3_rat_point random_d3_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_d3_rat_points_in_square(int n, int maxc, list<d3_rat_point>& L)

returns a list L of n points ... .

d3_rat_point random_d3_rat_point_in_unit_cube(int D = 16383)

returns a point 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¹⁴ - 1.

void random_d3_rat_points_in_unit_cube(int n, int D, list<d3_rat_point>& L)

returns a list L of n points ... .

void random_d3_rat_points_in_unit_cube(int n, list<d3_rat_point>& L)

as above, but the default value of D is used.

d3_rat_point random_d3_rat_point_in_ball(int R)

returns a random point with integer coordinates in the ball with radius R centered at the origin.
Precondition: R < = 2¹⁴.

void random_d3_rat_points_in_ball(int n, int R, list<d3_rat_point>& L)

returns a list L of n points ... .

d3_rat_point random_d3_rat_point_in_unit_ball(int D = 16383)

returns a point in the unit ball 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¹⁴ - 1.

void random_d3_rat_points_in_unit_ball(int n, int D, list<d3_rat_point>& L)

returns a list L of n points ... .

void random_d3_rat_points_in_unit_ball(int n, list<d3_rat_point>& L)

returns a list L of n points ... . The default value of D is used.

d3_rat_point random_d3_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¹⁴.

void random_d3_rat_points_in_disc(int n, int R, list<d3_rat_point>& L)

returns a list L of n points ... .

d3_rat_point random_d3_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_d3_rat_points_on_circle(int m, int R, list<d3_rat_point>& L)

returns a list L of n points ... .

d3_rat_point random_d3_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¹⁴ - 1.

void random_d3_rat_points_on_unit_circle(int m, int D, list<d3_rat_point>& L)

returns a list L of n points ... .

void random_d3_rat_points_on_unit_circle(int m, list<d3_rat_point>& L)

returns a list L of n points ... . The default value of D is used.

d3_rat_point random_d3_rat_point_on_sphere(int R)

returns a point with integer coordinates close to the sphere with radius R centered at the origin.

void random_d3_rat_points_on_sphere(int m, int R, list<d3_rat_point>& L)

returns a list L of n points ... .

d3_rat_point random_d3_rat_point_on_unit_sphere(int D = 16383)

returns a point close to the unit sphere 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¹⁴ - 1. In 2d this function is equivalent to point_on_unit_circle.

void random_d3_rat_points_on_unit_sphere(int m, int D, list<d3_rat_point>& L)

returns a list L of n points ... .

void random_d3_rat_points_on_unit_sphere(int m, list<d3_rat_point>& L)

returns a list L of n points ... . The default value of D is used.

d3_rat_point random_d3_rat_point_on_paraboloid(int maxc)

returns a point (x, y, z) with x and y random integers in the range [- maxc .. maxc], and z = 0.004*(x*x + y*y) - 1.25*maxc. The function does not make sense in 2d.

void random_d3_rat_points_on_paraboloid(int n, int maxc, list<d3_rat_point>& L)

returns a list L of n points ... .

void lattice_d3_rat_points(int n, int maxc, list<d3_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_d3_rat_points_on_segment(int n, int maxc, list<d3_rat_point>& L)

generates n points on the diagonal whose coordinates are random integer in the range from - maxc to maxc.

Next: Rational Planes ( d3_rat_plane Up: Basic Data Types for Previous: Planes ( d3_plane )

LEDA research project
1999-04-23

d3_rat_point	p	introduces a variable p of type d3_rat_point initialized to the point (0, 0, 0).
d3_rat_point	p(rational a, rational b, rational c)
		introduces a variable p of type d3_rat_point initialized to the point (a, b, c).
d3_rat_point	p(integer a, integer b, integer c)
		introduces a variable p of type d3_rat_point initialized to the point (a, b, c).
d3_rat_point	p(integer x, integer y, integer z, integer w)
		introduces a variable p of type d3_rat_point initialized to the point with homogeneous coordinates (x, y, z, w) if w > 0 and to point (- x, - y, - z, - w) if w < 0. Precondition: w! = 0.
d3_rat_point	p(rat_vector v)	introduces a variable p of type d3_rat_point initialized to the point (v[0], v[1], v[2]). Precondition: : v.dim() = 3.

d3_point	p.to_d3_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.
rational	p.zcoord()	returns the z-coordinate of p.
rational	p[int i]	returns the ith cartesian coordinate of p Precondition: 0 < = i < = 2.
double	p.xcoordD()	returns a floating point approximation of p.xcoord().
double	p.ycoordD()	returns a floating point approximation of p.ycoord().
double	p.zcoordD()	returns a floating point approximation of p.zcoord().
integer	p.X()	returns the first homogeneous coordinate of p.
integer	p.Y()	returns the second homogeneous coordinate of p.
integer	p.Z()	returns the third homogeneous coordinate of p.
integer	p.W()	returns the fourth homogeneous coordinate of p.
integer	p.hcoord(int i)	returns the ith homogeneous coordinate of p. Precondition: 0 < = i < = 3.
double	p.XD()	returns a floating point approximation of p.X().
double	p.YD()	returns a floating point approximation of p.Y().
double	p.ZD()	returns a floating point approximation of p.Z().
double	p.WD()	returns a floating point approximation of p.W().
rat_point	p.project_xy()	returns p projected into the xy-plane.
rat_point	p.project_yz()	returns p projected into the yz-plane.
rat_point	p.project_xz()	returns p projected into the xz-plane.
d3_rat_point	p.reflect(d3_rat_point p, d3_rat_point q, d3_rat_point r)
		returns p reflected across the plane passing through p, q and r. Precondition: p, q and r are not collinear.
d3_rat_point	p.reflect(d3_rat_point q)	returns p reflected across point q.
d3_rat_point	p.translate(rational dx, rational dy, rational dz)
		returns p translated by vector (dx, dy, dz).
d3_rat_point	p.translate(integer dx, integer dy, integer dz, integer dw)
		returns p translated by vector (dx/dw, dy/dw, dz/dw).
d3_rat_point	p.translate(rat_vector v)	returns p + v, i.e., p translated by vector v Precondition: v.dim() = 3.
d3_rat_point	p + rat_vector v	returns p translated by vector v Precondition: v.dim() = 3.
d3_rat_point	p - rat_vector v	returns p translated by vector - v Precondition: v.dim() = 3.
rational	p.sqr_dist(d3_rat_point q)
		returns the squared distance between p and q.
rational	p.xdist(d3_rat_point q)	returns the x-distance between p and q.
rational	p.ydist(d3_rat_point q)	returns the y-distance between p and q.
rational	p.zdist(d3_rat_point q)	returns the z-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, z, w) of p to output stream O.
istream&	istream& I >> d3_rat_point& p
		reads the homogeneous coordinates (x, y, z, w) of p from input stream I.

int	orientation(d3_rat_point a, d3_rat_point b, d3_rat_point c, d3_rat_point d)
		computes the orientation of points a, b, c and d as the sign of the determinant $\left\Vert \begin{array}{cccc} a_w & b_w & c_w &d_w\\ a_x & b_x & c_x &d_x\\ a_y & b_y & c_y &d_y\\ a_z & b_z & c_z &d_z \end{array} \right\Vert$ i.e., it returns +1 if point d lies left of the directed plane through a, b, c, 0 if a,b, c and d are coplanar, and -1 otherwise.
d3_rat_point	midpoint(d3_rat_point a, d3_rat_point b)
		returns the midpoint of a and b.
rational	volume(d3_rat_point a, d3_rat_point b, d3_rat_point c, d3_rat_point d)
		computes the signed volume of the simplex determined by a,b,c, and d, positive if orientation(a, b, c, d ) > 0 and negative otherwise.
bool	collinear(d3_rat_point a, d3_rat_point b, d3_rat_point c)
		returns true if points a, b, c are collinear, and false otherwise.
bool	coplanar(d3_rat_point a, d3_rat_point b, d3_rat_point c, d3_rat_point d)
		returns true if points a, b, c, d are coplanar and false otherwise.
int	side_of_sphere(d3_rat_point a, d3_rat_point b, d3_rat_point c, d3_rat_point d, d3_rat_point e)
		returns +1 (-1) if point e lies on the positive (negative) side of the oriented sphere through points a, b, c, and d, and 0 if e is contained in this sphere.
int	region_of_sphere(d3_rat_point a, d3_rat_point b, d3_rat_point c, d3_rat_point d, d3_rat_point x)
		determines whether the point x lies inside (= + 1), on (= 0), or outside (= - 1) the sphere through points a, b, c, d, (equivalent to orientation(a,b,c,d) * side_of_sphere(a,b,c,d,x)) Precondition: orientation(A)! = 0
bool	contained_in_simplex(d3_rat_point a, d3_rat_point b, d3_rat_point c, d3_rat_point d, d3_rat_point x)
		determines whether x is contained in the simplex spanned by the points a, b, c, d. Precondition: a, b, c, d are affinely independent.
bool	contained_in_simplex(array<d3_rat_point> A, d3_rat_point x)
		determines whether x is contained in the simplex spanned by the points in A. Precondition: A must have size < = 4 and the points in A must be affinely independent.
bool	contained_in_affine_hull(list<d3_rat_point> L, d3_rat_point x)
		determines whether x is contained in the affine hull of the points in L.
bool	contained_in_affine_hull(array<d3_rat_point> A, d3_rat_point x)
		determines whether x is contained in the affine hull of the points in A.
int	affine_rank(array<d3_rat_point> L)
		computes the affine rank of the points in L.
int	affine_rank(array<d3_rat_point> A)
		computes the affine rank of the points in A.
bool	affinely_independent(list<d3_rat_point> L)
		decides whether the points in A are affinely independent.
bool	affinely_independent(array<d3_rat_point> A)
		decides whether the points in A are affinely independent.
bool	inside_sphere(d3_rat_point a, d3_rat_point b, d3_rat_point c, d3_rat_point d, d3_rat_point e)
		returns true if point e lies in the interior of the sphere through points a, b, c, and d, and false otherwise.
bool	outside_sphere(d3_rat_point a, d3_rat_point b, d3_rat_point c, d3_rat_point d, d3_rat_point e)
		returns true if point e lies in the exterior of the sphere through points a, b, c, and d, and false otherwise.
bool	on_sphere(d3_rat_point a, d3_rat_point b, d3_rat_point c, d3_rat_point d, d3_rat_point e)
		returns true if points a, b, c, d, and e lie on a common sphere.
d3_rat_point	point_on_positive_side(d3_rat_point a, d3_rat_point b, d3_rat_point c)
		returns a point d with orientation(a, b, c, d ) > 0.

d3_rat_point	random_d3_rat_point_in_cube(int maxc)
		returns a point whose coordinates are random integers in [- maxc .. maxc].
void	random_d3_rat_points_in_cube(int n, int maxc, list<d3_rat_point>& L)
		returns a list L of n points ... .
d3_rat_point	random_d3_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_d3_rat_points_in_square(int n, int maxc, list<d3_rat_point>& L)
		returns a list L of n points ... .
d3_rat_point	random_d3_rat_point_in_unit_cube(int D = 16383)
		returns a point 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¹⁴ - 1.
void	random_d3_rat_points_in_unit_cube(int n, int D, list<d3_rat_point>& L)
		returns a list L of n points ... .
void	random_d3_rat_points_in_unit_cube(int n, list<d3_rat_point>& L)
		as above, but the default value of D is used.
d3_rat_point	random_d3_rat_point_in_ball(int R)
		returns a random point with integer coordinates in the ball with radius R centered at the origin. Precondition: R < = 2¹⁴.
void	random_d3_rat_points_in_ball(int n, int R, list<d3_rat_point>& L)
		returns a list L of n points ... .
d3_rat_point	random_d3_rat_point_in_unit_ball(int D = 16383)
		returns a point in the unit ball 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¹⁴ - 1.
void	random_d3_rat_points_in_unit_ball(int n, int D, list<d3_rat_point>& L)
		returns a list L of n points ... .
void	random_d3_rat_points_in_unit_ball(int n, list<d3_rat_point>& L)
		returns a list L of n points ... . The default value of D is used.
d3_rat_point	random_d3_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¹⁴.
void	random_d3_rat_points_in_disc(int n, int R, list<d3_rat_point>& L)
		returns a list L of n points ... .
d3_rat_point	random_d3_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_d3_rat_points_on_circle(int m, int R, list<d3_rat_point>& L)
		returns a list L of n points ... .
d3_rat_point	random_d3_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¹⁴ - 1.
void	random_d3_rat_points_on_unit_circle(int m, int D, list<d3_rat_point>& L)
		returns a list L of n points ... .
void	random_d3_rat_points_on_unit_circle(int m, list<d3_rat_point>& L)
		returns a list L of n points ... . The default value of D is used.
d3_rat_point	random_d3_rat_point_on_sphere(int R)
		returns a point with integer coordinates close to the sphere with radius R centered at the origin.
void	random_d3_rat_points_on_sphere(int m, int R, list<d3_rat_point>& L)
		returns a list L of n points ... .
d3_rat_point	random_d3_rat_point_on_unit_sphere(int D = 16383)
		returns a point close to the unit sphere 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¹⁴ - 1. In 2d this function is equivalent to point_on_unit_circle.
void	random_d3_rat_points_on_unit_sphere(int m, int D, list<d3_rat_point>& L)
		returns a list L of n points ... .
void	random_d3_rat_points_on_unit_sphere(int m, list<d3_rat_point>& L)
		returns a list L of n points ... . The default value of D is used.
d3_rat_point	random_d3_rat_point_on_paraboloid(int maxc)
		returns a point (x, y, z) with x and y random integers in the range [- maxc .. maxc], and z = 0.004(xx + yy) - 1.25maxc. The function does not make sense in 2d.
void	random_d3_rat_points_on_paraboloid(int n, int maxc, list<d3_rat_point>& L)
		returns a list L of n points ... .
void	lattice_d3_rat_points(int n, int maxc, list<d3_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_d3_rat_points_on_segment(int n, int maxc, list<d3_rat_point>& L)
		generates n points on the diagonal whose coordinates are random integer in the range from - maxc to maxc.