// -*- C++ -*-
// --------------------------------------------------------------------
// Geometric primitives
// --------------------------------------------------------------------
/*

    This file is part of the extensible drawing editor Ipe.
    Copyright (C) 1993-2007  Otfried Cheong

    Ipe is free software; you can redistribute it and/or modify it
    under the terms of the GNU General Public License as published by
    the Free Software Foundation; either version 2 of the License, or
    (at your option) any later version.

    As a special exception, you have permission to link Ipe with the
    CGAL library and distribute executables, as long as you follow the
    requirements of the Gnu General Public License in regard to all of
    the software in the executable aside from CGAL.

    Ipe is distributed in the hope that it will be useful, but WITHOUT
    ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
    or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public
    License for more details.

    You should have received a copy of the GNU General Public License
    along with Ipe; if not, you can find it at
    "http://www.gnu.org/copyleft/gpl.html", or write to the Free
    Software Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.

*/

#ifndef IPEGEO_H
#define IPEGEO_H

#include "ipebase.h"

#include <cmath>

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

/*! \var typedef double IpeScalar
 * \ingroup geo
 * Type of coordinates in IpeVectors.
 */
typedef double IpeScalar;

/*! \ingroup geo
  Maximum of two values.
*/
template<class T>
inline T IpeMax(const T &lhs, const T &rhs)
{
  return (lhs > rhs) ? lhs : rhs;
}

/*! \ingroup geo
  Minimum of two values.
*/
template<class T>
inline T IpeMin(const T &lhs, const T &rhs)
{
  return (lhs < rhs) ? lhs : rhs;
}

/*! \ingroup geo
  Absolute value.
*/
inline double IpeAbs(double val)
{
  return (val > 0) ? val : -val;
}


/*! \var double IpePi
 * \ingroup geo
 * The constant pi.
 */
// const double IpePi = 3.1415926535897932385;
#define IpePi 3.1415926535897932385
/*! \var double IpeTwoPi
 * \ingroup geo
 * The constant 2 * pi.
 */
// const double IpeTwoPi = 6.2831853071795862;
#define IpeTwoPi 6.2831853071795862
/*! \var double IpeHalfPi
 * \ingroup geo
 * The constant pi / 2.
 */
// const double IpeHalfPi = 1.5707963267948966;
#define IpeHalfPi 1.5707963267948966

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

class IpeAngle {
public:
  //! Construct uninitialized angle.
  inline explicit IpeAngle() { /* nothing */ }
  //! Construct an angle (in radians).
  inline IpeAngle(double alpha) : iAlpha(alpha) { }
  //! Construct an angle in degrees.
  inline static IpeAngle Degrees(double alpha) {
    return IpeAngle(alpha * IpePi / 180.0); }
  //! Return value (in radians).
  inline operator double() const { return iAlpha; }
  double Degrees() const;
  IpeAngle Normalize(double lowlimit);
  bool LiesBetween(IpeAngle small, IpeAngle large) const;
private:
  double iAlpha;
};

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

class IpeVector {
public:
  //! Uninitialized vector.
  IpeVector() { /* no initialization */ }
  explicit IpeVector(IpeAngle alpha);
  //! Construct a vector.
  explicit IpeVector(IpeScalar x, IpeScalar y) : iX(x), iY(y) { }
  //! Return square of Euclidean length
  inline double SqLen() const;
  double Len() const;
  IpeAngle Angle() const;
  IpeVector Normalized() const;
  IpeVector Orthogonal() const;
  double Factorize(IpeVector &unit) const;
  bool snap(const IpeVector &mouse, IpeVector &pos, double &bound) const;

  inline bool operator==(const IpeVector &rhs) const;
  inline bool operator!=(const IpeVector &rhs) const;
  inline void operator+=(const IpeVector &rhs);
  inline void operator-=(const IpeVector &rhs);
  inline void operator*=(double rhs);
  inline IpeVector operator+(const IpeVector &rhs) const;
  inline IpeVector operator-(const IpeVector &rhs) const;
  inline IpeVector operator*(double rhs) const;

  static IpeVector Zero;

public:
  //!{
  //! Vector coordinates are public.
  IpeScalar iX;
  IpeScalar iY;
  //!}
};

