Triangulating a Polygon with the Ear-Clipping Algorithm in JavaScript

The JavaScript program below, when run, draws a complex polygon, converts that polygon to triangles using an “ear-clipping” algorithm, and displays the results. To see it in action, copy the code into an .html file and open that file in a web browser that runs JavaScript.

The program still needs some work. Currently, the triangulation only works with the polygon provided. Even reversing the order of the vertices in the polygon is enough to crash the algorithm.

PolygonTriangulation



<html>
<body>

<div id="divMain" />

<script type="text/javascript">

// main

function main()
{
	var viewSizeInPixels = new Coords
	(
		100, 100
	);

	var displayHelper = new DisplayHelper
	(
		viewSizeInPixels
	);

	// An "H" shape.
	var polygonH = new Polygon
	([
		new Coords(20, 20),
		new Coords(40, 20),
		new Coords(40, 40),
		new Coords(60, 40),
		new Coords(60, 20),
		new Coords(80, 20),
		new Coords(80, 80),
		new Coords(60, 80),
		new Coords(60, 60),
		new Coords(40, 60),
		new Coords(40, 80),
		new Coords(20, 80),
	]);

	// The same polygon, with the order of its vertices reversed.
	var polygonHReversed = polygonH.clone();
	polygonHReversed.vertices.reverse();

	var polygonsToTest = 
	[
		polygonH,
		//polygonHReversed // Doesn't work yet!
	];

	for (var i = 0; i < polygonsToTest.length; i++)
	{
		var polygonToTriangulate = polygonsToTest[i];

		var polygonAsTriangles = GeometryHelper.triangulatePolygon
		(
			polygonToTriangulate
		);
		
		displayHelper.initialize();
		displayHelper.clear();
		displayHelper.drawPolygon(polygonToTriangulate);

		displayHelper.initialize();
		displayHelper.clear();
		displayHelper.drawPolygons(polygonAsTriangles);
	}
}

// extensions

function ArrayExtensions()
{
	// extension class
}
{
	Array.prototype.remove = function(itemToRemove)
	{
		return this.splice(this.indexOf(itemToRemove), 1);
	}

	Array.prototype.reverse = function()
	{
		var length = this.length;
		var lengthHalf = Math.floor(length / 2);
		for (var i = 0; i < lengthHalf; i++)
		{
			var iReversed = length - i - 1;

			var item = this[i];
			var itemToSwapWith = this[iReversed];
			this[i] = itemToSwapWith;
			this[iReversed] = item;
		}

		return this;
	}
}

// classes

function Coords(x, y)
{
	this.x = x;
	this.y = y;
}
{
	Coords.prototype.dotProduct = function(other)
	{
		return (this.x * other.x + this.y * other.y);
	}

	Coords.prototype.overwriteWith = function(other)
	{
		this.x = other.x;
		this.y = other.y;
		return this;
	}

	Coords.prototype.right = function()
	{
		var temp = this.x;
		this.x = 0 - this.y;
		this.y = temp;
		return this;
	}

	Coords.prototype.subtract = function(other)
	{
		this.x -= other.x;
		this.y -= other.y;
		return this;
	}
}

function DisplayHelper(viewSizeInPixels)
{
	this.viewSizeInPixels = viewSizeInPixels;
}
{
	// constants

	DisplayHelper.ColorBack = "White";
	DisplayHelper.ColorFore = "Gray";

	// methods

	DisplayHelper.prototype.clear = function()
	{
		this.graphics.fillStyle = DisplayHelper.ColorBack;
		this.graphics.fillRect
		(
			0, 0, 
			this.viewSizeInPixels.x, 
			this.viewSizeInPixels.y
		);

		this.graphics.strokeStyle = DisplayHelper.ColorFore;
		this.graphics.strokeRect
		(
			0, 0, 
			this.viewSizeInPixels.x, 
			this.viewSizeInPixels.y
		);
	}

	DisplayHelper.prototype.colorRandom = function()
	{
		var hueMax = 360;
		var hue = Math.floor(Math.random() * hueMax);
		var returnValue = "hsl(" + hue + ", 100%, 50%)";
		
		return returnValue;
	}

	DisplayHelper.prototype.drawPolygon = function(polygon)
	{
		this.graphics.fillStyle = this.colorRandom();

		this.graphics.beginPath();

		var vertices = polygon.vertices;
		var vertex0 = vertices[0];

		this.graphics.moveTo(vertex0.x, vertex0.y);

		for (var i = 1; i < vertices.length; i++)
		{
			var vertex = vertices[i];
			this.graphics.lineTo(vertex.x, vertex.y);
		}

		this.graphics.closePath();
		this.graphics.fill();
		this.graphics.stroke();
	}

	DisplayHelper.prototype.drawPolygons = function(polygons)
	{
		for (var i = 0; i < polygons.length; i++)
		{
			var polygon = polygons[i];
			this.drawPolygon(polygon);
		}
	}

	DisplayHelper.prototype.initialize = function()
	{
		var canvas = document.createElement("canvas");
		canvas.width = this.viewSizeInPixels.x;
		canvas.height = this.viewSizeInPixels.y;

		this.graphics = canvas.getContext("2d");
		
		var divMain = document.getElementById("divMain");
		divMain.appendChild(canvas);
	}
}

