/*******************************************************************************
+
+  LEDA 3.5
+
+  d3_rat_point.h
+
+  This file is part of the LEDA research version (LEDA-R) that can be 
+  used free of charge in academic research and teaching. Any commercial
+  use of this software requires a license which is distributed by the
+  LEDA Software GmbH, Postfach 151101, 66041 Saarbruecken, FRG
+  (fax +49 681 31104).
+
+  Copyright (c) 1991-1997  by  Max-Planck-Institut fuer Informatik
+  Im Stadtwald, 66123 Saarbruecken, Germany     
+  All rights reserved.
+ 
*******************************************************************************/

#ifndef LEDA_D3_RAT_POINT_H
#define LEDA_D3_RAT_POINT_H

#if !defined(LEDA_ROOT_INCL_ID)
#define LEDA_ROOT_INCL_ID 350029
#include <LEDA/REDEFINE_NAMES.h>
#endif


#include <LEDA/integer.h>
#include <LEDA/rational.h>
#include <LEDA/rat_vector.h>
#include <LEDA/d3_point.h>
#include <LEDA/rat_point.h>

class d3_rat_point;


//------------------------------------------------------------------------------
// d3_rat_points
//------------------------------------------------------------------------------

class d3_rat_point_rep  : public handle_rep {

friend class d3_rat_point;

static leda_mutex mutex_id_counter;
static unsigned long id_counter;
   
   integer x;
   integer y;
   integer z;
   integer w;

   double  xd;
   double  yd;
   double  zd;
   double  wd;

   unsigned long id;

public:

   d3_rat_point_rep();
   d3_rat_point_rep(const rational&, const rational&, const rational&);
   d3_rat_point_rep(integer, integer, integer);
   d3_rat_point_rep(integer, integer, integer,integer);

  ~d3_rat_point_rep() {}

friend int orientation(const d3_rat_point&, const d3_rat_point&, 
                                 const d3_rat_point&, const d3_rat_point&);

friend inline unsigned long ID_Number(const d3_rat_point& p);

};



/*{\Manpage {d3_rat_point} {} {Rational Points} }*/

class d3_rat_point  : public handle_base {

/*{\Mdefinition
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 \ref{Integers of Arbitrary Length}) such that $a = x/w$,
$b = y/w$, $c = z/w$ and $w > 0$. 
}*/

 d3_rat_point_rep* ptr() const { return (d3_rat_point_rep*)PTR; } 

public:

static int orient_count;
static int exact_orient_count;

static int sos_count;
static int exact_sos_count;

static int cmp_count;
static int exact_cmp_count;

static int use_filter;

/*{\Mcreation p}*/

d3_rat_point() { PTR = new d3_rat_point_rep; }
/*{\Mcreate introduces a variable |\Mvar| of type |\Mname|
initialized to the point $(0,0,0)$.}*/

d3_rat_point(const rational& a, const rational& b, const rational& c)       
{ PTR = new d3_rat_point_rep(a,b,c); }
/*{\Mcreate introduces a variable |\Mvar| of type |\Mname|
initialized to the point $(a,b,c)$.}*/

/*{\Moptions nextwarning=no }*/

d3_rat_point(int a, int b, int c)  
{ PTR = new d3_rat_point_rep(integer(a),integer(b), integer(c)); }

d3_rat_point(integer a, integer b, integer c)  
{ PTR = new d3_rat_point_rep(a,b,c); }
/*{\Mcreate introduces a variable |\Mvar| of type |\Mname|
initialized to the point $(a,b,c)$.}*/

d3_rat_point(integer x, integer y, integer z, integer w) 
{ PTR = new d3_rat_point_rep(x,y,z,w); }
/*{\Mcreate introduces a variable |\Mvar| of type |\Mname|
initialized to the point with homogeneous coordinates $(x,y,z,w)$ if $w > 0$
and to point $(-x,-y,-z,-w)$ if $w < 0$.\\
\precond $w \not= 0$.}*/

d3_rat_point(const rat_vector& v) 
{ PTR = new d3_rat_point_rep(v.hcoord(0),v.hcoord(1),v.hcoord(2),v.hcoord(3)); }
/*{\Mcreate introduces a variable |\Mvar| of type |\Mname| initialized 
            to the point  $(v[0],v[1],v[2])$. \precond: |v.dim() = 3|. }*/

 d3_rat_point(const d3_rat_point& p) : handle_base(p) {}
~d3_rat_point() {}

