Plotting, Drawing, and Intersecting Bezier Curves in JavaScript

The JavaScript code below, when run, plots and draws two Bezier curves (one is a straight line), and calculates and draws their bounding boxes. It also makes an attempt to find and highlight the intersections between them, though the keen observer will note that it currently doesn’t do that very well at all. To see the code in action, copy it into an .html file and open that file in a web browser that runs JavaScript.

The program was written with extensive reference to a document hosted at the URL “https://pomax.github.io/bezierinfo/”, which is the clearest and most lucid exploration of the inner workings of Bezier curves that I’ve seen on the internet to date. Even so, some of the math is still beyond my meager understanding. Accordingly, the code in my program that calculates the bounds and intersections of the curves does not achieve completely accurate results.

Especially interesting is the document’s presentation of an intuitive geometric method for drawing a Bezier curve, using a process that it calls “de Casteljau’s algorithm”. Using this algorithm, a Bezier curve with an arbitrary number of control points can be drawn by hand using a simple straightedge. It is this algorithm that is used to calculate the points along the curves in this program. It can be described as follows:

  • First, the curve’s start, end, and control points are drawn.
  • Straight lines are drawn between each adjacent pair of control points to connect them.
  • Some value t is selected, in the range 0 to 1, where t = 0 represents the position at the start of the curve and t = 1 represents the position at the end of it.
  • For a particular value of t, and for each line between a pair of control points, a point is drawn on that line at distance t times the length of the line from the first control point of the pair. The number of points drawn will be one fewer than the initial number of control points.
  • Lines are drawn between the points plotted in the previous step.
  • The previous two steps are repeated, using the same value of t, but using the newly drawn lines rather than the initial set of lines.
  • The previous steps are repeated until there is only one line left. The point at (t * length) along the last line is the point along the Bezier curve that corresponds to the value t.
  • All the lines are erased except for the ones between the original control points, a new value of t is selected, and the process is repeated to locate the next point on the curve.
  • After enough points on the curve have been located, they can be connected to form a smooth curve.

BezierCurvesIntersecting

<html>
<body>

<div id="divMain" />

<script type="text/javascript">

// main

function BezierPlottingTest()
{
	this.main = function()
	{
		var canvasSize = new Coords(256, 256);
		var canvas = document.createElement("canvas");
		canvas.width = canvasSize.x;
		canvas.height = canvasSize.y;		

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

		graphics = canvas.getContext("2d");
		graphics.fillStyle = "Gray";
		graphics.strokeStyle = "Gray";

		var curves = 
		[
			// straight line

			 new BezierCurve
			([
				new Coords(20, 0),
				new Coords(120, 100),
				new Coords(220, 200),
			]),
		
			// four control points

			new BezierCurve
			([
				new Coords(65, 25),
				new Coords(5, 150),
				new Coords(80, 290),
				new Coords(220, 235),
				new Coords(250, 150),
				new Coords(135, 125),
			]),

		];

		var distanceThreshold = 1;

		for (var i = 0; i < curves.length; i++)
		{
			var curve = curves[i];
			curve.draw
			(
				graphics, 
				1 // distanceThreshold
			);
		}

		var intersections = curves[0].intersectionsWith
		(
			curves[1], 
			1  // distanceThreshold
		);

		for (var i = 0; i < intersections.length; i++)
		{
			var intersection = intersections[i];
			graphics.beginPath();
			graphics.arc
			(
				intersection.x, intersection.y, 
				4, // radius
				0, Math.PI * 2
			);
			graphics.stroke();
		}

		var one = 1;
	}
}

// classes

