# De Casteljau's Algorithm Tool for Khan Academy Contest

So I wrote this code for a contest going on over at Khan Academy known as "Pixar in a Program". The goal of the contest is to create an entry that uses one of the skills shown in the new "Pixar in a Box" course made by them in their partnership with Disney Pixar. In my entry I used De Casteljau's algorithm to make a tool that allowed for easy editing to find the touching point of a parabola. My entry can be found here: https://www.khanacademy.org/computer-programming/de-casteljaus-algorithm-made-easy-wip/5879067530887168

It is written in their live editor over at Khan Academy using the Processing port to JavaScript known as Processing.JS. Here's the code:

var a = [-150, 50], b = [0, -50], c = [150, 50];
var ar = [], br = [], cr = []; // The "r" in these variable names means rounded, this is for grid snapping.
var ad = [], bd = [], cd = [], qd = [], rd = [], pd = []; // The "d" in these variable names means data, this is for data ouput to match the Cartesian coordinate plane snaps.
var t = 0.25;
var q = [(1 - t) * a[0] + t * b[0], (1 - t) * a[1] + t * b[1]];
var r = [(1 - t) * b[0] + t * c[0], (1 - t) * b[1] + t * c[1]];
var p = [(1 - t) * q[0] + t * r[0], (1 - t) * q[1] + t * r[1]];
var mfp = false; // Stands for "Make Full Parabola"
var totalPoints = 3;
var selected = false;

var x = function(i) {
if(i === 0) {
return ar[0];
} else if(i === 1) {
return br[0];
} else if(i === 2) {
return cr[0];
}
}; // Used to get the x value of a certain point
var y = function(i) {
if(i === 0) {
return ar[1];
} else if(i === 1) {
return br[1];
} else if(i === 2) {
return cr[1];
}
}; // Used to get the y value of a certain point
var setX = function(i, value) {
if(i === 0) {
a[0] = value;
} else if(i === 1) {
b[0] = value;
} else if(i === 2) {
c[0] = value;
}
}; // Used to set the x value of a certain point
var setY = function(i, value) {
if(i === 0) {
a[1] = value;
} else if(i === 1) {
b[1] = value;
} else if(i === 2) {
c[1] = value;
}
}; // Used to get the y value of a certain point
var drawControlPoint = function(cp) {
var cpX;
var cpY;
if(cp === 0) {
cpX = ar[0]; cpY = ar[1];
} else if(cp === 1) {
cpX = br[0]; cpY = br[1];
} else if(cp === 2) {
cpX = cr[0]; cpY = cr[1];
}
if(cp === selected) {
if(mouseIsPressed) {
fill(66, 97, 222);
} else {
fill(128, 128, 128);
}
} else {
fill(255, 255, 255);
}
strokeWeight(1);
stroke(163, 163, 163);
ellipse(cpX, -cpY, 10, 10);
noStroke();
}; // Used to draw each control point

