#ifndef T_GEOMETRY_INCLUDED

#define T_GEOMETRY_INCLUDED

#include "tutil.h"

#include <cmath></cmath>

#undef DVAPI

#undef DVVAR

#ifdef TGEOMETRY_EXPORTS

#define DVAPI DV_EXPORT_API

#define DVVAR DV_EXPORT_VAR

#else

#define DVAPI DV_IMPORT_API

#define DVVAR DV_IMPORT_VAR

#endif

//=============================================================================

/* 

* This is an example of how to use the TPointT, the TRectT and the TAffine classes.

*/

/*!  The template class TPointT defines the x- and y-coordinates of a point.

*/

template <class t=""></class>

class TPointT

{

public:

	T x, y;

	TPointT() : x(0), y(0){};

	TPointT(T _x, T _y) : x(_x), y(_y){};

	TPointT(const TPointT &point) : x(point.x), y(point.y){};

	inline TPointT &operator=(const TPointT &a)

	{

		x = a.x;

		y = a.y;

		return *this;

	};

	inline TPointT &operator+=(const TPointT &a)

	{

		x += a.x;

		y += a.y;

		return *this;

	};

	inline TPointT &operator-=(const TPointT &a)

	{

		x -= a.x;

		y -= a.y;

		return *this;

	};

	inline TPointT operator+(const TPointT &a) const { return TPointT(x + a.x, y + a.y); };

	inline TPointT operator-(const TPointT &a) const { return TPointT(x - a.x, y - a.y); };

	inline TPointT operator-() const { return TPointT(-x, -y); };

	bool operator!=(const TPointT &p) const

	{

		return x != p.x || y != p.y;

	}

};

/*! \relates TPointT  

* Rotate a point 90 degrees (counterclockwise).

\param p a point. 

\return the rotated point

\sa rotate270

*/

template <class t=""></class>

inline TPointT<t> rotate90(const TPointT<t> &p) // counterclockwise</t></t>

{

	return TPointT<t>(-p.y, p.x);</t>

}

/*! \relates TPointT  

* Rotate a point 270 degrees (clockwise).

\param p a point. 

\return the rotated point

\sa rotate90

*/

template <class t=""></class>

inline TPointT<t> rotate270(const TPointT<t> &p) // clockwise</t></t>

{

	return TPointT<t>(p.y, -p.x);</t>

}

/*!

\relates TPointT   

*/

template <class t=""> // prodotto scalare</class>

inline T operator*(const TPointT<t> &a, const TPointT<t> &b)</t></t>

{

	return a.x * b.x + a.y * b.y;

}

//-----------------------------------------------------------------------------

template <class t=""></class>

inline std::ostream &operator<<(std::ostream &out, const TPointT<t> &p)</t>

{

	return out << "(" << p.x << ", " << p.y << ")";

}

//-----------------------------------------------------------------------------

typedef TPointT<int> TPoint, TPointI;</int>

typedef TPointT<double> TPointD;</double>

#ifdef _WIN32

template class DVAPI TPointT<int>;</int>

template class DVAPI TPointT<double>;</double>

#endif

template <class t=""></class>

inline bool operator==(const TPointT<t> &p0, const TPointT<t> &p1)</t></t>

{

	return p0.x == p1.x && p0.y == p1.y;

}

//-----------------------------------------------------------------------------

//!\relates TPointT

inline TPoint operator*(int a, const TPoint &p)

{

	return TPoint(a * p.x, a * p.y);

}

//!\relates TPointT

inline TPoint operator*(const TPoint &p, int a)

{

	return TPoint(a * p.x, a * p.y);

}

//!\relates TPointT

inline TPointD operator*(double a, const TPointD &p)

{

	return TPointD(a * p.x, a * p.y);

}

//!\relates TPointT

inline TPointD operator*(const TPointD &p, double a)

{

	return TPointD(a * p.x, a * p.y);

}

//-----------------------------------------------------------------------------

/*!

\relates TPointT   

This helper function returns the square of the absolute value of the specified point (a TPointI)

*/

inline int norm2(const TPointI &p)

{

	return p.x * p.x + p.y * p.y;

}

//-----------------------------------------------------------------------------

/*!

\relates TPointT   

This helper function returns the square of the absolute value of the specified point (a TPointD)

*/