function GeometryHelper()
{
	// static class
}
{
	GeometryHelper.triangulatePolygon = function(polygonToTriangulate)
	{
		var polygonMinusTriangles = polygonToTriangulate.clone();

		var polygonAsTriangles = [];

		var right = new Coords();
		var displacement = new Coords();

		var vertices = polygonMinusTriangles.vertices;
		var numberOfVertices = vertices.length;

		while (numberOfVertices > 3)
		{
			for (var i = 0; i < numberOfVertices; i++)
			{
				GeometryHelper.triangulatePolygon_ForEachVertex
				(
					i, 
					numberOfVertices, 
					vertices, 
					right, 
					displacement,
					polygonAsTriangles,
					polygonMinusTriangles
				);

				numberOfVertices = vertices.length;

			} // end for (each vertex)

		} // end while (numberOfVertices > 3)

		polygonAsTriangles.push(polygonMinusTriangles);

		return polygonAsTriangles;
	}

	GeometryHelper.triangulatePolygon_ForEachVertex = function
	(
		i, 
		numberOfVertices, 
		vertices, 
		right, 
		displacement, 
		polygonAsTriangles,
		polygonMinusTriangles
	)
	{
		var iPlusOne = i + 1;
		if (iPlusOne >= numberOfVertices)
		{
			iPlusOne -= numberOfVertices;
		}
	
		var iPlusTwo = i + 2;
		if (iPlusTwo >= numberOfVertices)
		{
			iPlusTwo -= numberOfVertices;
		}

		var vertexI = vertices[i];
		var vertexIPlusOne = vertices[iPlusOne];
		var vertexIPlusTwo = vertices[iPlusTwo];
	
		right.overwriteWith
		(
			vertexIPlusOne
		).subtract
		(
			vertexI
		).right();
	
		displacement.overwriteWith
		(
			vertexIPlusTwo
		).subtract
		(
			vertexI
		);
	
		var dotProduct = displacement.dotProduct(right);
		var isVertexIPlusOneConvex = (dotProduct > 0);
			
		if (isVertexIPlusOneConvex == true)
		{
			var polygonEar = new Polygon
			([
				vertexI,
				vertexIPlusOne,
				vertexIPlusTwo
			]);
			
			var doesEarContainAnyOtherVertices = false;
	
			for (var j = 0; j < i; j++)
			{
				var vertexToCheck = vertices[j];
				if (polygonEar.containsPoint(vertexToCheck) == true)
				{
					doesEarContainAnyOtherVertices = true;
					break;
				}					
			}

			if (doesEarContainAnyOtherVertices == false)
			{
				for (var j = i + 3; j < numberOfVertices; j++)
				{
					var vertexToCheck = vertices[j];
					if (polygonEar.containsPoint(vertexToCheck) == true)
					{
						doesEarContainAnyOtherVertices = true;
						break;
					}
				}
			}
	
			if (doesEarContainAnyOtherVertices == false)
			{
				polygonAsTriangles.push(polygonEar);
				var vertexAtEarTip = polygonEar.vertices[1];
				polygonMinusTriangles.trimVertex(vertexAtEarTip);
				return;
			}
		}	
	}	
}

function Polygon(vertices)
{
	this.vertices = vertices;
}
{
	Polygon.prototype.clone = function()
	{
		var returnValue = new Polygon
		(
			this.vertices.slice(0)
		);

		return returnValue;
	}

	Polygon.prototype.containsPoint = function(pointToCheck)
	{
		var returnValue = true;

		var numberOfVertices = this.vertices.length;

		if (numberOfVertices != 3)
		{
			var errorMessage = "Only works for triangles!";
			throw errorMessage;
		}

		var displacementFromVertexToPoint = new Coords();
		var rightOfEdgeFromVertexToNext = new Coords();

		for (var i = 0; i < numberOfVertices; i++)
		{
			var iNext = i + 1;
			if (iNext >= numberOfVertices)
			{
				iNext = 0;
			}

			var vertex = this.vertices[i];
			var vertexNext = this.vertices[iNext];

			displacementFromVertexToPoint.overwriteWith
			(
				pointToCheck
			).subtract
			(
				vertex
			);

			rightOfEdgeFromVertexToNext.overwriteWith
			(
				vertexNext
			).subtract
			(
				vertex
			).right();

			var dotProduct = rightOfEdgeFromVertexToNext.dotProduct
			(
				displacementFromVertexToPoint
			);

			if (dotProduct < 0)
			{
				returnValue = false;
				break;	
			}			
		}

		return returnValue;
	}

	Polygon.prototype.trimVertex = function(vertexToTrim)
	{
		this.vertices.remove(vertexToTrim);
	}
}

// run

main();

</script>
</body>
</html>

This entry was posted in Uncategorized and tagged , , , , . Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s