Finding Collisions of Circles and Line Segments in Javascript

The JavaScript program below creates a field full of circles and line segments of random size, position, and velocity, and calculates and displays the collisions between them.

To see the code in action, copy it into an .html file and open it in a web browser that runs JavaScript.

collisionsofcirclesandlinesegments


<html>
<body>
<div id="divMain"></div>
<script type="text/javascript">

// main

function main()
{
	var display = new Display
	(
		new Coords(200, 200),
		"LightGray", "White"
	);

	Globals.Instance.initialize
	(
		new TimerHelper(10), 
		display,
		World.random
		(
			display.size, 
			16, // numberOfBodies
			20, // bodyDimensionMin
			80, // bodyDimensionMax
			1 // speedMax 
		)
	);
}

// classes

function Body(collider, vel)
{
	this.collider = collider;
	this.vel = vel;
}
{
	Body.prototype.posAddAndWrap = function(offset, rangeMax)
	{
		this.collider.posAddAndWrap(offset, rangeMax);
	}

	// drawable

	Body.prototype.drawToDisplay = function(display)
	{
		this.collider.drawToDisplay(display);
	}
}

function Collision()
{
	this.isActive = null;
	this.colliders = [];
	this.points = [];
}
{	
	Collision.prototype.ofColliders = function(collider0, collider1)
	{
		var collider0TypeName = collider0.constructor.name;
		var collider1TypeName = collider1.constructor.name;
	
		if (collider0TypeName == "ShapeCircle")
		{
			if (collider1TypeName == "ShapeCircle")
			{
				this.ofCircles(collider0, collider1);
			}
			else // if (collider1TypeName == "ShapeLineSegment")
			{
				this.ofCircleAndLineSegment(collider0, collider1);
			}
		}
		else // if (collider0TypeName == "ShapeLineSegment")
		{
			if (collider1TypeName == "ShapeCircle")
			{
				this.ofCircleAndLineSegment(collider1, collider0);	
			}
			else // if (collider1TypeName == "ShapeLineSegment")
			{
				this.ofLineSegments(collider0, collider1);
			}
		}

		return this;
	}

	// shapes

	Collision.prototype.ofCircleAndLineSegment = function(circle, segment)
	{

		// todo

		var segmentRight = segment.right;
		var closestApproachOfSegmentLineToOrigin = segment.right.dotProduct
		(
			segment.start
		);

		var centerOfCircleProjectedOntoRight = circle.center.dotProduct
		(
			segmentRight
		);

		var distanceToRadicalCenter =
			closestApproachOfSegmentLineToOrigin 
			- centerOfCircleProjectedOntoRight;

		if (Math.abs(distanceToRadicalCenter) >= circle.radius)
		{
			this.isActive = false;
			this.colliders.length = 0;
			this.points.length = 0;
		}
		else
		{
			this.isActive = true;
			this.colliders.push(circle);
			this.colliders.push(segment);

			var radicalCenter = circle.center.clone().add
			(
				segment.right.clone().multiplyScalar
				(
					distanceToRadicalCenter
				)
			);
			
			var distanceFromRadicalCenterToIntersection = 
				Math.sqrt
				(
					circle.radius * circle.radius
					- (distanceToRadicalCenter * distanceToRadicalCenter)
				);

			var offsetFromRadicalCenterToIntersection = 
				segment.direction.clone().multiplyScalar
				(
					distanceFromRadicalCenterToIntersection 
				);


			for (var i = 0; i < 2; i++)
			{
				var intersection = radicalCenter.clone().add
				(
					offsetFromRadicalCenterToIntersection
				);

				var distanceAlongSegment = 
					intersection.clone().subtract
					(
						segment.start
					).dotProduct
					(
						segment.direction
					);

				if 
				(
					distanceAlongSegment > 0 
					&& distanceAlongSegment < segment.length
				)
				{
					this.points.push(intersection); 				
				}

				// hack
				offsetFromRadicalCenterToIntersection.multiplyScalar(-1);
			}
		}
	}

	Collision.prototype.ofCircles = function(circle0, circle1)
	{
		var displacementFromCenter0To1 = 
			circle1.center.clone().subtract
			(
				circle0.center	
			);

		var distanceBetweenCenters = 
			displacementFromCenter0To1.magnitude();

		var circle0Radius = circle0.radius;
		var circle1Radius = circle1.radius;

		var sumOfRadii = circle0Radius + circle1Radius;

		if (distanceBetweenCenters > sumOfRadii)
		{
			this.isActive = false;
			this.colliders.length = 0;
			this.points.length = 0;
		}
		else
		{

			this.isActive = true;
			this.colliders.push(circle0);
			this.colliders.push(circle1);

			// Adapted from formulas derived at the URL
			// http://mathworld.wolfram.com/Circle-CircleIntersection.html
			
			var distanceToRadicalCenter = 
			(
				distanceBetweenCenters * distanceBetweenCenters
				+ circle0Radius * circle0Radius
				- circle1Radius * circle1Radius
			)
			/ (2 * distanceBetweenCenters);

			var directionToRadicalCenter = 
				displacementFromCenter0To1.divideScalar
				(
					distanceBetweenCenters
				);

			var displacementToRadicalCenter = 
				directionToRadicalCenter.clone().multiplyScalar
				(
					distanceToRadicalCenter
				)

			var radicalCenter = circle0.center.clone().add
			(
				displacementToRadicalCenter
			);

			var differenceOfRadii = circle1Radius - circle0Radius;

			var directionFromRadicalCenterToIntersection = 
				directionToRadicalCenter.right();

			var radicalLineLengthHalf = Math.sqrt
			(
				(-distanceBetweenCenters + differenceOfRadii)
				* (-distanceBetweenCenters - differenceOfRadii)
				* (-distanceBetweenCenters + sumOfRadii)
				* (distanceBetweenCenters + sumOfRadii)
			) / (2 * distanceBetweenCenters);

			var displacementFromRadicalCenterToIntersection = 
				directionFromRadicalCenterToIntersection.multiplyScalar
				(
					radicalLineLengthHalf
				);

			var intersection0 = radicalCenter.clone().add
			(
				displacementFromRadicalCenterToIntersection
			);			
		

			var intersection1 = radicalCenter.clone().subtract
			(
				displacementFromRadicalCenterToIntersection
			);

			// this.points.push(radicalCenter);
			this.points.push(intersection0);
			this.points.push(intersection1);			

		}

		return this;
	}

	Collision.prototype.ofLineSegments = function(segment0, segment1)
	{
		this.isActive = false;
		this.colliders.length = 0;
		this.points.length = 0;

		var segment1ProjectedOnto0 = segment1.clone().projectOnto
		(
			segment0
		);
		var segmentProjected = segment1ProjectedOnto0;

		var segmentProjectedLength = segmentProjected.length;

		var point0 = segmentProjected.start;
		var point1 = segmentProjected.end();

		var lineProjectedCrossesXAxis = (point0.y / point1.y < 0);

		if (lineProjectedCrossesXAxis == true)
		{
			var lengthAlongSegment1ToIntersection = Math.abs
			(
				point0.y / segmentProjected.direction.y
			);

			var lengthAlongSegment0ToIntersection =  
				segmentProjected.start.x
			 	+ segmentProjected.direction.x
				* lengthAlongSegment1ToIntersection; 

			if 
			(
				lengthAlongSegment0ToIntersection > 0
				&& lengthAlongSegment0ToIntersection < segment0.length
				&& lengthAlongSegment1ToIntersection > 0
				&& lengthAlongSegment1ToIntersection < segment1.length
			)
			{
				this.isActive = true;
				this.colliders.push(segment0);
				this.colliders.push(segment1);

				var collisionPos = segment1.start.clone().add
				(
					segment1.direction.clone().multiplyScalar
					(
						lengthAlongSegment1ToIntersection
					)
				);	

				this.points.push(collisionPos);			
			}
		}

		return this;
	}


	// drawable

	Collision.prototype.drawToDisplay = function(display)
	{
		for (var i = 0; i < this.points.length; i++)
		{
			var point = this.points[i];

			display.drawCircle(point, 3);
		}
	}
}

