package 
{

	//Credit to Paul Bourke (pbourke@swin.edu.au) for the original Fortran 77 Program :))
	//Converted to a standalone C# 2.0 library by Morten Nielsen (www.iter.dk)
	//Check out: http://astronomy.swin.edu.au/~pbourke/terrain/triangulate/
	//You can use this code however you like providing the above credits remain in tact

	/**
	 * @author nicoptere
	 * http://en.nicoptere.net/
	 */

	public class Delaunay	
	{
		
		/**
		 * performs a Delaunay triangulation on a  set of points 
		 * @param Vertex the original set of points
		 * @return an array of triangl objects
		 */
		public static function Triangulate( Vertex:Array ):Array
		{

			//those will be used quite everywhere so I am storing them here not to declare them x times
			var i:int;
			var j:int;
			var nv:int = Vertex.length;

			if (nv < 3) return [];

			var trimax:int = 4 * nv;

			
			
			// Find the maximum and minimum vertex bounds.
			// This is to allow calculation of the bounding supertriangle

			var xmin:Number = Vertex[0].x;
			var ymin:Number = Vertex[0].y;
			var xmax:Number = xmin;
			var ymax:Number = ymin;
			
			
			for ( i = 1; i < nv; i++)
			{
				
				( Vertex[i] as Point ).id = i;
				
				if (Vertex[i].x < xmin) xmin = Vertex[i].x;

				if (Vertex[i].x > xmax) xmax = Vertex[i].x;

				if (Vertex[i].y < ymin) ymin = Vertex[i].y;

				if (Vertex[i].y > ymax) ymax = Vertex[i].y;

			}
			


			var dx:Number = xmax - xmin;
			var dy:Number = ymax - ymin;
			var dmax:Number = (dx > dy) ? dx : dy;

			var xmid:Number = (xmax + xmin) * 0.5;
			var ymid:Number = (ymax + ymin) * 0.5;



			

			// Set up the supertriangle
			// This is a triangle which encompasses all the sample points.
			// The supertriangle coordinates are added to the end of the
			// vertex list. The supertriangle is the first triangle in
			// the triangle list.

			Vertex.push(new Point( (xmid - 2 * dmax), (ymid - dmax), nv+1 ) );
			Vertex.push(new Point( xmid, (ymid + 2 * dmax), nv+2 ) );
			Vertex.push(new Point((xmid + 2 * dmax), (ymid - dmax), nv+3));

			var triangles:Array = new Array();//array typé de triangles

			triangles.push( new Triangle( Vertex[ nv ], Vertex[ nv + 1 ], Vertex[ nv + 2 ] ) ); //SuperTriangle placed at index 0

			

			// Include each point one at a time into the existing mesh
			for ( i = 0; i < nv; i++)
			{
				
				var Edges:Array = new Array(); //[trimax * 3];

				// Set up the edge buffer.
				// If the point (Vertex(i).x,Vertex(i).y) lies inside the circumcircle then the
				// three edges of that triangle are added to the edge buffer and the triangle is removed from list.
				for ( j = 0; j < triangles.length; j++ )
				{
					
					if ( InCircle( Vertex[ i ], triangles[ j ].p1, triangles[ j ].p2, triangles[ j ].p3 ) )
					{

						Edges.push(new Edge(triangles[j].p1, triangles[j].p2) );

						Edges.push(new Edge(triangles[j].p2, triangles[j].p3) );

						Edges.push(new Edge(triangles[j].p3, triangles[j].p1) );

						triangles.splice( j,1 );

						j--;

					}

				}

				if ( i >= nv) continue; //In case we the last duplicate point we removed was the last in the array



				// Remove duplicate edges
				// Note: if all triangles are specified anticlockwise then all
				// interior edges are opposite pointing in direction.

				for ( j = Edges.length - 2; j >= 0; j--)
				{

					for (var k:int = Edges.length - 1; k >= j + 1; k--)
					{

						if ( Edges[ j ].Equals( Edges[ k ] ) )
						{

							Edges.splice( k, 1 );
							Edges.splice( j, 1 );
							k--;
							continue;

						}

					}

				}

				// Form new triangles for the current point
				// Skipping over any tagged edges.
				// All edges are arranged in clockwise order.
				for ( j = 0; j < Edges.length; j++)
				{

					if (triangles.length >= trimax )
					{
						//	throw new ApplicationException("Exceeded maximum edges");
						trace("Exceeded maximum edges");
						
					}
					triangles.push( new Triangle( Edges[ j ].p1, Edges[ j ].p2, Vertex[ i ] ));

				}

				Edges = [];
				
			}
			
			// Remove triangles with supertriangle vertices
			// These are triangles which have a vertex number greater than nv

			for ( i = triangles.length - 1; i >= 0; i--)
			{

				if ( triangles[ i ].p1.id >= nv || triangles[ i ].p2.id >= nv || triangles[ i ].p3.id >= nv)
				{

					triangles.splice(i, 1);
				}
				
			}

			//Remove SuperTriangle vertices
			Vertex.splice(Vertex.length - 1, 1);
			Vertex.splice(Vertex.length - 1, 1);
			Vertex.splice(Vertex.length - 1, 1);
			
			triangles.concat();
			return triangles;

		}



		/// <summary>
		/// Returns true if the point (p) lies inside the circumcircle made up by points (p1,p2,p3)
		/// </summary>
		/// <remarks>
		/// NOTE: A point on the edge is inside the circumcircle
		/// </remarks>
		/// <param name="p">Point to check</param>
		/// <param name="p1">First point on circle</param>
		/// <param name="p2">Second point on circle</param>
		/// <param name="p3">Third point on circle</param>
		/// <returns>true if p is inside circle</returns>

		private static function InCircle( p:Point, p1:Point, p2:Point, p3:Point ):Boolean

		{

			//Return TRUE if the point (xp,yp) lies inside the circumcircle
			//made up by points (x1,y1) (x2,y2) (x3,y3)
			//NOTE: A point on the edge is inside the circumcircle


			var Epsilon:Number = Number.MIN_VALUE;
			if ( Math.abs( p1.y - p2.y ) < Epsilon && Math.abs( p2.y - p3.y) < Epsilon)
			{

				//INCIRCUM - F - Points are coincident !!
				return false;

			}



			var m1:Number;
			var m2:Number;

			var mx1:Number;
			var mx2:Number;

			var my1:Number;
			var my2:Number;

			var xc:Number;
			var yc:Number;

						

			if ( Math.abs(p2.y - p1.y) < Epsilon)
			{

				m2 = -(p3.x - p2.x) / (p3.y - p2.y);

				mx2 = (p2.x + p3.x) * 0.5;

				my2 = (p2.y + p3.y) * 0.5;

				//Calculate CircumCircle center (xc,yc)
				xc = (p2.x + p1.x) * 0.5;

				yc = m2 * (xc - mx2) + my2;

			}
			else if ( Math.abs(p3.y - p2.y) < Epsilon)
			{

				m1 = -(p2.x - p1.x) / (p2.y - p1.y);

				mx1 = (p1.x + p2.x) * 0.5;

				my1 = (p1.y + p2.y) * 0.5;

				//Calculate CircumCircle center (xc,yc)

				xc = (p3.x + p2.x) * 0.5;

				yc = m1 * (xc - mx1) + my1;

			}
			else
			{

				m1 = -(p2.x - p1.x) / (p2.y - p1.y);

				m2 = -(p3.x - p2.x) / (p3.y - p2.y);

				mx1 = (p1.x + p2.x) * 0.5;

				mx2 = (p2.x + p3.x) * 0.5;

				my1 = (p1.y + p2.y) * 0.5;

				my2 = (p2.y + p3.y) * 0.5;

				//Calculate CircumCircle center (xc,yc)
				xc = (m1 * mx1 - m2 * mx2 + my2 - my1) / (m1 - m2);

				yc = m1 * (xc - mx1) + my1;

			}



			var dx:Number = p2.x - xc;

			var dy:Number = p2.y - yc;

			var rsqr:Number = dx * dx + dy * dy;

			//double r = Math.Sqrt(rsqr); //Circumcircle radius

			dx = p.x - xc;

			dy = p.y - yc;

			var drsqr:Number = dx * dx + dy * dy;



			return ( drsqr <= rsqr );

		}

	}

}