/*******************************************************************************
+
+  LEDA 3.5
+
+  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_RAT_POINT_H
#define LEDA_RAT_POINT_H

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


#include <LEDA/integer.h>
#include <LEDA/rational.h>
#include <LEDA/rat_vector.h>
#include <LEDA/point.h>

class rat_point;
class rat_segment;


//------------------------------------------------------------------------------
// rat_points
//------------------------------------------------------------------------------

class rat_point_rep  : public handle_rep {

friend class rat_point;
friend class rat_segment;

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

   double  xd;
   double  yd;
   double  wd;

   unsigned long id;

public:

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

  ~rat_point_rep() {}

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

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


};



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

class rat_point  : public handle_base {

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


 friend class rat_segment;

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

public:

static int orient_count;
static int exact_orient_count;

static int soc_count;
static int exact_soc_count;

static int cmp_count;
static int exact_cmp_count;

static int use_filter;

/*{\Mcreation p}*/

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

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

/*{\Moptions nextwarning=no }*/
 rat_point(int a, int b)  { PTR = new rat_point_rep(integer(a),integer(b)); }
 rat_point(integer a, integer b)  { PTR = new rat_point_rep(a,b); }
/*{\Mcreate introduces a variable |\Mvar| of type |\Mname|
initialized to the point $(a,b)$.}*/

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

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

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

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

/*{\Moperations 2 3.5 }*/

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

rat_vector  to_vector() const { return rat_vector(ptr()->x,ptr()->y,ptr()->w); }
/*{\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|.}*/

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 W() const { return ptr()->w; }
/*{\Mop     returns the third homogeneous coordinate of |\Mvar|.}*/


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


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()|. }*/



rat_point rotate90(const rat_point& q) const;
/*{\Mopl    returns |\Mvar| rotated by 90 degrees about $q$. }*/

rat_point rotate90() const;
/*{\Mop     returns |\Mvar| rotated by 90 degrees about the origin. }*/


rat_point reflect(const rat_point& p, const rat_point& q) const;
/*{\Mop     returns |\Mvar| reflected  across the straight line passing
            through $p$ and $q$.\\
\precond $p \not= q$.}*/

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

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

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

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

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

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


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

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

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


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


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

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

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


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

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


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


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


static int  cmp_xy(const rat_point&, const rat_point&);
static int  cmp_yx(const rat_point&, const rat_point&);
static int  cmp(const rat_point& a, const rat_point& b) { return cmp_xy(a,b); }

static void print_statistics();

};

/*{\Moptions nextwarning=no}*/
inline rat_point center(const rat_point& a, const rat_point& b)
{ return rat_point(a.X()*b.W()+b.X()*a.W(), 
                   a.Y()*b.W()+b.Y()*a.W(),2*a.W()*b.W()); } 

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



extern 
rational area(const rat_point& a, const rat_point& b, 
                                          const rat_point& c);
/*{\Mfuncl computes the signed area of the triangle determined by $a$,$b$,$c$,
           positive if $orientation(a,b,c) > 0$ and negative otherwise. }*/


inline bool collinear(const rat_point& a,const rat_point& b,const rat_point& c)
{ return orientation(a,b,c) == 0; }
/*{\Mfuncl  returns true if points $a$, $b$, $c$ are collinear, i.e.,
           $orientation(a,b,c) = 0$, and false otherwise. }*/


inline bool right_turn(const rat_point& a,const rat_point& b,const rat_point& c)
{ return orientation(a,b,c) < 0; }
/*{\Mfuncl  returns true if points $a$, $b$, $c$ form a righ turn, i.e.,
           $orientation(a,b,c) < 0$, and false otherwise. }*/


inline bool left_turn(const rat_point& a,const rat_point& b,const rat_point& c)
{ return orientation(a,b,c) > 0; }
/*{\Mfuncl  returns true if points $a$, $b$, $c$ form a left turn, i.e.,
           $orientation(a,b,c) > 0$, and false otherwise. }*/


extern
int side_of_circle(const rat_point& a, const rat_point& b, 
                                                 const rat_point& c,
                                                 const rat_point& d);
/*{\Mfuncl 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. }*/


/*{\Moptions nextwarning=no}*/
inline
bool incircle(const rat_point& a, const rat_point& b, const rat_point& c,
                                                      const rat_point& d)
{ return (orientation(a,b,c) * side_of_circle(a,b,c,d)) > 0; }
inline
bool inside_circle(const rat_point& a, const rat_point& b, const rat_point& c,
                                                      const rat_point& d)
{ return (orientation(a,b,c) * side_of_circle(a,b,c,d)) > 0; }

/*{\Mfuncl returns $true$ if point $d$ lies in the interior of the circle
           through points $a$, $b$, and $c$, and $false$ otherwise. }*/

/*{\Moptions nextwarning=no}*/
inline
bool outcircle(const rat_point& a, const rat_point& b, const rat_point& c,
                                                      const rat_point& d)
{ return (orientation(a,b,c) * side_of_circle(a,b,c,d)) < 0; }
inline
bool outside_circle(const rat_point& a, const rat_point& b, const rat_point& c,
                                                      const rat_point& d)
{ return (orientation(a,b,c) * side_of_circle(a,b,c,d)) < 0; }
/*{\Mfuncl returns $true$ if point $d$ lies outside of the circle
           through points $a$, $b$, and $c$, and $false$ otherwise. }*/

inline
bool on_circle(const rat_point& a, const rat_point& b, const rat_point& c,
                                                      const rat_point& d)
{ return side_of_circle(a,b,c,d) == 0; }
/*{\Mfuncl returns $true$ if points $a$, $b$, $c$, and $d$ are corcircular. }*/

inline
bool cocircular(const rat_point& a, const rat_point& b, const rat_point& c,
                                                      const rat_point& d)
{ return side_of_circle(a,b,c,d) == 0; }
/*{\Mfuncl returns $true$ if points $a$, $b$, $c$, and $d$ are corcircular. }*/



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



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

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

#endif