function Constants()
{
	// static class
}
{
	// constants

	Constants.RadiansPerCycle = 2.0 * Math.PI;
}

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

	Coords.Instances = new Coords_Instances();

	function Coords_Instances()
	{
		this.Ones = new Coords(1, 1);
		this.Zeroes = new Coords(0, 0);
	}

	// 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.fromAngle = function(angleInCycles)
	{
		var radiansPerCycle = Constants.RadiansPerCycle;
		var angleInRadians = angleInCycles * radiansPerCycle;
		this.x = Math.cos(angleInRadians);
		this.y = Math.sin(angleInRadians);
		return this;
	}

	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.overwriteWith = function(other)
	{
		this.x = other.x;
		this.y = other.y;
		return this;
	}

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

	Coords.prototype.projectOntoXY = function(axisX, axisY)
	{
		return this.overwriteWithXY
		(
			this.dotProduct(axisX),
			this.dotProduct(axisY)
		);
	}

	Coords.prototype.randomize = function()
	{
		this.x = Math.random();
		this.y = Math.random();
		return this;
	}

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

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

	Coords.prototype.wrapToRangeMax = function(max)
	{
		while (this.x < 0)
		{
			this.x += max.x;
		}

		while (this.x >= max.x)
		{
			this.x -= max.x;
		}

		while (this.y < 0)
		{
			this.y += max.y;
		}

		while (this.y >= max.y)
		{
			this.y -= max.y;
		}

		return this;
	}
}