IpeStream &operator<<(IpeStream &stream, const IpeVector &rhs);

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

class IpeRect {
public:
  //! Create empty rectangle.
  explicit IpeRect() : iMin(1,0), iMax(-1,0) { }
  //! Create rectangle containing just the point \a c.
  explicit IpeRect(const IpeVector &c) : iMin(c), iMax(c) { }
  explicit IpeRect(const IpeVector &c1, const IpeVector &c2);

  //! True if rectangle is empty.
  int IsEmpty() const { return iMin.iX > iMax.iX; }
  //! Return top right corner.
  inline IpeVector Max() const { return iMax; }
  //! Return bottom left corner.
  inline IpeVector Min() const { return iMin; }
  //! Return top left corner.
  inline IpeVector TopLeft() const { return IpeVector(iMin.iX, iMax.iY); }
  //! Return bottom right corner.
  inline IpeVector BottomRight() const { return IpeVector(iMax.iX, iMin.iY); }
  //! Return width.
  IpeScalar Width() const { return iMax.iX - iMin.iX; }
  //! Return height.
  IpeScalar Height() const { return iMax.iY - iMin.iY; }
  void AddPoint(const IpeVector &rhs);
  void AddRect(const IpeRect &rhs);
  bool Contains(const IpeVector &rhs) const;
  bool Contains(const IpeRect &rhs) const;
  bool CertainClearance(const IpeVector &v, double bound) const;
  bool Intersects(const IpeRect &rhs) const;
private:
  IpeVector iMin;   //!< Lower-left corner.
  IpeVector iMax;   //!< Top-right corner.
};

IPE_EXPORT IpeStream &operator<<(IpeStream &stream, const IpeRect &rhs);

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

class IpeLine {
public:
  //! Create default line (x-axis).
  explicit IpeLine() : iP(0.0, 0.0), iDir(1.0, 0.0) { }
  explicit IpeLine(const IpeVector &p, const IpeVector &dir);
  static IpeLine Through(const IpeVector &p, const IpeVector &q);
  double Side(const IpeVector &p) const;
  inline IpeVector Normal() const;
  double Distance(const IpeVector &v) const;
  bool Intersects(const IpeLine &line, IpeVector &pt);
  IpeVector Project(const IpeVector &v) const;
  inline IpeVector Dir() const;

public:
  //! Point on the line.
  IpeVector iP;
private:
  IpeVector iDir; // unit vector
};

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

class IpeSegment {
public:
  //! Create uninitialized segment
  IpeSegment() { /* nothing */ }
  explicit IpeSegment(const IpeVector &p, const IpeVector &q)
    : iP(p), iQ(q) { }
  inline IpeLine Line() const;
  double Distance(const IpeVector &v, double bound) const;
  double Distance(const IpeVector &v) const;
  bool Project(const IpeVector &v, IpeVector &projection) const;
  bool Intersects(const IpeSegment &seg, IpeVector &pt) const;
  bool Intersects(const IpeLine &l, IpeVector &pt) const;
  bool snap(const IpeVector &mouse, IpeVector &pos, double &bound) const;
public:
  //! First endpoint.
  IpeVector iP;
  //! Second endpoint.
  IpeVector iQ;
};

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

class IpeBezier {
public:
  //! Default constructor, uninitialized curve.
  inline IpeBezier() { /* nothing */ }
  inline IpeBezier(const IpeVector &p0, const IpeVector &p1,
		   const IpeVector &p2, const IpeVector &p3);
  IpeVector Point(double t) const;
  double Distance(const IpeVector &v, double bound);
  bool Straight(double precision) const;
  void Subdivide(IpeBezier &l, IpeBezier &r) const;
  void Approximate(double precision, std::vector<IpeVector> &result) const;
  IpeRect BBox() const;
  static IpeBezier QuadBezier(const IpeVector &p0, const IpeVector &p1,
			      const IpeVector &p2);
  static void Spline(int n,  const IpeVector *v,
		     std::vector<IpeBezier> &result);
  static void ClosedSpline(int n,  const IpeVector *v,
			   std::vector<IpeBezier> &result);
  bool Intersects(const IpeLine &l, IpeVector &pt) const;
  bool Intersects(const IpeSegment &l, std::vector<IpeVector> &result) const;
  bool Intersects(const IpeBezier &b, std::vector<IpeVector> &result) const;
public:
  IpeVector iV[4];
};

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