inline double norm2(const TPointD &p)

{

	return p.x * p.x + p.y * p.y;

}

/*!

\relates TPointT  

This helper function returns the absolute value of the specified point 

*/

inline double norm(const TPointD &p)

{

	return std::sqrt(norm2(p));

}

/*!

\relates TPointT  

This helper function returns the normalized version of the specified point 

*/

inline TPointD normalize(const TPointD &p)

{

	double n = norm(p);

	assert(n != 0.0);

	return (1.0 / n) * p;

}

/*!

\relates TPointT 

This helper function converts a TPoint (TPointT<int>) into a TPointD</int>

*/

inline TPointD convert(const TPoint &p)

{

	return TPointD(p.x, p.y);

}

/*!

\relates TPointT 

This helper function converts a TPointD (TPointT<double>) into a TPoint</double>

*/

inline TPoint convert(const TPointD &p)

{

	return TPoint(tround(p.x), tround(p.y));

}

/*!

\relates TPointT  

This helper function returns the square of the distance between two points  

*/

inline double tdistance2(const TPointD &p1, const TPointD &p2)

{

	return norm2(p2 - p1);

}

inline bool operator==(const TPointD &p0, const TPointD &p1)

{

	return tdistance2(p0, p1) < TConsts::epsilon * TConsts::epsilon;

}

/*!

\relates TPointT  

This helper function returns the distance between two points  

*/

inline double tdistance(const TPointD &p1, const TPointD &p2)

{

	return norm(p2 - p1);

}

/*!

the cross product

\relates TPointT

*/

inline double cross(const TPointD &a, const TPointD &b)

{

	return a.x * b.y - a.y * b.x;

}

/*!

the cross product

\relates TPoint

*/

inline int cross(const TPoint &a, const TPoint &b)

{

	return a.x * b.y - a.y * b.x;

}

/*!

returns the angle of the point p in polar coordinates

n.b atan(-y) = -pi/2, atan(x) = 0, atan(y) = pi/2, atan(-x) = pi

*/

inline double atan(const TPointD &p)

{

	return atan2(p.y, p.x);

}

//=============================================================================

template <class t=""></class>

class DVAPI T3DPointT

{

public:

	T x, y, z;

	T3DPointT()

		: x(0), y(0), z(0) {}

	T3DPointT(T _x, T _y, T _z)

		: x(_x), y(_y), z(_z) {}

	T3DPointT(const TPointT<t> &_p, T _z)</t>

		: x(_p.x), y(_p.y), z(_z) {}

	T3DPointT(const T3DPointT &_p)

		: x(_p.x), y(_p.y), z(_p.z) {}

	inline T3DPointT &operator=(const T3DPointT &a)

	{

		x = a.x;

		y = a.y;

		z = a.z;

		return *this;

	}

	inline T3DPointT &operator+=(const T3DPointT &a)

	{

		x += a.x;

		y += a.y;

		z += a.z;

		return *this;

	}

	inline T3DPointT &operator-=(const T3DPointT &a)

	{

		x -= a.x;

		y -= a.y;

		z -= a.z;

		return *this;

	}

	inline T3DPointT operator+(const T3DPointT &a) const

	{

		return T3DPointT(x + a.x, y + a.y, z + a.z);

	}

	inline T3DPointT operator-(const T3DPointT &a) const

	{

		return T3DPointT(x - a.x, y - a.y, z - a.z);

	}

	inline T3DPointT operator-() const

	{

		return T3DPointT(-x, -y, -z);

	}

	bool operator==(const T3DPointT &p) const

	{

		return x == p.x && y == p.y && z == p.z;

	}

	bool operator!=(const T3DPointT &p) const

	{

		return x != p.x || y != p.y || z != p.z;

	}

};

//=============================================================================

template <class t=""></class>

inline std::ostream &operator<<(std::ostream &out, const T3DPointT<t> &p)</t>

{

	return out << "(" << p.x << ", " << p.y << ", " << p.z << ")";

}

typedef T3DPointT<int> T3DPoint, T3DPointI;</int>

typedef T3DPointT<double> T3DPointD;</double>

#ifdef _WIN32

template class DVAPI T3DPointT<int>;</int>

