/****************************************************************************************************

		Delauney.h
		Copyright: (c) 2001 Eovia Corp. All rights reserved.

		Author:	Charles
		Date:	4/14/2001

****************************************************************************************************/

#ifndef __Delauney__
#define __Delauney__

#if CP_PRAGMA_ONCE
#pragma once
#endif

#include "Vector2.h"
#include "MCArray.h"
#include "MCPtrArray.h"

template <class T> class TMCPtrArray;

namespace Delauney
{

// ***************************************************************************
//					class VertexIndex
//
//
class VertexIndex : public TMCObject
{
public:
	// no constructor taking a int32 enforce no implicit conversion
	inline VertexIndex() : fValue(0) {}

	inline VertexIndex(const VertexIndex& index)
	{
		fValue = index.fValue;
	}
	inline VertexIndex& operator=(const VertexIndex& index)
	{
		fValue = index.fValue;
		return *this;
	}
	inline void operator++()
	{
		fValue++;
	}
	inline boolean operator<(int32 count)
	{
		return fValue<count;
	}

	inline boolean operator==(const VertexIndex& index) const
	{
		return fValue == index.fValue;
	}

	inline boolean operator!=(const VertexIndex& index) const
	{
		return fValue != index.fValue;
	}

	inline int32 GetValue() const
	{
		MCAssert(fValue>=0);
		return fValue; 
	}
	inline void SetValue(int32 value)
	{
		MCAssert(fValue>=0);
		fValue=value;
	}
private:
	int32 fValue;
};

// *************************************************************************
//							struct Vertex
//
// defines a vertex on a triangle for 2D triangulation
//
class Vertex : public TVector2
{
public:
	enum eLocation
	{
		kInvalid=0,
		kInside=1,
		kOnEdge=2
	};

	Vertex(real x,real y,eLocation location);

	void SetInvalid() const { fLocation=kInvalid; }
	
	boolean IsInvalid() const   { return fLocation == kInvalid; }
	boolean IsOnEdge() const    { return fLocation == kOnEdge; }
//	boolean IsDuplicate() const { return fLocation == kDuplicate; }
//	boolean IsOnSameEdge(const Vertex& vertex) const;

	mutable eLocation	fLocation;

//	void			SetIsDuplicateFrom(VertexIndex vertexIndex) const { fDuplicateFrom=vertexIndex; fLocation=kDuplicate; }

//	VertexIndex		DuplicateFrom() const { return fDuplicateFrom; }
private:
//	mutable VertexIndex		fDuplicateFrom; // vertex this vertex is a duplicate from
};

// ************************************************************************
//						class VertexList
//
//
class VertexList : public TMCObject
{
public:
	VertexList(const TMCArray<Vertex>& vertexArray);

	const Vertex& operator[](const VertexIndex& vertexIndex) const { return fVertices[vertexIndex.GetValue()]; }

	Vertex& operator[](const int32 index){ return fVertices[index]; }

	// returns the number of vertices in the list
	int32 GetCount() const { return fVertices.GetElemCount(); }

private:
	TMCArray<Vertex>	fVertices;
};


// *************************************************************************
//							struct Triangle
//
// defines a triangle on a triangle for 2D triangulation
//
class Triangle : public TMCObject
{
public:
	Triangle(VertexIndex vertex1,VertexIndex vertex2,VertexIndex vertex3);

	// returns true if the point is in the circumcircle of the triangle
	boolean InCircle(const TVector2& position,const VertexList& vertices) const;

	// returns true if the edge (vertex1,vertex2) intersect the triangle
	boolean Intersect(VertexIndex vertex1,VertexIndex vertex2,const VertexList& vertices) const;

	// returns true if the edge (vertex1,vertex2) is an edge of the triangle
	boolean ContainsEdge(VertexIndex vertex1,VertexIndex vertex2) const;

	VertexIndex	vertexIndex[3];
};

// ***************************************************************************
//					class Polygon
//
//
class Polygon : public TMCArray<VertexIndex>
{
public:
	// returns the number of vertex in the polygon
	int32 GetVertexCount() const { return (int32)GetElemCount(); }

	VertexIndex Vertex(int32 i) const { return (*this)[i]; }

	// try to merge one triangle with this polygon
	boolean Merge(const Triangle& triangle);

	// split the polygon by the segment [vertex1,vertex2] ( vertex1 and vertex2 must be vertices of the polygon )
	boolean Split(VertexIndex vertex1,VertexIndex vertex2,Polygon& polygon1,Polygon& polygon2) const;

protected:
	// return the index of the vertex of the triangle, non contained in commonPoints
	VertexIndex NonCommonVertex(const Triangle& triangle,
								const TMCArray<int32>& commonPoints) const;
};

class Segment : public TMCObject
{
public:
	Segment (VertexIndex vertex1,VertexIndex vertex2)
	{
		fVertex1 = vertex1;
		fVertex2 = vertex2;
	}
	boolean IsInside(const TMCArray<VertexIndex>& polygon,const VertexList& vertices);

private:
	VertexIndex fVertex1;
	VertexIndex fVertex2;
};


// ************************************************************************
//						class Triangulator
//
// implement the classic constraint Delauney Triangulation for a set of
// points contained in a triangle ( the triangle vertices are part of the
// final triangulation
//
// all the vertices should be either inside or on the edges of the triangle
//
class Triangulator : public TMCObject
{
public:
	// vertices is a set of points for which we want the triangulation
	// the three first points defines the enclosing triangle
	Triangulator(const TMCArray<Vertex>& vertices);

	~Triangulator();

	// Build Initial Triangulation
	void Triangulate();

	// add a constraint to the triangulation ( should be called only after Triangulate as been called)
	void AddConstraint(VertexIndex vertexIndex1,VertexIndex vertexIndex2);

	// returns a list of triangles corresponding to the triangulation
	const TMCPtrArray<const Triangle>* GetTriangulation();

	inline const Vertex& GetVertex(VertexIndex vertexIndex)
	{
		return fVertices[vertexIndex];
	}

	// returns true if there was a constraint set between the two points
	boolean CheckContraint(VertexIndex vertexIndex1,VertexIndex vertexIndex2);

protected:
	// triangulate the polygon around the vertex, vertexIndex
	void TriangulateButterfly(const Polygon& polygon,VertexIndex vertexIndex);

	// Merge the triangles into a polygon, returns false if unable to merge
	boolean MergeTriangles(Polygon& mergedPolygon,TMCPtrArray<Triangle> trianglesToMerge);

	// Triangulate a polygon and add the result to the current triangulation
	boolean Triangulate(const Polygon& polygon);

	// Remove duplicated points
//	void PruneDuplicatedPoints();

	// scale the vertices pos to place them in a 0,1 * 0,1 square
	void ScaleData();
private:
	VertexList				fVertices; // vertices of the triangulation
	TMCPtrArray<Triangle>	fTriangles; // current triangulation

	TMCPtrArray< TMCArray<int32> >	fConstraints; // for each vertex, the list of vertex it is linked to by a constraint
};

// performs a basic test of triangulation
// boolean Test();

} // end of namespace Delauney


#endif