class IpeLinear {
public:
  IpeLinear();
  explicit IpeLinear(IpeAngle angle);
  inline explicit IpeLinear(double m11, double m21, double m12, double m22);
  explicit IpeLinear(IpeString str);
  IpeLinear Inverse() const;
  inline bool IsIdentity() const;
  inline IpeVector operator*(const IpeVector &rhs) const;
  inline bool operator==(const IpeLinear &rhs) const;
public:
  double iA[4];
};

IpeStream &operator<<(IpeStream &stream, const IpeLinear &rhs);

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

class IpeMatrix {
public:
  IpeMatrix();
  inline IpeMatrix(const IpeLinear &linear);
  inline explicit IpeMatrix(const IpeLinear &linear, const IpeVector &t);
  inline explicit IpeMatrix(double m11, double m21, double m12, double m22,
			    double t1, double t2);
  inline explicit IpeMatrix(const IpeVector &v);
  explicit IpeMatrix(IpeString str);
  IpeMatrix Inverse() const;
  inline IpeVector operator*(const IpeVector &rhs) const;
  inline IpeBezier operator*(const IpeBezier &rhs) const;
  inline IpeVector Translation() const;
  inline IpeLinear Linear() const;
  inline bool IsIdentity() const;
  inline bool operator==(const IpeMatrix &rhs) const;
public:
  double iA[6];
};

IPE_EXPORT IpeStream &operator<<(IpeStream &stream, const IpeMatrix &rhs);

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

class IpeArc {
public:
  //! Construct unit circle.
  inline IpeArc() : iAlpha(0.0), iBeta(0.0) { /* nothing */ }
  inline IpeArc(const IpeMatrix &m, IpeAngle alpha, IpeAngle beta);
  inline IpeArc(const IpeMatrix &m);
  IpeArc(const IpeMatrix &m0, const IpeVector &begp, const IpeVector &endp);
  double Distance(const IpeVector &v, double bound);
  double Distance(const IpeVector &v, double bound,
		  IpeVector &pos, IpeAngle &angle);
  IpeRect BBox() const;
  bool Intersects(const IpeLine &l, IpeVector &pt) const;
  bool Intersects(const IpeSegment &s, std::vector<IpeVector> &result) const;
  bool Intersects(const IpeArc &a, std::vector<IpeVector> &result) const;
  bool Intersects(const IpeBezier &b, std::vector<IpeVector> &result) const;

private:
  void Subdivide(IpeArc &l, IpeArc &r) const;
  bool Straight(const double precision) const;
  void GetCPs(IpeVector &start, IpeVector &end) const;
  void AsSegment(IpeSegment &seg) const;

public:
  IpeMatrix iM;
  IpeAngle iAlpha;
  IpeAngle iBeta;
};

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

//! Return square of vector's length.
inline double IpeVector::SqLen() const
{
  return (iX * iX + iY * iY);
}

//! Equality.
inline bool IpeVector::operator==(const IpeVector &rhs) const
{
  return iX == rhs.iX && iY == rhs.iY;
}

//! Inequality.
inline bool IpeVector::operator!=(const IpeVector &rhs) const
{
  return iX != rhs.iX || iY != rhs.iY;
}

//! Vector-addition.
inline void IpeVector::operator+=(const IpeVector &rhs)
{
  iX += rhs.iX; iY += rhs.iY;
}

//! Vector-subtraction.
inline void IpeVector::operator-=(const IpeVector &rhs)
{
  iX -= rhs.iX; iY -= rhs.iY;
}

//! Multiply vector by scalar.
inline void IpeVector::operator*=(double rhs)
{
  iX *= rhs; iY *= rhs;
}

//! Vector-addition.
inline IpeVector IpeVector::operator+(const IpeVector &rhs) const
{
  IpeVector result = *this; result += rhs; return result;
}