template class DVAPI T3DPointT<double>;</double>

#endif

//-----------------------------------------------------------------------------

//!\relates T3DPointT

template <class t=""></class>

inline T3DPointT<t> operator*(T a, const T3DPointT<t> &p)</t></t>

{

	return T3DPointT<t>(a * p.x, a * p.y, a * p.z);</t>

}

//!\relates TPointT

template <class t=""></class>

inline T3DPointT<t> operator*(const T3DPointT<t> &p, T a)</t></t>

{

	return T3DPointT<t>(a * p.x, a * p.y, a * p.z);</t>

}

//-----------------------------------------------------------------------------

/*!

\relates TPointT   

This helper function returns the square of the absolute value of the specified point (a TPointI)

*/

template <class t=""></class>

inline T norm2(const T3DPointT<t> &p)</t>

{

	return p.x * p.x + p.y * p.y + p.z * p.z;

}

/*!

*/

template <class t=""></class>

inline T norm(const T3DPointT<t> &p)</t>

{

	return std::sqrt(norm2(p));

}

/*!

*/

inline T3DPointD normalize(const T3DPointD &p)

{

	double n = norm(p);

	assert(n != 0.0);

	return (1.0 / n) * p;

}

/*!

*/

inline T3DPointD convert(const T3DPoint &p)

{

	return T3DPointD(p.x, p.y, p.z);

}

/*!

*/

inline T3DPoint convert(const T3DPointD &p)

{

	return T3DPoint(tround(p.x), tround(p.y), tround(p.z));

}

//!

template <class t=""></class>

inline T tdistance(const T3DPointT<t> &p1, const T3DPointT<t> &p2)</t></t>

{

	return norm<t>(p2 - p1);</t>

}

//!

template <class t=""></class>

inline T tdistance2(const T3DPointT<t> &p1, const T3DPointT<t> &p2)</t></t>

{

	return norm2<t>(p2 - p1);</t>

}

//!

template <class t=""></class>

inline T3DPointT<t> cross(const T3DPointT<t> &a, const T3DPointT<t> &b)</t></t></t>

{

	return T3DPointT<t>(a.y * b.z - b.y * a.z,</t>

						a.z * b.x - b.z * a.x,

						a.x * b.y - b.x * a.y);

}

//=============================================================================

/*!

TThickPoint describe a thick point.

\relates TThickQuadratic, TThickCubic

*/

class DVAPI TThickPoint : public TPointD

{

public:

	double thick;

	TThickPoint()

		: TPointD(), thick(0) {}

	TThickPoint(double _x, double _y, double _thick = 0)

		: TPointD(_x, _y), thick(_thick) {}

	TThickPoint(const TPointD &_p, double _thick = 0)

		: TPointD(_p.x, _p.y), thick(_thick) {}

	TThickPoint(const T3DPointD &_p)

		: TPointD(_p.x, _p.y), thick(_p.z) {}

	TThickPoint(const TThickPoint &_p)

		: TPointD(_p.x, _p.y), thick(_p.thick) {}

	inline TThickPoint &operator=(const TThickPoint &a)

	{

		x = a.x;

		y = a.y;

		thick = a.thick;

		return *this;

	}

	inline TThickPoint &operator+=(const TThickPoint &a)

	{

		x += a.x;

		y += a.y;

		thick += a.thick;

		return *this;

	}

	inline TThickPoint &operator-=(const TThickPoint &a)

	{

		x -= a.x;

		y -= a.y;

		thick -= a.thick;

		return *this;

	}

	inline TThickPoint operator+(const TThickPoint &a) const

	{

		return TThickPoint(x + a.x, y + a.y, thick + a.thick);

	}

	inline TThickPoint operator-(const TThickPoint &a) const

	{

		return TThickPoint(x - a.x, y - a.y, thick - a.thick);

	}

	inline TThickPoint operator-() const

	{

		return TThickPoint(-x, -y, -thick);

	}

	bool operator==(const TThickPoint &p) const

	{

		return x == p.x && y == p.y && thick == p.thick;

	}

	bool operator!=(const TThickPoint &p) const

	{

		return x != p.x || y != p.y || thick != p.thick;

	}

};

inline double operator*(const TThickPoint &a, const TThickPoint &b)