function BezierCurve(points)
{
	// The first point is the start,
	// the last point is the end,
	// and the middle points are "control" points.

	this.points = points;
}
{
	BezierCurve.prototype.bounds = function(distanceThreshold)
	{
		var thisAsSegment = new BezierCurveSegment(this, [0, 1]);

		var returnValue = thisAsSegment.bounds(distanceThreshold);

		return returnValue;
	}

	BezierCurve.prototype.draw = function(graphics, distanceThreshold)
	{
		var pointsOnCurve = this.pointsAtResolutionThreshold(distanceThreshold);

		graphics.beginPath();

		var point = pointsOnCurve[0];
		graphics.moveTo(point.x, point.y);

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

		graphics.stroke();

		this.bounds(distanceThreshold).draw(graphics);
	}

	BezierCurve.prototype.pointsAtResolutionThreshold = function(distanceThreshold)
	{
		var thisAsSegment = new BezierCurveSegment(this, [0, 1]);

		var pointsOnCurve = thisAsSegment.pointsAtThresholdAddToList
		(
			distanceThreshold,
			[], // pointsSoFar
			true // includeEndPoint
		);

		return pointsOnCurve;
	}


	BezierCurve.prototype.intersectionsWith = function(other, distanceThreshold)
	{
		var intersections = this.intersectionsWith_1
		(
			distanceThreshold,
			new BezierCurveSegment(this, [0, 1]),
			new BezierCurveSegment(other, [0, 1]),
			[] // instersectionsSoFar
		);

		var displacement = new Coords();

		for (var i = 0; i < intersections.length; i++)
		{
			var intersectionThis = intersections[i];

			for (var j = i + 1; j < intersections.length; j++)
			{
				var intersectionOther = intersections[j];

				displacement.overwriteWith
				(
					intersectionOther
				).subtract
				(
					intersectionThis
				);

				var distance = displacement.magnitude();
				if (distance < distanceThreshold)
				{
					intersectionThis.add(intersectionOther).divideScalar(2);
					intersections.splice(j, 1);
					j--;
				}
			}
		}

		return intersections;
	}

	BezierCurve.prototype.intersectionsWith_1 = function
	(
		distanceThreshold,
		curveSegment0, 
		curveSegment1,
		intersectionsSoFar
	)
	{
		var curveSegment0Bounds = curveSegment0.bounds(distanceThreshold);
		var curveSegment1Bounds = curveSegment1.bounds(distanceThreshold);

		var doBoundsOverlap = curveSegment0Bounds.overlapWith
		(
			curveSegment1Bounds
		);

		if (doBoundsOverlap == true)
		{			
			var curveSegment0Magnitude = curveSegment0Bounds.size.dimensionMin();
			var curveSegment1Magnitude = curveSegment1Bounds.size.dimensionMin();

			if 
			(
				curveSegment0Magnitude < distanceThreshold
				|| curveSegment1Magnitude < distanceThreshold
			)
			{
				var intersection = new Coords().overwriteWith
				(
					curveSegment0Bounds.center()
				).add
				(
					curveSegment1Bounds.center()
				).divideScalar
				(
					2
				);

				intersectionsSoFar.push(intersection);
			}
			else
			{
				var curveSegment0Subdivisions = curveSegment0.subdivide();
				var curveSegment1Subdivisions = curveSegment1.subdivide();

				for (var i = 0; i < curveSegment0Subdivisions.length; i++)
				{
					var curveSegment0Subdivision = curveSegment0Subdivisions[i];

					for (var j = 0; j < curveSegment1Subdivisions.length; j++)
					{
						var curveSegment1Subdivision = curveSegment1Subdivisions[j];

						this.intersectionsWith_1
						(
							distanceThreshold,
							curveSegment0Subdivision,
							curveSegment1Subdivision,
							intersectionsSoFar	
						);
					}
				}
			}
		}

		return intersectionsSoFar;
	}
}

function BezierCurveSegment(curve, tMinAndMax)
{
	this.curve = curve;
	this.tMinAndMax = tMinAndMax;
}
{
	BezierCurveSegment.prototype.bounds = function(distanceThreshold)
	{
		var points = this.pointsAtThresholdAddToList(distanceThreshold, [], true);
		var returnValue = Bounds.fromPositionsMany(points);

		return returnValue;
	}

	BezierCurveSegment.prototype.pointsAtThresholdAddToList = function
	(
		distanceThreshold, 
		pointsSoFar,
		includeEndPoint
	)
	{
		// Based on a description of "de Casteljau's algorithm"
		// found at the URL "https://pomax.github.io/bezierinfo/".

		var displacement = new Coords();

		var pointsAtTMinAndMax = [];

		for (var tmm = 0; tmm < this.tMinAndMax.length; tmm++)
		{
			var t = this.tMinAndMax[tmm];	

			var points = this.curve.points;

			while (points.length > 1)
			{
				var pointsNext = [];

				for (var i = 0; i < points.length - 1; i++)
				{
					var point = points[i];
					var pointNext = points[i + 1];
	
					displacement.overwriteWith
					(
						pointNext
					).subtract
					(
						point
					).multiplyScalar
					(
						t
					).add
					(
						point
					);
	
					pointsNext.push
					(
						displacement.clone()
					);
				}

				points = pointsNext;

			} // end while (points.length > 1)

			var pointOnCurve = points[0];

			pointsAtTMinAndMax.push(pointOnCurve);
		} // end for t

		displacement.overwriteWith
		(
			pointsAtTMinAndMax[1]
		).subtract
		(
			pointsAtTMinAndMax[0]
		);

		// hack
		// This could fail if the start and end point
		// are closer than the threshold distance.

		var distanceBetweenPoints = displacement.magnitude();

		if (distanceBetweenPoints > distanceThreshold)
		{
			var subdivisions = this.subdivide();

			subdivisions[0].pointsAtThresholdAddToList
			( 
				distanceThreshold,
				pointsSoFar,
				false // includeEndPoint
			);
			subdivisions[1].pointsAtThresholdAddToList
			(
				distanceThreshold,
				pointsSoFar,
				false // includeEndPoint
			);
		}
		else
		{
			pointsSoFar.push(pointsAtTMinAndMax[0]);
		}

		if (includeEndPoint == true)
		{
			pointsSoFar.push(pointsAtTMinAndMax[1]);
		}

		return pointsSoFar;
	}

	BezierCurveSegment.prototype.subdivide = function()
	{
		var tMin = this.tMinAndMax[0];
		var tMax = this.tMinAndMax[1];
		var tMidpoint = (tMin + tMax) / 2;

		var returnValues = 
		[
			new BezierCurveSegment(this.curve, [tMin, tMidpoint]),
			new BezierCurveSegment(this.curve, [tMidpoint, tMax])
		];

		return returnValues;
	}
}