 d3_rat_point& operator=(const d3_rat_point& p) 
 { handle_base::operator=(p); return *this; }

/*{\Moperations 2 3.5 }*/

d3_point to_d3_point() const;
/*{\Mop  returns a floating point approximation of |\Mvar|.}*/

rat_vector to_vector() const;
/*{\Mop     returns the vector extending from the origin to |\Mvar|.}*/


rational xcoord()  const { return rational(X(),W()); }
/*{\Mop     returns the $x$-coordinate of |\Mvar|.}*/

rational ycoord()  const { return rational(Y(),W()); }
/*{\Mop     returns the $y$-coordinate of |\Mvar|.}*/

rational zcoord()  const { return rational(Z(),W()); }
/*{\Mop     returns the $z$-coordinate of |\Mvar|.}*/

rational operator[](int i) const;
/*{\Marrop  returns the $i$th cartesian coordinate of |\Mvar|\\
            \precond  $0 \le i \le 2$. }*/


double xcoordD() const { return XD()/WD(); }
/*{\Mop     returns a floating point approximation of |\Mvar.xcoord()|. }*/

double ycoordD() const { return YD()/WD(); }
/*{\Mop     returns a floating point approximation of |\Mvar.ycoord()|. }*/

double zcoordD() const { return ZD()/WD(); }
/*{\Mop     returns a floating point approximation of |\Mvar.zcoord()|. }*/


integer X() const { return ptr()->x; }
/*{\Mop     returns the first homogeneous coordinate of |\Mvar|.}*/

integer Y() const { return ptr()->y; }
/*{\Mop     returns the second homogeneous coordinate of |\Mvar|.}*/

integer Z() const { return ptr()->z; }
/*{\Mop     returns the third homogeneous coordinate of |\Mvar|.}*/

integer W() const { return ptr()->w; }
/*{\Mop     returns the fourth homogeneous coordinate of |\Mvar|.}*/

integer hcoord(int i) const;
/*{\Mop     returns the $i$th homogeneous coordinate of |\Mvar|.\\
            \precond  $0 \le i \le 2$. }*/


double XD() const { return ptr()->xd; }
/*{\Mop     returns a floating point approximation of |\Mvar.X()|. }*/

double YD() const { return ptr()->yd; }
/*{\Mop     returns a floating point approximation of |\Mvar.Y()|. }*/

double ZD() const { return ptr()->zd; }
/*{\Mop     returns a floating point approximation of |\Mvar.Z()|. }*/

double WD() const { return ptr()->wd; }
/*{\Mop     returns a floating point approximation of |\Mvar.W()|. }*/

rat_point project_xy() const;
/*{\Mop  returns |\Mvar| projected into the xy-plane. }*/

rat_point project_yz() const;
/*{\Mop  returns |\Mvar| projected into the yz-plane. }*/

rat_point project_xz() const;
/*{\Mop  returns |\Mvar| projected into the xz-plane. }*/


d3_rat_point reflect(const d3_rat_point& p, 
                     const d3_rat_point& q,  const d3_rat_point& r) const;
/*{\Mop     returns |\Mvar| reflected  across the plane passing
            through $p$, $q$ and $r$.\\ 
            \precond $p$, $q$ and $r$ are not collinear.}*/

d3_rat_point reflect(const d3_rat_point& q) const;
/*{\Mop     returns |\Mvar| reflected across point $q$.}*/


d3_rat_point translate(const rational& dx, const rational& dy, 
                                           const rational& dz) const;
/*{\Mopl    returns |\Mvar| translated by vector $(dx,dy,dz)$.}*/

d3_rat_point translate(integer dx, integer dy, integer dz, integer dw) const;
/*{\Mopl    returns |\Mvar| translated by vector $(dx/dw,dy/dw,dz/dw)$.}*/

d3_rat_point translate(const rat_vector& v) const
{ return translate(v.hcoord(0),v.hcoord(1),v.hcoord(2),v.hcoord(3)); }
/*{\Mop     returns $|\Mvar| + v$, i.e., |\Mvar| translated by vector $v$\\
            \precond $v$.dim() = 3.}*/

d3_rat_point operator+(const rat_vector& v) const { return translate(v); }
/*{\Mbinop  returns |\Mvar| translated by vector $v$\\
	    \precond $v$.dim() = 3.}*/

d3_rat_point operator-(const rat_vector& v) const { return translate(-v); }
/*{\Mbinop  returns |\Mvar| translated by vector $-v$\\
            \precond $v$.dim() = 3.}*/



rational sqr_dist(const d3_rat_point& q) const;
/*{\Mopl    returns the squared distance between |\Mvar| and $q$. }*/

rational xdist(const d3_rat_point& q) const;
/*{\Mopl    returns the x-distance between |\Mvar| and $q$. }*/

rational ydist(const d3_rat_point& q) const;
/*{\Mopl    returns the y-distance between |\Mvar| and $q$. }*/

rational zdist(const d3_rat_point& q) const;
/*{\Mopl    returns the z-distance between |\Mvar| and $q$. }*/


friend unsigned long ID_Number(const d3_rat_point& p) { return p.ptr()->id; }


friend bool operator==(const d3_rat_point& p, const d3_rat_point& q)
{ return (identical(p,q)) || d3_rat_point::cmp_xyz(p,q) == 0; }

friend bool operator!=(const d3_rat_point& p, const d3_rat_point& q)
{ return (!identical(p,q)) && d3_rat_point::cmp_xyz(p,q) != 0; }

rat_vector operator-(const d3_rat_point& q)  const
{ return to_vector() - q.to_vector(); }
/*{\Mbinop  returns the difference vector of the coordinates.}*/


friend ostream& operator<<(ostream& O, const d3_rat_point& p) ;
/*{\Mbinopfunc  writes the homogeneous coordinates $(x,y,z,w)$ of |\Mvar| to 
                output stream $O$.}*/

friend istream& operator>>(istream& I, d3_rat_point& p) ;
/*{\Mbinopfunc  reads the homogeneous coordinates $(x,y,z,w)$ of |\Mvar| from 
                input stream $I$.}*/


/*{\Mtext
{\bf Non-Member Functions}
\smallskip
}*/


friend int orientation(const d3_rat_point& a, const d3_rat_point& b, 
                                 const d3_rat_point& c, const d3_rat_point& d);
/*{\Mfuncl computes the orientation of points $a$, $b$, $c$ and $d$ as the 
           sign of the determinant\\
           \[ \left\Lvert \begin{array}{cccc} a_x & a_y & a_z &a_w\\
                                              b_x & b_y & b_z &b_w\\
                                              c_x & c_y & c_z &c_w\\
                                              d_x & d_y & d_z &d_w
                       \end{array} \right\Lvert \] 
           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. }*/

friend int orientation_xy(const d3_rat_point& a,
                                    const d3_rat_point& b,
                                    const d3_rat_point& c);

friend int orientation_yz(const d3_rat_point& a, 
                                    const d3_rat_point& b, 
                                    const d3_rat_point& c);

friend int orientation_xz(const d3_rat_point& a, 
                                    const d3_rat_point& b, 
                                    const d3_rat_point& c);



static int  cmp_xyz(const d3_rat_point&, const d3_rat_point&);

static int  cmp(const d3_rat_point& a, const d3_rat_point& b) 
{ return cmp_xyz(a,b); }

static void print_statistics();

};