{

	return a.x * b.x + a.y * b.y + a.thick * b.thick;

}

inline TThickPoint operator*(double a, const TThickPoint &p)

{

	return TThickPoint(a * p.x, a * p.y, a * p.thick);

}

inline TThickPoint operator*(const TThickPoint &p, double a)

{

	return TThickPoint(a * p.x, a * p.y, a * p.thick);

}

/*!

\relates TPointD 

This helper function converts a TThickPoint into a TPointD

*/

inline TPointD convert(const TThickPoint &p)

{

	return TPointD(p.x, p.y);

}

/*!

\relates TThickPoint  

This helper function returns the square of the distance between two thick points  

(only x and y are used)

*/

inline double tdistance2(const TThickPoint &p1, const TThickPoint &p2)

{

	return norm2(convert(p2 - p1));

}

/*!

\relates TThickPoint  

This helper function returns the distance between two thick  points  

(only x and y are used)

*/

inline double tdistance(const TThickPoint &p1, const TThickPoint &p2)

{

	return norm(convert(p2 - p1));

}

inline std::ostream &operator<<(std::ostream &out, const TThickPoint &p)

{

	return out << "(" << p.x << ", " << p.y << ", " << p.thick << ")";

}

//=============================================================================

//!	This is a template class representing a generic vector in a plane, i.e. a point.

/*!	

		It is a data structure with two objects in it representing coordinate of the point and 

		the basic operations on it.

	*/

template <class t=""></class>

class DVAPI TDimensionT

{

public:

	T lx, ly;

	/*!

		Constructs a vector of two elements, i.e. a point in a plane.

	*/

	TDimensionT() : lx(), ly() {}

	TDimensionT(T _lx, T _ly) : lx(_lx), ly(_ly) {}

	/*!

		Copy constructor.

	*/

	TDimensionT(const TDimensionT &d) : lx(d.lx), ly(d.ly) {}

	/*!

		Vector addition.

	*/

	TDimensionT &operator+=(TDimensionT a)

	{

		lx += a.lx;

		ly += a.ly;

		return *this;

	}

	/*!

		Difference of two vectors.

	*/

	TDimensionT &operator-=(TDimensionT a)

	{

		lx -= a.lx;

		ly -= a.ly;

		return *this;

	}

	/*!

		Addition of two vectors.

	*/

	TDimensionT operator+(TDimensionT a) const

	{

		TDimensionT ris(*this);

		return ris += a;

	}

	/*!

		Vector difference.

	*/

	TDimensionT operator-(TDimensionT a) const

	{

		TDimensionT ris(*this);

		return ris -= a;

	}

	/*!

		Compare vectors and returns \e true if are equals element by element.

	*/

	bool operator==(const TDimensionT &d) const

	{

		return lx == d.lx && ly == d.ly;

	}

	/*!

		Compare vectors and returns \e true if are not equals element by element.

	*/

	bool operator!=(const TDimensionT &d) const { return !operator==(d); }

};

//=============================================================================

typedef TDimensionT<int> TDimension, TDimensionI;</int>

typedef TDimensionT<double> TDimensionD;</double>

//=============================================================================

template <class t=""></class>

inline std::ostream &operator<<(std::ostream &out, const TDimensionT<t> &p)</t>

{

	return out << "(" << p.lx << ", " << p.ly << ")";

}

#ifdef _WIN32

template class DVAPI TDimensionT<int>;</int>

template class DVAPI TDimensionT<double>;</double>

#endif

//=============================================================================

//! Specifies the corners of a rectangle.

/*!\arg \a x0 specifies the x-coordinate of the bottom-left corner of a rectangle.

\arg \a y0 specifies the y-coordinate of the bottom-left corner of a rectangle.

\arg \a x1 specifies the x-coordinate of the upper-right corner of a rectangle.

\arg \a y1 specifies the y-coordinate of the upper-right corner of a rectangle.

*/

template <class t=""></class>

class DVAPI TRectT

{

public:

	/*! if x0>x1 || y0>y1 then rect is empty

    if x0==y1 && y0==y1 and rect is a  TRectD then rect is empty */

	T x0, y0;

	T x1, y1;

	/*! makes an empty rect */

	TRectT();