translate(200, 200); // Translate the program to make the origin at the center of the screen
mouseDragged = function() {
// See the comments in the mouseMoved function
var MouseX = mouseX - 200;
var MouseY = -(mouseY - 200);
var PMouseX = pmouseX - 200;
// If a point is selected, set its x and y to the MouseX and MouseY
if (selected !== null) {
setX(selected, MouseX);
setY(selected, MouseY);
}
// Variable t controller
if(mouseX > 200 && mouseX < 400 && mouseY > 0 && mouseY < 40) {
t += (MouseX - PMouseX) / 160;
}
};
mouseMoved = function() {
// I have to adjust the mouse coords due to the translation of data
var MouseX = mouseX - 200;
var MouseY = -(mouseY - 200); // Make MouseY follow the Cartesian coordinate system
selected = null;
// Find the distance of the mouse to the control point
for(var i = 0; i < totalPoints; i++) {
if(dist(MouseX, MouseY, x(i), y(i)) < 5) {
selected = i;
}
}
if(mouseY > 380) {
if(mouseX > 50 && mouseX < 100) {
} else if(mouseX > 150 && mouseX < 200) {
} else if(mouseX > 250 && mouseX < 300) {
} else if(mouseX > 360 && mouseX < 400) {
} else {
}
} else {
}
};
mouseClicked = function() {
// variable = !variable allows me to toggle variables
if(mouseY > 380) {
if(mouseX > 50 && mouseX < 100) {
} else if(mouseX > 150 && mouseX < 200) {
} else if(mouseX > 250 && mouseX < 300) {
} else if(mouseX > 360 && mouseX < 400) {
}
}
if(settingsMenu && mouseX > 370 && mouseX < 390 && mouseY > 355 && mouseY < 375) {
mfp = !mfp; // Toggle Make Full Parabola
}
};
draw = function() {
/** --- CARTESIAN COORDINATE PLANE --- **/
background(120, 228, 255);
stroke(0, 0, 0);
strokeWeight(0.5);
for (var x = -200; x < 200; x += 20) {
line(x, -200, x, 200);
}
for (var y = -200; y < 200; y += 20) {
line(-200, y, 200, y);
}
// Draw a thicker line along the origin lines of the x and y axes
strokeWeight(2);
line(0, -200, 0, 200);
line(-200, 0, 200, 0);

/* --- GRID SNAPPING --- */
// This is where we use those "r" variables.
ar[0] = round(a[0] / 10) * 10;
ar[1] = round(a[1] / 10) * 10;
br[0] = round(b[0] / 10) * 10;
br[1] = round(b[1] / 10) * 10;
cr[0] = round(c[0] / 10) * 10;
cr[1] = round(c[1] / 10) * 10;

// We then set the "d" variables for later output.
bd[0] = br[0] / 20;
bd[1] = br[1] / 20;
cd[0] = cr[0] / 20;
cd[1] = cr[1] / 20;
qd[0] = q[0] / 20;
qd[1] = q[1] / 20;
rd[0] = r[0] / 20;
rd[1] = r[1] / 20;
pd[0] = p[0] / 20;
pd[1] = p[1] / 20;

/** --- POINTS A-C AND Q,R,P ALGORITHM GENERATION --- **/
strokeWeight(3);
stroke(255, 0, 21);
line(ar[0], -ar[1], br[0], -br[1]);
line(br[0], -br[1], cr[0], -cr[1]);
if(!mfp) {
strokeWeight(3);
q = [(1 - t) * ar[0] + t * br[0], (1 - t) * ar[1] + t * br[1]];
r = [(1 - t) * br[0] + t * cr[0], (1 - t) * br[1] + t * cr[1]];
p = [(1 - t) * q[0] + t * r[0], (1 - t) * q[1] + t * r[1]];
line(q[0], -q[1], r[0], -r[1]);
noStroke();
fill(255, 242, 0); // Show that these are not draggable
ellipse(q[0], -q[1], 10, 10);
ellipse(r[0], -r[1], 10, 10);
ellipse(p[0], -p[1], 10, 10);
} else {
strokeWeight(1);
for(var i = 0; i < 1; i += 0.05) {
q = [(1 - i) * ar[0] + i * br[0], (1 - i) * ar[1] + i * br[1]];
r = [(1 - i) * br[0] + i * cr[0], (1 - i) * br[1] + i * cr[1]];
p = [(1 - i) * q[0] + i * r[0], (1 - i) * q[1] + i * r[1]];
line(q[0], -q[1], r[0], -r[1]);
}
}
for(var i = 0; i < totalPoints; i++) {
drawControlPoint(i);
} // Draw control points

/** --- VARIABLE 'T' SLIDER --- **/
t = constrain(t, 0, 1); // It's possible to exceed 1 or going the opposite way with 0, so we'll constrain it.
noStroke();
fill(255, 255, 255, 200);
rect(0, -200, 200, 40);
stroke(152, 179, 230);
strokeWeight(2);
line(40, -180, 180, -180);
fill(72, 123, 224);
ellipse(40 + t * 140, -180, 15, 15);
fill(0, 0, 0);
textAlign(CENTER, CENTER);
textSize(25);
text("t", 20, -180);
textSize(12);
text(t, 40 + t * 140, -166);

/** --- ALGORITHM COMPUTATION DISPLAY --- **/
textAlign(CORNER, CORNER);
textSize(18);
fill(0, 0, 0);
text("Q: (" + qd[0].toFixed(2) + ", " + qd[1].toFixed(2) + ")", -180, -180);
text("R: (" + rd[0].toFixed(2) + ", " + rd[1].toFixed(2) + ")", -180, -160);
text("P: (" + pd[0].toFixed(2) + ", " + pd[1].toFixed(2) + ")", -180, -140);

/** --- STEP-BY-STEP ALGORITHM EVALUATIONS WITH MENU --- **/
// The reason I have so many .toFixed(2), it's because in weird situations it will go up to 16 decimal places
// There can be rounding errors because of .toFixed not rounding, that's why I compute the final step with the qd/rd/pd rather than manually
fill(0, 0, 0, 200);
noStroke();
rect(-200, -25, 200, 205);
fill(255, 255, 255);
textSize(11);
textAlign(CENTER, CENTER);
text("Qx = (1-t) * Ax + t * Bx", -100, -10);
text("Qx = (1-" + t.toFixed(2) + ") * " + ad[0].toFixed(2) + " + " + t.toFixed(2) + " * " + bd[0].toFixed(2), -100, 10);
text("Qx = (" + (1 - t.toFixed(2)).toFixed(2) + ") * " + ad[0].toFixed(2) + " + " + t.toFixed(2) + " * " + bd[0].toFixed(2), -100, 30);
text("Qx = " + ((1 - t.toFixed(2)) * ad[0]).toFixed(2) + " + " + (t.toFixed(2) * bd[0]).toFixed(2), -100, 50);
text("Qx = " + qd[0].toFixed(2), -100, 70);
text("Qy = (1-t) * Ay + t * By", -100, 90);
text("Qy = (1-" + t.toFixed(2) + ") * " + ad[1].toFixed(2) + " + " + t.toFixed(2) + " * " + bd[1].toFixed(2), -100, 110);
text("Qy = (" + (1 - t.toFixed(2)).toFixed(2) + ") * " + ad[1].toFixed(2) + " + " + t.toFixed(2) + " * " + bd[1].toFixed(2), -100, 130);
text("Qy = " + ((1 - t.toFixed(2)) * ad[1]).toFixed(2) + " + " + (t.toFixed(2) * bd[1]).toFixed(2), -100, 150);
text("Qy = " + qd[1].toFixed(2), -100, 170);
}
fill(0, 0, 0, 200);
noStroke();
rect(-100, -25, 200, 205);
fill(255, 255, 255);
textSize(11);
textAlign(CENTER, CENTER);
text("Rx = (1-t) * Bx + t * Cx", 0, -10);
text("Rx = (1-" + t.toFixed(2) + ") * " + bd[0].toFixed(2) + " + " + t.toFixed(2) + " * " + cd[0].toFixed(2), 0, 10);
text("Rx = (" + (1 - t.toFixed(2)).toFixed(2) + ") * " + bd[0].toFixed(2) + " + " + t.toFixed(2) + " * " + cd[0].toFixed(2), 0, 30);
text("Rx = " + ((1 - t.toFixed(2)) * bd[0]).toFixed(2) + " + " + (t.toFixed(2) * cd[0]).toFixed(2), 0, 50);
text("Rx = " + rd[0].toFixed(2), 0, 70);
text("Ry = (1-t) * By + t * Cy", 0, 90);
text("Ry = (1-" + t.toFixed(2) + ") * " + bd[1].toFixed(2) + " + " + t.toFixed(2) + " * " + cd[1].toFixed(2), 0, 110);
text("Ry = (" + (1 - t.toFixed(2)).toFixed(2) + ") * " + bd[1].toFixed(2) + " + " + t.toFixed(2) + " * " + cd[1].toFixed(2), 0, 130);
text("Ry = " + ((1 - t.toFixed(2)) * bd[1]).toFixed(2) + " + " + (t.toFixed(2) * cd[1]).toFixed(2), 0, 150);
text("Ry = " + rd[1].toFixed(2), 0, 170);
}
fill(0, 0, 0, 200);
noStroke();
rect(0, -25, 200, 205);
fill(255, 255, 255);
textSize(11);
textAlign(CENTER, CENTER);
text("Px = (1-t) * Qx + t * Rx", 100, -10);
text("Px = (1-" + t.toFixed(2) + ") * " + qd[0].toFixed(2) + " + " + t.toFixed(2) + " * " + rd[0].toFixed(2), 100, 10);
text("Px = (" + (1 - t.toFixed(2)).toFixed(2) + ") * " + qd[0].toFixed(2) + " + " + t.toFixed(2) + " * " + rd[0].toFixed(2), 100, 30);
text("Px = " + ((1 - t.toFixed(2)) * qd[0]).toFixed(2) + " + " + (t.toFixed(2) * rd[0]).toFixed(2), 100, 50);
text("Px = " + pd[0].toFixed(2), 100, 70);
text("Py = (1-t) * Qy + t * Ry", 100, 90);
text("Py = (1-" + t.toFixed(2) + ") * " + qd[1].toFixed(2) + " + " + t.toFixed(2) + " * " + rd[1].toFixed(2), 100, 110);
text("Py = (" + (1 - t.toFixed(2)).toFixed(2) + ") * " + qd[1].toFixed(2) + " + " + t.toFixed(2) + " * " + rd[1].toFixed(2), 100, 130);
text("Py = " + ((1 - t.toFixed(2)) * qd[1]).toFixed(2) + " + " + (t.toFixed(2) * rd[1]).toFixed(2), 100, 150);
text("Py = " + pd[1].toFixed(2), 100, 170);
}
fill(0, 0, 0, 200);
noStroke();
rect(50, 125, 150, 55);
fill(186, 186, 186);
textSize(12);
textAlign(CENTER, CENTER);
text("If this is pressed it will\nnullify other data.", 125, 141);
fill(255, 255, 255);
text("Make Full Parabola", 110, 166);
stroke(255, 255, 255);
noFill();
rect(170, 156, 20, 20);
if(mfp) {
stroke(0, 255, 9);
strokeWeight(3);
line(172, 171, 177, 176);
line(177, 176, 187, 156);
}
noStroke();
}
textAlign(CORNER, CORNER);

