next up previous contents index
Next: Straight Rational Rays in Up: Basic Data Types for Previous: Simplices in 3D-Space (   Contents   Index


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/geo/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(const rational& a, const rational& b, const 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 $ \not=$ 0 .

d3_rat_point p(const 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_float() returns a floating point approximation of p.

rat_vector p.to_vector() returns the vector extending from the origin to p.

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.

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().

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 i th 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.hcoord(int i) returns the i th homogeneous coordinate of p.
Precondition 0 < = i < = 3 .

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(const d3_rat_point& p, const d3_rat_point& q, const 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(const d3_rat_point& q)
    returns p reflected across point q .

d3_rat_point p.translate(const rational& dx, const rational& dy, const 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(const rat_vector& v)
    returns p + v , i.e., p translated by vector v
Precondition v .dim() = 3.

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

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

rational p.sqr_dist(const d3_rat_point& q)
    returns the squared distance between p and q .

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

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

rational p.zdist(const d3_rat_point& q)
    returns the z-distance between p and q .

rat_vector p - const d3_rat_point& q returns the difference vector of the coordinates.

ostream& ostream& O < < const d3_rat_point& 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(const d3_rat_point& a, const d3_rat_point& b, const d3_rat_point& c, const 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.

int orientation_xy(const d3_rat_point& a, const d3_rat_point& b, const d3_rat_point& c)
    returns the orientation of the projections of a , b and c into the xy -plane.

int orientation_yz(const d3_rat_point& a, const d3_rat_point& b, const d3_rat_point& c)
    returns the orientation of the projections of a , b and c into the yz -plane.

int orientation_xz(const d3_rat_point& a, const d3_rat_point& b, const d3_rat_point& c)
    returns the orientation of the projections of a , b and c into the xz -plane.

int cmp_distances(const d3_rat_point& p1, const d3_rat_point& p2, const d3_rat_point& p3, const d3_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 .

d3_rat_point midpoint(const d3_rat_point& a, const d3_rat_point& b)
    returns the midpoint of a and b .

rational volume(const d3_rat_point& a, const d3_rat_point& b, const d3_rat_point& c, const 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(const d3_rat_point& a, const d3_rat_point& b, const d3_rat_point& c)
    returns true if points a , b , c are collinear, and false otherwise.

bool coplanar(const d3_rat_point& a, const d3_rat_point& b, const d3_rat_point& c, const d3_rat_point& d)
    returns true if points a , b , c , d are coplanar and false otherwise.

int side_of_sphere(const d3_rat_point& a, const d3_rat_point& b, const d3_rat_point& c, const d3_rat_point& d, const 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(const d3_rat_point& a, const d3_rat_point& b, const d3_rat_point& c, const d3_rat_point& d, const 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(const d3_rat_point& a, const d3_rat_point& b, const d3_rat_point& c, const d3_rat_point& d, const 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(const array< d3_rat_point> & A, const 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(const list< d3_rat_point> & L, const d3_rat_point& x)
    determines whether x is contained in the affine hull of the points in L .

bool contained_in_affine_hull(const array< d3_rat_point> & A, const d3_rat_point& x)
    determines whether x is contained in the affine hull of the points in A .

int affine_rank(const array< d3_rat_point> & L)
    computes the affine rank of the points in L .

int affine_rank(const array< d3_rat_point> & A)
    computes the affine rank of the points in A .

bool affinely_independent(const list< d3_rat_point> & L)
    decides whether the points in A are affinely independent.

bool affinely_independent(const array< d3_rat_point> & A)
    decides whether the points in A are affinely independent.

bool inside_sphere(const d3_rat_point& a, const d3_rat_point& b, const d3_rat_point& c, const d3_rat_point& d, const 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(const d3_rat_point& a, const d3_rat_point& b, const d3_rat_point& c, const d3_rat_point& d, const 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(const d3_rat_point& a, const d3_rat_point& b, const d3_rat_point& c, const d3_rat_point& d, const 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(const d3_rat_point& a, const d3_rat_point& b, const 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 214 - 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 < = 214 .

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 214 - 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 < = 214 .

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 214 - 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 214 - 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 up previous contents index
Next: Straight Rational Rays in Up: Basic Data Types for Previous: Simplices in 3D-Space (   Contents   Index
Christian Uhrig 2017-04-07