function Display(size, colorFore, colorBack)
{
	this.size = size;
	this.colorFore = colorFore;
	this.colorBack = colorBack;
}
{
	// methods

	Display.prototype.clear = function()
	{
		this.drawRectangle
		(
			Coords.Instances.Zeroes,
			this.size,
			this.colorBack, this.colorFore
		);
	}

	Display.prototype.drawCircle = function(center, radius)
	{
		this.graphics.beginPath();
		this.graphics.arc
		(
			center.x, center.y,
			radius,
			0, Constants.RadiansPerCycle
		);
		this.graphics.strokeStyle = this.colorFore;
		this.graphics.stroke();
	}

	Display.prototype.drawLine = function(fromPos, toPos)
	{
		this.graphics.beginPath();
		this.graphics.moveTo(fromPos.x, fromPos.y);
		this.graphics.lineTo(toPos.x, toPos.y);
		this.graphics.strokeStyle = this.colorFore;
		this.graphics.stroke();	
	}

	Display.prototype.drawRectangle = function
	(
		pos, size, colorFill, colorBorder
	)
	{
		if (colorFill != null)
		{
			this.graphics.fillStyle = colorFill;
			this.graphics.fillRect
			(
				pos.x, pos.y,
				size.x, size.y
			);
		}

		if (colorBorder != null)
		{
			this.graphics.strokeStyle = colorBorder;
			this.graphics.strokeRect
			(
				pos.x, pos.y,
				size.x, size.y
			);
		}
	}

	Display.prototype.initialize = function()
	{
		this.canvas = document.createElement("canvas");
		this.canvas.width = this.size.x;
		this.canvas.height = this.size.y;

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

		var divMain = document.getElementById("divMain");
		divMain.appendChild(this.canvas);
		
	}
}

function Globals()
{
	// do nothing
}
{
	// instance

	Globals.Instance = new Globals();

	// methods

	Globals.prototype.initialize = function(timerHelper, display, world)
	{
		this.timerHelper = timerHelper;
		this.display = display;
		this.world = world;

		this.display.initialize();
		this.timerHelper.initialize(this.handleEventTimerTick.bind(this));
	}

	// events

	Globals.prototype.handleEventTimerTick = function()
	{
		this.world.updateForTimerTick();
		this.world.drawToDisplay(this.display);
	}
}

function ShapeCircle(center, radius)
{
	this.center = center;
	this.radius = radius;
}
{
	ShapeCircle.prototype.posAddAndWrap = function(offset, rangeMax) 
	{ 
		this.center.add(offset).wrapToRangeMax(rangeMax); 
	}

	// drawable

	ShapeCircle.prototype.drawToDisplay = function(display)
	{
		display.drawCircle(this.center, this.radius);
	}
}

