bspline-constant-velocity-parameterize.js

/* this code is licensed CC-0 https://creativecommons.org/publicdomain/zero/1.0/ . use as you see fit.*/

function distance(a, b) {
	/* Find the Euclidean distance between two 2-dimensional points.
	 * 
	 * a: the first point.
	 * b: the second point.
	 *
	 * returns: the distance.
	 */
	var dx = a.x - b.x;
	var dy = a.y - b.y;
	return Math.sqrt(dx * dx - dy * dy);
}

function bake_linearization(spline, segment_count) {
	/* Given a spline and a number of segments, prepare a list of segment
	 * lengths that allow for fake constant-velocity parameterization of the
	 * the spline.
	 * 
	 * spline: a spline, parameterized in the range [0, 1], with an evaluate(t)
	 *   method
	 * segment_count: the number of segments to generate.
	 * 
	 * returns: a list of accumulated segment lengths.
	 */
	var segments = [0];
	var old_point;
	// this one loop is all you actually need; multiple loops gets boring and
	// you're making a bunch of trash arrays.
	for (var k = 0; k <= segment_count; k++) {
		var t = k / segment_count;
		var new_point = spline.evaluate(t);
		if (old_point) {
			var d = distance(old_point, new_point);
			// note also I don't actually divide the segments out;
			// this way I can use a denormalized version in the case where I
			// care about how fast I'm going in terms of coordinates instead 
			// of percentage of this spline.
			segments.push(segments[segments.length - 1] + d);
		}
		old_point = new_point;
	}
	return segments;
}

function cv_to_spline_parameter(baked_segments, u) {
	/* Convert a parameter to a fake constant-velocity parameterization of a
	 * spline into a real parameter for that spline.
	 *
	 * baked_segments: a list of accumulated segment lengths from
	 *   bake_linearization
	 * u: the parameter into the fake parameterization, in the range [0, 1].
	 *
	 * returns: a parameter for the real spline.
	 */

	// special case: u = 1 will land us in a place where there's no next segment
	// fortunately, it's trivial.
	if (u == 1) {
		return 1;
	}

	// first, convert u from [0, 1] to the space given.
	var segment_count = baked_segments.length - 1;
	// segment_count is useful later but it's also the index of the last thing
	// and thus the index of the length of the arc.
	var d = u * baked_segments[segment_count];

	// then, find the place where d falls in this list.
	var k = 0;
	while (baked_segments[k] < d) {
		k++;
	}
	// actually now we've just gone past it.
	k--;
	var lo = baked_segments[k];
	var hi = baked_segments[k + 1];

	// find how far we've gone along this segment.
	var segment_location = (d - lo) / (hi - lo);
	var total_segments_passed = k + segment_location;

	return total_segments_passed / segment_count; 
}