Finding Intersections Between Polygons in JavaScript

The JavaScript code below generates and displays two random triangles, then locates and highlights any and all intersections between them. To see the program in action, copy it into an .html file and open that file in a web browser that runs JavaScript.

IntersectingTriangles

<html>
<body>
<script type='text/javascript'>

// main

function main()
{
	var viewSize = new Coords(300, 200);

	var numberOfTriangles = 2;

	var triangles = [];

	for (var t = 0; t < numberOfTriangles; t++)
	{
		var vertexPositions = [];

		for (var v = 0; v < Triangle.NumberOfVertices; v++)
		{
			var vertexPos = Coords.random().multiply
			(
				viewSize
			);
			vertexPositions.push(vertexPos);
		}

		var triangle = new Triangle(vertexPositions);

		triangles.push(triangle);
	}

	Globals.Instance.initialize
	(
		new DisplayHelper(viewSize),
		triangles
	);
}

// classes

function Bounds(min, max)
{
	this.min = min;
	this.max = max;
}
{
	Bounds.calculateFromPositions = function(positions)
	{	
		var minSoFar = new Coords
		(
			Number.POSITIVE_INFINITY, Number.POSITIVE_INFINITY
		);
		var maxSoFar = new Coords
		(
			Number.NEGATIVE_INFINITY, Number.NEGATIVE_INFINITY
		);
	
		for (var i = 0; i < positions.length; i++)
		{
			var position = positions[i];
			
			if (position.x < minSoFar.x)
			{
				minSoFar.x = position.x;
			}
			if (position.y < minSoFar.y)
			{
				minSoFar.y = position.y;
			}
			if (position.x > maxSoFar.x)
			{
				maxSoFar.x = position.x;
			}
			if (position.y > maxSoFar.y)
			{
				maxSoFar.y = position.y;
			}
		}
	
		var returnValue = new Bounds(minSoFar, maxSoFar);

		return returnValue;
	}

}

function Collision()
{}
{	
	Collision.findCollisionOfEdges = function(edge0, edge1)
	{
		var returnValue = null;

		var edge1ProjectedOntoEdge0 = edge1.clone().projectOnto
		(
			edge0
		);

		var t = 
			(0 - edge1ProjectedOntoEdge0.vertexPositions[0].y) 
			/ edge1ProjectedOntoEdge0.direction.y;

		if (t >= 0 && t <= edge1ProjectedOntoEdge0.length)
		{
			var x = edge1ProjectedOntoEdge0.vertexPositions[0].x
				+ edge1ProjectedOntoEdge0.direction.x 
				* t;

			if (x >= 0 && x <= edge0.length)
			{
				returnValue = edge0.vertexPositions[0].clone().add
				(
					edge0.direction.clone().multiplyScalar(x)
				);
			}
		}

		return returnValue;
	}

	Collision.findCollisionsOfTriangles = function(triangle0, triangle1)
	{
		var returnCollisions = [];

		for (var e = 0; e < triangle0.edges.length; e++)
		{
			var edgeThis = triangle0.edges[e];

			for (var f = 0; f < triangle1.edges.length; f++)
			{
				var edgeOther = triangle1.edges[f];

				var collision = Collision.findCollisionOfEdges
				(
					edgeThis, 
					edgeOther
				);
			
				if (collision != null)
				{
					returnCollisions.push(collision);
				}
			}
		}

		return returnCollisions;
	}

	Collision.findCollisionsOfTrianglesInSet = function(triangleSet)
	{
		var returnCollisions = [];

		for (var s = 0; s < triangleSet.length; s++)
		{
			var triangleThis = triangleSet[s];

			for (var t = s + 1; t < triangleSet.length; t++)
			{
				var triangleOther = triangleSet[t];

				var collisions = Collision.findCollisionsOfTriangles
				(
					triangleThis, 
					triangleOther
				);
			
				for (var c = 0; c < collisions.length; c++)
				{
					var collision = collisions[c];
					returnCollisions.push(collision);
				}
			}
		}

		return returnCollisions;		
	}
}

