/*******************************************************************************
+
+  LEDA 3.5
+
+  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_POINT_H
#define LEDA_POINT_H

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


#include <LEDA/list.h>
#include <LEDA/vector.h>

class point;
class segment;

//------------------------------------------------------------------------------
// points
//------------------------------------------------------------------------------

class point_rep  : public handle_rep {

friend class point;
friend class segment;
friend class line;
friend class circle;

static leda_mutex mutex_id_counter;
static unsigned long id_counter;
   
   double x;
   double y;

   unsigned long id;

public:
    
   point_rep(double=0, double=0);
  ~point_rep() {}

friend inline unsigned long ID_Number(const point&);
   
};

/*{\Manpage {point} {} {Points}}*/

class point  : public handle_base 
{
/*{\Mdefinition
An instance of the data type $point$ is a point in the two-dimensional
plane $\real^2$. We use $(x,y)$ to denote a point with first (or x-)
coordinate $x$ and second (or y-) coordinate $y$.}*/

friend class segment;
friend class line;
friend class circle;


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

public:

/*{\Mcreation p }*/

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

 point(double x, double y);
/*{\Mcreate introduces a variable |\Mvar| of type |\Mname| initialized to 
            the point $(x,y)$.}*/

 point(vector v);
/*{\Mcreate introduces a variable |\Mvar| of type |\Mname| initialized 
            to the point $(v[0],v[1])$. \precond: |v.dim() = 2|. }*/

// for compatibility with rat_point. 
 point(double x, double y, double w);

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

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


/*{\Moperations 2 4}*/

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

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

vector  to_vector() const { return vector(xcoord(),ycoord()); }
/*{\Mop     returns the vector $\vec{xy}$.}*/

point   to_point() const { return *this; }
/*{\Xop  for compatibility with |rat_point|. }*/

double  xcoordD()  const   { return ptr()->x; }
/*{\Xop  for compatibility with |rat_point|. }*/

double  ycoordD()  const   { return ptr()->y; }
/*{\Xop  for compatibility with |rat_point|. }*/


int     dim() const { return 2; }
/*{\Xop  returns 2.}*/


double  sqr_dist(const point& q) const;
/*{\Mop     returns the square of the Euclidean distance between |\Mvar|
            and $q$.}*/

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

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


double  distance(const point& q) const;
/*{\Mop     returns the Euclidean distance between |\Mvar| and $q$.}*/

double  distance() const { return distance(point(0,0)); }
/*{\Mop     returns the Euclidean distance between |\Mvar| and $(0,0)$.}*/


double  angle(const point& q, const point& r) const;
/*{\Mop     returns the angle between $\vec{\Mvar q}$ and $\vec{\Mvar r}$.}*/


point   translate_by_angle(double alpha, double d) const;
/*{\Mopl    returns |\Mvar| translated in direction $alpha$ by distance $d$. 
            The  direction is given by its angle with a right oriented 
            horizontal ray.}*/

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


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

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

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



point   rotate(const point& q, double a) const;
/*{\Mopl    returns |\Mvar| rotated about $q$ by angle $a$.}*/

point   rotate(double a) const;
/*{\Mop     returns |\Mvar|.rotate($point(0,0),\ a$). }*/

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

point   rotate90() const;
/*{\Mop     returns |\Mvar|.rotate90($point(0,0)$). }*/


point reflect(const point& q, const point& r) const;
/*{\Mop     returns |\Mvar| reflected  across the straight line passing
            through $q$ and $r$.}*/

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


int operator==(const point& q) const;
int operator!=(const point& q)  const { return !operator==(q);}

vector operator-(const point& q)  const
{ return vector(xcoord()-q.xcoord(),ycoord()-q.ycoord()); }
/*{\Mbinop  returns the difference vector of the coordinates.}*/


static int  cmp_xy(const point&, const point&);
static int  cmp_yx(const point&, const point&);


friend ostream& operator<<(ostream& O, const point& p) ;
/*{\Mbinopfunc  writes |\Mvar| to output stream $O$.}*/

friend istream& operator>>(istream& I, point& p) ;
/*{\Mbinopfunc  reads the coordinates of |\Mvar| (two $double$ numbers)
	        from input stream $I$.}*/

friend inline unsigned long ID_Number(const point&);

};


inline int compare(const point& a, const point& b)
{ int r = compare(a.xcoord(),b.xcoord());
  return (r!=0) ? r : compare(a.ycoord(),b.ycoord());
 }



// geometric primitives

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

inline point center(const point& a, const point& b)
{ return point((a.xcoord()+b.xcoord())/2,(a.ycoord()+b.ycoord())/2); } 
/*{\Mfuncl returns the center of $a$ and $b$, i.e. $a +\vec{ab}/2$. }*/

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



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

inline int orientation(const point& a, const point& b, const point& c)
{ return compare((a.xcoord()-b.xcoord()) * (a.ycoord()-c.ycoord()),
                 (a.ycoord()-b.ycoord()) * (a.xcoord()-c.xcoord())); }

/*{\Mfuncl computes the orientation of points $a$, $b$, and $c$ as
           the sign of the determinant\\
           \[ \left\Lvert \begin{array}{ccc} a_x & a_y & 1\\
                                        b_x & b_y & 1\\
                                        c_x & c_y & 1
                       \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. }*/


inline double area(const point& a, const point& b, const point& c)
{ return ((a.xcoord()-b.xcoord()) * (a.ycoord()-c.ycoord()) -
          (a.ycoord()-b.ycoord()) * (a.xcoord()-c.xcoord()))/2; }
/*{\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 point& a, const point& b, const point& c)
{ return (a.ycoord()-b.ycoord()) * (a.xcoord()-c.xcoord()) ==
         (a.xcoord()-b.xcoord()) * (a.ycoord()-c.ycoord()); }
/*{\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 point& a, const point& b, const point& c)
{ return (a.xcoord()-b.xcoord()) * (a.ycoord()-c.ycoord()) <
         (a.ycoord()-b.ycoord()) * (a.xcoord()-c.xcoord()); }
/*{\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 point& a, const point& b, const point& c)
{ return (a.xcoord()-b.xcoord()) * (a.ycoord()-c.ycoord()) >
         (a.ycoord()-b.ycoord()) * (a.xcoord()-c.xcoord()); }
/*{\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 point& a, const point& b, const point& c,
                                                             const 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. }*/


inline
bool incircle(const point& a, const point& b, const point& c, const 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. }*/

inline
bool outcircle(const point& a, const point& b, const point& c, const 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 cocircular(const point& a, const point& b, const point& c, const point& d)
{ return side_of_circle(a,b,c,d) == 0; }

/*{\Mfuncl returns $true$ if points $a$, $b$, $c$, and $d$ are corcircular. }*/


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


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

#endif