/* --- BOTTOM BAR --- */
fill(0, 0, 0, 200);
noStroke();
rect(-200, 180, width, 20);
textSize(15);
fill(255, 255, 255, 100);
rect(-175, 180, 100, 20);
fill(255, 255, 255, 100);
rect(-75, 180, 100, 20);
fill(255, 255, 255, 100);
rect(25, 180, 100, 20);
fill(255, 255, 255, 100);
rect(160, 180, 40, 20);
}
fill(255, 255, 255);
text("Point Q", -150, 195);
text("Point R", -50, 195);
text("Point P", 50, 195);
stroke(255, 255, 255);
line(170, 195, 180, 185);
line(180, 185, 190, 195);
};


Note: I didn't use mouseDragged in totality because it gets flaky if you move your mouse too fast. So instead I set a boolean based off dist(); in mouseDragged, and controlled it elsewhere.

This will be a slightly abstract review. I'm not a big fan of Processing.js - or rather, I don't know it well enough to know if I'm going against the grain. And Khan Academy's editor is annoying me (it reminds me too much of Microsoft's Clippy; always butting in).

So I'll be talking mostly about how you could do things in raw JavaScript. Some of it already exists in Processing.js, or is done differently in Processing.js.

Anyway, my first point would be that user interface and core logic are too intermingled here. But that's Processing for you - it gets messy.

My next point would be to attack this more high-level. The core data type you're dealing with is coordinates - x and y. Also known as a point, or a vector.

You're storing them as two numbers in an array, which is valid, but with a little more preparation, you can use objects instead, which in turn can make you code more expressive. Right now a lot of your code relies on hard-coded array indices, when what you really mean is x or y, or point a or b.

So let's make some points, using a Point constructor (Processing has a PVector constructor you can use instead):

function Point(x, y) {
this.x = x;
this.y = y;
}

var a = new Point(-150, 20);
var b = new Point(0, -50);
var c = new Point(150, 50);


That's our control points. Next are the interpolated points Q, R, and P.

Here's where object orientation comes in handy. The coordinates of the interpolated points are derived entirely from the coordinates of the control points. So we'll want our InterpolatedPoint constructor to take two Points as arguments:

function InterpolatedPoint(a, b) {
this.a = a;
this.b = b;
}


Now, instead of just assigning some numbers to the interpolated point's x and y, let's make getter methods that'll calculate coordinates on the fly:

InterpolatedPoint.prototype = {
getX: function (t) {
return lerp(this.a.x, this.b.x, t);
},

getY: function (t) {
return lerp(this.a.y, this.b.y, t);
}
};


I'm using lerp here, which is a basic linear interpolation function that's also in Processing.js. It's just (b - a) * t + a.

So putting that to use:

var q = new InterpolatedPoint(a, b);
var r = new InterpolatedPoint(b, c);
var p = new InterpolatedPoint(q, r);


So now, you can change the coordinates of points a, b, and c, yet as soon as you call p.getX(0.5) or q.getY(0.8) you'll get the right value back. The InterpolatedPoint object keep references to the Point objects that define them. So you're pretty close to a algebraic definition, and the logic has been encapsulated in objects.

$$\vec{q} = (\vec{b}-\vec{a})t + \vec{a}$$ $$\vec{r} = (\vec{c}-\vec{b})t + \vec{b}$$ $$\vec{p} = (\vec{r}-\vec{q})t + \vec{q}$$

From here it's a question of drawing the points and lines. I'd suggest moving some of this logic to methods on Point/InterpolatedPoint - i.e. make them draw themselves.

Because it was a fun little challenge, I've written an alternative implementation (which also differs from the above a little by defining "real" getters) in plain JS. Note: Since I'm using a built-in slider input, it won't work in IE9 and below.

• I see, thank you for the great answer. I was going to switch to objects, but was borderline at the time. The algorithm I used of Q = (1 - t)a + tb is what was used in Pixar in a Box, but using your vector version is fine with me. I'll try my implementation of it, and message back here with my work. Thank you! :) – KingCodeFish Oct 23 '15 at 21:07