	TRectT(T _x0, T _y0, T _x1, T _y1)

		: x0(_x0), y0(_y0), x1(_x1), y1(_y1){};

	TRectT(const TRectT &rect)

		: x0(rect.x0), y0(rect.y0), x1(rect.x1), y1(rect.y1){};

	TRectT(const TPointT<t> &p0, const TPointT<t> &p1) // non importa l'ordine</t></t>

		: x0(tmin((T)p0.x, (T)p1.x)),

		  y0(tmin((T)p0.y, (T)p1.y)),

		  x1(tmax((T)p0.x, (T)p1.x)),

		  y1(tmax((T)p0.y, (T)p1.y)){};

	TRectT(const TPointT<t> &bottomLeft, const TDimensionT<t> &d);</t></t>

	TRectT(const TDimensionT<t> &d);</t>

	void empty();

	/*! TRectD is empty if and only if (x0>x1 || y0>y1) || (x0==y1 && y0==y1); 

    TRectI  is empty if x0>x1 || y0>y1 */

	bool isEmpty() const;

	T getLx() const;

	T getLy() const;

	TDimensionT<t> getSize() const</t>

	{

		return TDimensionT<t>(getLx(), getLy());</t>

	};

	TPointT<t> getP00() const { return TPointT<t>(x0, y0); };</t></t>

	TPointT<t> getP10() const { return TPointT<t>(x1, y0); };</t></t>

	TPointT<t> getP01() const { return TPointT<t>(x0, y1); };</t></t>

	TPointT<t> getP11() const { return TPointT<t>(x1, y1); };</t></t>

	//!Returns the union of two source rectangles.

	/*!The union is the smallest rectangle that contains both source rectangles. 

    */

	TRectT<t> operator+(const TRectT<t> &rect) const</t></t>

	{ // unione

		if (isEmpty())

			return rect;

		else if (rect.isEmpty())

			return *this;

		else

			return TRectT<t>(</t>

				tmin((T)x0, (T)rect.x0), tmin((T)y0, (T)rect.y0),

				tmax((T)x1, (T)rect.x1), tmax((T)y1, (T)rect.y1));

	};

	TRectT<t> &operator+=(const TRectT<t> &rect)</t></t>

	{ // unione

		return *this = *this + rect;

	};

	TRectT<t> &operator*=(const TRectT<t> &rect)</t></t>

	{ // intersezione

		return *this = *this * rect;

	};

	/*!Returns the intersection of two existing rectangles. 

      The intersection is the largest rectangle contained in both existing rectangles.

    */

	TRectT<t> operator*(const TRectT<t> &rect) const</t></t>

	{ // intersezione

		if (isEmpty() || rect.isEmpty())

			return TRectT<t>();</t>

		else if (rect.x1 < x0 || x1 < rect.x0 || rect.y1 < y0 || y1 < rect.y0)

			return TRectT<t>();</t>

		else

			return TRectT<t>(</t>

				tmax((T)x0, (T)rect.x0), tmax((T)y0, (T)rect.y0),

				tmin((T)x1, (T)rect.x1), tmin((T)y1, (T)rect.y1));

	};

	TRectT<t> &operator+=(const TPointT<t> &p)</t></t>

	{ // spostamento

		x0 += p.x;

		y0 += p.y;

		x1 += p.x;

		y1 += p.y;

		return *this;

	};

	TRectT<t> &operator-=(const TPointT<t> &p)</t></t>

	{

		x0 -= p.x;

		y0 -= p.y;

		x1 -= p.x;

		y1 -= p.y;

		return *this;

	};

	TRectT<t> operator+(const TPointT<t> &p) const</t></t>

	{

		TRectT<t> ris(*this);</t>

		return ris += p;

	};

	TRectT<t> operator-(const TPointT<t> &p) const</t></t>

	{

		TRectT<t> ris(*this);</t>

		return ris -= p;

	};

	bool operator==(const TRectT<t> &r) const</t>

	{

		return x0 == r.x0 && y0 == r.y0 && x1 == r.x1 && y1 == r.y1;

	};

	bool operator!=(const TRectT<t> &r) const</t>

	{

		return x0 != r.x0 || y0 != r.y0 || x1 != r.x1 || y1 != r.y1;

	};

