#ifndef K3DSDK_GEOMETRY_H
#define K3DSDK_GEOMETRY_H

// K-3D
// Copyright (c) 1995-2004, Timothy M. Shead
//
// Contact: tshead@k-3d.com
//
// This library 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.
//
// This library 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 this library; if not, write to the Free Software
// Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA

/** \file
		\brief 2D geometry routines
		\author Tim Shead (tshead@k-3d.com)
*/

#include "vectors.h"

namespace k3d
{

/////////////////////////////////////////////////////////////////////////////
// rectangle

/// A two-dimensional rectangle with left, right, top, bottom
class rectangle
{
public:
	/// Stores the rectangle's left edge
	double left;
	/// Stores the rectangle's right edge
	double right;
	/// Stores the rectangle's top edge
	double top;
	/// Stores the rectangle's bottom edge
	double bottom;

	// Constructors
	rectangle();
	rectangle(const double Left, const double Right, const double Top, const double Bottom);
	/// Copy Constructor
	rectangle(const rectangle& v);
	/// Assignment of an rectangle
	rectangle& operator = ( const rectangle& v );
	/// Returns the left coordinate
	double Left() const;
	/// Returns the right coordinate
	double Right() const;
	/// Returns the top coordinate
	double Top() const;
	/// returns the bottom coordinate
	double Bottom() const;
	/// Returns the rectangle width
	double Width() const;
	/// Returns the rectangle height
	double Height() const;
	/// Applies horizontal and vertical offsets to the rectangle coordinates
	void Offset(const double Horizontal, const double Vertical);
	/// Returns a larger rectangle
	void Grow(const double Thickness);
	/// Returns a larger rectangle
	void Grow(const double Horizontal, const double Vertical);
	/// Returns a smaller rectangle
	void Shrink(const double Thickness);
	/// Returns a smaller rectangle
	void Shrink(const double Horizontal, const double Vertical);
	/// Ensures that the rectangle coordinates are ordered properly, Left < Right, Top < Bottom
	void Normalize();
	/// Returns the center of the rectangle
	vector2 Center() const;
	/// Tests a point to see if it is contained within the rectangle
	bool Contains(const vector2& Point) const;
};

/// Returns the source rectangle, proportionately constrained to fit within the destination
rectangle ConstrainProportions(const rectangle& Source, const rectangle& Destination);

/// Output inserter
std::ostream& operator << (std::ostream& Stream, const rectangle& Arg);
/// Input extractor
std::istream& operator >> (std::istream& Stream, rectangle& Arg);

/// Encapsulates a 3D plane surface
class plane
{
friend std::ostream& operator << (std::ostream& Stream, const plane& Arg);
friend std::istream& operator >> (std::istream& Stream, plane& Arg);
public:
	/// Constructs a plane from its normal and distance from the origin
	plane(const vector3& Normal, const double Distance);
	/// Constructs a plane from its normal and one point located within the plane
	plane(const vector3& Normal, const vector3& ContainedPoint);
	/// Constructs a plane from three points contained within the plane
	plane(const vector3& ContainedPointA, const vector3& ContainedPointB, const vector3& ContainedPointC);

	/// Returns the plane normal vector
	vector3 Normal() const;
	/// Returns the plane's distance from the origin
	double Distance() const;