/*{\Moptions nextwarning=no}*/
d3_rat_point center(const d3_rat_point& a, const d3_rat_point& b);

inline d3_rat_point midpoint(const d3_rat_point& a, const d3_rat_point& b)
{ return center(a,b); }
/*{\Mfuncl returns the midpoint of $a$ and $b$. }*/




rational volume(const d3_rat_point& a, const d3_rat_point& b, 
                                          const d3_rat_point& c);
/*{\Mfuncl 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);
/*{\Mfuncl  returns true if points $a$, $b$, $c$ are collinear, 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);
/*{\Mfuncl 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. }*/

/*{\Moptions nextwarning=no}*/
inline bool insphere(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)
{ return (orientation(a,b,c,d) * side_of_sphere(a,b,c,d,e)) > 0; }


inline 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)
{ return (orientation(a,b,c,d) * side_of_sphere(a,b,c,d,e)) > 0; }
/*{\Mfuncl returns $true$ if point $e$ lies in the interior of the sphere
           through points $a$, $b$, $c$, and $d$, and $false$ otherwise. }*/


/*{\Moptions nextwarning=no}*/


/*{\Moptions nextwarning=no}*/
inline bool outsphere(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)
{ return (orientation(a,b,c,d) * side_of_sphere(a,b,c,d,e)) < 0; }


inline 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)
{ return (orientation(a,b,c,d) * side_of_sphere(a,b,c,d,e)) < 0; }
/*{\Mfuncl returns $true$ if point $e$ lies in the exterior of the sphere
           through points $a$, $b$, $c$, and $d$, and $false$ otherwise. }*/



inline
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)
{ return side_of_sphere(a,b,c,d,e) == 0; }
/*{\Mfuncl 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);
/*{\Mfuncl returns $a + (b-a)\times (c-a)$. }*/



inline int compare(const d3_rat_point& a, const d3_rat_point& b)
{  return (identical(a,b))  ? 0 : d3_rat_point::cmp_xyz(a,b); }


inline char* leda_tname(const d3_rat_point*) { return "d3_rat_point"; }

/*{\Mtext
\vspace{1cm} {\bf Point Generators}}*/

void random_points_in_cube(int n, int maxc, list<d3_rat_point>& L);
/*{\Mfuncl }*/

void random_points_in_ball(int n, int R, list<d3_rat_point>& L);
/*{\Mfuncl }*/

void points_on_sphere(int m, int R, list<d3_rat_point>& L);
/*{\Mfuncl }*/

void points_on_paraboloid(int n, int maxc, list<d3_rat_point>& L);
/*{\Mfuncl }*/

void lattice_points(int n, int maxc, list<d3_rat_point>& L);
/*{\Mfuncl }*/


void random_points_in_square(int n, int maxc, list<d3_rat_point>& L);
/*{\Mfuncl }*/

void random_points_on_disc(int n, int R, list<d3_rat_point>& L);
/*{\Mfuncl }*/

void random_points_on_segment(int n, int maxc, list<d3_rat_point>& L);
/*{\Mfuncl }*/


#if LEDA_ROOT_INCL_ID == 350029
#undef LEDA_ROOT_INCL_ID
#include <LEDA/UNDEFINE_NAMES.h>
#endif

#endif