	bool contains(const TPointT<t> &p) const</t>

	{

		return x0 <= p.x && p.x <= x1 && y0 <= p.y && p.y <= y1;

	};

	bool contains(const TRectT<t> &b) const</t>

	{

		return x0 <= b.x0 && x1 >= b.x1 && y0 <= b.y0 && y1 >= b.y1;

	};

	bool overlaps(const TRectT<t> &b) const</t>

	{

		return x0 <= b.x1 && x1 >= b.x0 &&

			   y0 <= b.y1 && y1 >= b.y0;

	};

	TRectT<t> enlarge(T dx, T dy) const</t>

	{

		if (isEmpty())

			return *this;

		return TRectT<t>(x0 - dx, y0 - dy, x1 + dx, y1 + dy);</t>

	};

	TRectT<t> enlarge(T d) const { return enlarge(d, d); };</t>

	TRectT<t> enlarge(TDimensionT<t> d) const</t></t>

	{

		return enlarge(d.lx, d.ly);

	};

};

//-----------------------------------------------------------------------------

typedef TRectT<int> TRect, TRectI;</int>

typedef TRectT<double> TRectD;</double>

#ifdef _WIN32

template class DVAPI TRectT<int>;</int>

template class DVAPI TRectT<double>;</double>

#endif

//=============================================================================

// check this, not final version

/*! 

\relates TRectT

Convert a TRectD into a TRect

*/

inline TRect convert(const TRectD &r)

{

	return TRect(

		(int)(r.x0 + 0.5), (int)(r.y0 + 0.5),

		(int)(r.x1 + 0.5), (int)(r.y1 + 0.5));

}

/*! 

\relates TRectT  

Convert a TRect into a TRectD

*/

inline TRectD convert(const TRect &r)

{

	return TRectD(r.x0, r.y0, r.x1, r.y1);

}

// template?

/*! 

\relates TRectT 

\relates TPointT  

*/

inline TRectD boundingBox(const TPointD &p0, const TPointD &p1)

{

	return TRectD(tmin(p0.x, p1.x), tmin(p0.y, p1.y),

				  tmax(p0.x, p1.x), tmax(p0.y, p1.y));

}

/*!

\relates TRectT 

\relates TPointT  

*/

inline TRectD boundingBox(

	const TPointD &p0,

	const TPointD &p1,

	const TPointD &p2)

{

	return TRectD(tmin(p0.x, p1.x, p2.x), tmin(p0.y, p1.y, p2.y),

				  tmax(p0.x, p1.x, p2.x), tmax(p0.y, p1.y, p2.y));

}

/*!

\relates TRectT 

\relates TPointT  

*/

inline TRectD boundingBox(

	const TPointD &p0,

	const TPointD &p1,

	const TPointD &p2,

	const TPointD &p3)

{

	return TRectD(

		tmin(p0.x, p1.x, p2.x, p3.x),

		tmin(p0.y, p1.y, p2.y, p3.y),

		tmax(p0.x, p1.x, p2.x, p3.x),

		tmax(p0.y, p1.y, p2.y, p3.y));

}

//-----------------------------------------------------------------------------

template <>

inline TRectT<int>::TRectT() : x0(0), y0(0), x1(-1), y1(-1) {}</int>

template <>

inline TRectT<int>::TRectT(const TPointT<int> &bottomLeft, const TDimensionT<int> &d)</int></int></int>

	: x0(bottomLeft.x), y0(bottomLeft.y), x1(bottomLeft.x + d.lx - 1), y1(bottomLeft.y + d.ly - 1){};

template <>

inline TRectT<int>::TRectT(const TDimensionT<int> &d)</int></int>

	: x0(0), y0(0), x1(d.lx - 1), y1(d.ly - 1){};

template <>

inline bool TRectT<int>::isEmpty() const { return x0 > x1 || y0 > y1; }</int>

template <>

inline void TRectT<int>::empty()</int>

{

	x0 = y0 = 0;

	x1 = y1 = -1;

}

template <>

inline int TRectT<int>::getLx() const { return x1 >= x0 ? x1 - x0 + 1 : 0; }</int>

template <>

inline int TRectT<int>::getLy() const { return y1 >= y0 ? y1 - y0 + 1 : 0; }</int>