//! Vector-subtraction.
inline IpeVector IpeVector::operator-(const IpeVector &rhs) const
{
  IpeVector result = *this; result -= rhs; return result;
}

//! Vector * scalar.
inline IpeVector IpeVector::operator*(double rhs) const
{
  IpeVector result = *this; result *= rhs; return result;
}

//! Scalar * vector. \relates IpeVector
inline IpeVector operator*(double lhs, const IpeVector &rhs)
{
  return IpeVector(lhs * rhs.iX, lhs * rhs.iY);
}

//! Dotproduct of two vectors. \relates IpeVector
inline double Dot(const IpeVector &lhs, const IpeVector &rhs)
{
  return lhs.iX * rhs.iX + lhs.iY * rhs.iY;
}

//! Return a normal vector pointing to the left of the directed line.
inline IpeVector IpeLine::Normal() const
{
  return IpeVector(-iDir.iY, iDir.iX);
}

//! Return direction of line.
inline IpeVector IpeLine::Dir() const
{
  return iDir;
}

//! Return directed line supporting the segment.
inline IpeLine IpeSegment::Line() const
{
  return IpeLine(iP, (iQ - iP).Normalized());
}

//! Unary minus for IpeVector.
inline IpeVector operator-(const IpeVector &rhs)
{
  return -1 * rhs;
}

//! Constructor with four control points.
inline IpeBezier::IpeBezier(const IpeVector &p0, const IpeVector &p1,
			    const IpeVector &p2, const IpeVector &p3)
{
  iV[0] = p0; iV[1] = p1; iV[2] = p2; iV[3] = p3;
}

//! Transform Bezier spline.
inline IpeBezier IpeMatrix::operator*(const IpeBezier &rhs) const
{
  return IpeBezier(*this * rhs.iV[0], *this * rhs.iV[1],
		   *this * rhs.iV[2], *this * rhs.iV[3]);
};

//! Construct with given parameters.
inline IpeArc::IpeArc(const IpeMatrix &m, IpeAngle alpha, IpeAngle beta)
  : iM(m), iAlpha(alpha), iBeta(beta)
{
  // nothing
}

//! Construct an ellipse
inline IpeArc::IpeArc(const IpeMatrix &m)
  : iM(m), iAlpha(0.0), iBeta(0.0)
{
  // nothing
}

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

//! Create identity matrix.
inline IpeLinear::IpeLinear()
{
  iA[0] = iA[3] = 1.0;
  iA[1] = iA[2] = 0.0;
}

//! Create linear matrix with given coefficients.
inline IpeLinear::IpeLinear(double m11, double m21, double m12, double m22)
{
  iA[0] = m11; iA[1] = m21; iA[2] = m12; iA[3] = m22;
}

//! Linear matrix times vector.
inline IpeVector IpeLinear::operator*(const IpeVector &rhs) const
{
  return IpeVector(iA[0] * rhs.iX + iA[2] * rhs.iY,
		   iA[1] * rhs.iX + iA[3] * rhs.iY);
};

//! Is this the identity matrix?
inline bool IpeLinear::IsIdentity() const
{
  return (iA[0] == 1.0 && iA[1] == 0.0 &&
	  iA[2] == 0.0 && iA[3] == 1.0);
}

//! Linear matrix multiplication.
inline IpeLinear operator*(const IpeLinear &lhs, const IpeLinear &rhs)
{
  IpeLinear m;
  m.iA[0] = lhs.iA[0] * rhs.iA[0] + lhs.iA[2] * rhs.iA[1];
  m.iA[1] = lhs.iA[1] * rhs.iA[0] + lhs.iA[3] * rhs.iA[1];
  m.iA[2] = lhs.iA[0] * rhs.iA[2] + lhs.iA[2] * rhs.iA[3];
  m.iA[3] = lhs.iA[1] * rhs.iA[2] + lhs.iA[3] * rhs.iA[3];
  return m;
}

//! Check for equality of two linear matrices.
inline bool IpeLinear::operator==(const IpeLinear &rhs) const
{
  return (iA[0] == rhs.iA[0] && iA[1] == rhs.iA[1] &&
	  iA[2] == rhs.iA[2] && iA[3] == rhs.iA[3]);
}

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