function Coords(x, y)
{
	this.x = x;
	this.y = y;
}
{
	// static methods

	Coords.random = function()
	{
		return new Coords(Math.random(), Math.random());
	}

	// instance methods

	Coords.prototype.add = function(other)
	{
		this.x += other.x;
		this.y += other.y;

		return this;
	}

	Coords.prototype.clone = function()
	{
		return new Coords(this.x, this.y);
	}

	Coords.prototype.divideScalar = function(scalar)
	{
		this.x /= scalar;
		this.y /= scalar;

		return this;
	}

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

	Coords.prototype.magnitude = function()
	{
		return Math.sqrt(this.x * this.x + this.y * this.y);
	}

	Coords.prototype.multiply = function(other)
	{
		this.x *= other.x;
		this.y *= other.y;

		return this;
	}

	Coords.prototype.multiplyScalar = function(scalar)
	{
		this.x *= scalar;
		this.y *= scalar;

		return this;
	}


	Coords.prototype.overwriteWithXY = function(x, y)
	{
		this.x = x;
		this.y = y;

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

		return this;
	}

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

		return this;
	}
}

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

		this.graphics = this.canvas.getContext("2d");

		document.body.appendChild(this.canvas);
	}	

	DisplayHelper.prototype.clear = function()
	{
		this.graphics.fillStyle = "White";
		this.graphics.fillRect
		(
			0, 0,
			this.viewSize.x, this.viewSize.y
		);
	}

	DisplayHelper.prototype.drawLine = function(startPos, endPos)
	{
		this.graphics.strokeStyle = "Green";
		this.graphics.beginPath();
		this.graphics.moveTo(startPos.x, startPos.y);
		this.graphics.lineTo(endPos.x, endPos.y);
		this.graphics.stroke();
	}

	DisplayHelper.prototype.drawRectangle = function(pos, size)
	{
		var displayHelper = Globals.Instance.displayHelper;

		this.graphics.strokeStyle = "Blue";		
		this.graphics.strokeRect
		(
			pos.x, pos.y,
			size.x, size.y
		);
	}

	DisplayHelper.prototype.drawTriangle = function(triangle)
	{
		var displayHelper = Globals.Instance.displayHelper;

		for (var e = 0; e < triangle.edges.length; e++)
		{
			var edge = triangle.edges[e];
			displayHelper.drawLine
			(
				edge.vertexPositions[0],
				edge.vertexPositions[1]
			)
		}
	}

}

function Edge(vertexPositions)
{
	this.vertexPositions = vertexPositions;

	this.recalculate();
}
{
	Edge.buildManyFromVertexPositions = function(vertexPositions)
	{
		var returnValues = [];

		var numberOfVertexPositions = vertexPositions.length;
		for (var i = 0; i < numberOfVertexPositions; i++)
		{
			var vertexPosition = vertexPositions[i];

			var iNext = i + 1;
			if (iNext >= numberOfVertexPositions)
			{
				iNext = 0;
			}

			var vertexPositionNext = vertexPositions[iNext];

			var edge = new Edge([vertexPosition, vertexPositionNext]);

			returnValues.push(edge);
		}

		return returnValues;
	}

	// instance methods

	Edge.prototype.clone = function()
	{
		return new Edge
		([
			this.vertexPositions[0].clone(),
			this.vertexPositions[1].clone()
		]);
	}

	Edge.prototype.projectOnto = function(other)
	{
		for (var i = 0; i < this.vertexPositions.length; i++)
		{
			var vertexPos = this.vertexPositions[i];

			vertexPos.subtract(other.vertexPositions[0]);

			vertexPos.overwriteWithXY
			(
				vertexPos.dotProduct(other.direction),
				vertexPos.dotProduct(other.transverse)
			);
		}

		this.recalculate();

		return this;		
	}

	Edge.prototype.recalculate = function()
	{
		this.displacement = this.vertexPositions[1].clone().subtract
			(
			this.vertexPositions[0]
			);
			this.length = this.displacement.magnitude();
		this.direction = this.displacement.clone().divideScalar
		(
			this.length
		);
		this.transverse = this.direction.clone().transverse();
		this.bounds = Bounds.calculateFromPositions(this.vertexPositions);
	}
}

function Globals()
{}
{
	Globals.Instance = new Globals();

	Globals.Instance.initialize = function(displayHelper, trianglesToDraw)
	{
		this.displayHelper = displayHelper;
		this.displayHelper.initialize();

		this.displayHelper.clear();
		
		for (var i = 0; i < trianglesToDraw.length; i++)
		{
			var triangleToDraw = trianglesToDraw[i];

			displayHelper.drawTriangle(triangleToDraw);
		}

		var collisions = Collision.findCollisionsOfTrianglesInSet
		(
			trianglesToDraw
		);

		var collisionMarkerDimension = 8;
		var collisionMarkerSize = new Coords(1, 1).multiplyScalar
		(
			collisionMarkerDimension
		);
		var collisionMarkerSizeHalf = collisionMarkerSize.clone().divideScalar(2)

		for (var i = 0; i < collisions.length; i++)
		{
			var collision = collisions[i];
			this.displayHelper.drawRectangle
			(
				collision.clone().subtract(collisionMarkerSizeHalf),
				collisionMarkerSize
			);
		}
	}
}

function Triangle(vertexPositions)
{
	this.vertexPositions = vertexPositions;	
	this.edges = Edge.buildManyFromVertexPositions(this.vertexPositions);

	this.bounds = Bounds.calculateFromPositions(this.vertexPositions);
}
{
	Triangle.NumberOfVertices = 3;
}

// 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