	/// Sets the plane normal vector
	void SetNormal(const vector3& Normal);
	/// Sets the plane's distance from the origin
	void SetDistance(double Distance);

protected:
	vector3 m_Normal;
	double m_Distance;
};

/// Output inserter
std::ostream& operator << (std::ostream& Stream, const plane& Arg);
/// Input extractor
std::istream& operator >> (std::istream& Stream, plane& Arg);

/// Enumerates the ways in which two line segments might (or might not) intersect
typedef enum
{
	SDP_NOINTERSECTION,
	SDP_EXTERIORINTERSECTION,
	SDP_INTERIORINTERSECTION,

	SDP_EXTERIORCOLINEARPOINT,
	SDP_INTERIORCOLINEARPOINT,

	SDP_INTERIORCOLINEARPOINTS,
	SDP_INTERIOREXTERIORCOLINEARPOINTS,
	SDP_EXTERIORCOLINEARPOINTSNOINTERSECTION,
	SDP_EXTERIORCOLINEARPOINTS,

	SDP_ERROR
} line_segment_intersection_type;

/// Determines whether two line segments intersect, and if so, how
line_segment_intersection_type LineSegmentIntersection(const vector2& A1, const vector2& A2, const vector2& B1, const vector2& B2);
/// Calculates the intersection of a plane with a line
bool PlaneLineIntersection(const plane& Plane, const vector3 LineOrigin, const vector3 LineDirection, vector3& Result);
/// Calculates the intersection of two lines, specified by two contained points each
bool LineIntersection(const vector2& A1, const vector2& A2, const vector2& B1, const vector2& B2, vector2& Result);

/*
/// Calculates the area of a triangle
double Area(const vector2& Point1, const vector2& Point2, const vector2& Point3);
*/

/// Returns a Bezier / Bernstein basis for the given order, control point number, and parameter value
double BernsteinBasis(const unsigned long Order, const unsigned long ControlPoint, const double Parameter);

/// Computes a Bezier curve value with given order,  control points, and parameter value
template<class Type>
Type Bezier(const std::vector<Type>& ControlPoints, const double Parameter)
{
	// Sanity checks ...
	assert(ControlPoints.size() > 1);

	Type result = 0.0;

	for(unsigned long i = 0; i < ControlPoints.size(); i++)
		result += BernsteinBasis(ControlPoints.size(), i, Parameter) * ControlPoints[i];

	return result;
}

/** Find the point at which two infinite lines intersect. The algorithm generates a plane from one of the lines and finds the intersection point between this plane and the other line.
	\param P1 A point that lies on the first line
	\param T1 Direction vector for the first line
	\param P2 A point that lies on the second line
	\param T2 Direction vector for the second line
	\param Result Returns the intersection between the two lines
	\result Returns true iff the lines intersect, false if they are parallel
	\note Code originally from Aqsis, http://www.aqsis.com
*/
bool intersect_lines(const k3d::vector3& P1, const k3d::vector3& T1, const k3d::vector3& P2, const k3d::vector3& T2, k3d::vector3& Result);

/** Calculates a 3rd-order NURBS curve that creates a circular arc centered at the origin with unit radius
	\param X Defines the X axis of the plane containing the arc
	\param Y Defines the Y axis of the plane containing the arc
	\param StartAngle Start angle of the arc in radians
	\param EndAngle End angle of the arc in radians
	\param Segments The number of NURBS segments in the resulting arc
	\param Knots Output container for the resulting arc knot vector
	\param Weights Output container for the resulting arc control point weights
	\param ControlPoints Output container for the resulting arc control point positions
*/
template<typename knots_t, typename weights_t, typename control_points_t>
void nurbs_arc(const k3d::vector3& X, const k3d::vector3& Y, const double StartAngle, const double EndAngle, const unsigned long Segments, knots_t& Knots, weights_t& Weights, control_points_t& ControlPoints)
{
	const double start_angle = std::min(StartAngle, EndAngle);
	const double end_angle = std::max(StartAngle, EndAngle);
	const double theta = (end_angle - start_angle) / static_cast<double>(Segments);
	const double weight = std::cos(theta * 0.5);
	
	Knots.clear();
	Knots.insert(Knots.end(), 3, 0);
	for(unsigned long i = 1; i != Segments; ++i)
		Knots.insert(Knots.end(), 2, i);
	Knots.insert(Knots.end(), 3, Segments);
	
	Weights.clear();
	Weights.push_back(1.0);
	for(unsigned long i = 0; i != Segments; ++i)
		{
			Weights.push_back(weight);
			Weights.push_back(1);
		}
		
	ControlPoints.clear();
	ControlPoints.push_back(std::cos(start_angle) * X + std::sin(start_angle) * Y);
	for(unsigned long i = 0; i != Segments; ++i)
		{
			const double a0 = start_angle + (theta * (i));
			const double a2 = start_angle + (theta * (i + 1));
			
			const k3d::vector3 p0(std::cos(a0) * X + std::sin(a0) * Y);
			const k3d::vector3 p2(std::cos(a2) * X + std::sin(a2) * Y);
			
			const k3d::vector3 t0(-std::sin(a0) * X + std::cos(a0) * Y);
			const k3d::vector3 t2(-std::sin(a2) * X + std::cos(a2) * Y);

			k3d::vector3 p1;
			k3d::intersect_lines(p0, t0, p2, t2, p1);
				
			ControlPoints.push_back(p1);
			ControlPoints.push_back(p2);
		}
}

} // namespace k3d

#endif // K3DSDK_GEOMETRY_H