//! Create matrix with given coefficients.
inline IpeMatrix::IpeMatrix(double m11, double m21, double m12, double m22,
			    double t1, double t2)
{
  iA[0] = m11; iA[1] = m21; iA[2] = m12; iA[3] = m22;
  iA[4] = t1; iA[5] = t2;
}

//! Create linear matrix.
inline IpeMatrix::IpeMatrix(const IpeLinear &linear)
{
  iA[0] = linear.iA[0]; iA[1] = linear.iA[1];
  iA[2] = linear.iA[2]; iA[3] = linear.iA[3];
  iA[4] = iA[5] = 0.0;
}

inline IpeMatrix::IpeMatrix(const IpeLinear &linear, const IpeVector &t)
{
  iA[0] = linear.iA[0]; iA[1] = linear.iA[1];
  iA[2] = linear.iA[2]; iA[3] = linear.iA[3];
  iA[4] = t.iX; iA[5] = t.iY;
}

//! Matrix times vector.
inline IpeVector IpeMatrix::operator*(const IpeVector &rhs) const
{
  return IpeVector(iA[0] * rhs.iX + iA[2] * rhs.iY + iA[4],
		   iA[1] * rhs.iX + iA[3] * rhs.iY + iA[5]);
};

//! Is this the identity matrix?
inline bool IpeMatrix::IsIdentity() const
{
  return (iA[0] == 1.0 && iA[1] == 0.0 &&
	  iA[2] == 0.0 && iA[3] == 1.0 &&
	  iA[4] == 0.0 && iA[5] == 0.0);
}

//! Create identity matrix.
inline IpeMatrix::IpeMatrix()
{
  iA[0] = iA[3] = 1.0;
  iA[1] = iA[2] = iA[4] = iA[5] = 0.0;
}

//! Matrix multiplication.
inline IpeMatrix operator*(const IpeMatrix &lhs, const IpeMatrix &rhs)
{
  IpeMatrix m;
  m.iA[0] = lhs.iA[0] * rhs.iA[0] + lhs.iA[2] * rhs.iA[1];
  m.iA[1] = lhs.iA[1] * rhs.iA[0] + lhs.iA[3] * rhs.iA[1];
  m.iA[2] = lhs.iA[0] * rhs.iA[2] + lhs.iA[2] * rhs.iA[3];
  m.iA[3] = lhs.iA[1] * rhs.iA[2] + lhs.iA[3] * rhs.iA[3];
  m.iA[4] = lhs.iA[0] * rhs.iA[4] + lhs.iA[2] * rhs.iA[5] + lhs.iA[4];
  m.iA[5] = lhs.iA[1] * rhs.iA[4] + lhs.iA[3] * rhs.iA[5] + lhs.iA[5];
  return m;
}

//! Create translation matrix.
inline IpeMatrix::IpeMatrix(const IpeVector &v)
{
  iA[0] = iA[3] = 1.0;
  iA[1] = iA[2] = 0.0;
  iA[4] = v.iX;
  iA[5] = v.iY;
}

//! Return translation component.
inline IpeVector IpeMatrix::Translation() const
{
  return IpeVector(iA[4], iA[5]);
}

//! Check for equality of two matrices.
inline bool IpeMatrix::operator==(const IpeMatrix &rhs) const
{
  return (iA[0] == rhs.iA[0] && iA[1] == rhs.iA[1] && iA[2] == rhs.iA[2] &&
	  iA[3] == rhs.iA[3] && iA[4] == rhs.iA[4] && iA[5] == rhs.iA[5]);
}

//! Return linear transformation component of this affine transformation.
inline IpeLinear IpeMatrix::Linear() const
{
  return IpeLinear(iA[0], iA[1], iA[2], iA[3]);
}

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

//! Transform arc.
inline IpeArc operator*(const IpeMatrix &lhs, const IpeArc &rhs)
{
  return IpeArc(lhs * rhs.iM, rhs.iAlpha, rhs.iBeta);
}

// --------------------------------------------------------------------
#endif