function ShapeLineSegment(start, displacement)
{
	this.start = start;
	this.displacement = displacement;

	this.length = null;
	this.direction = new Coords();
	this.right = new Coords();

	this.recalculateDerivedValues();
}
{
	ShapeLineSegment.prototype.clone = function()
	{
		return new ShapeLineSegment
		(
			this.start.clone(), this.displacement.clone()
		);
	}

	ShapeLineSegment.prototype.end = function()
	{
		return this.start.clone().add(this.displacement);
	}

	ShapeLineSegment.prototype.posAddAndWrap = function(offset, rangeMax) 
	{
		this.start.add(offset).wrapToRangeMax(rangeMax);
	}

	ShapeLineSegment.prototype.projectOnto = function(other)
	{
		this.start.subtract
		(
			other.start
		).projectOntoXY
		(
			other.direction, other.right
		);

		this.displacement.projectOntoXY(other.direction, other.right);

		this.recalculateDerivedValues();

		return this;
	}

	ShapeLineSegment.prototype.recalculateDerivedValues = function()
	{
		this.length = this.displacement.magnitude();

		this.direction.overwriteWith
		(
			this.displacement
		).divideScalar
		(
			this.length
		);

		this.right.overwriteWith(this.direction).right();
	}

	// drawable

	ShapeLineSegment.prototype.drawToDisplay = function(display)
	{
		display.drawLine
		(
			this.start, 
			this.end()
		);
	}

}

function TimerHelper(ticksPerSecond)
{
	this.ticksPerSecond = ticksPerSecond;
}
{
	TimerHelper.prototype.initialize = function(tickEventHandler)
	{
		var millisecondsPerTick = 1000 / this.ticksPerSecond;
		this.timer = setInterval
		(
			tickEventHandler,
			millisecondsPerTick
		);
	}
}

function World(size, bodies)
{
	this.size = size;
	this.bodies = bodies;
}
{
	// static methods

	World.random = function
	(
		size, numberOfBodies, bodyDimensionMin, bodyDimensionMax, speedMax
	)
	{
		var bodies = [];

		var bodyDimensionRange = bodyDimensionMax - bodyDimensionMin;
		var ones = Coords.Instances.Ones;

		for (var i = 0; i < numberOfBodies; i++)
		{
			var collider;

			var pos = new Coords().randomize().multiply(size);

			var bodyDimension = 
				bodyDimensionMin 
				+ bodyDimensionRange * Math.random();	

			if (i % 2 == 0)
			{
				collider = new ShapeCircle
				(
					pos, bodyDimension / 2
				);
			}
			else
			{
				var angle = 
					Math.random() 
					* Constants.RadiansPerCycle;
				var direction = new Coords().fromAngle(angle);
				var displacement = direction.multiplyScalar
				(
					bodyDimension
				);

				collider = new ShapeLineSegment
				(
					pos, displacement
				);
			}

			var vel = new Coords().randomize().multiplyScalar
			(
				2
			).subtract
			(
				ones
			).multiplyScalar
			(
				speedMax
			);

			var body = new Body(collider, vel);

			bodies.push(body);
		}

		var returnValue = new World
		(
			size, 
			bodies
		);

		return returnValue;
	}

	World.simpleLines = function(size)
	{
		return new World
		(
			size,
			[
				new Body
				(
					new ShapeLineSegment
					(
						new Coords(size.x / 4, size.y / 2), // start
						new Coords(size.x / 2, 0) // disp
					),
					new Coords(0, 0)
				),

				new Body
				(
					new ShapeLineSegment
					(
						new Coords(size.x / 2, 3 * size.y / 4), // start
						new Coords(-size.x / 4, - size.y / 2) // disp
					),
					new Coords(0, 0)
				),
			]
		);
	}

	// instance methods

	World.prototype.updateForTimerTick = function()
	{
		for (var i = 0; i < this.bodies.length; i++)
		{
			var body = this.bodies[i];
			body.posAddAndWrap
			(
				body.vel,
				this.size
			);
		}
	}

	// drawable

	World.prototype.drawToDisplay = function(display)
	{
		display.clear();
		for (var i = 0; i < this.bodies.length; i++)
		{
			var body = this.bodies[i];

			body.drawToDisplay(display);
		}

		var collision = new Collision();

		for (var i = 0; i < this.bodies.length; i++)
		{
			var body = this.bodies[i];
			var collider = body.collider;

			for (var j = i + 1; j < this.bodies.length; j++)
			{
				var bodyOther = this.bodies[j];
				var colliderOther = bodyOther.collider;

				collision.ofColliders(collider, colliderOther);

				if (collision.isActive == true)
				{
					collision.drawToDisplay(display);
				}				
			}
		}

	}
}

// run

main();

</script>
</body>

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 )

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