function Bounds(min, max)
{
	this.min = min;
	this.max = max;
	this.size = new Coords();
	this.recalculateDerivedValues();
}
{
	// static methods

	Bounds.fromPositionsMany = function(positions)
	{
		var positionMin = positions[0].clone();
		var positionMax = positions[0].clone();

		for (var i = 1; i < positions.length; i++)
		{
			var position = positions[i];

			if (position.x < positionMin.x)
			{
				positionMin.x = position.x;
			}
			else if (position.x > positionMax.x)
			{
				positionMax.x = position.x;
			}

			if (position.y < positionMin.y)
			{
				positionMin.y = position.y;
			}
			else if (position.y > positionMax.y)
			{
				positionMax.y = position.y;
			}
		}

		var returnValue = new Bounds(positionMin, positionMax);

		return returnValue;
	}

	// instance methods

	Bounds.prototype.add = function(offset)
	{
		this.min.add(offset);
		this.max.add(offset);
		this.recalculateDerivedValues();
		return this;
	}

	Bounds.prototype.center = function()
	{
		return this.min.clone().add(this.max).divideScalar(2);
	}

	Bounds.prototype.clone = function()
	{
		return new Bounds(this.min.clone(), this.max.clone());
	}

	Bounds.prototype.draw = function(graphics)
	{
		graphics.strokeRect
		(
			this.min.x, this.min.y,
			this.size.x, this.size.y
		);
	}

	Bounds.prototype.overlapWith = function(other)
	{
		var returnValue = false;

		var bounds = [ this, other ];

		for (var b = 0; b < bounds.length; b++)
		{
			var boundsThis = bounds[b];
			var boundsOther = bounds[1 - b];			

			var doAllDimensionsOverlapSoFar = true;

			for (var d = 0; d < Coords.NumberOfDimensions; d++)
			{
				if 
				(
					boundsThis.max.dimension(d) < boundsOther.min.dimension(d)
					|| boundsThis.min.dimension(d) > boundsOther.max.dimension(d)
				)
				{
					doAllDimensionsOverlapSoFar = false;
					break;
				}
			}

			if (doAllDimensionsOverlapSoFar == true)
			{
				returnValue = true;
				break;
			}
		}

		return returnValue;
	}

	Bounds.prototype.overwriteWith = function(other)
	{
		this.min.overwriteWith(other.min);
		this.max.overwriteWith(other.max);
		this.recalculateDerivedValues();
		return this;
	}

	Bounds.prototype.recalculateDerivedValues = function()
	{
		this.size.overwriteWith(this.max).subtract(this.min);
	}
}

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

	Coords.NumberOfDimensions = 2;

	// 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.dimension = function(dimensionIndex)
	{
		var returnValue;

		if (dimensionIndex == 0)
		{
			returnValue = this.x;
		}
		else if (dimensionIndex == 1)
		{
			returnValue = this.y;
		}
		else
		{
			throw "Invalid dimension index.";
		}

		return returnValue;
	}

	Coords.prototype.dimensionMin = function()
	{
		return (this.x <= this.y ? this.x : this.y);
	}

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

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

	Coords.prototype.isInRange = function(max)
	{
		var returnValue = 
		(
			this.x >= 0
			&& this.x <= max.x
			&& this.y >= 0
			&& this.y <= max.y
		);

		return returnValue;
	}

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

	Coords.prototype.randomize = function()
	{
		this.x = Math.random();
		this.y = Math.random();
		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;
	}

	Coords.prototype.toString = function()
	{
		return "(" + this.x + "," + this.y + ")";
	}
}

// run

new BezierPlottingTest().main();

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

Notes

  • I have actually touched on the subject of Bezier curves in a previous post, but that program was significantly less developed than this one, and I believe it was specific to cubic curves only. It used the traditional algebraic formula to find the points along the curve at various values of t, rather than the geometric method used here.
This entry was posted in Uncategorized and tagged , , , , . Bookmark the permalink.

One Response to Plotting, Drawing, and Intersecting Bezier Curves in JavaScript

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