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.

2018/02/15 – I have updated this code to clean it up and add area calculation and checking that attempts to obtain the triangles with the least area. It still can’t handle reversing the order of vertices, though.

PolygonTriangulation


<html>
<body>

<div id="divMain" />

<script type="text/javascript">

// main

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

	var display = new Display(displaySize);

	// An "H" shape, in clockwise order.
	var polygonH = new Polygon
	([
		new Coords(.2, .2).multiply(displaySize),
		new Coords(.4, .2).multiply(displaySize),
		new Coords(.4, .4).multiply(displaySize),
		new Coords(.6, .4).multiply(displaySize),
		new Coords(.6, .2).multiply(displaySize),
		new Coords(.8, .2).multiply(displaySize),
		new Coords(.8, .8).multiply(displaySize),
		new Coords(.6, .8).multiply(displaySize),
		new Coords(.6, .6).multiply(displaySize),
		new Coords(.4, .6).multiply(displaySize),
		new Coords(.4, .8).multiply(displaySize),
		new Coords(.2, .8).multiply(displaySize),
	]);

	var polygonsToTest = 
	[
		polygonH
	];
	
	var geometryHelper = new GeometryHelper();

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

		var polygonAsTriangles = geometryHelper.triangulatePolygon
		(
			polygonToTriangulate, display
		);
		
		display.initialize();
		display.clear();
		display.drawPolygon(polygonToTriangulate);

		display.initialize();
		display.clear();
		display.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.crossProduct = function(other)
	{
		return (this.x * other.y - this.y * other.x);
	}

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

	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 Display(viewSizeInPixels)
{
	this.viewSizeInPixels = viewSizeInPixels;
	this.colorBack = "White";
	this.colorFore = "Gray";
}
{
	// methods

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

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

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

	Display.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();
	}

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

	Display.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()
{
	// Helper variables.
	this._right = new Coords();
	this._displacement = new Coords();
}
{
	GeometryHelper.prototype.triangulatePolygon = function(polygonToTriangulate, display)
	{
		var returnValues = [];
	
		var polygonMinusTriangles = polygonToTriangulate.clone();
		var verticesRemaining = polygonMinusTriangles.vertices;
		
		while (verticesRemaining.length > 3)
		{
			var earAreaLeastSoFar = null;		
			var earWithLeastAreaSoFar = null;

			for (var i = 0; i < verticesRemaining.length; i++)
			{
				var ear = this.triangulatePolygon_Vertex(verticesRemaining, i);
				
				if (ear != null)
				{
					var earArea = ear.area();
					if (earWithLeastAreaSoFar == null || earArea < earAreaLeastSoFar)
					{
						earAreaLeastSoFar = earArea;
						earWithLeastAreaSoFar = ear;
					}
				}
			}
			
			returnValues.push(earWithLeastAreaSoFar);
			var vertexAtEarTip = earWithLeastAreaSoFar.vertices[1];
			polygonMinusTriangles.trimVertex(vertexAtEarTip);
		}

		returnValues.push(polygonMinusTriangles.clone());

		return returnValues;
	}

	GeometryHelper.prototype.triangulatePolygon_Vertex = function(verticesRemaining, i)
	{
		var numberOfVertices = verticesRemaining.length;
		var right = this._right;
		var displacement = this._displacement;
		
		var iPlusOne = i + 1;
		if (iPlusOne >= numberOfVertices)
		{
			iPlusOne -= numberOfVertices;
		}
	
		var iPlusTwo = i + 2;
		if (iPlusTwo >= numberOfVertices)
		{
			iPlusTwo -= numberOfVertices;
		}

		var vertexI = verticesRemaining[i];
		var vertexIPlusOne = verticesRemaining[iPlusOne];
		var vertexIPlusTwo = verticesRemaining[iPlusTwo];
	
		right.overwriteWith
		(
			vertexIPlusOne
		).subtract
		(
			vertexI
		).right();
	
		displacement.overwriteWith
		(
			vertexIPlusTwo
		).subtract
		(
			vertexI
		);
	
		var dotProduct = displacement.dotProduct(right);
		var isVertexIPlusOneConvex = (dotProduct > 0);
			
		var returnValue = null;
		
		if (isVertexIPlusOneConvex == true)
		{
			var polygonEar = this.triangulatePolygon_Vertex_Convex
			(
				verticesRemaining, i, vertexI, vertexIPlusOne, vertexIPlusTwo
			);
			
			if (polygonEar != null)
			{
				returnValue = polygonEar;
			}
		}	
		
		return returnValue;
	}
	
	GeometryHelper.prototype.triangulatePolygon_Vertex_Convex = function
	(
		vertices, i, vertexI, vertexIPlusOne, vertexIPlusTwo
	)
	{
		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 < vertices.length; j++)
			{
				var vertexToCheck = vertices[j];
				if (polygonEar.containsPoint(vertexToCheck) == true)
				{
					doesEarContainAnyOtherVertices = true;
					break;
				}
			}
		}
		
		var returnValue = (doesEarContainAnyOtherVertices ? null : polygonEar);
		
		return returnValue;
	}
}

function Polygon(vertices)
{
	this.vertices = vertices;
}
{
	Polygon._Edge0 = new Coords();
	Polygon._Edge1 = new Coords();	

	Polygon.prototype.area = function()
	{
		if (this.vertices.length != 3)
		{
			throw "Not yet implemented!";
		}
		
		var vertex0 = this.vertices[0];
		
		var edge0 = Polygon._Edge0.overwriteWith
		(
			this.vertices[1]
		).subtract(vertex0);
		
		var edge2 = Polygon._Edge1.overwriteWith
		(
			this.vertices[2]
		).subtract(vertex0);

		var area = Math.abs
		(	
			edge2.crossProduct
			(
				edge0
			) / 2
		);
	
		return area;
	}

	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>

Advertisements
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 )

Google+ photo

You are commenting using your Google+ 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 )

w

Connecting to %s